训练 CF 1700分 题解

$CodeForces264B$ $GoodSequences$

思路： 质因数分解后，求当前数的质因数种出现的最大次数，然后当前数的所有质因数赋值当前的最大，进行$dp$即可，时间复杂度 $O(nlogn)$

/* * @Author: vain * @Date: 2020 * @LastEditTime: 2020-10-06 13:40:49 * @LastEditors: sueRimn * @Description: 学不会 dp 的 fw * @FilePath: \main\demo.cpp */ //#include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; ll in[maxn], cnt, head[maxn]; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; double Max(double a, double b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } int lowbit(int x) { return (x) & (-x); } map<int, int> mp; ll ksm(ll a, ll b) { ll res = 1; for (; b;) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } vector<int> f; int a[maxn]; int dp[maxn]; int solve(int x) { int k = x, res = 0; for (int i = 2; i * i <= x; i++) { bool fla = true; while (x % i == 0) { if (fla) dp[i]++, fla = false; x /= i; res = max(dp[i], res); } } if (x > 1) dp[x]++, res = max(dp[x], res); x = k; for (int i = 2; i * i <= x; i++) { bool fla = true; while (x % i == 0) { x /= i; if (fla) fla = false, dp[i] = res; } } if (x > 1) dp[x] = res; return res; } int main() { int n; read(n); for (int i = 1; i <= n; i++) { read(a[i]); } int ans = 1; for (int j = 1; j <= n; j++) { ans = max(ans, solve(a[j])); } //cout << endl; printf("%d\n", ans); }

$CodeForces246D$ $ColorfulGraph$

思路： 分组，染色，求贡献

/* * @Author: vain * @Date: 2020 * @LastEditTime: 2020-10-06 19:56:23 * @LastEditors: sueRimn * @Description: 学不会 dp 的 fw * @FilePath: \main\demo.cpp */ #include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; int cnt, head[maxn], pos[maxn]; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; double Max(double a, double b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } int lowbit(int x) { return (x) & (-x); } map<int, int> vis; //unordered_map<int,int>vis; ll ksm(ll a, ll b) { ll res = 1; for (; b;) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } struct node { int v, nex; } edge[maxn << 1]; void add(int u, int v) { edge[cnt].v = v, edge[cnt].nex = head[u]; head[u] = cnt++; } vector<int> vec[maxn], f; int main() { int n, m, color = 100000; read(n), read(m); for (int i = 1; i <= n; i++) { head[i] = -1; read(pos[i]); f.push_back(pos[i]); vec[pos[i]].push_back(i); if (pos[i] < color) color = pos[i]; } sort(f.begin(), f.end()); f.erase(unique(f.begin(), f.end()), f.end()); for (int i = 1; i <= m; i++) { int u, v; read(u), read(v); add(u, v), add(v, u); } int ans = 0, k = f.size(); for (int i = 0; i < k; i++) { int maxx = 0; vis.clear(); for (int j = 0; j < vec[f[i]].size(); j++) { int p = vec[f[i]][j]; for (int u = head[p]; ~u; u = edge[u].nex) { int v = edge[u].v; if ((pos[v] != pos[p]) && (!vis[pos[v]])) maxx++, vis[pos[v]] = 1; } if (maxx > ans) color = pos[p], ans = maxx; else if (maxx == ans && pos[p] < color) color = pos[p]; } } printf("%d\n", color); }

$CodeForces369C$ $ValeraandElections$

思路： 枚举叶节点，边权转化，找最先出现的坏点 数据水了，被俩队友hack了，最坏时间复杂度是$O(N^2)$，但记录一下

/* * @Author: vain * @Date: 2020 * @LastEditTime: 2020-10-11 12:08:33 * @LastEditors: sueRimn * @Description: 学不会 dp 的 fw * @FilePath: \main\demo.cpp */ #include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; double Max(double a, double b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } int lowbit(int x) { return (x) & (-x); } //map<int, int> vis; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res % mod; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } struct node { int v, pos, nex, w; } edge[maxn << 1]; int cnt, head[maxn], pre[maxn], vis[maxn]; int dwn[maxn], in[maxn], color[maxn]; vector<int> f; void add(int u, int v, int w) { edge[cnt].v = v, edge[cnt].w = w; edge[cnt].nex = head[u], head[u] = cnt++; } void dfs(int u, int fa) { pre[u] = fa; for (int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].v; if (v != fa) { if (edge[i].w == 2) vis[v] = 1; dfs(v, u); } } } int main() { int n; read(n); for (int i = 1; i <= n; i++) head[i] = -1; for (int i = 1; i < n; i++) { int u, v, w; read(u), read(v), read(w); in[v]++, in[u]++; add(u, v, w), add(v, u, w); } dfs(1, 0); for (int i = 2; i <= n; i++) { if (in[i] == 1) { f.push_back(i); } } int m = f.size(); for (int i = 0; i < m; i++) { int k = f[i]; bool fla = false; while (k != 1) { if (color[k]) break; if (fla) color[k] = 1; if (vis[k]) { dwn[k]=1; fla = true; } k = pre[k]; } } f.clear(); int ans = 0; for (int i = 1; i <= n; i++) { if (dwn[i] == 1 && (!color[i])) ans++, f.push_back(i); } printf("%d\n", ans); bool fla=false; for (int i = 0; i < ans; i++) { fla=true; printf("%d ", f[i]); } if(fla) puts(""); }

$CodeForces815A$ $KarenandGame$ 思路：考虑两种状况 ，$n>m$和$n<=m$

参考代码

#include<iostream> #include<vector> #include<stack> #include<queue> #include<map> #include<unordered_map> #include<unordered_set> #include<set> #include<cstdlib> #include<cmath> #include<cstdio> #include<cstring> #include<set> using namespace std; typedef long long ll; const int maxn=2e5+5; const int N=5e2+5; int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } ll ksm(ll a,ll b) { ll res=1; while(b) { if(b&1) res*=a; b>>=1,a=a*a; } return res; } int mp[105][105],sum=0; int ans[3][105]; int dp[105][105]; int dx[105][105]; void solve1(int n,int m)//先算行 { for(int i=1; i<=n; i++) { int minx=505; for(int j=1; j<=m; j++) minx=min(minx,mp[i][j]); if(minx) ans[0][i]=minx,sum+=minx; dp[i][1]-=minx,dp[i][m+1]+=minx; for(int j=1; j<=m; j++) mp[i][j]=dp[i][j]+mp[i][j-1]; } } void solve2(int n,int m)//先算列 { for(int i=1; i<=m; i++) { int minx=505; for(int j=1; j<=n; j++) minx=min(minx,mp[j][i]); if(minx) ans[1][i]=minx,sum+=minx; dx[1][i]-=minx,dx[n+1][i]+=minx; for(int j=1; j<=n; j++) mp[j][i]=dx[j][i]+mp[j-1][i]; } } void init1(int n,int m) { for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { dx[j][i]=mp[j][i]-mp[j-1][i]; } } } void init2(int n,int m) { for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { dp[i][j]=mp[i][j]-mp[i][j-1]; } } } int main() { int n,m; read(n),read(m); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { read(mp[i][j]); } } if(n>m) { init1(n,m); solve2(n,m); init2(n,m); solve1(n,m); } else { init2(n,m); solve1(n,m); init1(n,m); solve2(n,m); } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(mp[i][j]) { puts("-1"); return 0; } } } printf("%d\n",sum); for(int i=1; i<=n; i++) { while(ans[0][i]--) { printf("row %d\n",i); } } for(int i=1; i<=m; i++) { while(ans[1][i]--) { printf("col %d\n",i); } } }

$CodeForces711C$ $ColoringTrees$ 思路 暴力转移dp，用一个三维的$dp$，记录第$i$颗树，使用第$j$种颜色，分了$k$组的最小贡献，时间复杂度$O(N^3)$ 参考代码

#include<iostream> #include<vector> #include<stack> #include<queue> #include<map> #include<unordered_map> #include<unordered_set> #include<set> #include<cstdlib> #include<cmath> #include<cstdio> #include<cstring> #include<set> using namespace std; typedef long long ll; const int maxn=2e5+5; const int N=5e2+5; int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } ll ksm(ll a,ll b) { ll res=1; while(b) { if(b&1) res*=a; b>>=1,a=a*a; } return res; } ll dp[105][105][105]; int cost[105][105]; int color[105],reg[105][105]; int main() { int n,m,k; read(n),read(m),read(k); for(int i=1; i<=n; i++) read(color[i]); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { read(cost[i][j]); } } for(int i=0; i<=n; i++) { for(int j=0; j<=m; j++) { for(int l=0; l<=k; l++) { dp[i][j][l]=100000000000000000; } } } if(!color[1]) { for(int i=1; i<=m; i++) { dp[1][i][1]=cost[1][i]; } } else { dp[1][color[1]][1]=0; } for(int i=2; i<=n; i++) { if(!color[i]) { for(int j=1; j<=m; j++) { for(int a=1; a<=m; a++) { for(int b=1; b<=k; b++) { if(a!=j) dp[i][j][b]=min(dp[i-1][a][b-1]+cost[i][j],dp[i][j][b]); else dp[i][j][b]=min(dp[i-1][a][b]+cost[i][j],dp[i][j][b]); } } } } else { int j=color[i]; for(int a=1; a<=m; a++) { for(int b=1; b<=k; b++) { if(color[i]!=a) dp[i][j][b]=min(dp[i-1][a][b-1],dp[i][j][b]); else dp[i][j][b]=min(dp[i-1][a][b],dp[i][j][b]); } } } } ll minx=100000000000000000; for(int i=1;i<=m;i++) { minx=min(dp[n][i][k],minx); } if(minx==100000000000000000ll) puts("-1"); else printf("%lld\n",minx); }

$CodeForces409H$ $A+BStrikesBack$ 思路：没有 愚人节的一道题目，然而并没有什么思维上的考察

参考代码

#include<bits/stdc++.h> using namespace std; int main() { int a,b; scanf("%d %d",&a,&b); printf("%d\n",a+b); }

$CodeForces494A$ $Treasure$ 思路 模拟栈，先将可以匹配的下标匹配，对剩下的下标进行操作即可 参考代码

/* * @Author: vain * @Date: 2020 * @LastEditTime: 2020-10-11 09:42:28 * @LastEditors: sueRimn * @Description: 学不会 dp 的 fw * @FilePath: \main\demo.cpp */ #include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; int cnt, head[maxn], pos[maxn]; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; double Max(double a, double b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } int lowbit(int x) { return (x) & (-x); } //map<int, int> vis; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res % mod; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } char s[maxn]; int sta[maxn], sum[maxn], ans[maxn]; int main() { scanf("%s", s + 1); int n = strlen(s + 1); int top = 0; for (int i = 1; i <= n; i++) { if (s[sta[top]] == '(' && s[i] == ')') top--; else if (s[i] != '#') sta[++top] = i; } for (int i = 1; i <= n; i++) { if (s[i] == '#') sta[++top] = i; } sort(sta + 1, sta + 1 + top); bool fla = true; for (int i = 1; i <= top; i++) { if (s[sta[i]] == ')') { fla = false; break; } if (s[sta[i]] == '(') sum[i] = sum[i - 1] + 1; else sum[i] = sum[i - 1]; } int res = sum[top]; int x = 0; for (int i = 1; i <= top; i++) { sum[i] -= x; if (s[sta[i]] == '#' && sum[i]) ans[sta[i]] = 1, x++, sum[i]--, res--; else if (s[sta[i]] == '#' && (!sum[i])) { fla = false; break; } } for (int i = top; i >= 1; i--) { if (s[sta[i]] == '(') { fla = false; break; } else { break; } } if (fla) { int x = 0; for (int i = top; i >= top; i--) { if (s[sta[i]] == '#') { ans[sta[i]] += res; break; } } for (int i = 1; i <= top; i++) { if (s[sta[i]] == '#') printf("%d\n", ans[sta[i]]); } } else { puts("-1"); } }

$CodeForces977F$ $ConsecutiveSubsequence$ 思路 用$map$进行离散化$dp$ 参考代码

/* * @Author: vain * @Date: 2020 * @LastEditTime: 2020-10-12 21:26:12 * @LastEditors: sueRimn * @Description: 学不会 dp 的 fw * @FilePath: \main\demo.cpp */ #include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 2e5 + 20; const int mod = 998244353; int cnt, head[maxn], pos[maxn]; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; double Max(double a, double b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } int lowbit(int x) { return (x) & (-x); } //map<int, int> vis; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res % mod; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } int sta[maxn], pre[maxn]; vector<int> f; map<int, int> dp; int main() { int n; read(n); for (int i = 1; i <= n; i++) read(sta[i]), pre[i] = -1; for (int i = 1; i <= n; i++) { dp[sta[i]] = max(dp[sta[i]],dp[sta[i] - 1] + 1); } int ans = 0, k; for (int i = 1; i <= n; i++) { if (dp[sta[i]] > ans) ans = dp[sta[i]], k = i; } printf("%d\n", ans); int x = sta[k]; for (int i = n; i >= 1; i--) { if (sta[i] == x) { f.push_back(i); x--; } } sort(f.begin(), f.end()); for (int i = 0; i < f.size(); i++) printf("%d ", f[i]); puts(""); }

CodeForces 625A Guest From the Past

$CodeForces279C$ $Ladder$ 思路 差分构造+前缀和，当然有更简单的写法，我没有想到，太菜了

参考代码

#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> #include <unordered_map> #include <unordered_set> using namespace std; typedef long long ll; #define ll long long //pedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; int cnt, head[maxn], pos[maxn]; //pedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res % mod; } void read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; } int d[maxn],dp[maxn],a[maxn],sam[maxn]; int main() { int n,q; read(n),read(q); for(int i=1; i<=n; i++) { read(a[i]); if(a[i]==a[i-1]) sam[i]=sam[i-1]+1; if(a[i]>=a[i-1]) d[i]=0; else d[i]=1; } dp[0]=0; for(int i=1; i<=n; i++) dp[i]=dp[i-1]+d[i]; while(q--) { int l,r; read(l),read(r); if(dp[r]-dp[l]==0) puts("Yes"); else if(dp[r]-dp[l]==r-l) puts("Yes"); else { int x=dp[r]-dp[l]; r=r-sam[r]; if(dp[r]-dp[r-x]==x) puts("Yes"); else puts("No"); } } return 0; }

$CodeForces476C$ $DreamoonandSums$ 思路 数学题，推导公式 参考代码

/* * @Author: vain * @Date: 2020 * @LastEditTime: 2020-10-11 16:49:16 * @LastEditors: sueRimn * @Description: 学不会 dp 的 fw * @FilePath: \main\demo.cpp */ #include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 1000000007; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; double Max(double a, double b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } int lowbit(int x) { return (x) & (-x); } //map<int, int> vis; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res % mod; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } struct node { int v, pos, nex, w; } edge[maxn << 1]; int cnt, head[maxn], pre[maxn], vis[maxn]; int dwn[maxn], in[maxn], color[maxn]; vector<int> f; void add(int u, int v, int w) { edge[cnt].v = v, edge[cnt].w = w; edge[cnt].nex = head[u], head[u] = cnt++; } void dfs(int u, int fa) { pre[u] = fa; for (int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].v; if (v != fa) { if (edge[i].w == 2) vis[v] = 1; dfs(v, u); } } } int main() { ll a, b; scanf("%lld %lld", &a, &b); ll ans = 0, res = (b * (b - 1) / 2) % mod; for (int i = 1; i <= a; i++) { ans = (ans + res * (i * b % mod + 1) % mod) % mod; } printf("%lld\n", ans); }

CodeForces 833A The Meaningless Game $NewYearandthePermutationConcatenation$ 思路 打表找规律 参考代码

#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res % mod; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } int a[10]; vector<int>f; ll dp[1000005]; int main() { int n; ll sum=6; dp[1]=1,dp[2]=2,dp[3]=9; for(int i=4;i<=1000000;i++) { sum=(sum*i)%mod; dp[i]=((((dp[i-1]-1)%mod)*i%mod)+sum)%mod; } read(n); printf("%lld\n",dp[n]); return 0; }

$CodeForces584C$ $MarinaandVasya$ 思路 构造相同字符，模拟 参考代码

#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> #include <unordered_map> #include <unordered_set> using namespace std; typedef long long ll; #define ll long long const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; //pedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res % mod; } void read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; } vector<int>samq,difq; char s[maxn]; int check(char *s,string s1,string s2) { int n=s1.size(),ans=0; for(int i=0; i<n; i++) { if(s[i]!=s1[i]&&s[i]!=s2[i]) ans++; } return ans; } int main() { int n,t,ct; read(n),read(t); t=n-t; ct=t; string s1,s2; cin>>s1>>s2; for(int i=0; i<n; i++) { if(s1[i]==s2[i]) samq.push_back(i); else difq.push_back(i); } if(t==samq.size()) { for(int i=0; i<difq.size(); i++) { char c='a'; int k=0; while(s1[difq[i]]==c||s2[difq[i]]==c) { c=char(c+(++k)%26); } s[difq[i]]=c; } for(int i=0; i<samq.size(); i++) { s[samq[i]]=s1[samq[i]]; } printf("%s\n",s); } if(t<samq.size()) { for(int i=0; i<difq.size(); i++) { char c='a'; int k=0; while(s1[difq[i]]==c||s2[difq[i]]==c) { c=char(c+(++k)%26); } s[difq[i]]=c; } for(int i=0; i<samq.size(); i++) { if(t) { s[samq[i]]=s1[samq[i]]; --t; } else { char c='a'; int k=0; while(s1[samq[i]]==c) { c=char(c+(++k)%26); } s[samq[i]]=c; } } printf("%s\n",s); } if(t>samq.size()) { t-=samq.size(); int t1=t,t2=t; int ok=0; for(int i=0; i<difq.size(); i++) { char c='a'; int k=0; if(t1||t2) { if(ok%2==0&&t1) { c=s1[difq[i]]; t1--; } else if(t2) { c=s2[difq[i]]; t2--; } ok++; } else { while(s1[difq[i]]==c||s2[difq[i]]==c) { c=char(c+((++k)%26)); } } s[difq[i]]=c; } for(int i=0; i<samq.size(); i++) { s[samq[i]]=s1[samq[i]]; } if(t1||t2) puts("-1"); else printf("%s\n",s); } return 0; }

$CodeForces598D$ $IgorIntheMuseum$ 思路 预处理连通块贡献 参考代码

#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> #include <unordered_map> using namespace std; typedef long long ll; #define ll long long const int N = 1000 + 20; const int maxn = 1e5 + 5; const int mod = 998244353; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; ll ksm(ll a, ll b) { ll res = 1; for (; b;) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } struct node { int x,y; } p; vector<node>f[maxn*10]; int dir[4][2]= {1,0,0,1,0,-1,-1,0}; char mp[N][N]; int vis[N][N]; int ans[100005][2],corrt[1000005]; int ck[N][N]; int sum=0,n,m; void check(int x,int y) { if(x-1>0&&mp[x-1][y]=='*') sum++; if(y-1>0&&mp[x][y-1]=='*') sum++; if(x+1<=n&&mp[x+1][y]=='*') sum++; if(y+1<=m&&mp[x][y+1]=='*') sum++; } void dfs(int x,int y,int block) { if(!vis[x][y]) { node p; p.x=x,p.y=y; f[block].push_back(p); check(x,y); vis[x][y]=1; } else { return; } for(int i=0; i<4; i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(xx<0||yy<0||xx>n||yy>m||mp[xx][yy]=='*'||vis[xx][yy]) continue; dfs(xx,yy,block); } } int main() { int k; read(n),read(m),read(k); for(int i=1; i<=n; i++) scanf("%s",mp[i]+1); for(int i=1; i<=k; i++) scanf("%d %d",&ans[i][0],&ans[i][1]); int block=0; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if((!vis[i][j])&&mp[i][j]=='.') { dfs(i,j,++block); corrt[block]=sum; sum=0; } } } for(int i=1;i<=block;i++) { int l=f[i].size(); for(int j=0;j<l;j++) { ck[f[i][j].x][f[i][j].y]=corrt[i]; } } for(int i=1;i<=k;i++) { printf("%d\n",ck[ans[i][0]][ans[i][1]]); } return 0; }