Dashboard - Codeforces Round #824 (Div. 2) - Codeforces

1.Problem - A - Codeforces

考虑第一部分只取一天然后第二部分取1/3，最后一天取剩下的。然后再中间的增大，第三天减小。但最大值不再增大时就breakl。

void slove(){
    cin>>n;
    if(n<=8){
        cout<<0<<endl;
        return;
    }
    int t1=1;
    int t2=(n-4)/3;
    int t3=n-4-t2;
    int ans=min(t2-t1,t3-t2);
    while(1){
        if(min(t2+1-t1,(t3-1)-(t2+1))>ans)  {
            ans=min(t2+1-t1,(t3-1)-(t2+1));
            t2++;
            t3--;
        }
        else    break;
    }
    cout<<ans<<endl;
}

2.Problem - B - Codeforces

考虑每部分最多可以时多少，最小值的两倍-1，所以考虑每次都切出去这么多。但是如果直接a[i] / (a[1] * 2 - 1)会发现10，然后38需要两刀实际上只需要一刀。所以对那种是倍数的就-1即可。

void slove(){
    cin>>n;
    fel(i,1,n) cin>>a[i];
    sort(a+1,a+1+n);
    int ans=0;
    if(a[1]==1){
        int ans=0;
        fel(i,2,n){
            ans+=(a[i]-1);
        }
        cout<<ans<<endl;
    }
    else{
        int ans=0;
        fel(i,2,n){
            ans+=a[i]/(a[1]*2-1)-(a[i]%(a[1]*2-1)==0);
        }
        cout<<ans<<endl;
    }
}

3.Problem - C - Codeforces

就是对前面的字符尽量选择大的，然后如何判断这个字符可不可以选呢?

就是我后面的字符没有他，或者后面有25给字母绕个圈于是他就可以接在我的头上。

const int N=500;
int n;
string s;
int q[N],h[N],vis[N],cnt,flag;
void dfs(int now,int pre){
    if(now==-1) return;
    cnt++;
    if(now==pre) flag=1;
    dfs(h[now],pre);
}
bool check(char pre,char ne){
    if(pre!=ne&&vis[pre]==0){//pre此时还没做过前驱，所以只要搜他在ne的后面没即可。
        //两种可能一种是这个字符还没用过，另外一种是是ne和pre之间隔24个字母首位相接
        cnt=0,flag=0;
        dfs(h[ne],pre);
        if(flag==0||cnt==25){
            return true;
        }
    }
    return false;
}
void slove(){
    cin >> n;
    cin >> s;
    s = " " + s;
    fel(i,0,200) vis[i]=0,q[i]=-1,h[i]=-1;
    string ans="";
    fel(i,1,n){
        if(q[s[i]]!=-1){
            ans+=q[s[i]];
            continue;   
        } 
        for(char j='a';j<='z';j++){
            if(check(j,s[i])){
                q[s[i]]=j;
                h[j]=s[i];
                vis[j]=1;//后面有字符的给标记
                ans+=j;
                break;
            }   
        }
    }
    cout<<ans<<endl;
}

4.Problem - D - Codeforces

这样的map确实也不错。

首先分析一下三张牌想要是good的话必须得每一项得和是三的倍数。000，111，222，012。总共就这四种情况。

让后再考虑五张牌必须组成两个集合。那么两个集合必然会重复一张牌。考虑是否可以证明两个集合最多只会共享一张牌。题目保证了向量不会重复。如果一个good集合中有两个向量相同那另外一个向量也必须是这个向量否则取模三是不可能等于0的，看上面的四种情况就知道。所以一个集合中三个向量都是不相同的。那考虑取1作为中心牌，后面如果2，3向量和2，4向量的和是相等的。那就会只选四个数。这种情况看似会出现。实际并不会，因为一个集合中如果两个向量相同第三个向量也必然相同，但是1，2，3和1，2，4并不全部相同所以这种情况并不会出现。

那么就可以考虑先算出两张牌的和。然后求每个牌作为重复的那张牌所产生mete--set。这样五个向量都是选择了不同的。

void slove(){
    cin>>n>>k;
    map<vector<int>,int>mp;
    vector<vector<int> >a(n+1,vector<int>(k+1));
    vector<int>v(k+1);
    fel(i,1,n){
        fel(j,1,k){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int w=1;w<=k;w++){
                v[w]=(6-a[i][w]-a[j][w])%3;
            }
            mp[v]++;
        }
    }   
    int ans=0;
    for(int i=1;i<=n;i++){
        int x=mp[a[i]];
        ans+=(x*(x-1)/2);
    }
    cout<<ans<<endl;
}