A

签到

判断一个数列是否由给定元素构成，由于反例很少，可以从反例入手，写的更短

#include<bits/stdc++.h>
using namespace std;
int main(){
    int f=0;
    for(int i=0;i<7;i++){
        int x;
        cin>>x;
        if(x==4||x==7)f=1;
    }
    if(f)cout<<"NO";
    else cout<<"YES";
}

B

签到

找到至少比一半元素小的最大元素，先排序然后找中位数前面那个数就行

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    cout<<a[n/2]-1;
}

D

贪心

一个元素，如果出现至少两次，那么第二次出现及后面的部分，都可以成为满足题目要求的子串，因为可以把这个字符用第一次出现进行替换，就能得到和这个子串相同的非连续子序列了

所以我们记录每个字符的出现次数，出现第二次之后，用这个字符及后面子串的长度更新答案。这个结论从左往右和从右往左看都成立，所以把字符串反转再跑一遍

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    cout<<a[n/2]-1;
}

C

构造

注意到 $D$ 题的结论，有影响的只有一个字符的第一次出现和第二次出现的位置，所以我们完全可以把一个字符x的第一次出现安排在 $a[1]$ ，第二次出现安排在 $a[n-m 1]$ ，中间安排其它元素，第二次出现后面的元素可以随便安排，这样 $a[n-m 1,n]$ 就是最大的子串，答案为 $n-(n-m)=m$ 。

具体构造的时候，一种构造方式是，直接a[i]='a'+i%(n-m)即可，就是满足上面的要求的。

显然根据我们的构造方式，第一次和第二次出现中间要都是非 $x$ 的字符，那么当 $n-m>26$ 的时候就无解了，因为只有26种字母，没法保证中间都是不同的，且非 $x$ 的字母了。

另外根据 $D$ 题的求法，显然答案最大值在a[1]=a[2]时取到，为 $n-1$ ，因此有 $m<=n-1$ ，所以 $m=n$ 时也无解

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        if(n==m||n-m>26){
            cout<<"NO\n";
            continue;
        }
        cout<<"YES\n";
        for(int i=0;i<n;i++){
            char c='a'+i%(n-m);
            cout<<c;
        }
        cout<<'\n';
    }
}

E

贪心，线段树

对一个区间，一个牌被推倒的条件为sum(i-1)-sum(l-1)>=a(i)，其中 $sum(i)$ 为前缀和数组， $l$ 位置的牌可以被无条件推倒，问对于每个区间 $[l,r]$ ，想把把这个区间全部推倒，的最少操作次数？每次操作可以把一个位置的权值加一/减一。

首先，如果我们要操作，应该怎么操作最省？我们如果要加一的话，加在 $a(l)$ 上，可以对所有以 $l$ 为左端点的区间都有影响，效率显然是最高的。

其次，如果我们减一，对当前位置的推倒是有帮助，但是对于后面的牌来说，这其实是减少了左侧牌的重量和，我们还要额外加上减去的值才能弥补回来，这会增加操作次数，如果我们想在 $a(i)$ 上减 $x$ ，r让 $a(l)$ 倒下，那我们在 $a(l)$ 上加 $x$ 也能起到同样的效果，并且后面并不用再额外加以抵消这个减的影响。所以加法永远优于减法，我们可以只考虑加。

然后考虑在 $a(l)$ 上加 $x$ 的话，前面的推倒条件的不等式就变为x+sum(i-1)-sum(l-1)>=a(i)。变形可得x>=a(i)-sum(i-1)+sum(l-1)

要可以推倒 $[l,r]$ ，就是要让上式对于i∈[l+1,r]都成立，也就是 x>=max(a(i)-sum(i-1)+sum(l-1))。

到这一步，就转化为一个区间 $max$ 问题了，用支持区间查的数据结构都可以。注意需要特判 $l=r$ 的情况

struct Tree{
    struct Node{
        int l,r;
        ll mx,add;
    }tr[N<<2];
     
    void pushup(int u){
        tr[u].mx=max(tr[ls].mx,tr[rs].mx);
    }
     
    void pushdown(int u){
        if(tr[u].add){
            tr[ls].mx+=tr[u].add;
            tr[rs].mx+=tr[u].add;
            tr[ls].add+=tr[u].add;
            tr[rs].add+=tr[u].add;
            tr[u].add=0;
        }
    }
     
    void build(int u,int l,int r){
        tr[u]={l,r,0,0};
        if(l==r){
            if(l!=n)tr[u].mx=a[l+1]-sum[l];
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);    build(rs,mid+1,r);
        pushup(u);
    }
     
    void modify(int u,int l,int r,int val){
        if(tr[u].l>=l&&tr[u].r<=r){   
            tr[u].mx+=val;
            tr[u].add+=val;
            return ;
        }
        else{
            int mid=(tr[u].l+tr[u].r)>>1;
            pushdown(u);
            if(mid>=l)   modify(ls,l,r,val);
            if(r>mid) modify(rs,l,r,val);
            pushup(u);  
        }
    }
     
    ll query(int u,int l,int r){
        if(l<=tr[u].l&&tr[u].r<=r)    return  tr[u].mx;
        pushdown(u);
        int mid=(tr[u].l+tr[u].r)>>1;
        if(r<=mid)return query(ls,l,r);
        if(l>mid)return query(rs,l,r);
        return max(query(ls,l,r),query(rs,l, r));
    }
}t;
void solve(){
	cin>>n>>m;
	rep(i,1,n){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	t.build(1,1,n);
	rep(i,1,m){
		int l,r;
		cin>>l>>r;
		if(l==r){
			cout<<0<<'\n';
		}
		else{
			t.modify(1,l,r,sum[l-1]);
			cout<<t.query(1,l,r-1)<<'\n';
			t.modify(1,l,r,-sum[l-1]);
		}
	}
}	

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int test=1;
    //cin>>test;
    
    while(test--){
    	solve();
    }
}

F

位运算/打表

首先打表也能做，这个就不讲了

然后正解其实是用到一个位运算知识x+y=x^y+2*(x&y)。带入题目的式子可以发现就是x|y=x&y，这显然只有在 $x=y$ 时成立，因此答案就是区间长度

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long l,r;
        cin>>l>>r;
        cout<<r-l+1<<'\n';
    }
}

G

倍增思想

倍增是增长很快的，因此每次都 $*m$ 实际上只会进行 $logn$ 次就会超过 $n$ ，所以直接枚举每个温度就行。需要特判的是 $m=1和m>n$ ，我的写法有点屎。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long n,m;
        cin>>n>>m;
        if(m==1||m>n){
            cout<<0<<'\n';
            continue;
        }
        long long t=m;
        long long mn=abs(n-t);
        int cnt=0;
        while(t<=n){
            cnt++;
            mn=min(mn,n-t);
            t*=m;
        }
        if(t-n<mn){
            cout<<cnt+1<<'\n';
        }
        else{
            cout<<cnt<<'\n';
        }
    }
}

H

贪心，数学

三点共圆的极限情况是三点共线，此时圆无穷大，因此越接近三点共线，圆越大。因此我们可以先把两个点安排在一条线上，另一个点就在最接近三点共线的位置上，也就是其他边上最接近这条边的位置上。

然后这两点具体在这条线上的位置，可以根据一个结论分析 $2R=A/sina$ ，我们这里的 $a>90度$ ， $a$ 越大 $sin$ 越小，因此应该把这两个点往尽量远离第三个点的地方放，这样离得远 $A$ 变大， $a$ 变大， $sina$ 变小， $R$ 变大。然后由于不能重叠，就在里第三个点最远的两个点上。

然后上述分析我们没考虑长边和短边的影响，显然我们应该把两个共线的点放在长边上，因为长边上 $A$ 更大， $a$ 更小， $R$ 一定更大

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(b-a>d-c){
            cout<<a<<' '<<c<<'\n';
            cout<<a+1<<' '<<c<<'\n';
            cout<<b<<' '<<c+1<<'\n';
        }
        else{
            cout<<a<<' '<<c<<'\n';
            cout<<a<<' '<<c+1<<'\n';
            cout<<a+1<<' '<<d<<'\n';
        }
    }
}

M

数学，思维

首先这个数独就是一个滑窗，出去一列，进来一列，但是前后的数字集合是相同的，因此出去一定等于进来，也就是每三列，所包含的数字集合是循环的，形式化就是s(i%3)都相同，s(i)表示第 $i$ 列的数字集合

那么无解的情况可以先分析出来了：一列一个数字出现不止一次，一个数字出现在模3不同的列上，模3相同的列，出现的数字不止三种，都无解

对于有解的方案数，首先显然对于每一列的问号，我们填的数字可以随意排列，因此乘上每一列的问号个数的排列数。然后我们能填的数字屎未出现过的数字，假设模3余 $i$ 的列出现元素个数为 $a_i$ ，那模3余 $i$ 的列就有 $3-x$ 个空位可以填，这就是个放球问题。最后方案数为 $C(9-a_1-a_2-a_3,3-a_1)*C(6-a_2-a_3,3-a_2)*C(3-a_3,3-a_3)$

#include<bits/stdc++.h>
using namespace std;
#define int  long long
using ll = long long;
template <const int mod> struct comb {
    vector<int> f, g, v;
    
    comb(int n) : f(n + 1), g(n + 1), v(n + 1) {
        f[0] = g[0] = v[0] = 1;
        v[1] = 1;
        for (int i = 2; i <= n; i++) {
          v[i] = (1LL * (mod - mod / i) * v[mod % i]) % mod;
        }
        for (int i = 1; i <= n; i++) {
            f[i] = (1LL * i * f[i - 1]) % mod;
            g[i] = (1LL * g[i - 1] * v[i]) % mod;
        }
    }
    
    ll operator()(int n, int m) {
        if (m > n || m < 0 || n < 0) return 0;
        int ans = (1LL * f[n] * g[m]) % mod;
        ans = (1LL * ans * g[n - m]) % mod;
        return ans;
    }
};

const int mod = 1e9 + 7;
        
comb<mod> C(1000000);
signed main(){
        int t;
        cin>>t;
        vector<int>fac(10);
        fac[0]=1;
        for(int i=1;i<10;i++)fac[i]=fac[i-1]*i%mod;
        while(t--){
            int n;
            cin>>n;
            set<int>s[3];
            vector<int>c(n);
            vector<vector<char>>a(3,vector<char>(n));
            for(int i=0;i<3;i++){
                for(int j=0;j<n;j++){
                    cin>>a[i][j];
                    if(a[i][j]=='?'){
                        c[j]++;
                        continue;
                    }
                    int x=a[i][j]-'0';
                    s[j%3].insert(x);
                }
            }
            bool ok=1;
            for(int i=0;i<n;i++){
                set<int>vis;
                for(int j=0;j<3;j++){
                    if(a[j][i]=='?')continue;
                    int x=a[j][i]-'0';
                    if(vis.count(x))ok=0;
                    vis.insert(x);
                }
            }
            
            for(int i=1;i<10;i++){
                int cnt=0;
                for(int j=0;j<3;j++){
                    if(s[j].count(i)){
                        cnt++;
                    }
                }
                if(cnt>1){
                    ok=0;
                }
            }
            
            for(int i=0;i<3;i++){
                if(s[i].size()>3){
                    ok=0;
                }
            }
            if(!ok){
                cout<<0<<'\n';
            }
            else{
                vector<int>cnt(3);
                cnt[0]=s[0].size();
                cnt[1]=s[1].size();
                cnt[2]=s[2].size();
                int ans=C(9-cnt[0]-cnt[1]-cnt[2],3-cnt[0]);
                ans=ans*C(6-cnt[1]-cnt[2],3-cnt[2])%mod;
                for(int i=0;i<n;i++){
                    ans=ans*fac[c[i]]%mod;
                }
                cout<<ans<<'\n';
            }
        }
}

2025牛客寒假营第二场题解(不含IL)

A

B

D

C

E

F

G

H

M