当前位置：首页 > news >正文

【题解】Codeforces Round 1046 (Div. 1) A~C

news 2025/9/4 8:14:44

A. Against the Difference

1.dp定义

采用block转移不影响这次转移之前的情况，显然可以dp。
定义dp[i]表示考虑前i个位置的最大答案。

2.dp转移

开vector记录不同大小的数字在数组中位置的下标，贪心地考虑，对于数字k，一定从倒数第k-1个数字下标转移过来最优
a[i] == 1 时需要特判，答案直接加1。

代码

#include<bits/stdc++.h>
#define int long longusing namespace std;void solve()
{int n;cin >> n;vector<int> a(n+1);for(int i = 1; i <= n; i ++){cin >> a[i];}vector<int> dp(n+1);vector<vector<int>> cnt(n+1);for(int i = 1; i <= n; i ++){dp[i] = max(dp[i],dp[i-1]);if(a[i] == 1){dp[i] = max(dp[i],dp[i-1] + 1);}else{if(cnt[a[i]].size() >= a[i] - 1){int p = cnt[a[i]].size() - (a[i] - 1);dp[i] = max(dp[i],dp[cnt[a[i]][p]-1] + a[i]);}cnt[a[i]].push_back(i);}}cout << dp[n] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while(t --){solve();}
}

B.For the Champion

1. $n = 1$ 时的做法

首先将机器人移到该点的右上方。由于机器人横纵坐标均大于该点，返回值为机器人新坐标 - 该点坐标，没有绝对值，直接得出机器人坐标 X + Y的值。
首先将机器人移到该点的右下方。由于机器人横纵坐标均小于该点，返回值为该点坐标 - 机器人坐标，没有绝对值，直接得出机器人坐标 -X + Y的值。

解二元一次方程组，得X、Y。

2. $n = 100$ 的做法

通过移动1e9这种大数字，使得离机器人最近的一定是最右上/右下的点，从而转化回 n = 1的情况。

PS：只要四个角上的边缘点都可以，不一定要右上右下。

代码

#include<bits/stdc++.h>
#define int long longusing namespace std;void solve(){int n;cin >> n;vector<pair<int,int>> p(n+1);for(int i = 1; i <= n; i ++){cin >> p[i].first >> p[i].second;}int ret;cout << "? L 1000000000" << endl;cin >> ret;cout << "? L 1000000000" << endl;cin >> ret;cout << "? D 1000000000" << endl;cin >> ret;cout << "? D 1000000000" << endl;int ret1,ret2;cin >> ret1;cout << "? R 1000000000" << endl;cin >> ret;cout << "? R 1000000000" << endl;cin >> ret;cout << "? R 1000000000" << endl;cin >> ret;cout << "? R 1000000000" << endl;cin >> ret2;int mi1 = 1e18,mi2 = 1e18;for(int i = 1; i <= n; i ++){mi1 = min(mi1,p[i].first + p[i].second);mi2 = min(mi2,-p[i].first + p[i].second);}int k1 = mi1 - ret1 + 4e9,k2 = ret2 - 4e9 - mi2;cout << "! " << (k1 + k2)/ 2 << ' ' << (k1-k2)/2 << endl;}signed main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while(t --){solve();}
}

C. By the Assignment

前置知识：边双连通分量

1.观察

不构成环的点，不影响答案。
构成环的点，在环内任取几点观察，得出，环上的点至少相同。

2.进一步观察

如果在长度为奇数环上，所有数必须为0.
如果在长度为偶数的环上，所有数必须相同。

3.tarjan求边双连通分量（EBCC)

4.判断连通分量内是否有奇数环

可以在分量内再次dfs，记录每个点到开始点的距离，如果出现了两个相连的点距离奇偶性相同，就有奇数环。

代码

#include<bits/stdc++.h>
#define int long longusing namespace std;
const int mod = 998244353;
struct EBCC{int n;vector<vector<int>> &v;vector<int> dfn,low,stk,bel;int cur,cnt;EBCC (vector<vector<int>> &g) : v(g){n = g.size() - 1;dfn.resize(n + 1);low.resize(n + 1);bel.resize(n + 1);cur = cnt = 0;}void tarjan(int u,int p){low[u] = dfn[u] = ++ cur;stk.push_back(u);bool flag = false;for(int i : v[u]){if(i == p && !flag){flag = 1;continue;}if(!dfn[i]){tarjan(i,u);low[u] = min(low[u],low[i]);}else low[u] = min(low[u],dfn[i]);}if(dfn[u] == low[u]){cnt ++;int x;do{x = stk.back();bel[x] = cnt;stk.pop_back();}while(x != u);}}void work(){for(int i = 1; i <= n; i ++){if(!dfn[i]){tarjan(i,-1);}}}
};void solve(){int n,m,vv;cin >> n >> m >> vv;vector<int> a(n+1);for(int i = 1; i <= n; i ++){cin >> a[i];}vector<vector<int>> v(n+1);for(int i = 1; i <= m; i ++){int x,y;cin >> x >> y;v[x].push_back(y),v[y].push_back(x);}EBCC b(v);b.work();vector<int> st(n+1),dist(n+1);int op1 = 2,op2 = 2,num = -1;auto dfs = [&](auto &&self,int u,int bcc,int dis) -> void{if(a[u] != -1){if(num == -1){num = a[u];op2 = 1;}else if(num != a[u]){op2 = 0;}}st[u] = 1;dist[u] = dis;for(int i : v[u]){if(b.bel[i] != bcc) continue;if(!st[i]){self(self,i,bcc,dis + 1);}else{if(dis % 2 == dist[i] % 2){op1 = 0;}}}};long long ans = 1;for(int i = 1; i <= n; i ++){if(!st[i]){op1 = 2,op2 = 2,num = -1;dfs(dfs,i,b.bel[i],0);if(op2 == 0){ans *= 0;break;}else if(op2 == 1){if(num == 0){ans *= 1;}else{if(op1 == 0){ans *= 0;break;}else{ans *= 1;}}}else{if(op1 == 0){ans *= 1;}else ans *= vv;}ans %= mod;}}cout << ans << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while(t --){solve();}
}