比赛链接
({frak{A. Card Game}})
显然，二者最大值大的人赢。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
int n,n1,n2,Max1,Max2;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
int main()
{
int t=in();
while(t--){
n1=in(),n2=in(),Max1=Max2=0;
while(n1--) Max1=max(Max1,in());
while(n2--) Max2=max(Max2,in());
puts(Max1<Max2?"NO":"YES");
}
return 0;
}
({frak{B. Interesting Subarray}})
若相邻两个元素的差值都小于(2)，则不可能找出满足条件的序列。故只需要检查相邻元素即可。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3;
int n,a[N],l,r,Max,Min;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
int main()
{
int t=in();
while(t--){
n=in();
for(int i=1;i<=n;++i) a[i]=in();
for(int i=1;i<n;++i)
if(abs(a[i]-a[i+1])>=2){
puts("YES");printf("%d %d
",i,i+1);goto dd;
}
puts("NO");
dd:;
}
return 0;
}
({frak{C. Make Good}})
异或与和进行比较不好处理，考虑先加一个数(xor)等于原数组的异或和，使异或值等于零，再加上(sum+xor)即可完成构造。
（因为(LL)输出(\%lld) (WA)了两次。。。）
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e5+3;
int n,a[N],xo;
LL sum;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
void write(LL x){
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main()
{
int t=in();
while(t--){
n=in(),sum=xo=0;
for(int i=1;i<=n;++i) a[i]=in(),sum+=a[i],xo^=a[i];
write(2),putchar('
'),write(xo),putchar(' '),write(sum+xo),putchar('
');
}
return 0;
}
({frak{D. Strange Device}})
显然只需询问(k+1)个元素，询问相当于删去一个数问第(m)个数。我们发现答案只有两种情况，二者的较小数的出现次数便是(m)。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=5e2+3;
int n,k,a[N],res,m1,m2,n1,n2;
LL sum;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
void write(LL x){
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main()
{
n=in(),k=in(),m1=m2=-1,n1=n2=0;
for(int i=1;i<=k+1;++i){
printf("?");
for(int j=1;j<=k+1;++j)
if(i^j) printf(" %d",j);
printf("
"),fflush(stdout);
in();res=in();
if(m1==-1) m1=res,++n1;
else if(res==m1) ++n1;
else if(m2==-1) m2=res,++n2;
else ++n2;
}
if(m1<m2) swap(m1,m2),swap(n1,n2);
printf("! %d
",n1);fflush(stdout);
return 0;
}
({frak{E. Divide Points}})
对点((x,y))的奇偶性进行讨论，共有(4)个集合，易证若其中两个集合非空，则可构造出分类。否则将((x,y))转化为({(x/2,y/2)})再循环。
*赛场上思路局限于建图，并未注意到距离相等的条件苛刻。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=1e3+3;
int n,a[N],b[N],num[2][2],ans[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL void pre(){memset(num,0,sizeof(num));}
int main()
{
int x,y;n=in();
for(int i=1;i<=n;++i) a[i]=in(),b[i]=in();
while(1){
pre();
for(int i=1;i<=n;++i) ++num[a[i]&1][b[i]&1];
if((!num[0][0]+!num[0][1]+!num[1][0]+!num[1][1])<=2){
if((!!num[0][0]|!!num[1][1])&&(!!num[1][0]|!!num[0][1])){
for(int i=1;i<=n;++i) if(a[i]+b[i]&1) ans[++ans[0]]=i;
}
else if(!!num[0][0]){
for(int i=1;i<=n;++i) if((a[i]&1)&&(b[i]&1)) ans[++ans[0]]=i;
}
else for(int i=1;i<=n;++i) if((a[i]&1)&&!(b[i]&1)) ans[++ans[0]]=i;
printf("%d
",ans[0]);for(int i=1;i<=ans[0];++i) printf("%d ",ans[i]);
puts("");return 0;
}
for(int i=1;i<=n;++i) a[i]=a[i]>>1,b[i]=b[i]>>1;
}
return 0;
}
({frak{*F. Awesome Substrings}})
先求出前缀和(pre)，答案为(sumlimits_{i=1}^{n}{sumlimits_{j=i}^{n}{left[left(pre_j-pre_{i-1} ight)k =j-i+1 ight]}},kin{N^*}。)
我们对(k)进行划分，对(k leq T)则用桶在(O(nT))的时间复杂度下求出答案数。
对于(k>T)，枚举左端点，每增加(1)便至少向右扩展(T+1)个点，故时间复杂度为(O(ncdotfrac{n}{T})。)
因为计算(k>T)的常数更小，所以取(T<sqrt{n})，实测(T)取(300)时可在(2s)内通过。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3,M=300;
int n,num,buk[N*M+N],pos[N],pre[N];
char s[N];
LL ans;
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;++i) pre[i]=pre[i-1]+s[i]-'0';
for(int i=1;i<=n;++i) if(s[i]=='1') pos[++num]=i;pos[++num]=n+1;
for(int i=1;i<=M;++i){
++buk[i*n];
for(int j=1;j<=n;++j){
int val=j+i*(n-pre[j]);
ans+=buk[val],++buk[val];
}
--buk[i*n];
for(int j=1;j<=n;++j) --buk[j+i*(n-pre[j])];
}
for(int i=0;i<n;++i){
for(int j=1;j+pre[i]+1<=num;++j){
int l=max(pos[pre[i]+j],j*(M+1)+i),r=pos[pre[i]+j+1]-i-1;
if(l>n) break;l-=i;
if(l<=r) ans+=r/j-(l-1)/j;
}
}
printf("%I64d
",ans);
return 0;
}
({frak{G. Subset with Zero Sum}})
显然，(1 leq i-a_i leq n),所以(forall i in [1,n])向(i-a_i)连一条边,则必然存在一个环。
这个环体现以下等式：
(i_1-a_{i_1}=i_2)
(i_2-a_{i_2}=i_3)
(vdots)
(i_n-a_{i_n}=i_1)
等式相加，得(sumlimits_{k=1}^n a_{i_k} = 0。)
注意回溯的处理。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=1e6+3;
int n,fa[N],ans[N],vis[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
void dfs(int u){
if(vis[u]){
int v=u;ans[++ans[0]]=u,u=fa[u];
while(u^v) ans[++ans[0]]=u,u=fa[u];
return;
}
vis[u]=1,dfs(fa[u]),vis[u]=0;
}
int main()
{
int t=in();
while(t--){
n=in(),ans[0]=0;
for(int i=1;i<=n;++i) fa[i]=i-in();
dfs(1);printf("%d
",ans[0]);
for(int i=1;i<=ans[0];++i) printf("%d ",ans[i]);puts("");
}
return 0;
}