跳转至

Codeforces Round 1018, Div. 1 + Div. 2

2025-04-19

最不专注的一集，C 题的很重要的一句话没看到。A题也是题都没看清楚就交，耽误好多分钟。

link: https://codeforces.com/contest/2096

maodie.gif

A

看样例解释就能看出来啊，而且题目明明说得很清楚了。\(s_i='>'\) ，那么 \(a_{i+1}\) 必须大于前面的所有数字，否则 \(a_{i+1}\) 小于前面的所有数字。

void ChatGptDeepSeek() // Date: 2025-04-19
{                      // Time: 22:37:01 
    int n;
    cin>>n;
    string s;
    cin>>s;
    vi a;
    int L=1,R=n;
    for(int i=sz(s)-1;i>=0;i--){
        if(s[i]=='>') a.push_back(R--);
        else a.push_back(L++);
    }
    a.push_back(L);
    reverse(all(a));
    for(auto x:a)
        cout<<x<<" ";
    cout<<'\n';
}

B

这个还行的，首先 \(n\) 个 \(max(l_i,r_i)\) 肯定是都得加上的。那么剩下的，我们肯定是先把前 \(k-1\) 个大的 \(min(l_i,r_i)\) 拿了，然后再无论如何拿一个就拿不了了。

void ChatGptDeepSeek() // Date: 2025-04-19
{                      // Time: 22:53:39 
    int n,k;
    cin>>n>>k;
    vi l(n),r(n);
    for(int i=0;i<n;i++) cin>>l[i];
    for(int i=0;i<n;i++) cin>>r[i];
    ll ans=0;
    vi c(n);
    for(int i=0;i<n;i++){
        ans+=max(l[i],r[i]);
        c[i]=min(l[i],r[i]);
    }
    sort(all(c),greater<int>());
    for(int i=0;i+1<k;i++)
        ans+=c[i];
    cout<<ans+1<<'\n';

}

C

服了自己了。。。每个工人只能使用一次！！！

所以直接枚举前一个有没有加。我真是，想了一小时，我想着每行最多加 \(n\) 次吧，所以复杂度 \(n^3\) 。。。

每个工人用一次就很简单，而且行和列还是独立的。

void ChatGptDeepSeek() // Date: 2025-04-20
{                      // Time: 00:09:04 
    int n;
    cin>>n;

    vector<vi>a(n+1,vi(n+1));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];
    vi A(n+1),B(n+1);
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<=n;i++) cin>>B[i];
    vector<vl> c(n+1,vl(2,LNF));
    c[1][0]=0;
    c[1][1]=A[1];
    for(int i=2;i<=n;i++){
        for(int x=0;x<2;x++){
            for(int y=0;y<2;y++){
                bool ok=true;
                for(int j=1;j<=n;j++){
                    if(a[i-1][j]+x==a[i][j]+y){ok=false;break;}
                }
                if(ok) cmin(c[i][y],c[i-1][x]+(y?A[i]:0));
            }
        }
    }
    ll ans=min(c[n][0],c[n][1]);
    if(ans==LNF){
        cout<<"-1\n";
        return;
    }
    c=vector<vl>(n+1,vl(2,LNF));
    c[1][1]=B[1],c[1][0]=0;
    for(int i=2;i<=n;i++){
        for(int x=0;x<2;x++){
            for(int y=0;y<2;y++){
                bool ok=true;
                for(int j=1;j<=n;j++){
                    if(a[j][i]+y==a[j][i-1]+x){ok=false;break;}
                }
                if(ok) cmin(c[i][y],c[i-1][x]+(y?B[i]:0));
            }
        }
    }
    if(min(c[n][1],c[n][0])==LNF){
        cout<<"-1\n";
        return;
    }
    ans+=min(c[n][1],c[n][0]);
    cout<<ans<<'\n';
}

D

难难，不会，明天我将进行一个题解大学习。

六百六十六啊，这题和算法有啥关系？？？每次操作，每行的灯泡的数量的变化一定是偶数，稍微想一下就能发现没有问题。但是纵坐标怎么找呢？如果是正方形，那么会和横坐标一样，但这题的形状不太一样。但是 \(x+y\) 的数量的变化一定也是偶数。

void ChatGptDeepSeek() // Date: 2025-04-20
{                      // Time: 10:01:56 
    int n;
    cin>>n;
    int X=0,Y=0;
    while(n--){
        int x,y; cin>>x>>y;
        X^=x,Y^=(x+y);
    }
    cout<<X<<" "<<Y-X<<'\n';
}