Codeforces Round #682 (Div. 2)
CF1438A Specific Tastes of Andre
洛谷传送门
CF1438A
代码（全铺成1就可以了）
#include
#include
#define rr register
using namespace std;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
signed main(){
for (rr int T=iut();T;--T,putchar(10)){
for (rr int n=iut();n;--n)
putchar(49),putchar(32);
}
return 0;
}
CF1438B Valerii Against Everyone
洛谷传送门
CF1438B
分析
如果不存在两个数相同，那么就不可能产生进位，相加之后也不一样。
如果存在两个数相同，那答案就是这两个数所在的区间 \([i,i]\) 和 \([j,j]\)
代码
#include
#include
#include CF1438C Engineer Artem
洛谷传送门
CF1438C
分析
直接对矩阵黑白染色，黑色放奇数，白色放偶数即可
反正考场上没想到QAQ
代码
#include
using namespace std;
int T,n,m;
int main(){
ios::sync_with_stdio(0);
for (cin>>T;T;--T){
cin>>n>>m;
for (int i=1;i<=n;++i,cout<>x;
if ((i^j^x)&1) cout< CF1438D Powerful Ksenia
洛谷传送门
CF1438D
分析
有一些性质：异或前后异或和不变；如果有两个数 \(a_j,a_k\) 相同，那么 \(a_i,a_j,a_k\) 异或之后全部变成 \(a_i\)。
那么给两两配对，如果序列长度为奇数意味着可以先用 \(\frac{n-1}{2}\) 次将配对的数变为相同的数，
再用 \(\frac{n-1}{2}\) 次将所有数变相同。
否则序列长度为偶数有解当且仅当所有数异或和为0，这样只对前 \(n-1\) 个数操作第 \(n\) 个数会自动相同
代码
#include
using namespace std;
int n,sum;
int main(){
ios::sync_with_stdio(0);
cin>>n;
for (int i=1;i<=n;++i){
int x; cin>>x,sum^=x;
}
if (!(n&1)&&sum) cout<<"NO";
else{
cout<<"YES"< CF1438E Yurii Can Do Everything
洛谷传送门
CF1438E
分析
考虑 \(O(n^2)\) (bushi
因为总和肯定会增大，所以考虑以左端点为基准或者以右端点为基准，
当增大到 \(2^{mx[i]+1}\) 时异或值一定不相等，退出循环。
这样看时间貌似是差不多的，但是如果考虑枚举 \(mx[i]\) 的话，每个位置最多被访问两次。
所以时间复杂度为 \(O(n\log \max\{a_i\})\)
代码
#include
#include
using namespace std;
const int N=34011;
int n,mx[N],a[N*6],bit[N*6]; set >ans;
int main(){
ios::sync_with_stdio(0);
cin>>n;
for (int i=0;i<15;++i)
for (int j=(1<>a[i];
if (!(a[i]>>15)) bit[i]=mx[a[i]];
else bit[i]=15+mx[a[i]>>15];
}
for (int i=1;i=(1<2;--j){
int sum=a[j-1];
for (int i=j-2;i;--i){
if (sum>=(1< CF1438F Olha and Igor
洛谷传送门
CF1438F
分析
如果把这种题放考场可能还是不会做QWQ
这道题最妙的就是用420次随机三个点，
就可以知道根节点的两个子节点。
然后再用 \(n\) 次判断根节点即可，证明也不会。
反正随机题都挺玄学的
代码
#include
#include
using namespace std;
const int N=300011;
int n,h,rk[N],c[N];
bool cmp(int x,int y){return c[x]>c[y];}
int main(){
ios::sync_with_stdio(0);
cin>>h,n=(1<>x; ++c[x];
}
sort(rk+1,rk+1+n,cmp);
for (int i=1;i<=n;++i)
if (i!=rk[1]&&i!=rk[2]){
cout<<"? "<>x;
if (x==i){
cout<<"! "<