A Vasya and Coins
题意：a个1元，b个2元。问最小不能构成的金额数 答案：a * 1 + b * 2 + 1 （特判0）
void solve() { int a, b; cin >> a >> b; int res = 0; if(a == 0) res = 1; else if(b == 0) res = a + 1; else res = a + b * 2 + 1; cout << res << endl; }
B Vlad and Candies
题意：n种糖，每种ai个，每次选择剩余最多的吃（相同则任选）。 并且不能连续吃两个相同的糖，问能否实现，YES or NO 思路：最大和次大差2以上，则按“吃法”会连吃两个最大的。 此题区别于： 《算法竞赛》p166，组合数学的鸽巢原理。 题意：无“吃法”，只要满足不连吃两个相同的糖就行 思路：”隔板法“，最多的糖看成n个隔板，其它糖插入，满足S>=n-1就行，YES （S：除去最多糖的其余糖数） （n：最多糖数）
int a[N]; void solve() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; if(n == 1 && a[0] >= 2) { puts("NO"); return ; } sort(a, a + n); if(a[n - 1] - a[n - 2] >= 2) puts("NO"); else puts("YES"); }
C Get an Even String
题意：删除任意位置字符，使得最后字符“成偶”，问最少步数。 思路：最优转化：最近（最内部）的偶数个会保留不删。（自己的理解hh） 例如：dacaddbb 答案：会选则删d，c，留aaddbb，最有转化即内部aa保留，优于删aa两侧的dd ==详见代码== 样例： 6 aabbdabdccc zyx aaababbb aabbcc oaoaaaoo bmefbmuyw 输出： 3 3 2 0 2 7
void solve() { int cnt[26] = {0}; string s; cin >> s; int n = s.sz, ans = 0; for (int i = 0; i < n; i++) { ++cnt[s[i] - 'a']; if(cnt[s[i] - 'a'] == 2) { ans += 2; memset(cnt, 0, sizeof cnt); } } cout << n - ans << endl; }
D Maximum Product Strikes Back
题意：n个数ai，（-2<=ai<=2），问删前后缀，使得最后剩余数的连积最大。 思路：按0分块隔开，每块考虑偶数or奇数个负数的情况。 对于偶数，当然全留！（统计|2|的个数） 对于奇数，只需看第一个负，倒一个负左右的情况
int n, ans, x, y; int a[N]; // 处理偶数个负数的情况，直接就是统计2的个数 void update(int l, int r) { if(l > r) return ; int res = 0; for (int i = l; i <= r; i++) if(abs(a[i]) == 2) res++; if(res >= ans) x = l - 1, y = n - r, ans = res; } void work(int l, int r) { int cnt = 0; for (int i = l; i <= r; i++) if(a[i] < 0) cnt++; if(cnt % 2 == 0) update(l, r); else { // 分别对前后最大的偶数个负数情况讨论 int now = l; while(a[now] > 0 && now < r) now++; update(l, now - 1); update(now + 1, r); now = r; while(a[now] > 0 && now > l) now--; update(l, now - 1); update(now + 1, r); } } void solve() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; a[n + 1] = 0; // 1 1 1 保证能把这块丢进work，最后置0 x = n, y = ans = 0; for (int i = 1, j = 1; i <= n + 1; i++) { if(a[i] == 0) { if(i - j > 0) work(j, i - 1); j = i + 1; } } cout << x << ' ' << y << endl; }
E Matrix and Shifts
题意：给定01矩阵，能上下左右的一行（列）循环换位，不造成代价。 也可以对任意位进行xor，为最后主对角线全1的最小代价。 思路：循环换位，等价于，拼接矩阵，[] == [][][][] ，n*n 变 2n*2n 答案：矩阵中1的个数 - 对角线上1的个数 +（0的xor次数）（n - 对角线上1的个数）
#include <iostream> #include <cstring> using namespace std; const int N = 4010; char g[N][N]; int a[N][N]; int s[N][N], p[N][N]; // s是矩阵中1的个数的前缀和，p是对角线上1的个数的前缀和 // 答案是矩阵中1的个数-对角线上1的个数 + （n - 对角线上1的个数） // 那些操作可以转换成复制三遍这个矩阵，组成一个2n*2n的矩阵，枚举每个n*n的矩阵 void solve() { int n, m; scanf("%d", &n); m = n * 2; for(int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1); for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) a[i][j] = a[i][j + n] = a[i + n][j] = a[i + n][j + n] = g[i][j] - '0'; // 二维前缀和记录矩阵中1的个数 for(int i = 1; i <= m; i ++ ) for(int j = 1; j <= m; j ++ ) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; p[i][j] = p[i - 1][j - 1] + a[i][j]; } int ans = n * n; for(int i = n; i <= m; i ++ ) for(int j = n; j <= m; j ++ ) { int sum = s[i][j] - s[i][j - n] - s[i - n][j] + s[i - n][j - n]; int psum = p[i][j] - p[i - n][j - n]; ans = min(ans, sum + n - 2 * psum); } printf("%d\n", ans); return; } int main() { int t; scanf("%d", &t); while(t --) { solve(); } return 0; }
F1 Promising String (easy version)
题意：给定字符串s，（s只含“+”，“-”），等价规则：“--”能和“+”等价。 问s的所有非空子串有多少个平衡串。（平衡串：“+”=1，“-”=-1，之和为0的串为平衡串） 思路：发现平衡串就是，k * 0 or k * -3 ，和值为这两种就一定是平衡的。
void solve() { int n; cin >> n; string s; cin >> s; int cnt = 0; for (int i = 0; i < n; i++) { int res = 0; for (int j = i; j < n; j++) { res += s[j] == '+' ? 1 : -1; if(res == 0) cnt++; if(res < 0) { int x = res * -1; if(x / 3 * 3 == x) cnt++; } } } cout << cnt << endl; }
不配了
