这是一场考得很不好的比赛，逐一分析问题，下次找回面子（和(Rating)）。
(A.quad Subtractquad orquad Divide)
第一眼感觉没有思路（也是我第一次(div_2)的(A)题没思路），于是打了个100的表出来。
发现当(4leq n)时，偶数答案为2，奇数答案为3。
思考原因，发现若是偶数，则一次除成2再减1，若为奇数则先减成偶数。
正确性显然。考场代码如下：
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
int T,n,dp[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int main(){
T=read();
while(T--){
n=read();
if(n==1)puts("0");
else if(n==2)puts("1");
else if(n==3)puts("2");
else if(n%2==0)puts("2");
else puts("3");
}
return 0;
}
(B.quad Non-Substringquad Subsequence)
考虑改变串首和串尾的位置，若可以改变则可行，否则一定不可行。
考场代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e3+10;
const int mod=1e9+7;
int T,n,m,sum[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int main(){
T=read();
while(T--){
n=read(),m=read();
string s;cin>>s;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+s[i-1]-'0';
int l,r;
for(int i=1;i<=m;i++){
l=read(),r=read();
if(s[l-1]=='0'&&sum[l-1]!=l-1)puts("YES");
else if(s[l-1]=='1'&&sum[l-1])puts("YES");
else if(s[r-1]=='0'&&sum[n]-sum[r]!=n-r)puts("YES");
else if(s[r-1]=='1'&&sum[n]-sum[r])puts("YES");
else puts("NO");
}
}
return 0;
}
以上是我做出来了的，没错，只有两道，(rank)到了(5000^+)。
重点分析以下没有做出来的/做错的题目：
(C.quad Stringquad Equality)
不考虑顺序。考场上我直接排了个序，但发现元素只有26个，可以桶排。
由于字母只能越变越大，则我们从前往后考虑。
如果对字母(alpha)，若(b)中比(a)中多，则无论如何操作都无法将(a)中的(alpha)变多，故不行。
当(a)中的部分(alpha)跟(b)中的抵掉后，需要将剩余的传到下一个，若剩余的不为(k)的倍数，也不行。
否则，则将(a)的(alpha+1)加上剩余的，考虑下一个。
考后改题代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
int T,n,m,a[maxn],b[maxn];
string A,B;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int main(){
T=read();
while(T--){
n=read();m=read();
cin>>A>>B;
for(int i=0;i<26;i++)
a[i]=b[i]=0;
for(int i=0;i<n;i++)
a[A[i]-'a']++,b[B[i]-'a']++;
int flag=1;
for(int i=0;i<26;i++){
if(a[i]<b[i]){flag=0;break;}
if((a[i]-b[i])%m){flag=0;break;}
a[i+1]+=a[i]-b[i];
}
puts(flag?"Yes":"No");
}
return 0;
}
(D.quad Circlequad Game)
给出结论：找到最大的(ans)使((ans*k,ans*k))在圆内，若((ans*k,ans*k+k))也在圆内，则先手赢，否则后手赢。
证明：若((ans*k,ans*k+k))不在圆内则后手只需保持在(y=x)上即可。否则先手只需保持在(y=x-k)上即可。
很少做博弈论的题，以后注意找特殊的必胜策略。
考后改题代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int T,d,k;
inline int check(int x,int y){
return x*x+y*y<=d*d;
}
signed main(){
T=read();
while(T--){
d=read(),k=read();
int l=0,r=d/k+1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid*k,mid*k))ans=mid,l=mid+1;
else r=mid-1;
}
//printf("%lld
",ans);
puts(check(ans*k,ans*k+k)?"Ashish":"Utkarsh");
}
return 0;
}
注意不要爆(long long)了。
(E1.quad Bitwisequad Queriesquad (Easyquad Version))
其实这道题我考场想出来正解了，然而由于不会写交互鸽了。
给出构造：发现只要五个式子就可以唯一确定三个数，即：({a|b,b|c,a&b,b&c,c&a} ightarrow{a,b,c})
原因是：(a+b=a&b+a|b)，(a+b+c=a|b|c+a&b+b&c+c&a-a&b&c)
又有知道一个数与已知数的异或可以唯一确定这个数，故操作次数为(n+2)次。
改题代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,a[maxn],a12,a23,a13,o12,o23,sum;
signed main(){
n=read();
puts("AND 1 2");fflush(stdout);a12=read();
puts("AND 2 3");fflush(stdout);a23=read();
puts("AND 1 3");fflush(stdout);a13=read();
puts("OR 1 2");fflush(stdout);o12=read();
puts("OR 2 3");fflush(stdout);o23=read();
sum=(o12|o23)+a12+a23+a13-(a12&a23);
a[1]=sum-a23-o23;a[3]=sum-a12-o12;a[2]=sum-a[1]-a[3];
for(int i=4;i<=n;i++){
printf("XOR 1 %lld
",i);
fflush(stdout);
a[i]=read()^a[1];
}
printf("!");
for(int i=1;i<=n;i++)
printf(" %lld",a[i]);
return 0;
}
收获：知道怎么做交互了？？（大雾）
(E2.quad Bitwisequad Queriesquad (Hardquad Version))
(F.quad Nullifyquad Thequad Matrix)