Codeforces Edu Round 61 A-C + F
A. Regular Bracket Sequence显然,"(())"不影响结果它是自我匹配的,可以把所有的((()和()))都放在左边/右边,这样只要检查它们的数目就行,还有个坑点,就是如果()()多于一,需要给左右两边一个负担,必须小于它们的数量才行。 #include <cstdio> #include <iostream> using namespace std; int c1,c2,c3,c4; int main(){ scanf("%d%d%d%d",&c1,&c2,&c3,&c4); if(c1 == c4 && c4 >= min(c3,1)) puts("1"); else puts("0"); return 0; } B. Discounts模拟,从小到大排好序后,答案 (=) 总数 - (a[n - q_i + 1])。 #include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int N = 300010; typedef long long LL; int n,m,a[N],q; LL sum = 0; int main(){ scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",a + i),sum += a[i]; } sort(a + 1,a + 1 + n); scanf("%d",&m); for(int i = 1; i <= m; i++){ scanf("%d",&q); printf("%lldn",sum - a[n - q + 1]); } return 0; } C. Painting the Fence考虑到(q <= 5000),用前缀和维护每个位置都有几个人刷,然后预处理([l,r])这段有多少(1)(他不刷就没人刷)和(2)(安排掉他俩就没人刷),用(O(q ^ 2))的复杂度暴力枚举两个人分别是谁,然后(O(1))找即可。 #include <cstdio> #include <iostream> #include <cmath> #include <algorithm> using namespace std; typedef pair<int,int> PII; const int N = 5010; int n,sum[N],c[N],c2[N],tot = 0,ans = -1; PII a[N]; int main(){ scanf("%d%d",&n,&m); for(int i = 1; i <= m; i++){ scanf("%d%d",&a[i].first,&a[i].second); } sort(a + 1,a + 1 + m); for(int i = 1; i <= m; i++){ sum[a[i].first]++,sum[a[i].second + 1]--; } for(int i = 1; i <= n; i++) { sum[i] += sum[i - 1]; c[i] = c[i - 1] + (sum[i] == 1); c2[i] = c2[i - 1] + (sum[i] == 2); tot += (sum[i] > 0); } for(int i = 1; i < m; i++){ for(int j = i + 1; j <= m; j++){ int cnt = tot; int L = a[i].first,R = a[i].second; int L1 = a[j].first,R1 = a[j].second; if(L1 <= R) { cnt -= c[L1 - 1] - c[L - 1]; cnt -= c[max(R,R1)] - c[min(R,R1)]; cnt -= c2[min(R,R1)] - c2[L1 - 1]; }else{ cnt -= c[R] - c[L - 1]; cnt -= c[R1] - c[L1 - 1]; } ans = max(ans,cnt); } } printf("%dn",ans); return 0; } F. Clear the String区间(dp)。 设(f[i][j]) 为合并([i,j])区间的最小花费,对于任何一个(f[i][j]),有三种决策:
(f[i + 1][k - 1] + f[k][j] + (s[k] != s[i])) 等于是把([i + 1,k - 1])先合并起来,然后(i)字符就会贴到(k)一起,然后这两个字符一样,可以视作一个字符,每次修改最坏是用(k)为左边界,(i)字符作为附庸不用计算花费
想状态的时候我也会有疑惑,为什么只用找开头和结尾跟中间匹配呢?重复,每次处理区间时,(l + 1、l + 2...)已经找过匹配点了... 后来发现只需要处理用开头字符一种情况,因为两种状态转移上重复了,每次找(k)的过程中也相当于(k)去找(i),在这之前想到于已经匹配过([l + 1,r],[l + 2,r]...[l + n,r]),这样的匹配方式是可逆的,先后反复是相同的,即使此时的(l + n)左边还没处理,但是每次处理相当于一个包围的形式,可以不重不漏地继承。所以可以不需用步骤(3),但是蒟蒻的我肯定想不到啦... 顺便,注意初始化问题,对于(f[i][j] (i > j)) 花费是(0),当然如果边界写的精准了这种状态不会用到。 #include <cstdio> #include <iostream> #include <cstring> #include <cmath> using namespace std; const int N = 510; int n,f[N][N]; char s[N]; int main(){ scanf("%d%s",s + 1); for(int i = 1; i <= n; i++) f[i][i] = 1; for(int l = 2; l <= n; l++){ for(int i = 1,j; (j = i + l - 1) <= n; i++){ f[i][j] = min(f[i + 1][j],f[i][j - 1]) + 1; for(int k = i; k <= j - 2; k++){ f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j - 1] + (s[k] != s[j])); } for(int k = i + 2; k <= j; k++){ f[i][j] = min(f[i][j],f[i + 1][k - 1] + f[k][j] + (s[k] != s[i])); } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) printf("%d ",f[i][j]); puts(""); } printf("%dn",f[1][n]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |