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的面向对象设计

更多资讯

PaddleX+YOLOv3实现废水水质目标检测：从数据清洗到模型部署

PDF密码解除技术：原理、工具与实战指南

Gatus 多语言界面配置指南：自定义中文标题、公告与仪表板

ROS2通信接口深度解析：话题、服务、动作与参数实战指南

social-auto-upload 小红书上传运行前提：安装 sau CLI、patchright Chromium 与无头/有头调用方式详解

《道德经》第二章的辩证智慧与现代应用

今日更新

51单片机开环控制磁阻传感器的硬件匹配与代码实现

AI Agent安全操作数据库：SQL注入防御与参数化查询实战

Android逆向实战：还原激励类App签到接口的签名算法

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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