AtCoder Beginner Contest 450 复盘

总结这是第一次打Atcode Beginner的网赛以前一直打codeforce的网赛总体来说题目比codeforce的难度梯度还是明显比codeforce的题目相对还是有点难恐怕是看不懂题目题目描述和codeforce有比较大的区别第一题和第二题就是送分的没有什么难度第三题开始就要用到一些固定的算法比如深度优先算法之类的对思维还是很少到第四题就是一个纯纯蒙人的题目看起来很难想一想就知道的那种第五题就感觉像是codeforce的第4题目的水平就有点难必须要算法和思维一起上然后这个时候我还没学完图论第五题直接就没了还是太菜了总体来说1个小时40分钟做5个是我现在的极限了后面看可以突破图论的限制吗一般图论还是很简单的题目。A - 3,2,1,GO这个题目没啥说的基本上会写代码的都会写数据也很小暴力过就行#include iostream #include vector #include algorithm #include map #include string using namespace std; using ll long long; #define forn(i,n) for(int i 0;i (int)n;i) void solve(); int main() { solve(); } void solve() { int n; cin n; for (int i n; i 0; i--)cout i ,; cout 0; }B - Split Ticketing这个题观察数据N最大也就100直接暴力过就行也不大这个题但是要注意的是给了N-1行,每行 N-i(base_0)个数据也就是说给了N*N矩阵的上三角部分而且没有对角线毕竟i-i也就是0没啥算的但是在后面循环的时候要注意范围或者初始化的时候就把下三角也补充好还有让输出的是Yes和No!!!codeforce一般都是YES和NO本人亲自实验错了三次才发现O_O无语#include iostream #include vector #include algorithm #include map #include string using namespace std; using ll long long; #define forn(i,n) for(int i 0;i (int)n;i) void solve(); int main() { solve(); } void solve() { int n; cin n; vectorvectorint arr(n, vectorint(n)); for (int i 0; i n - 1;i) { for (int j i 1; j n; j)cin arr[i][j]; } bool OK false; for (int i 0; i n - 2 !OK; i) { for (int j i 2; j n !OK; j) { for (int z i 1; z j !OK; z) { if (arr[i][z] arr[z][j] arr[i][j])OK true; } } } if (OK)cout Yes endl; else cout No endl; }C - Puddles这个题目说是让#完全包裹.就算一个部分统计有多少个部分这里的H和W都不算大那么我们可以先遍历每一个字符维护一个res,遇到.”的话就设置一个OKtrue,然后深度优先把每一个和这个.相邻的.变成#如果遇到.在边上就把OKfalse然后判断OK如果为T就res如果为F就啥都不干然后全部遍历即可。#include iostream #include vector #include algorithm #include map #include string #include functional using namespace std; using ll long long; #define forn(i,n) for(int i 0;i (int)n;i) void solve(); int main() { solve(); } void solve() { int H, W; int X[] { 0,0,-1,1 }; int Y[] { -1,1,0,0 }; cin H W; vectorstring arr(H); forn(i, H)cin arr[i]; int res 0; forn(i, H) { forn(j, W) { if (arr[i][j] .) { int OK true; functionvoid(int,int) dfs [](int h, int w) { if (arr[h][w] #)return; if ((w 0 || w W - 1 || h 0 || h H - 1) arr[h][w] .) { arr[h][w] #; OK false; } arr[h][w] #; for (int z 0; z 4; z) { int nw w X[z]; int nh h Y[z]; if (nw 0 nw W nh 0 nh H) { dfs(nh, nw); } } }; dfs(i, j); if (OK)res; } } } cout res endl; }D - Minimize Range这个题目上手有点懵但是问题不大这里啥最大值 - 最小值要求最小第一个想到的是二分找到这个最小值但是感觉不对没法证明这个最小值是否存在然后从题目的K入手不管这个数字如何反正最后对于形式都是,不管现在的值是啥反正这个k * q的部分都得没所以说只考虑的部分了对于这个部分我们设就是这个那么最小的答案如何呢肯定就是中最大的和最小的之差了但是要注意还有一种情况就是最小的k的情况这个时候中最大的哪个就成最小的了要用,所以说有两种情况一个。思路清楚了代码也就好写了。#include iostream #include vector #include algorithm #include map #include string #include queue using namespace std; using ll long long; #define forn(i,n) for(int i 0;i (int)n;i) void solve(); int main() { solve(); } void solve() { int N; ll K; cin N K; vectorll A(N); for (int i 0; i N; i) { cin A[i]; } vectorll B(N); for (int i 0; i N; i) { B[i] A[i] % K; } sort(B.begin(), B.end()); ll ans B[N - 1] - B[0]; for (int i 0; i N - 1; i) { ll minV min(B[0] K, B[i 1]); ll maxV max(B[N - 1], B[i] K); ll diff maxV - minV; if (diff ans) ans diff; } cout ans endl; }E - Fibonacci String这个题目也是上手一脸懵但是问题不大先看规律然后他让我们统计L到R的中字符C的个数这个10^18的确很吓人但是1≤Q≤1051≤Li​≤Ri​≤1018这两个直接把问题卡死了也就说S根本到不了10^18斐波那契数列来看也就90项根本到不了这么大这纯纯哄人然后看这个数列的规律每一次Sn来说把n-1放到了前面n-2放到了后面这样我们统计L-R的个数的时候如何统计可以把大的拆分成小的比如S8我统计X从1-10的个数那么我们看S8的个数也就21个是21 13 8得到的也就是说我们要的1-10全都在S7中然后看S7个数13个是138 5 得到的然后就是说前8个在S6后两个在S5中然后就递归下去但是我要他的个数啊不能一直递归下去啊要不然栈内存要爆炸那么我们可以预处理几个比较小的S的数据然后用前缀和统计之后把大的化成小的然后去计算这样预处理一下小的就可以计算大的了。#include iostream #include string #include vector #include functional using namespace std; using ll long long; const ll MAXL 1e18; int main() { string X, Y; cin X Y; int Q; cin Q; int lenX X.size(), lenY Y.size(); vectorll len { 0, lenX, lenY }; vectorvectorll cnt { {}, {}, {} }; cnt[1].assign(26, 0); cnt[2].assign(26, 0); for (char c : X) cnt[1][c - a]; for (char c : Y) cnt[2][c - a]; vectorvectorint prefX(26, vectorint(lenX 1, 0)); vectorvectorint prefY(26, vectorint(lenY 1, 0)); for (int i 0; i lenX; i) { for (int j 0; j 26; j) prefX[j][i 1] prefX[j][i]; prefX[X[i] - a][i 1]; } for (int i 0; i lenY; i) { for (int j 0; j 26; j) prefY[j][i 1] prefY[j][i]; prefY[Y[i] - a][i 1]; } int idx 2; while (len[idx] MAXL) { idx; ll newLen len[idx - 1] len[idx - 2]; len.push_back(newLen); vectorll newCnt(26); for (int c 0; c 26; c) newCnt[c] cnt[idx - 1][c] cnt[idx - 2][c]; cnt.push_back(newCnt); } int K idx; functionll(int, ll, int) countPrefix [](int i, ll n, int c) - ll { if (n 0) return 0; if (i 1) return prefX[c][n]; if (i 2) return prefY[c][n]; if (n len[i - 1]) return countPrefix(i - 1, n, c); else return cnt[i - 1][c] countPrefix(i - 2, n - len[i - 1], c); }; for (int q 0; q Q; q) { ll L, R; char ch; cin L R ch; int c ch - a; ll ans countPrefix(K, R, c) - countPrefix(K, L - 1, c); cout ans \n; } return 0; }然后后面的题目太有技巧了而且没有时间写了最后一题哪个mod不知道咋搞的看了半天没看懂然后就这样了QAQ