打div3翻車了

?

A.第一個操作是除二，第二個操作視為兩下操作之后除三，第三個操作視為三下操作之后除五，直接計算貢獻

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 110; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; LL N; int main(){int T; Sca(T);while(T--){Scl(N);int ans = 0;while(!(N % 2)){N /= 2;ans++;}while(!(N % 3)){N /= 3;ans += 2;} while(!(N % 5)){N /= 5;ans += 3;}if(N != 1) ans = -1;Pri(ans);} return 0; } A

?

B.毫無疑問先把所有數模3，整除的直接計入貢獻，余1的找余2的湊一對計入貢獻，最后剩下的三個湊一對計入貢獻

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 1010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int a[maxn]; int b[maxn]; int main(){int T; Sca(T);while(T--){Sca(N);b[0] = b[1] = b[2] = 0;for(int i = 1; i <= N ; i ++){Sca(a[i]);a[i] %= 3;b[a[i]]++;} if(b[1] > b[2]) swap(b[1],b[2]);Pri(b[0] + b[1] + (b[2] - b[1]) / 3);}return 0; } B

?

C.比較套路的一個尋找子序列數量，開6個計數器即可。最后答案就是字符串長度len - 匹配成功的子序列數量 * 6

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 5e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int a[maxn]; const int b[10] = {0,4,8,15,16,23,42}; int dp[maxn]; int main(){Sca(N);for(int i = 1; i <= N ; i ++) Sca(a[i]);dp[0] = INF;for(int i = 1; i <= N ; i ++){for(int j = 1; j <= 6; j ++){if(b[j] == a[i] && dp[j - 1]){dp[j - 1]--;dp[j]++;}}}Pri(N - dp[6] * 6);return 0; } C

?

D.將所有數從大到小排序然后掃描，遇到的當前最大的數如果是素數說明是一個小素數變過來的，否則說明他要變成他最大的因子。

直接遞推即可。

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 3e6 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int a[maxn]; int prime[maxn]; int pos[maxn]; bool isprime[maxn]; void init(){for(int i = 2 ; i <= 2750131; i ++) isprime[i] = 1;int cnt = 0;for(int i = 2 ; i <= 2750131; i ++){if(!isprime[i]) continue;prime[++cnt] = i;pos[i] = cnt;for(int j = i + i; j <= 2750131; j += i) isprime[j] = 0;} } int delnum[maxn]; int find(int x){for(int i = 2; i <= x; i ++){if(!(x % i)) return max(i,x / i);}return 1; } int main(){Sca(N); init();for(int i = 1; i <= N * 2 ; i ++) Sca(a[i]);sort(a + 1,a + 1 + N * 2);for(int i = N * 2; i >= 1; i --){if(delnum[a[i]]){delnum[a[i]]--;continue;}if(isprime[a[i]]){delnum[pos[a[i]]]++;printf("%d ",pos[a[i]]);}else{int n = find(a[i]);delnum[n]++;printf("%d ",a[i ]);}}return 0; } D

?

E.一看是個最小點覆蓋，仔細看看發現沒有要求最小，只是找一個點覆蓋。

對原圖進行一手黑白染色，然后白點集合和黑點集合必定有一個符合答案，取集合元素數量較小的那個集合輸出。

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; struct Edge{int to,next; }edge[maxn * 2]; int head[maxn],tot; int color[maxn]; vector<int>w[2]; void init(){for(int i = 0 ; i <= N ; i ++){color[i] = head[i] = -1;}w[0].clear(); w[1].clear();tot = 0; } void add(int u,int v){edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } void dfs(int t){for(int i = head[t]; ~i ; i = edge[i].next){int v = edge[i].to;if(color[v] != -1) continue;color[v] = 1 ^ color[t];dfs(v);} } int main(){int T; Sca(T);while(T--){Sca2(N,M); init();for(int i = 1; i <= M ; i ++){int u,v; Sca2(u,v);add(u,v); add(v,u);}for(int i = 1; i <= N ; i ++){if(color[i] == -1){color[i] = 0;dfs(i);}}for(int i = 1; i <= N ; i ++) w[color[i]].push_back(i);if(w[0].size() > w[1].size()) swap(w[0],w[1]);Pri(w[0].size());for(int i = 0 ; i < w[0].size(); i ++){printf("%d ",w[0][i]);}puts("");}return 0; } E

?

轉載于:https://www.cnblogs.com/Hugh-Locke/p/11140861.html

總結

以上是生活随笔為你收集整理的codeforces-1176 (div3)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。