题解：Atcoder Beginner Contest abc466 A~D
A - Compromise
题目描述
有 $N$ 个选择。
你将选择其中之一。如果你选择 $i$ \-个选项，你的幸福感将是 $X _ i$ 。
如果无论你选择哪个选项，你的幸福感都是负数，那么输出 `Yes` ；否则，输出 `No` 。
解题思路
A题不讲了。脑残题。
完整代码
#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 pair<int,int> #define pll pair<ll,ll> #define _1st first #define _2nd second #define elif else if #define debug cout<<endl<<"-------------------------------------------------------------"<<endl using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n; cin>>n; bool flag=false; fr1(i,1,n){ int x; cin>>x; if(x>=0)flag=true; } if(flag)cout<<"No\n"; else cout<<"Yes\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题。
完整代码
#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 pair<int,int> #define pll pair<ll,ll> #define _1st first #define _2nd second #define elif else if #define debug cout<<endl<<"-------------------------------------------------------------"<<endl using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int N,M; cin>>N>>M; int mx[105]; fr1(i,1,M)mx[i]=-1; fr1(i,1,N){ int c,s; cin>>c>>s; mx[c]=max(mx[c],s); } fr1(k,1,M){ if(k>1)cout<<" "; cout<<mx[k]; } return 0; }C - Count Close Pairs
题目描述
这是一个交互式问题（在这个问题中，你的程序和法官程序通过标准输入和输出进行通信）。
在一条数线上，点 $1$ 、 $2$ 、 $\ldots$ 、 $N$ 从左到右依次排列。
最初只给出整数 $N$ 。
然后，你最多可以向法官提出以下问题 ${2N}$ 次：
选择满足 $1 \leq i < j \leq N$ 的整数 $i$ 和 $j$ ，问点 $i$ 和 $j$ 之间的距离是否最多为 $1$ 。
输出距离最多为 $1$ 的点对的个数，即满足 $1 \leq i < j \leq N$ 的整数 $(i,j)$ 中，点 $i$ 与 $j$ 之间的距离最多为 $1$ 的点对的个数。
如何交互
首先，从标准输入中接收代表点数的整数 $N$ ：
$N$
然后，你可以向法官重复问题陈述中描述的问题最多 $2N$ 次。
按以下格式将问题输出到标准输出，其中 $i$ 和 $j$ 必须是满足 $1 \leq i<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$ 到点 $i+1,i+2,\ldots,M_i$ 的距离都在 $1$ 或以下时，那么点 $(i+1)$ 到点 $i+2, i+3,\ldots,M_i$ 的距离都在 $1$ 或以下。
所以，我们可以确定 $M_i$ 的值在 $i=1,2,\ldots,N$ 的顺序中，从而避免询问距离已知为 $1$ 或更小的线对，从而减少问题的数量。
具体来说，我们从 $L=1,R=2$ 开始，重复下面的操作：
- 询问点 $L$ 和点 $R$ 之间的距离是否最多为 $1$ 。在此，如果是 $L=R$ ，则不提问，而是进入下一步，即点 $L$ 与点 $R$ 之间的距离最多是 $1$ 。
- 如果点 $L$ 与 $R$ 之间的距离最多为 $1$ ，则将 $R$ 增加 1，并进入下一步。如果得出 $R>N$ ，则确定 $M_L=M_{L+1}=\cdots=M_N=N$ 并终止程序。
- 如果点 $L$ 与 $R$ 之间的距离大于 $1$ ，求出 $M_L=R-1$ ，并将 $L$ 增加 1。在此，根据上述事实，注意从新点 $L$ 到点 $L+1,\ldots,R-1$ 的距离均为 $1$ 或以下。
这里， $L$ 和 $R$ 单调递增，或者说总是 $L\leq R$ 。在一次操作中， $L+R$ 总是增加 1，一旦 $R>N$ ，程序就终止，因此循环最多迭代 $(2N+1)-3=2N-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 pair<int,int> #define pll pair<ll,ll> #define _1st first #define _2nd second #define elif else if #define debug cout<<endl<<"-------------------------------------------------------------"<<endl using namespace std; int n,l=1,r=2,ans; string s; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n; while(r<=n){ cout<<"? "<<l<<" "<<r<<endl; cin>>s; if(s=="Yes"){ r++; }else{ ans+=(r-l-1); l++; if(l==r)r++; } } while(l<n){ ans+=(r-l-1); l++; } cout<<"! "<<ans<<endl; 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)\)。
- 如果存在一个操作序号 \(k>i\)，使得 \(R_k=r\)，第 k 步一开始就清空第 r 行，第 i 步放的棋子消失；
- 如果存在一个操作序号 \(k>i\)，使得 \(C_k=c\)，第 k 步会清空第 c 列，第 i 步棋子消失；
- 只有：i 是第 r 行最后一次被选中的操作，并且 i 也是第 c 列最后一次被选中的操作，这枚棋子最后存活。
数组解释
\(lr[x]\)：记录第 x 行最后一次被操作的序号；
\(lc[y]\)：记录第 y 列最后一次被操作的序号。
只有 \(lr[R_i]==i\) 并且 \(lc[C_i]==i\)，第 i 次放下的棋子最终留下来。
完整代码
#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 pair<int,int> #define pll pair<ll,ll> #define _1st first #define _2nd second #define elif else if #define debug cout<<endl<<"-------------------------------------------------------------"<<endl using namespace std; const int maxn=300010; 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; cin>>n>>m; fr1(i,1,m){ cin>>r[i]>>c[i]; int rr=r[i]; int cc=c[i]; lr[rr]=i; lc[cc]=i; } ll ans=0; fr1(i,1,m){ int rr=r[i]; int cc=c[i]; if(lr[rr]==i&&lc[cc]==i){ ans++; } } cout<<ans; return 0; }