2026牛客寒假算法基础集训营5

B

用 $(i+j)\mod 2$ 的方法判断符号，注意 \ 是需要转义的。

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

signed main() { 
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i+j)%2==1)  cout<<'\\';
            else cout<<'/';
        }
        cout<<endl;
    }
}

D

合并果子，但是多了一个对每个堆数量的优化，如果直接将每堆的每个果子看成单独一个果子是会超时的。所以可以按堆为单位来操作，将分奇偶情况讨论即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;

struct Node {
    int c, w;
    friend bool operator<(Node a, Node b) { return a.w > b.w; }
};
priority_queue<Node> pq;
Node node[100005];

signed main() {
    int n,rem=0,ans=0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> node[i].c >> node[i].w;
        pq.push(node[i]);
    }
    while (pq.size()>1) {   
        Node tnode = pq.top();
        pq.pop();
        int w=tnode.w,c=tnode.c;
   //   cout<<c<<" "<<w<<endl;
        if(rem!=0){
            pq.push(Node{1,rem+w});
            ans=(ans+rem+w)%mod;
            c-=1,rem=0;
        }
        if(c%2==1){
            rem=w;
        }
        if(c>=2)pq.push(Node{c/2,w*2});
        ans=(ans+(c/2)*2*w)%mod;
    }
    if(rem) ans=(ans+rem+pq.top().w)%mod;
    cout<<ans<<endl;
}

E

如果要求最大值，首先先算出前缀和数组，然后可以分为几种情况：

前缀和数组自身
用比自身小的前缀和且顺序靠后的减去自身

情况1不需要解释，情况2是因为取模后的数变小后再减前面的数需要加上 $p$ ，我们假设前后两个前缀和的下标为$a$ ，$b$ 那么只需要当 $b$ 比 $a$ 小的时候，比较$sum[b]+p-sum[a]$ ，其他的情况是不可能大的。然后是优化的方法：直接从前开始遍历前缀和数组，对于遍历到的每个$sum[i]$，看比它小的也就是$sum[i-1]$，比较序号，如果自己的序号大，就直接跳出继续遍历，因为即使再向前找也不会比它前面的哪个数字找到的更大（ gemini 的证明），如果自己序号小，就和ans比较记录。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100005];
struct Node {
    int val, num;
    friend bool operator<(Node qa, Node qb) {
        if(qa.val == qb.val)    return qa.num<qb.num;
        return qa.val < qb.val;
    }
};
Node node[100005];
signed main() {
    int n, p, ans = -1, ansl=0, ansr=0;
    cin >> n >> p;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i]>ans){
            ans=a[i]%p;
            ansl=i,ansr=i;
        }
        node[i].val = (node[i - 1].val + a[i]) % p;
        if(i==0)    node[i].val=a[i];
        node[i].num = i;
        if(node[i].val>ans){
            ans=node[i].val;
            ansl=0,ansr=i;
        }
    }
    sort(node, node + n);
    for (int i = 1; i < n; i++) {
        if (node[i].num < node[i - 1].num&&node[i].val!=node[i-1].val) {
            if (ans <= node[i - 1].val + p - node[i].val) {
                ansl = node[i].num + 1; ansr = node[i - 1].num ;
                ans = node[i - 1].val + p - node[i].val;
            }
        }
    }
    cout << ansl << ' ' << ansr << ' ' << ans;
}

F

首先我们有三种决策，分别是 qcjjkkt ，qcjjkktd ，td 这三种。他们的长度是 7，8，2，显然最小公倍数是56，因此我们可以让 n 的可以整除 56 的部分来全部用三种的最优的方案，对于剩下的部分，我们还需要注意，有一部分情况是可能出现错误的，例如：最后剩下了6个字符，而我们可以通过调整之前的字符来让它塞得下一个7字符的字符串（只是随便举个例子，可以不是正确但是道理是这样的）。因此我们需要让剩余的部分至少比56要大。

而对于剩余的部分，由于数据范围比较小，我们既可以dp也可以暴力枚举，在这里我用的dp。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int max(int a,int b){
    return a>b?a:b;
}
int d[200];
signed main() {
    int t;
    cin>>t;

    while(t--){
        memset(d,0,sizeof(d));
        int n,a,b,ans=0;
        cin>>n>>a>>b;
        int r=n;
        if(n>=112){
            r=n%56; 
            r=r+56;             
            int tp;
            tp=max((n-r)/7*a,(n-r)/2*b);
            tp=max(tp,(n-r)/8*(a+b));
            ans+=tp;
        }

        for(int i=0;i<=r;i++){
            if(i>=2)    d[i]=max(d[i],d[i-2]+b);
            if(i>=7)    d[i]=max(d[i],d[i-7]+a);
            if(i>=8)    d[i]=max(d[i],d[i-8]+a+b);
            d[i]=max(d[i],d[i-1]);
        }
        ans+=d[r];
        cout<<ans<<endl;
    }

}

G

直接按题模拟即可，我看大佬的题解，有用异或来做的，我是用的模来做的，我的代码没了，这里给出大佬的题解：

首先最后两种操作对于状态无非是加一或是减一后对 44 取模。

00 操作会将 (0,3),(1,2)(0,3),(1,2) 互换，相当于是异或 33 。

11 操作会将 (1,3)(1,3) 互换， (0,2)(0,2) 不变，相当于是对奇数异或 22 。

22 操作会将 (0,1),(2,3)(0,1),(2,3) 互换，相当于是异或 11 。

33 操作会将 (0,2)(0,2) 互换， (1,3)(1,3) 不变，相当于是对偶数异或 22 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    string s = "01122334451420153201254102145302145102141023";
    s += "02142025101203201451451522302514203214510021454101002532";
    int tar = 0;
    for(auto &i : s){
        if(i == '0') tar ^= 3;
        if(i == '1' && (tar & 1)) tar ^= 2;
        if(i == '2') tar ^= 1;
        if(i == '3' && !(tar & 1)) tar ^= 2;
        if(i == '4') tar = (tar + 1) % 4;
        if(i == '5') tar = (tar + 3) % 4;
        cout << tar;
    }
    cout << endl;
}

I

每次操作后都能够使得所有的深度增加，答案具有单调性，因此考虑二分。在思考如何在每次判断时优化计算过程。考虑记录下每个位置的力度，是否是力度传播的源点，并且用另外的数组记录传播的尽头，在力度的传播过程递减的过程中，持续的修改当前力度的总和以及有多少源点在起作用，这样我们就能够通过从前到后和反向的两次遍历来计算出所有点的深度。注意两次重复计算了作为源点的力度，因此要减去这个数。复杂度 $O(nlogn)$ 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node{
    int p,f;
};
Node node[200005];
int depth[200005],waitDig[200005],lazyF[200005],lazyB[200005],spdArr[200005];
int max(int a,int b){
    return a>b?a:b;
}
signed main() {
    int n,m,h,ans=0;
    cin>>n>>m>>h;
    for(int i=1;i<=m;i++){
        cin>>node[i].p>>node[i].f;
    }
    int l=1,r=m,mid;
    mid=(l+r)/2;
    while(l<=r){

        memset(lazyF,0,sizeof(lazyF));
        memset(lazyB,0,sizeof(lazyB));      
        memset(waitDig,0,sizeof(waitDig));
        memset(depth,0,sizeof(depth));
        memset(spdArr,0,sizeof(spdArr));
        bool vis=0;
        mid=(l+r)/2;
        for(int i=1;i<=mid;i++){
            waitDig[node[i].p]+=node[i].f;//标记位置存有多少力度的数组
            lazyB[max(0, node[i].p-node[i].f+1)]+=1;
            lazyF[min(n, node[i].p+node[i].f-1)]+=1;
            spdArr[node[i].p]+=1;//标记当前位置挖过多少次
        }
        int spd=0;//传播大小
        int numSpd=0;//传播数量
        for(int i=1;i<=n;i++){//正向计算深度
            numSpd+=spdArr[i]; //传播数量加当前位置
            spd+=waitDig[i];   //力度传播
            depth[i]+=spd;     //深度更新
            spd-=numSpd;       //力度传播后更新
            numSpd-=lazyF[i];  //传播数量更新
            depth[i]-=waitDig[i];           
            //cout<<depth[i]<<' ';  

        }
        numSpd=0;
        spd=0;
        //cout<<endl;
        for(int i=n;i>=1;i--){//反向计算深度
            numSpd+=spdArr[i];
            spd+=waitDig[i];   
            depth[i]+=spd;
            spd-=numSpd;
            numSpd-=lazyB[i];
            if(depth[i]>h) vis=1,ans=mid;
            //cout<<depth[i]<<' ';
        }
        if(vis){
            r=mid;
            if(l==r)    break;
        }else{
            l=mid+1;
        }
    }
    if(ans){
        cout<<"Yes"<<endl;
        cout<<ans<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

J

判断各个数是否为15即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
bool vis[10];
signed main() {
    bool r=1;
    int line[4]={0},col[4]={0},x1=0,x2=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            int tp;
            cin>>tp;
            if(i==j) x1+=tp;
            if(i+j==4) x2+=tp;
            if(!vis[tp])    vis[tp]=1;
            else r=0;
            line[i]+=tp;
            col[j]+=tp;
        }
    }
    for(int i=1;i<=3;i++){
        if(line[i]!=15||col[i]!=15) r=0;
    }
    if(x1!=15||x2!=15)  r=0;
    if(r)   cout<<"Yes";
    else cout<<"No";
}

证明如下

假设我们找到了一个满足条件的完美答案是 $a_j - a_i$，其中 $i < j$，且 $p_i > p_j$（大的数字标号小）。>假设这两个数字不是相邻的，也就是说在它们中间还夹着一个数字 $a_k$（即 $i < k < j$）。

因为数组排好序了，所以这三个数字的大小关系必然是：

$$a_i \le a_k \le a_j$$

现在我们来看中间这个数 $a_k$ 的标号 $p_k$。因为 $p_i > p_j$，那么对于 $p_k$ 来说，必定满足以下两种情况之一：

要么 $p_k < p_i$：这意味着 $a_k$ 和 $a_i$ 组成了一个合法的对！而且因为 $a_k \le a_j$，所以它们的差值 $a_k - a_i \le a_j - a_i$。这说明找 $a_k$ 会得到一个更小或相等的差值。

要么 $p_k > p_j$：这意味着 $a_j$ 和 $a_k$ 组成了一个合法的对！而且因为 $a_k \ge a_i$，所以它们的差值 $a_j - a_k \le a_j - a_i$。这也说明找 $a_k$ 会得到一个更小或相等的差值。

结论：如果存在跨越多个数字的合法组合，我们总能在它们中间找到距离更近的合法组合，并且差值绝不会变大！因此，不断往中间缩小范围，最终的最小差值必然出现在某一对相邻的元素 $(a_{x-1}, a_x)$ 之间。

: )

2026牛客寒假算法基础集训营5

2026牛客寒假算法基础集训营5

B

D

E

F

G

I

J

2026牛客寒假算法基础集训营4

浅谈C#特性

Comments NOTHING

取消回复