CF1438A Specific Tastes of Andre
代码（全铺成1就可以了）
#include <cstdio>
#include <cctype>
#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
分析
如果不存在两个数相同，那么就不可能产生进位，相加之后也不一样。
如果存在两个数相同，那答案就是这两个数所在的区间 \([i,i]\) 和 \([j,j]\)
代码
#include <cstdio>
#include <cctype>
#include <map>
#define rr register
using namespace std;
int n,flag; map<int,bool>uk;
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){
n=iut(),uk.clear(),flag=0;
for (rr int i=1,x;i<=n;++i)
if (uk[x=iut()]) {
if (!flag) puts("YES");
flag=1;
}else uk[x]=1;
if (!flag) puts("NO");
}
return 0;
}
CF1438C Engineer Artem
分析
直接对矩阵黑白染色，黑色放奇数，白色放偶数即可
反正考场上没想到QAQ
代码
#include <iostream>
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<<endl)
for (int j=1;j<=m;++j){
int x; cin>>x;
if ((i^j^x)&1) cout<<x+1<<" ";
else cout<<x<<" ";
}
}
return 0;
}
CF1438D Powerful Ksenia
分析
有一些性质：异或前后异或和不变；如果有两个数 \(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 <iostream>
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"<<endl<<n-2+(n&1)<<endl;
for (int i=2;i<n;i+=2) cout<<1<<" "<<i<<" "<<i+1<<endl;
for (int i=2;i<n;i+=2) cout<<1<<" "<<i<<" "<<i+1<<endl;
}
return 0;
}
CF1438E Yurii Can Do Everything
分析
考虑 \(O(n^2)\) (bushi
因为总和肯定会增大，所以考虑以左端点为基准或者以右端点为基准，
当增大到 \(2^{mx[i]+1}\) 时异或值一定不相等，退出循环。
这样看时间貌似是差不多的，但是如果考虑枚举 \(mx[i]\) 的话，每个位置最多被访问两次。
所以时间复杂度为 \(O(n\log \max\{a_i\})\)
代码
#include <iostream>
#include <set>
using namespace std;
const int N=34011;
int n,mx[N],a[N*6],bit[N*6]; set<pair<int,int> >ans;
int main(){
ios::sync_with_stdio(0);
cin>>n;
for (int i=0;i<15;++i)
for (int j=(1<<i);j<(1<<(i+1));++j)
mx[j]=i+1;
for (int i=1;i<=n;++i){
cin>>a[i];
if (!(a[i]>>15)) bit[i]=mx[a[i]];
else bit[i]=15+mx[a[i]>>15];
}
for (int i=1;i<n-1;++i){
int sum=a[i+1];
for (int j=i+2;j<=n;++j){
if (sum>=(1<<bit[i])) break;
if ((a[i]^a[j])==sum) ans.insert(make_pair(i,j));
sum+=a[j];
}
}
for (int j=n;j>2;--j){
int sum=a[j-1];
for (int i=j-2;i;--i){
if (sum>=(1<<bit[j])) break;
if ((a[i]^a[j])==sum) ans.insert(make_pair(i,j));
sum+=a[i];
}
}
cout<<ans.size();
return 0;
}
CF1438F Olha and Igor
分析
如果把这种题放考场可能还是不会做QWQ
这道题最妙的就是用420次随机三个点，
就可以知道根节点的两个子节点。
然后再用 \(n\) 次判断根节点即可，证明也不会。
反正随机题都挺玄学的
代码
#include <iostream>
#include <algorithm>
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<<h)-1,srand(33333331);
for (int i=1;i<=n;++i) rk[i]=i;
for (int i=1;i<421;++i){
int x=(rand()*rand()+rand())%n+1,y=(rand()*rand()+rand())%n+1,rt=(rand()*rand()+rand())%n+1;
while (x==y) y=(rand()*rand()+rand())%n+1;
while (rt==x||rt==y) rt=(rand()*rand()+rand())%n+1;
cout<<"? "<<x<<" "<<y<<" "<<rt<<endl;
cin>>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<<"? "<<rk[1]<<" "<<rk[2]<<" "<<i<<endl;
int x; cin>>x;
if (x==i){
cout<<"! "<<x<<endl;
return 0;
}
}
return 0;
}