1004 Tokitsukaze and Multiple
队友半小时内A了这题,强的一匹!
给一列数,每次可以把相邻的两个数合并成一个大数(比如12,74合并成86),给一个数字p,问通过这样的操作,最多能使这数列中多少数是p的倍数
举例:p = 3, 数列为 2, 1, 3, 2, 1
该数列可以变成3,3,3, 答案就是3
这题我做的话半小时应该不能做出来
可以用贪心的方法线性做,从左往右扫,每当判断出能合并出符合要求的数时就合并
这个贪心和那个关于区间的贪心模板题很像
事实上,这题假设我们已知所有能合成出符合要求的数的区间,问题就变成在这些区间里找出最多的互不重合的区间,那就是把这些区间按右端点排序
队友这题写的代码并不是很美观,但还是很强的
赛后我自己也做了一遍,下面的是我的代码
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int MAXN = 1e5+7; int a[MAXN], last[MAXN]; int main() { int T; cin >> T; int n,p,x; while(T--){ cin>>n>>p; int su = 0, pos = 1, ans = 0; for(int i = 1;i < p;i++) last[i] = 0; for(int i = 1;i <= n;i++){ scanf("%d",&x); su += x; su %= p; if(su == 0 || last[su] >= pos){ pos = i + 1; su = 0; ans ++; } last[su] = i; } cout<<ans<<endl; } return 0; }
1005 Little W and Contest
这里就不叙述题意了
这题队友写的,队友写的很整齐,很美观
但是wa了很多发,很惨
比赛到后期的时候,队友叫我看这题,给了我题意和他的做法,我觉得他的做法没问题,代码也写的很好,查不出什么错,我找到一个地方可能有问题,就是一个取模的地方他是+MOD 再%MOD,我感觉+2*MOD再%MOD会更保险,然后队友改了下,还真就过了,队友气死了....
我之后才学到一个更保险的办法是先%MOD,再+MOD,再%MOD
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 1e5 + 7; const int MOD = 1e9 + 7; int fac[MAXN], inv[MAXN]; inline void Pre(int n) { fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD; inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; inv[0] = 1; for (int i = 1; i <= n; i++) inv[i] = inv[i] * inv[i - 1] % MOD; } inline int C(int n, int m) { if (m > n) return 0; return fac[n] * inv[m] % MOD * inv[n - m] % MOD; } // 计算组合数 inline int Pow(int a, int b) { int ret = 1; for (; b; b >>= 1, a = a * a % MOD) if (b & 1) ret = ret * a % MOD; return ret; } // 快速幂 int T; int n; int pts[MAXN]; int u, v; int ans; int tmp1, tmp2; struct DSU { int parent[MAXN]; int n; // Nums of Nodes int cnt; // Count Strongly Connected Components int sum1[MAXN]; int sum2[MAXN]; int rank[MAXN]; void init_parent(int n) { this -> n = n; cnt = 0; for (int i = 1; i <= n; ++i) { parent[i] = i; if (pts[i] == 1) { sum1[i] = 1; sum2[i] = 0; } else { sum1[i] = 0; sum2[i] = 1; } rank[i] = 0; } } int find_parent(int x) { if (parent[x] == x) return x; else parent[x] = find_parent(parent[x]); return parent[x]; } bool check_unicom(int x, int y) { return find_parent(x) == find_parent(y); } void merge(int x, int y) { x = find_parent(x); y = find_parent(y); if (x != y) { parent[x] = y; sum1[y] += sum1[x]; sum2[y] += sum2[x]; cnt++; } } int getsum1(int i) { return sum1[find_parent(i)]; } int getsum2(int i) { return sum2[find_parent(i)]; } }dsu; int32_t main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); Pre(100005); cin >> T; while (T--) { cin >> n; ans = 0; tmp1 = tmp2 = 0; for (int i = 1; i <= n; ++i) { cin >> pts[i]; if (pts[i] == 1) { tmp1++; } if (pts[i] == 2) { tmp2++; } } dsu.init_parent(n); ans = (C(tmp2, 2) % MOD * tmp1 % MOD) % MOD + C(tmp2, 3) % MOD; ans %= MOD; cout << ans << endl; for (int i = 1; i <= n - 1; ++i) { cin >> u >> v; if (!dsu.check_unicom(u, v)) { int usum1 = dsu.getsum1(u); int usum2 = dsu.getsum2(u); int vsum1 = dsu.getsum1(v); int vsum2 = dsu.getsum2(v); // cout << usum1 << " " << usum2 << " " << vsum1 << " " << vsum2 << endl; int les2 = tmp2 - usum2 - vsum2; int les1 = tmp1 - usum1 - vsum1; // cout << les1 << " " << les2 << endl; ans = ans + 2 * MOD - les2 * ((usum2 * vsum1) % MOD + (usum1 * vsum2) % MOD) % MOD - ((les2 + les1) % MOD) * (usum2 * vsum2 % MOD) % MOD ; dsu.merge(u, v); } ans %= MOD; cout << ans << endl; } } return 0; }
队友喜欢把并查集写成结构体,我通常不这样做。
1009 Parentheses Matching
这场的签到题,括号匹配题
括号匹配的栈模拟题我还挺怕的,所以我很早看了这题后就把这题先放了,把这题交给队友解决,自己想其他题,然而我什么也没想出来,队友也一直没做出这题,我还是得来写这题
写了几遍才知道怎么写好
因为是字典序最小,所以:
缺 ( 时,要把最左边的 * 变成 (
缺 ) 时,要把最右边的 * 变成 )
#include<iostream> #include<algorithm> #include<stack> using namespace std; stack<char> st; char ans[100007]; int main() { int t; string s,ans; cin>>t; while(t--){ cin>>s; while(!st.empty()) st.pop(); int cnt1 = 0,cnt2 = 0; bool flag = true; for(int i = 0;s[i];i++){ if(s[i]=='*') cnt1++; else if(s[i]=='(') st.push(s[i]); else{ if(!st.empty()) st.pop(); else { cnt2++; if(cnt2 > cnt1) { flag = false; break; } } } } if(!flag) { printf("No solution!\n"); continue; } else{ int cnt = 0; for(int i = 0;s[i]&&cnt<cnt2;i++){ if(s[i]=='*') { cnt++; s[i] = '('; } } while(!st.empty()) st.pop(); cnt = 0; cnt1 = 0; cnt2 = 0; int len = s.length(); for(int i = len - 1;i >= 0;i--){ if(s[i]==')'){ st.push(s[i]); } else if(s[i]=='*') cnt1++; else{ if(!st.empty()) st.pop(); else { cnt2++; if(cnt2>cnt1){ flag = false; break; } } } } if(!flag) { printf("No solution!\n"); continue; } for(int i = len - 1;i>=0&&cnt<cnt2;i--){ if(s[i]=='*'){ cnt++; s[i] = ')'; } } for(int i = 0;s[i];i++){ if(s[i]!='*') printf("%c",s[i]); } cout<<endl; } } return 0; }
第三场一题都补不来OAO,1006太难了