题解：Atcoder Beginner Contest abc466 A~D

A - Compromise题目描述有 $N$ 个选择。你将选择其中之一。如果你选择 $i$ \-个选项你的幸福感将是 $X #95; i$ 。如果无论你选择哪个选项你的幸福感都是负数那么输出 Yes 否则输出 No 。解题思路A题不讲了。脑残题。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n; cinn; bool flagfalse; fr1(i,1,n){ int x; cinx; if(x0)flagtrue; } if(flag)coutNo\n; else coutYes\n; return 0; }B - Representative Balls题目描述有 $N$ 个球。第 $i$ 个球的颜色是 $C_i$ 大小是 $S_i$ 。这里颜色用整数 $1, 2, \ldots, M$ 表示。对于 $k 1, 2, \ldots, M$ 输出颜色为 $k$ 的球的最大大小如果没有颜色为 $k$ 的球则输出 $-1$ 。解题思路最脑残的一次B题。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int N,M; cinNM; int mx[105]; fr1(i,1,M)mx[i]-1; fr1(i,1,N){ int c,s; cincs; mx[c]max(mx[c],s); } fr1(k,1,M){ if(k1)cout ; coutmx[k]; } return 0; }C - Count Close Pairs题目描述这是一个交互式问题在这个问题中你的程序和法官程序通过标准输入和输出进行通信。在一条数线上点 $1$ 、 $2$ 、 $\ldots$ 、 $N$ 从左到右依次排列。最初只给出整数 $N$ 。然后你最多可以向法官提出以下问题 ${2N}$ 次选择满足 $1 \leq i lt; j \leq N$ 的整数 $i$ 和 $j$ 问点 $i$ 和 $j$ 之间的距离是否最多为 $1$ 。输出距离最多为 $1$ 的点对的个数即满足 $1 \leq i lt; j \leq N$ 的整数 $(i,j)$ 中点 $i$ 与 $j$ 之间的距离最多为 $1$ 的点对的个数。如何交互首先从标准输入中接收代表点数的整数 $N$ $N$然后你可以向法官重复问题陈述中描述的问题最多 $2N$ 次。按以下格式将问题输出到标准输出其中 $i$ 和 $j$ 必须是满足 $1 \leq ilt;j \leq N$ 的整数? $i$ $j$作为对此的回应将从标准输入中给出以下信息之一Yes或者No。这里 $Yes$ 表示点 $i$ 和 $j$ 之间的距离最多为 $1$ $No$ 表示点 $i$ 和 $j$ 之间的距离大于 $1$ 。找到问题答案 $X$ 后按以下格式输出答案然后立即终止程序! $X$解题思路居然是滑动窗口。。。基本框架针对每个点 $1,2,\ldots,N$ 找出 $M_i$ 与 $i\leq M_i\leq N$ 的最大值使得从点 $i$ 到点 $M_i$ 的距离最多为 $1$ 。答案为 $ (M_1-1)(M_2-2)\cdots(M_N-N)$ 。重要的一点是 $M_1\leq M_2\leq \cdots \leq M_N$ .这是因为当点 $i$ 到点 $i1,i2,\ldots,M_i$ 的距离都在 $1$ 或以下时那么点 $(i1)$ 到点 $i2, i3,\ldots,M_i$ 的距离都在 $1$ 或以下。所以我们可以确定 $M_i$ 的值在 $i1,2,\ldots,N$ 的顺序中从而避免询问距离已知为 $1$ 或更小的线对从而减少问题的数量。具体来说我们从 $L1,R2$ 开始重复下面的操作询问点 $L$ 和点 $R$ 之间的距离是否最多为 $1$ 。在此如果是 $LR$ 则不提问而是进入下一步即点 $L$ 与点 $R$ 之间的距离最多是 $1$ 。如果点 $L$ 与 $R$ 之间的距离最多为 $1$ 则将 $R$ 增加 1并进入下一步。如果得出 $Rgt;N$ 则确定 $M_LM_{L1}\cdotsM_NN$ 并终止程序。如果点 $L$ 与 $R$ 之间的距离大于 $1$ 求出 $M_LR-1$ 并将 $L$ 增加 1。在此根据上述事实注意从新点 $L$ 到点 $L1,\ldots,R-1$ 的距离均为 $1$ 或以下。这里 $L$ 和 $R$ 单调递增或者说总是 $L\leq R$ 。在一次操作中 $LR$ 总是增加 1一旦 $Rgt;N$ 程序就终止因此循环最多迭代 $(2N1)-32N-2$ 次最后做一些简单推理即可。(我们可以证明查询次数最多为 $(2N-3)$ 。完整代码#include bits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int n,l1,r2,ans; string s; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cinn; while(rn){ cout? l rendl; cins; if(sYes){ r; }else{ ans(r-l-1); l; if(lr)r; } } while(ln){ ans(r-l-1); l; } cout! ansendl; return 0; }D - Placing Rooks题目描述有一个网格其中有 $N$ 行和 $N$ 列。起初网格上什么都没有。从这个状态开始高桥依次对网格执行 $M$ 次操作。 $i$ 次操作 $(1\leq i\leq M)$ 如下。移除从上往下第 $R_i$ 行单元格上的所有棋子。接着移除从左边起第 $C_i$ 列单元格上的所有棋子。最后在从上往下第 $R_i$ 行和从左往上第 $C_i$ 列的单元格上放置一个棋子。输出经过 $M$ 次操作后放置在网格上的棋子数量。解题思路核心推论只有后续没有再次清空 \(R_i\) 行、也没有再次清空 \(C_i\) 列时第 i 次放的棋子最后才会保留 只要后面有任意一次操作选中了第 \(R_i\) 行或者第 \(C_i\) 列这个棋子一定会被清除。举例子假设第 i 步放置棋子 \((r,c)\)。如果存在一个操作序号 \(ki\)使得 \(R_kr\)第 k 步一开始就清空第 r 行第 i 步放的棋子消失如果存在一个操作序号 \(ki\)使得 \(C_kc\)第 k 步会清空第 c 列第 i 步棋子消失只有i 是第 r 行最后一次被选中的操作并且 i 也是第 c 列最后一次被选中的操作这枚棋子最后存活。数组解释\(lr[x]\)记录第 x 行最后一次被操作的序号\(lc[y]\)记录第 y 列最后一次被操作的序号。只有 \(lr[R_i]i\) 并且 \(lc[C_i]i\)第 i 次放下的棋子最终留下来。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; const int maxn300010; int lr[maxn]; int lc[maxn]; int r[maxn], c[maxn]; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n, m; cinnm; fr1(i,1,m){ cinr[i]c[i]; int rrr[i]; int ccc[i]; lr[rr]i; lc[cc]i; } ll ans0; fr1(i,1,m){ int rrr[i]; int ccc[i]; if(lr[rr]ilc[cc]i){ ans; } } coutans; return 0; }