由于不是修仙党看见晚上12点开还3个小时就没打，后来线下开虚拟赛打的...估计现场打能涨不少分？
不过现场状态会更好还是更坏也说不定
A. Perfect Squares
题意: 求给定集合中最大的完全平方数 n<=1000 |ai|<=1000000
Sol:签到，我硬是没看见有负数WA了一发
Code:
#include<bits/stdc++.h> using namespace std; const int maxn = 1000009; int vis[maxn]; int n,ans=-10000000; int main() { cin>>n; for(int i=0;i<=1000;i++) vis[i*i]=1; for(int i=1;i<=n;i++) { int x;cin>>x; if(x<0) ans=max(ans,x); else if(!vis[x]) ans=max(ans,x); } cout<<ans<<endl; return 0; }B. Conan and Agasa play a Card Game
题意:n张纸牌上有数，Alice柯南和Morisa\Bob阿笠博士轮流操作，每次选一张牌，把所有严格<这张牌的牌和他本身拿走，无法操作输，问先手是否必胜
Sol:如果最大的有奇数张，先手胜，否则谁先最大的谁输，可以转化为去掉最大值后的子游戏，有奇数先手必胜，否则后手胜
Code:
#include<bits/stdc++.h> using namespace std; const int maxn = 1000009; int cnt[maxn],a[maxn]; int n; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++; bool flag=0; for(int i=100000;i>=1;i--) if(cnt[i]%2) flag=1; if(flag) puts("Conan"); else puts("Agasa"); return 0; }C. Travelling Salesman and Special Numbers
题意:定义f(x)=|x二进制位中1的个数|，n以内操作恰好k次变成1的数的个数 n<=2^1000 k <=1000
Sol:先dp出来1000以内每个数几次会变成1，规定1进行0次操作变成1，设为g(x)，枚举1000以内g(x)==k-1的数，转化为求n以内二进制位有x个1的数的个数，经典数位DP问题，需要特判k=0和k=1
Code:
#include<bits/stdc++.h> #define debug(x) cout<<#x<<"="<<x<<endl using namespace std; const int maxn = 1009; const int mod = 1e9+7; int f[maxn],a[maxn],C[maxn][maxn]; int n,m,ans,tot; char str[maxn]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int calc(int x) { int res=0; while(x){if(x&1)res++;x>>=1;} return res; } void work(int x) { int cnt=0; for(int i=n;i>=1;i--) { if(a[i]) { if(x>=cnt) ans=(ans+C[i-1][x-cnt])%mod; cnt++; } } if(x==tot) ans=(ans+1)%mod; } int main() { scanf("%s%d",str+1,&m);n=strlen(str+1); for(int i=1;i<=n;i++) a[i]=str[i]-'0',tot+=a[i]; reverse(a+1,a+1+n); for(int i=0;i<=n;i++) { C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } f[1]=1; for(int i=2;i<=1000;i++) f[i]=f[calc(i)]+1; if(m==0) puts("1"); else { for(int i=1;i<=1000;i++) if(f[i]==m) work(i); printf("%d\n",(ans-(m==1)+mod)%mod); } return 0; }D. Bash and a Tough Math Puzzle
题意:给定正整数序列，两种操作:
1.输入l,r,k 询问区间[l,r]是否可以最多改变一个数使gcd==k
2.输入x,y 讲a[x]改成y
Sol:可以转化为区间中多少个数是k的倍数----不可做
但是最多1个数不是就可以GG了，维护区间gcd，当一个范围内大区间gcd不是k的倍数意味着里面肯定至少有一个数不是，暴力递归下去找，最多暴力找2次就没了，复杂度O(nlog^2n)
Code:
#include<bits/stdc++.h> #define debug(x) cout<<#x<<"="<<x<<endl #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int maxn = 500009; const int mod = 1e9+7; struct sg_tree{int val;}node[maxn<<2]; int n,m,q,cnt; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int gcd(int x,int y) { if(y==0) return x; return gcd(y,x%y); } void update(int rt){node[rt].val=gcd(node[rt<<1].val,node[rt<<1|1].val);} void build(int l,int r,int rt) { if(l==r) { node[rt].val=read(); return ; }int mid=(l+r)>>1; build(lson);build(rson); update(rt); } void insert(int l,int r,int rt,int pos,int delta) { if(l==r) { node[rt].val=delta; return ; }int mid=(l+r)>>1; if(pos<=mid) insert(lson,pos,delta); else insert(rson,pos,delta); update(rt); } void query(int l,int r,int rt,int left,int right,int delta) { if(cnt<0) return ; if(l==r) { if(node[rt].val