2023新生赛题解

A 数一数三角形

难度：简单

- 在一般情况下，只要三个点不要都在一条边上就一定能构成三角形
所以在一般情况下，将所有特殊点加起来除以 3 向下取整就可以，即: cnt/3

当一条边特殊点的数量远远多于其他边的时候，这个时候只有除了这条边之外的点可以和这个边能构成三角形，构成的三角形个数是 cnt-max(a[i])
注意数据范围，需要开 long long
即结果为: min(cnt/3,cnt-max(a[i])
代码如下:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[200010];
int main()
{
    cin >> n;
    ll cnt = 0, maxa = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], cnt += a[i], maxa = max(maxa, a[i]);
    cout << min(cnt / 3, cnt - maxa) << '\n';
}

B 作文批改

难度：入门

一道考察大家代码功底的模拟题

#include<iostream>

using namespace std;
string word;
bool head = true;
int n, ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    while (n --)    
    {
        cin >> word;
        int i = 0;
        
        if((word.size() == 1 || word[1] < 'A') && word[0] == 'i')
        {
            ans ++;
            continue;
        }

        if(head)
        {
            if(word[i ++] > 'Z')ans ++;
            head = false;
        }


        for(; i < word.length(); i ++)
        {
            if(word[i] < 'A' && word[i] != ',')
            {
                head = true;
                continue;
            }
            if(word[i] < 'a' && word[i] >= 'A')ans ++;
        }
    }
    
    cout << ans;
}

C 找找 ACM

难度：中等

此题主要考察前缀和。当 s[i] 满足 s[i-2]=='a'&&s[i-1]=='c'&&s[i]=='m' 时，我们标记该点为合格点，再利用前缀和求出下标从 0 到 i 共有多少个合格点记为 g[i]。对于每个询问即求出下标 l+2 到 r 共有多少个合格点（即使 l 或 l+1 为合格点，其对应'acm'的左半部分也超出了 [l, r] 的范围），即 g[r]-g[l+1] 的值。

代码如下：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<int> g(n);
    for (int i = 2; i < n; i++)
    {
        if (s[i - 2] == 'a' && s[i - 1] == 'c' && s[i] == 'm')
            g[i] = 1;
        g[i] += g[i - 1];
    }
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << g[r] - g[l + 1] << '\n';
    }
    return 0;
}

D 字符串相约

难度：中等

如果答案是 YES，那么我们总能把两个字符串都变成 $00 \dots 01 \dots 11$ 的形式（前缀是 0，后缀是 1，所有 0 都在所有 1 之前）。之所以这么说，是因为在使两个字符串相等后，我们还可以对 $l = i, r = | a |$ 进行另一种操作，其中 $i$ 是使两个字符串相等后都有 $1$ 的最小索引。例如，在第一个测试用例中，在应用了语句中的所有操作后，字符串等于 $01110001$ 。我们可以通过对 $l = 2, r = 8$ 进行操作，将它们变成字符串 $01111111$ 。

现在让我们试着找出何时可以将字符串转化为 $00 \dots 0011 \dots 11$ 的形式。我们假设，当且仅当 $s_{i} = 0$ 和 $s_{i + 1} = 1$ 时，可以将字符串 $s$ 变换为 i 首元素为 0，其余元素均为 1 的形式：

如果有 $s_{i} = 0$ 和 $s_{i + 1} = 1$ ，我们可以对 $l = 1, r = i$ 和 $l = i + 1, r = | s |$ 进行两次运算，字符串就会变成 i 首元素为 0，其余元素均为 1 的形式；
然而，如果情况并非如此，那么要么是 $s_{i} = s_{i + 1}$ ，要么是 $s_{i} = 1$ 和 $s_{i + 1} = 0$ 。在前一种情况下，我们需要改变这两个元素中的一个；但由于它们相等且相邻，对它们的每个操作都会影响到它们两个，因此不可能只改变其中一个。在后一种情况下，我们需要先将 $s_{i}$ 设置为 $0$ 或将 $s_{i + 1}$ 设置为 $1$ ；当我们这样做时，这两个元素就变得相等了，对它们进行的任何操作都会同时影响到它们。因此，我们不可能将字符串变成i 的第一个元素为 0，其余元素均为 1 的形式。

因此，如果有一个索引 $i$ 能使 $a_{i} = b_{i} = 0$ 和 $a_{i + 1} = b_{i + 1} = 1$ 相等，那么答案就是 YES。否则，答案就是 NO。

#include<bits/stdc++.h>
using namespace std;
int t;
string a,b;
int main()
{
    cin>>t;
    while(t--)
    {
        cin >> a >> b;
        int size = a.size(), flag = 0;
        for (int i = 0; i < size - 1;i++)
	        if(a[i]==b[i]&&a[i]=='0'&&a[i+1]==b[i+1]&&a[i+1]=='1')
	            flag = 1;
        if(flag)
            cout << "YES" << '\n';
        else
	        cout<<"NO"<<'\n';
    }
}

E 简单 DP

难度：中等

对于每次加入或者删除一个小球我们重新去做一遍 dp 显然是不行的. 因为朴素的 dp 就是一个背包, 时间复杂度为 O（nv）。
我们考虑加入一个 x 小球：其实很好看出来就是让 $d p [j + x] + = d p [j]$ 从前往后是正好模拟了 dp 过程, 要是删除一个 x 小球：则是让以前的 dp 数组去

// 真有人打ACM O.o?
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
#define int long long
#define endl '\n'
void solve() {
    int n,k;cin>>n>>k;
    vector<int>dp(k+1);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        char c;cin>>c;
        int x;cin>>x;
        if(c=='-'){
            for(int j=0;j<=k;j++){
                if(j>=x)(dp[j]-=dp[j-x])%=mod;
            }
        }else{
            for(int j=k-x;j>=0;j--){
                (dp[j+x]+=dp[j])%=mod;
            }
        }
        cout<<(dp[k]+mod)%mod<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    solve();
    return 0;
}

F 两点距离

难度：困难

知识点：线段树、二分
这道题目难度较高，大家不必深究，感兴趣的同学可以先尝试了解线段树

// duziteng ^ ^
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
const int M = 998244353;
const int mod = 998244353;
#define db double
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
struct node{
    int l,r,v,cnt;
}tr[N<<2];
int n,m;
void pushup(int i){
    auto &u=tr[i],&l=tr[i<<1],&r=tr[i<<1|1];
    u.v=l.v+r.v;
    u.cnt=l.cnt+r.cnt;
}
void build(int i,int l,int r){
    tr[i].l=l,tr[i].r=r,tr[i].cnt=0,tr[i].v=0;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}
void modify(int i,int x,int k,int k2){
    if(tr[i].l>=x&&tr[i].r<=x){
        auto &u=tr[i];
        u.v+=k;
        u.cnt+=k2;
        return;
    }
    if(tr[i].l>x||tr[i].r<x)return;
    if(tr[i<<1].r>=x)modify(i<<1,x,k,k2);
    if(tr[i<<1|1].l<=x)modify(i<<1|1,x,k,k2);
    pushup(i);
}
int query(int i,int f){
    if(tr[i].l==tr[i].r){
        return tr[i].l;
    }
    if(tr[i<<1].cnt>=f)return query(i<<1,f);
    else{
        return query(i<<1|1,f-tr[i<<1].cnt);
    }
}
PII query(int i,int l,int r){
    PII res={0,0};
    if(tr[i].l>=l&&tr[i].r<=r){
        auto &u=tr[i];
        return {u.v,u.cnt};
    }
    if(tr[i].l>r||tr[i].r<l)return res;
    if(tr[i<<1].r>=l){
        PII now= query(i<<1,l,r);
        res.first+=now.first;
        res.second+=now.second;
    }
    if(tr[i<<1|1].l<=r){
        PII now= query(i<<1|1,l,r);
        res.first+=now.first;
        res.second+=now.second;
    }
    return res;
}
void solve(){
    cin>>n>>m;
    vector<int>a(n+1);
    map<int,int>mp;
    vector<int>mpp(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]-=i*114514;
        mp[a[i]]++;
    }
    int idx=0;
    for(auto [pos,w]:mp){
        ++idx;
        mp[pos]=idx;
        mpp[idx]=pos;
    }
    int l=1,r=n;
    while(l<r){
        int mid=l+r+1>>1;
        build(1,1,idx+1);
        for(int i=1;i<mid;i++)modify(1,mp[a[i]],a[i],1);
        int flag=0;
//        cout<<mid<<endl;
        for(int i=mid;i<=n;i++){
            modify(1,mp[a[i]],a[i],1);
            int z=mpp[query(1,up(mid,2))];
//            cout<<i<<' '<<z<<endl;
            auto [lv,lcnt]=query(1,1,mp[z]);
            auto [rv,rcnt]=query(1,mp[z]+1,idx);
//            cout<<lcnt<<' '<<lv<<' '<<rcnt<<' '<<rv<<endl;
//            cout<<lcnt*z-lv+rv-rcnt*z<<' '<<m<<endl;
            if(lcnt*z-lv+rv-rcnt*z<=m)flag=1;
            modify(1,mp[a[i-mid+1]],-a[i-mid+1],-1);
        }
        if(flag)l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
}
signed main(){
    fast
    solve();
}

G 每日一棵？

难度：中等

答案显然具有单调性
因此我们可以二分。对于 x 维我们可以直接排序解决，y 维我们可以维护一个前缀后缀 min max 即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>

void solve() {
    int n;cin>>n;
    vector<PII>v;
    vector<int>a,pre_mn(n,INF),pre_mx(n,-INF),suf_mn(n,INF),suf_mx(n,-INF);
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        v.push_back({x,y});
        a.push_back(x);
    }
    sort(all(v));
    sort(all(a));
    for(int i=0;i<n;i++){
        if(i)pre_mn[i]=min(pre_mn[i],pre_mn[i-1]);
        if(i)pre_mx[i]=max(pre_mx[i],pre_mx[i-1]);
        pre_mn[i]=min(pre_mn[i],v[i].second);
        pre_mx[i]=max(pre_mx[i],v[i].second);
    }
    for(int i=n-1;i>=0;i--){
        if(i!=n-1)suf_mn[i]=min(suf_mn[i],suf_mn[i+1]);
        if(i!=n-1)suf_mx[i]=max(suf_mx[i],suf_mx[i+1]);
        suf_mn[i]=min(suf_mn[i],v[i].second);
        suf_mx[i]=max(suf_mx[i],v[i].second);
    }
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r+1>>1;
        int x=mid,flag=0;
        for(int i=0;i<n;i++){
            int L=a[i];
            int R=a[i]+x;
            int it=lower_bound(all(a),R)-a.begin();
            if(it==n)continue;
            if(pre_mx[i]-suf_mn[it]>=x||suf_mx[it]-pre_mn[i]>=x){
                flag=1;
                break;
            }
        }
        if(flag)l=mid;
        else r=mid-1;
    }
    cout<<l<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    solve();
    return 0;
}

H & I 找 0_and_找 0_pro

难度：入门&简单

此题的本意考察大家思维或者说数学功底，不用使用高精度算法
我们只需查找 $a, b$ 两数中有多少对 2 和 5 的因子，因为一对 2，5 因子相乘等于 10. 也就是一对就一定有一个末尾0

#include<iostream>

long long a, b;

int solve(long long a, long long b)
{
    int cnt1 = 0, cnt2 = 0;
    long long A = a, B = b;
    while(A % 2 == 0)A /= 2, cnt1 ++;
    while(B % 2 == 0)B /= 2, cnt1 ++;
    while(a % 5 == 0)a /= 5, cnt2 ++;
    while(b % 5 == 0)b /= 5, cnt2 ++;
    return min(cnt1, cnt2);
}

int main()
{
    std::cin >> a >> b;
    std::cout << solve(a, b);
}

J 黎明之剑

难度：中等

思路：搜索的模板
考察宽搜/深搜, 敌方地盘用 # 表示，部分敌方地盘有碉堡用！表示，而答案要求输出的敌方地盘大小就是二者的和，需要派遣的白骑士的数量就是地盘的数量加碉堡数量的二倍。所以我们要找的就是地盘加碉堡的和的最大值，并且记录下当前这片区域碉堡的数量。因此宽搜或者深搜都可以解决，需要注意可以将所有已经跑过的路标除以免跑重复道路导致超时。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define maxn 1060
using namespace std;
int n,m;
char c[maxn][maxn];
int ti[4]={1,-1,0,0};
int tj[4]={0,0,1,-1};
bool v[maxn][maxn];
int ans1=0,ans2=0;
struct node{
	int x,y;
};
void find(int a,int b){//搜索
	int nans1=1,nans2=1;
	if(c[a][b]=='!')nans2++;
	v[a][b]=false;
	queue<node> Q;
	node X;
	X.x=a,X.y=b;
	Q.push(X);
	while(!Q.empty()){
		node fi=Q.front();
		Q.pop();
		int x=fi.x,y=fi.y;
		for(int i=0;i<4;i++)
			if(v[x+ti[i]][y+tj[i]]){
				nans1++;nans2++;
				if(c[x+ti[i]][y+tj[i]]=='!')nans2++;
				node N;
				N.x=x+ti[i],N.y=y+tj[i];
				Q.push(N);
				v[x+ti[i]][y+tj[i]]=false;
			}
	}
	if(nans1>ans1){
		ans1=nans1;
		ans2=nans2;
	}
}
int main(){
	memset(v,false,sizeof(v));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='*')v[i][j]=false;
			else v[i][j]=true;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(v[i][j])find(i,j);
	cout<<ans1<<" "<<ans2;
}

K 重构代码

难度：简单

思路：排序+贪心
考察任意排序算法，将所有 bug 的位置进行排序后，求出每两个 bug 差即为需要修改的行数。因为需要修改的段落尽可能的少，所以再次进行排序后从修改行数第 m+1 多的位置开始累加即为答案。题面增加了阅读难度因此需要看懂样例和样例说明。

#include<iostream>
#include<algorithm>
#define maxn 10050
using namespace std;
int x,n,m;
int a[maxn];
int b[maxn];
int ans;
int main(){
	cin>>x>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=2;i<=n;i++)
		b[i-1]=a[i]-a[i-1];
	sort(b+1,b+n);
	for(int i=n-m;i>=1;i--)
		ans+=b[i];
	cout<<ans;

L 概率机器人

难度：中等

此题考查知识点为动态规划——dp
其实 dp 大家早在中学阶段就有所接触，如数列的递推公式。求解 dp 问题的关键步骤即为找出递推方程。因为规定机器人只能向下或是向右走，那么在一个格子所获得的期望值一定来自于它右方格子的期望乘以概率+它下方格子的期望乘以概率。我们定义一个二维数组 dp[1000][1000] 那么可得到递推公式 $d p [i] [j] = d p [i + 1] [j] \times p_{1} + d p [i] [j + 1] \times p_{2}$ 即可得出答案

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
struct Grid{
  double value;
  double pd, pr;
}g[1010][1010];
int n, m;
void dp(){
  for(int i = n - 1; i >= 0; i--){
    for(int j = m - 1; j >= 0; j--){
      g[i][j].value += g[i + 1][j].value * g[i][j].pd + g[i][j + 1].value * g[i][j].pr; 
    }
  }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        cin >> g[i][j].value;
      }
    }
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        double p;
        cin >> p;
        g[i][j].pd = p / 100;
        g[i][j].pr = 1 - p / 100;
      }
    }
    dp();

    char ans[100];
    sprintf(ans, "%.0lf", g[0][0].value);
    cout << ans << endl;
}

M 养生的大学生

难度：简单

思路：二进制+贪心
考察思维，代码实现考察与或非运算或者模拟，文中提到至少需要两杯一样的才能合成一杯，当前拥有的杯数可以合成多少杯可以想成一杯最多可以装多少杯，显而易见的是一定是 $2^{n}$ 才能压缩成一个杯子。因此我们可以将给定的数字 n 转化成二进制表示，二进制情况下每拥有一个 1 就证明需要多加一个杯子。

N 的值	二进制表达	需要的杯子数量
2	10	1
3	11	2
4	100	1
5	101	2

所以问题就变成了查找当前二进制中 1 的个数，如果超出 m 就想办法消掉 1，计算到达 m 至少需要加多少。

代码实现：

如果熟悉与或非运算就会记得负数的补码转为原码是对补码（除符号位）逐位取反后，并在最低位＋1。-n 是 n 的二进制补码的求补运算，它等于 ~n + 1，再与 n 进行&运算就可以获得最小 1 的位置。
如果对于或非不熟悉就可以暴力打表记录下 $2^{27}$ 所有数字的值然后手动模拟查找位数过程，也可以获得答案。

#include<iostream>
using namespace std;
int n, m, ans;
int main() {
	cin>>n>>m;
	while(__builtin_popcount(n) > m) ans += n & -n, n += n & -n;
    //__builtin_popcount返回二进制数中1的个数
	cout<<ans;
}

A 数一数三角形

难度：简单

B 作文批改

难度 ：入门

C 找找 ACM

难度：中等

D 字符串相约

难度：中等

E 简单 DP

难度：中等

F 两点距离

难度：困难

G 每日一棵？

难度：中等

H & I 找 0_and_找 0_pro

难度 ：入门&简单

J 黎明之剑

难度：中等

K 重构代码

难度：简单

L 概率机器人

难度：中等

M 养生的大学生

难度：简单

难度：入门

难度：入门&简单