本文主要是介绍Codeforces Round #786 (Div. 3)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Codeforces Round #786 (Div. 3)

C

题意

给一个全是 \(a\) 的字符串 \(s\) ，对它每一个 \(a\) 都可以用一个串 \(t\) 替换 。

问可替换的出来的新串数量。

思路

分类讨论，首先如果 \(t = a\) ，无论如何替换都不会改变 \(s\)

如果 \(t\) 中有 \(a\) 且长度大于1 ，替换的新串长度无限增加，有无穷多解。

对其他情况，对 \(s\) 的每一个 \(a\) 都可以选择换或者不换 ，共 \(2^{|s|}\) 种可能

#include<bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define lowbit(x) x&-x
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    string s,t; cin >> s >> t;
    if(t == "a") cout << 1 << endl;
    else {
        int cnt[26]; memset(cnt,0,sizeof cnt);
        for(int i = 0;i < t.size();i ++) cnt[t[i] - 'a'] ++;
        int sum = accumulate(cnt,cnt + 26,0ll);
        if((cnt[0] && sum - cnt[0] > 0) || cnt[0] > 1) cout << -1 << endl;
        else {
            cout << (1ll << ((int)(s.size()))) << endl;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}

D

题意

给一个序列 \(a\) ，对其进行两轮变换，求变换后的的序列是否单调不减

• 第一轮变换：每次从 \(a\) 末尾取出一个数，插入在一个新序列 \(b\) 的中间，如果 \(b\) 长度为奇数，可以插在中间数字的左或者右。直到 \(a\) 为空
• 第二轮变换：每次从 \(b\) 的中间取出一个数，插在新序列 \(c\) 的末尾，如果 \(b\) 为长度为偶数，可以选择中间两数的任意一个，直到 \(b\) 为空。

（一开始 \(b\) ，和 \(c\) 都是空的）

思路

贪心模拟。观察这个变换可以发现，每次从 \(a\) 中取出两个数后，因为序列奇偶性变换，可以将这两个数字顺序进行一次交换，同时在第二轮交换时，也可以将相邻操作中取出的两数字进行一次交换，所以就贪心的在这两次交换中，保证每相邻两次操作的数字是单调不减的。最后判断最终序列是否已经有序，如果没有，我们已经无法再令结果更优。

#include<bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define lowbit(x) x&-x
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int N; cin >> N;
    vector<int> a(N + 1),b(N + 1);
    for(int i = 1;i <= N;i ++) cin >> a[i];
    for(int i = N,l = 1,r = N;i > 0;i -= 2) {
        int x = a[max(1ll,i - 1)], y = a[i];
        if(x > y) swap(x,y);
        b[l ++] = x, b[r --] = y;
    }
    
    vector<int> c;
    int l,r;
    if(N & 1) {
        l = r = N / 2 + 1;
    }else l = N / 2, r = l + 1; 
    for(;l > 0 && r <= N;l --,r ++) {
        c.push_back(b[l]);
        c.push_back(b[r]);
        if(l == r) c.pop_back();
    }
    if(is_sorted(c.begin(),c.end())) cout << "YES\n";
    else cout << "NO\n";
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}

E

题意

有一面墙由一个个小段拼成，每一个小段都有一个血量 \(a_i\) ，现在你有一个弩炮，每次射击可以对城墙的连续三段造成 \([-1,-2,-1]\) 的伤害。

现在要求至少使得两段墙的血量不大于0（这两段墙可以不相邻），问最少几次炮击可以完成。

思路

按间隔分类，贪心。

先分析最终状态，一定是有至少两面墙破掉，

这两块墙如果相距较远，那么弩炮的射击就可以看成互不影响，独立发生的。此时不难想到就是 最小值和次小值 对答案有贡献。

如果它们间隔距离为1，设这一小段为 \([x,y,z]\) 目标是击破 \(x,z\) 一种方案是直接打 \(x\) 和 \(z\) 。此时它们彼此独立，情况1就已经包括了。如果打中间的 \(y\)，会对边上的 \(x,z\) 造成 \(-1\) 的影响。可以推出如下计算式。

其实就是先用溅射伤害把血量低的干掉，再直击打另外一个。

如果它们相邻，首先可以解一个方程得到 $ \lceil \frac{x + y}{3} \rceil $ 的计算式。此时就很容易忽略一种情况。比如 血量为 \((1,5)\) 时，算出来 \(2\) 实际上需要 \(3\) 次炮击。（少了什么约束没想懂QAQ）这种情况按独立炮击来算就行。

讨论完所有情况，代码很简单。

#include<bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define lowbit(x) x&-x
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int N; cin >> N;
    vector<int> a(N + 1);
    for(int i = 1;i <= N;i ++) cin >> a[i];
    int ans = 0;
    vector<int> b = a;
    sort(b.begin() + 1,b.end());
    ans = (b[1] + 1) / 2 + (b[2] + 1) / 2;

    auto fuck = [&](int x,int y) {return max({x + 1 >> 1,y + 1 >> 1,(x + y + 2) / 3});};
    auto calc = [&](int x,int y,int z) {
        return  min(x,z) + (max(x,z) - min(x,z) + 1) / 2;
    };
    
    for(int i = 1;i < N;i ++) ans = min(ans,fuck(a[i],a[i + 1]));
    for(int i = 1;i < N - 1;i ++) ans = min(ans,calc(a[i],a[i + 1],a[i + 2]));
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    //int T;cin>>T;
    //while(T--)
        solve();

    return 0;
}

F

感觉比 \(E\) 好写很多，就硬模拟，但题面太谜语人了，英语弱鸡属实看不懂。

题意

给一个二维网格，上面放了若干画像。

现在要将这些画像按列优先排列，询问需要移动的画像个数。

给出 \(q\) 次询问，每次给出一个 \((x,y)\) 坐标，翻转这个点的状态（也就是让画像变空地，让空地变画像）。询问移动个数。

思路

暴力模拟。

我们很容易处理出初始的答案。之后每次询问，只改变排列后画像覆盖的面积和网格上的一个点。所以我们也仅对之前求出的答案做一些微调。调整策略如下。

维护画像个数 \(cnt\) 和会对答案有贡献的画像数量 \(ans\) ，对答案有贡献的就是在画像覆盖范围外的画像。

对每次操作，如果令画像增加，先看扩张的新点是否是空地，如果是空地，就需要令 $ans ++ $ ，再改变 \((x,y)\) 处的状态，看是否在扩张的范围内部，如果在，就可以令答案减一。

对以一种情况，基本同上，不过多赘述。

#include<bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define lowbit(x) x&-x
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int N,M,Q; cin >> N >> M >> Q;
    vector<vector<char>> a(N + 1,vector<char>(M + 1));
    int cnt = 0;
    for(int i = 1;i <= N;i ++) for(int j = 1;j <= M;j ++) {
        cin >> a[i][j];
        cnt += a[i][j] == '*';
    }
    
    int s1 = 0, s2 = 0;
    for(int j = 1,t = cnt;j <= M && t > 0; j ++) 
        for(int i = 1;i <= N && t > 0; i ++,t --) s1 += a[i][j] == '*';   
    s2 = cnt - s1;

    auto encode = [&](int x,int y) {return (y - 1) * N + x;};
    for(int i = 0;i < Q;i ++) {
        int x,y; cin >> x >> y;
        if(a[x][y] == '.') {
            if(a[cnt % N + 1][cnt / N + 1] == '.') s2 ++;
            a[x][y] = '*';     
            cnt ++;
            if(encode(x,y) <= cnt) s2 --;
        }else {
            if(encode(x,y) <= cnt) s2 ++;
            a[x][y] = '.';
            cnt --;
            if(a[cnt % N + 1][cnt / N + 1] == '.') s2 --;
        }
        cout << s2 << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    //int T;cin>>T;
    //while(T--)
        solve();

    return 0;
}

G

题意

给一个有向无环图，要求对每个点至少删除一条入边一条出边（如果没有就不删）。

定义点集 \(s\) ，其中任意两点 \(u,v\) 满足从 \(u\) 到 \(v\) 或者从 \(v\) 到 \(u\) 。求 \(max(|s|)\)

思路

找DAG上最长链。DP

对有向无环图，先拓扑排序。因为要满足任意两点单向可达， \(s\) 中的点一定构成一条链。

因为如果一个点出现分叉，那么从这个点一定只能到这条链的前半段或者后半段（如果都可以到就说明成环了）

所以这个问题就变成了在 DAG上找一条最长链。

我们定义 \(f[i]\) 表示从 \(i\) 开始的最长链。

考虑 \(i\) 的出度\(out_i\) ，如果 \(out_i <= 1\) 这条链就会断掉，这个点就是链的终点。

考虑 \(i\) 的出边 \(v\) 。如果 \(v\) 的出度大于 \(1\) ，就可以保证保留一条边和 \(i\) 连通。转移为 $ f[i] = max(f[i],f[v] + 1)$ 。

然后这个题就做完了。

#include<bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define lowbit(x) x&-x
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int N,M; cin >> N >> M;
    vector<vector<int>> adj(N + 1);
    vector<int> in(N + 1),out(N + 1);
    for(int i = 0;i < M;i ++) {
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        out[u] ++, in[v] ++;
    }

    vector<int> f(N + 1);
    function<void(int)> dfs = [&](int u) {
        if(f[u]) return;
        f[u] = 1;
        if(out[u] <= 1) return;
        
        for(auto v : adj[u]) {
            dfs(v);
            if(in[v] >= 2) f[u] = max(f[u],1 + f[v]);
        }
    };
    for(int i = 1;i <= N;i ++) if(!f[i]) dfs(i);

    cout << *max_element(f.begin(),f.end()) << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    //int T;cin>>T;
    //while(T--)
        solve();

    return 0;
}

这篇关于Codeforces Round #786 (Div. 3)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！