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

AtCoder Beginner Contest 466(ABCDEF)

相关推荐

营销分析实战七步法：从数据混乱到决策子弹

WPS Pro特殊版功能解锁与安全风险实测分析

C++学生管理系统实战：从静态数组到STL vector的面向对象设计

更多资讯

唐山哪里可以办电工证官方回应证书过期了不知道怎么复审延期

电工作业行为管理办法怎么用？含金量高的证书别过期了

电工证考试线路检验题库，学历不高也能考，上岗必备怎么准备？

特种作业架工证书过期了不知道怎么复审延期？真实经历教你一招搞定

马鞍山低压电工证报考网上查询怎么操作？实操考试心里没底怕挂科怎么办？

工地太忙根本没时间复习考试，个人有没有电工证值不值得考？

今日更新

西昌市电工作业查询怎么查？郑州报考避坑指南帮你少走弯路

西昌市电工作业查询通过率揭秘：怕考不过白交培训费？这几点要记牢

临夏电工证在哪里审官方报名入口怎么找

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？