Dashboard - Educational Codeforces Round 138 (Rated for Div. 2) - Codeforces

这场比赛写的就很菜了。D题有点思路但是没想到是求是去求不满足条件的序列。

1.Problem - A - Codeforces

考虑如果所有行所有列都被占据的话就是无法移动了。

void slove(){
    cin >> n >> q;
    fel(i,1,n) visx[i] = visy[i] = 0;
    fel(i,1,q) 
    {
        int x, y;
        cin >> x >> y;
        visx[x] = 1;
        visy[y] = 1;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(visx[i]) ans++;
        if(visy[i]) ans++;
    }
    if(ans == 2*n){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
    }
}

2.Problem - B - Codeforces

很明显每一个数都是会产生价值的除了最后一个被删除的。然后删除中间产生的价值肯定是更大的，所以考虑删除两边比较小的。双指针就好了。

void slove(){
    cin >> n;
    fel(i,1,n) cin>>a[i];
    fel(i,1,n) cin>>b[i];
    int l=1,r=n;
    int ans=0;
    while(l<r){
        if(b[l]>b[r]){
            ans+=a[r];
            ans+=b[r];
            r--;
        }
        else{
            ans+=a[l];
            ans+=b[l];
            l++;
        }
    }
    ans+=a[l];
    cout << ans <<endl;
}

3.Problem - C - Codeforces

很明显你想赢更多的次数，alice最优的选择肯定是选择先删除大的，而bob肯定是想要取删除最小的。去模拟这一过程即可。

void prime(){
    int cnt = 0;
    for(int i = 2;i < N; i++){
        if(!vis[i]){
            pr[++cnt] = i;
        }
        for(int j = 1; pr[j] * i < N;j++){
            vis[pr[j] * i] = 1;
            if(i % pr[j] == 0) break;
        }
    }
}

4.Problem - D - Codeforces

这个找满足条件的条件明显是难于不满足条件的。全一操作序列是明显满足条件的。

考虑一个位置如何只能在1号位置上被删除那他必须是1 - i 的 lcm 所以只要是1-i 的质数积即可。然后是枚举长度1-n即。

void prime(){
    int cnt = 0;
    for(int i = 2;i < N; i++){
        if(!vis[i]){
            pr[++cnt] = i;
        }
        for(int j = 1; pr[j] * i < N;j++){
            vis[pr[j] * i] = 1;
            if(i % pr[j] == 0) break;
        }
    }
}
void slove(){
    prime();
    cin >> n >> m;
    //想要减少取模是可以计算每一步唯一删除条件的方案数
    a[1] = m % mod;
    int lc = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i]) lc = i * lc / __gcd(i, lc);
        int cnt = m / lc;
        a[i] = a[i - 1] * (cnt % mod) % mod;//乘法和取模的优先级是相同的
    }
    
    b[1] = m % mod;
    for(int i = 2; i <= n; i++)
    {
        b[i] = b[i - 1] * (m % mod) %mod;
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
         ans = (ans + b[i] - a[i]) % mod;
    }
    cout << ans << endl;
}