上周的D题一直WA。看来我还是有点菜
立个flag，这周五套cfabc题
这就是这周的目标
冲冲冲
12.7周一
Codeforces Round #688 (Div. 2)
A. Cancel the Trains
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 110;
int a[MAXN];int main()
{int T; scanf("%d", &T);while(T--){memset(a, 0, sizeof(a));int n, m, x;scanf("%d%d", &n, &m);int ans = 0;_for(i, 1, n){scanf("%d", &x);a[x] = 1; } _for(i, 1, m){scanf("%d", &x);if(a[x]) ans++;}printf("%d\n", ans);} return 0;
}
B. Suffix Operations
这题卡了我好久
关键是意识到一点，对于当前的一个数，只要求通过加减和前一个数一样大就行
至于改变哪一个数，需要比较改变每一个数所造成的影响，选择影响最优的那个
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 2e5 + 10;
int a[MAXN], n;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);long long sum = 0;int key = 0;_for(i, 1, n - 1){sum += abs(a[i] - a[i+1]);if(i == 1) key = max(key, abs(a[i] - a[i+1]));else{int t = abs(a[i] - a[i+1]) + abs(a[i] - a[i-1]);int now = abs(a[i+1] - a[i-1]);key = max(key, t - now);}}key = max(key, abs(a[n-1] - a[n]));printf("%lld\n", sum - key);} return 0;
} C题没做出来，有点菜
接下来计划有变
把周训复习一遍，确保百分百掌握
考前可以打一下比赛找状态
12.8周二
今天复习了并查集
还是比较熟练的，题目比较简单，就不写到这了
复习了有向树，注意和无向树的区别
12.9周三
复习常用字符串函数
atoi atof stdlib.h
strcpy strncpy (只覆盖前几位)
strcat strncat
strcmp
12.11 周五
三分查找
学算法要理解本质才好记忆
比如三分算法
可以用来求单峰函数极值
知道L，R后让L，R不断靠近直到达到峰值
那么方法就是三分，算出lmid，rmid
这时要不l = lmid，要不r = rmid来缩小范围
当lmid，rmid在极值两侧时两种操作都可以
但是在同一侧时就不一样了，根据实际情况可以判断出是l更新还是r更新
理解本质就不难了
前缀和与差分
二维差分模仿一维差分
ai - ai-1
axy - ax-1y - axy-1 + ax-1y-1
除法取模：逆元
当结果要取模时，加减乘都可以直接在中间过程取模，而除法则要用逆元
逆元可以解决（a/b）%p的问题
转化为a * b^-1 % p
逆元相当于同余下的倒数
a的逆元记为a的负一次方
两者相乘在同余下为1
逆元怎么求呢
费马小定理
a^p-1 = 1
条件是p为质数且a，p互质
那么此时a的逆元就是a^p-2
p太大可以用快速幂求
快速乘
a * b % p当a * b爆long long时怎么办
类似快速幂的思想，可以把b看成二进制，拆开来和a乘
离校赛还有9天
校赛前来5套abc题
加油
12.12 周六
Codeforces Round #687
赛前第一套cf题目
A. Prison Break
写完看了题解，我写的稍微复杂了一点，不过过了就行
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int n, m, r, c;int cal(int x, int y)
{return abs(x - r) + abs(y - c);
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d%d%d", &n, &m, &r, &c);int ans = 0;ans = max(ans, cal(1, 1));ans = max(ans, cal(n, m));ans = max(ans, cal(1, m));ans = max(ans, cal(n, 1));printf("%d\n", ans);}return 0;
}B. Repainting Street
我很快就想到了确定了颜色之后贪心就好
那么就想到每种颜色都试一遍，但觉得会超时
其实不会超时，因为我漏看了c<=100这个条件，算一下一千万不会超
复杂度是n*max(c)
没看清题目，于是我就想了一个O（n）的算法
这个算法搞了我好久，最后还是写出来了。反正写题就是锻炼思维嘛
但最后我发现我写的比n*max（c）的时间还长。应该是我写的常数大一些
O（n）
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
int a[MAXN], cnt[MAXN], pre[MAXN], n, k;int cal(int x)
{if(x <= 0) return 0;if(x % k == 0) return x / k;return x / k + 1;
}int main()
{int T; scanf("%d", &T);while(T--){memset(cnt, 0, sizeof(cnt));memset(pre, 0, sizeof(pre));scanf("%d%d", &n, &k);int m = 0;_for(i, 1, n){scanf("%d", &a[i]);m = max(a[i], m);if(i == 1) continue;if(a[i] != a[i-1]){pre[a[i-1]] = max(pre[a[i-1]], i - 1);int len = i - pre[a[i]] - 1;if(len <= 0) continue;if(len % k == 0) cnt[a[i]] += len / k;else {cnt[a[i]] += len / k + 1;pre[a[i]] = min(n, pre[a[i]] + (len / k + 1) * k);}} } pre[a[n]] = n;int ans = 1e9;_for(i, 1, m) {cnt[i] += cal(n + 1 - pre[i] - 1);ans = min(ans, cnt[i]);}printf("%d\n", ans);}return 0;
}O（n * max（c)）
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
int a[MAXN], n, k;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);int m = 0; _for(i, 1, n) {scanf("%d", &a[i]);m = max(m, a[i]);} int ans = 1e9;_for(color, 1, m){int res = 0, p = 1;while(p <= n){if(a[p] != color){res++;p += k;}else p++;}ans = min(ans, res); }printf("%d\n", ans);}return 0;
}
C. Bouncing Ball
简单的线性dp。注意几个点
一.初始化最大用0x3f（后来发现不需要初始化）
二.一个数字输入可以用%1d
三.这题的关键是理解去掉首元素然后序号改变的意义。
可以一开始先做这个操作，把所有起点可能的情况初始化一下
题目说了不能少于p个元素，以为有什么坑，后来发现不影响做题，总之就是最少要跳一下
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
int a[MAXN], dp[MAXN], n, p, k, x, y;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d%d", &n, &p, &k);_for(i, 1, n) scanf("%1d", &a[i]);scanf("%d%d", &x, &y);int ans = 1e9;_for(i, p, n) dp[i] = (i - p) * y + (a[i] == 0) * x;_for(i, p, n){if(i >= p + k) dp[i] = min(dp[i], dp[i - k] + x * (a[i] == 0));if(i + k > n) ans = min(ans, dp[i]);}printf("%d\n", ans);}return 0;
}
现在的目标就是abc能比较快的熟练的做出来
后面再刚第四题
12.13 周日
Codeforces Round #689
赛前第二套cf题
提升实力秘诀就是：独立思考（不轻易看题解）+多做题
A. String Generation
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;char ch[] = {'a', 'b', 'c'};int main()
{int T; scanf("%d", &T);while(T--){int n, k, p = 0;scanf("%d%d", &n, &k);while(n > 0){if(n >= k){_for(i, 1, k) putchar(ch[p]);n -= k;p = (p + 1) % 3;}else{while(n--){putchar(ch[p]);p = (p + 1) % 3;}}}puts("");}return 0;
}B. Find the Spruce
直接暴力n的四次方
这题的关键点就是初始化前缀和可以省去一维循环，变成n的三次方
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 500 + 10;
char s[MAXN][MAXN];
int sum[MAXN][MAXN], n, m;int cal(int x, int y)
{_for(i, 1, n){if(x + i - 1 > n || y - i + 1 < 1 || y + i - 1 > m ) return i - 1;if(sum[x+i-1][y+i-1] - sum[x+i-1][y-i] != 2 * i - 1)return i - 1;}return n;
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%s", s[i] + 1);_for(i, 1, n)_for(j, 1, m)sum[i][j] = sum[i][j-1] + (s[i][j] == '*');int ans = 0;_for(i, 1, n)_for(j, 1, m)ans += cal(i, j);printf("%d\n", ans);}return 0;
}C. Random Events
这题的思路很快
首先发现各个操作独立，然后发现有一些操作根本成不成功对答案没有影响（把样例手算一遍可以提供思路）
然后注意要特判一下，我特判的时候直接把后面的输入也省去了，这个低级错误卡了我好久，以后注意
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
int a[MAXN], n, m;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%d", &a[i]);int p = 1;for(int i = n; i >= 1; i--)if(a[i] != i){p = i;break;}double t = 1;while(m--){int x; double y;scanf("%d%lf", &x, &y);if(x >= p) t *= (1 - y);}if(p == 1) puts("1.000000");else printf("%.6f\n", 1 - t);}return 0;
}
Codeforces Round #685 (Div. 2)
赛前第3套abc
A. Subtract or Divide
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{int T; scanf("%d", &T);while(T--){int n; scanf("%d", &n);if(n <= 3) printf("%d\n", n - 1);else printf("%d\n", (n & 1) + 2);}return 0;
}B. Non-Substring Subsequence
一开始就有种想法是直接从原串上改，也就是把两边其中一边的元素移到远处
但不知道这样做对不对，不知道这样能不能覆盖所有情况
后来想通了如果这样都找不到，那就一定找不到
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 100 + 10;
int a[MAXN], n, q;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &q);_for(i, 1, n) scanf("%1d", &a[i]);while(q--){int l, r;scanf("%d%d", &l, &r);int ans = 0;_for(i, 1, l - 1)if(a[i] == a[l]){ans = 1;break;}_for(i, r + 1, n)if(a[i] == a[r]){ans = 1;break;}if(ans) puts("YES");else puts("NO");}}return 0;
}
现在做思维题还是有点慢
没有什么捷径
打cf，补题，打cf，补题
一直刷一直刷，独立思考
一直做比自己水平高一些的题目，一直刷一直刷