AtCoder Beginner Contest 466(ABCDEF)

前言回归了这个暑假真要猛猛训练了一、A - Compromise#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout #x x endl; #define vdbg(a) \ cout #a endl; \ for (auto x : a) \ cout x ; \ cout endl; #define YES \ cout YES endl; \ return; #define Yes \ cout Yes endl; \ return; #define NO \ cout NO endl; \ return; #define No \ cout No endl; \ return; #define popcount __builtin_popcount using ll long long; using i128 __int128; using ld long double; using pii pairint, int; using pll pairll, ll; const int INF 1e9; const ll INFLL 1e18; const int dx[] {-1, 1, 0, 0}; const int dy[] {0, 0, -1, 1}; const int ddx[] {-2, -1, 1, 2, 2, 1, -1, -2}; const int ddy[] {1, 2, 2, 1, -1, -2, -2, -1}; void solve() { int n; cin n; vectorint a(n 1); int ok 0; for (int i 1; i n; i) { cin a[i]; if (a[i] 0) { ok 1; } } if (ok) { No; } Yes; } void init() { } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t 1; // cint; init(); while (t--) { solve(); } return 0; }直接判断输出即可。二、B - Representative Balls#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n,m; cinnm; vectorintsiz(m1,-1); for(int i1,x,y;in;i) { cinxy; siz[x]max(siz[x],y); } for(int i1;im;i) { coutsiz[i] ; } coutendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }直接在输入时就对每个种类更新大小的最大值最后统一输出即可。三、C - Count Close Pairsabc 居然出交互了。#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; int ask(int i,int j) { cout? i jendl; string res; cinres; return resYes; } void solve() { int n; cinn; int ans0; for(int i1,j1;in;i) { jmax(j,i); ansj-i; while(j1nask(i,j1)) { ans; j; } } cout! ansendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先2n 的交互次数启发我们扫两边数组。之后可以发现距离这个东西是存在单调性的。对于小于等于 1 的两个位置 (i,j)之后 i 到 j 之间的所有位置和 j 的距离必然都是小于等于 1 的。所以就可以考虑使用双指针每次让 j 扫到最后一个和当前 i 的距离小于等于 1 的位置这些都是当前 i 的合法位置。除此之外在每次开始时当前 i 还可以和从 i 到 j 之间的所有位置产生贡献那么再加上 j-i 即可。注意双指针滑动的时候需要每次将 j 至少来到 i否则特殊情况下 j 是不会动的。四、D - Placing Rooks#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n,q; cinnq; vectorarrayint,2qry(q1); for(int i1;iq;i) { cinqry[i][0]qry[i][1]; } vectorsetintrow(n1); vectorsetintcol(n1); for(int i1;iq;i) { auto [x,y]qry[i]; for(auto ry:row[x]) { col[ry].erase(x); } for(auto rx:col[y]) { row[rx].erase(y); } row[x].clear(); col[y].clear(); row[x].insert(y); col[y].insert(x); } int ans0; for(int i1;in;i) { ansrow[i].size(); } coutansendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }注意到一共只有 m 个点所以每次是可以暴力删除的。又因为不能开一个 n*n 的数组记录所以考虑分别用 set 维护每一行和每一列的有点的位置。那么对于每次添加的点 (x,y)就去遍历当前行和当前列的所有点去另一维里删除。最后清空当前行和当前列把这个点添加进去即可。五、E - Range Flip#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n,k; cinnk; vectorarrayll,2card(n1); for(int i1;in;i) { cincard[i][0]card[i][1]; } ll ans0; vectorlla(n1); for(int i1;in;i) { anscard[i][0]; a[i]card[i][1]-card[i][0]; } vectorllsum(n1); for(int i1;in;i) { sum[i]sum[i-1]a[i]; } vectorvectorlldp(n1,vectorll(k1,-INFLL)); vectorllbest(k1,-INFLL); dp[0][0]0; best[0]0; for(int i1;in;i) { dp[i][0]0; for(int j1;jmin(i,k);j) { dp[i][j]max(dp[i-1][j],best[j-1]sum[i]); } for(int j0;jmin(i,k);j) { best[j]max(best[j],dp[i][j]-sum[i]); } } ll add0; for(int j0;jk;j) { addmax(add,dp[n][j]); } coutansaddendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先由于是翻转操作所以两个区间是没必要重叠的因为重叠的部分相当于没操作过。那么问题首先就变为选择不超过 k 个区间区间两两不重叠使得最终价值最大。之后还是一个常见的转化可以先默认数组全是正面统计出此时的价值然后构建 b-a 数组。此时问题就又转化为在这个数组内选择不超过 k 个区间使得最终额外的价值最大。对于这个问题由于 k 不大所以可以考虑定义为考虑前 i 个数选了 j 个区间的最大价值。那么首先若不选当前位置就是。而如果选的话就需要从之前某个位置 p 的状态转移过来收益是区间累加和。对于区间累加和可以通过前缀和 O(1) 查询。而对于这个枚举前缀位置 p 的行为可以考虑构建表示从前缀中选 j 个区间的最大收益每次转移完看当前的 dp 能否更新这个最大收益。注意每次更新时需要用 dp 值减去当前位置的前缀和这样在后续某个位置继承时直接累加前缀和就是区间价值了。六、F - Many Mod Calculation势能分析无敌了……#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { ll n,x; cinnx; vectorlla(n1); for(int i1;in;i) { cina[i]; } ll minn2e18; vectorllb; for(int i1;in;i) { if(a[i]minn) { minna[i]; b.push_back(a[i]); } } nb.size(); mapll,lldp; auto calc[](auto self,ll cur)-ll { if(cur0) { return 1; } if(dp.find(cur)!dp.end()) { return dp[cur]; } int l0; int rn-1; int m; int ansn; while(lr) { mlr1; if(b[m]cur) { ansm; rm-1; } else { lm1; } } if(ansn) { dp[cur]1; return 1; } ll res(cur/b[ans])*self(self,b[ans]-1)self(self,cur%b[ans]); dp[cur]res; return res; }; coutcalc(calc,x)-1endl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }首先对于连续取模这个问题需要想到在之前对小的数取模后之后对于大的数不管怎么取模都是没影响的。那么就可以先处理出一个严格递减的序列 b满足每个数在原数组中都是前缀最小值。之后取模运算有一个重要的性质对于任意两个正整数那么。这就意味着在每次做完取模后当前数都至少减小一半所以这个复杂度是的。而对于另一个递归由于其取决于模数且每次不回退所以其规模就是的。又因为对于每个模数之后都只会经过的规模所以整体的复杂度最多也就是级别。总结何时能突破 F 题……END