A. Vasya and Socks
水题就不用多说了，直接暴力枚举就完事了。
#include <iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;#define LL __int64int main(){ int n,k; while(~scanf("%d%d",&n,&k)) { int m=n; int ans=n; int yu=0; while(m) { m=m+yu; yu=m%k; m=m/k; ans+=m; } cout<<ans<<endl; } return 0;}B. Little Dima and Equation
立即学习“前端免费学习笔记（深入）”；
也不用说，水题一个，直接枚举s(x)，然后得到x，然后根据x推出s(x)是不是合适。
当时把81写成了72，不由的十分悲伤，sad.
#include <iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;#define LL __int64#define INF 1000000000vector<int>vec;LL pows(LL x,LL y){ LL ans=1; while(y--)ans=ans*x; return ans;}int dus(LL x){ int ans=0; while(x) { ans=ans+x%10; x=x/10; } return ans;}int main(){ int n,k; int a,b,c; while(~scanf("%d%d%d",&a,&b,&c)) { LL ans=0; vec.clear(); for(int i=1;i<=81;i++) { ans=(LL)b; ans=ans*pows(i,a); ans=ans+(LL)c; if(ans>=INF)break; if(ans<=0)continue; if(dus(ans)==i)vec.push_back(ans); } cout<<vec.size()<<endl; sort(vec.begin(),vec.end()); for(int i=0;i<vec.size();i++) { printf("%d",vec[i]); if(i!=vec.size()-1)printf(" "); else puts(""); } } return 0;}C. Present
二分+贪心。也是一种水题的表现形式。。。。
二分一下结果，贪心看当前结果能不能达到。
#include <iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;#define LL __int64#define INF 1000000000#define maxn 220000LL a[maxn];LL b[maxn];LL flag[maxn];LL n,w;LL qiu(LL x){ memset(flag,0,sizeof(flag)); for(LL i=1;i<=n;i++) { b[i]=x-a[i]; } LL ch=0; LL ans=0; for(LL i=1;i<=n;i++) { ch-=flag[i]; b[i]-=ch; if(b[i]<0)b[i]=0; flag[i+w]+=b[i]; ch+=b[i]; ans+=b[i]; } return ans;}int main(){ LL m; while(~scanf("%I64d%I64d%I64d",&n,&m,&w)) { for(LL i=1;i<=n;i++)scanf("%I64d",&a[i]); LL l=0; LL r=1e9; r=r*2; LL mid=(l+r)/2; while(l<r) { if(qiu(mid)>m)r=mid; else l=mid+1; mid=(l+r)/2; } mid--; cout<<mid<<endl; } return 0;}D. Little Victor and Set
写这个题的时候要多悲剧有多悲剧，竟然在我认为最不可能错的地方写错了。
我很悲伤.
n=r-l+1;
若n
若k
当k=1时，很明显取l。
当k=2时，很明显取两个相邻的，并且只有末位不同的数，他们的异或结果为1.
当k=3时，第一个数取l，然后假如结果为0，算出剩下两个数的最小值。如果两个数最大的
不大于r，那我们就取这三个数，否则取两个数使得结果为1.
当k>=4时：
对于下面两个数交替处：
..........0111110 k-2
..........0111111 k-1
..........1000000 k
..........1000001 k+1
很明显我们可以看出来k-2,k-1,k,k+1的异或值为0。
因为n>20，我们一定能找出这种k。
#include <iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;#define LL __int64#define INF 1000000000#define maxn 220000void dos1(LL l,LL r,LL k){ LL n=r-l+1; LL st=((LL)1)<<n; LL ans=0; LL res=r+100; LL rst=0; LL len=0; for(LL i=1; i<st; i++) { ans=0; len=0; for(LL j=0; j<n; j++) { if(i&(((LL)1)<<j)) { ans=ans^(j+l); len++; } } if(len>k)continue; if(res>ans) { res=ans; rst=i; } } len=0; for(LL i=0; i<n; i++) { if(rst&(((LL)1)<<i))len++; } cout<<res<<endl; cout<<len<<endl; for(LL i=0; i<n; i++) { if(rst&(((LL)1)<<i)) { len--; cout<<(i+l); if(len)cout<<" "; else cout<<endl; } }}LL dos2(LL l,LL r,LL ks){ for(LL i=50; i>=0; i--) { if((l&(((LL)1)<<i))!=((r&(((LL)1)<<i)))) { LL k=((LL)1)<<i; LL n=(l>>i); n=(n<<i); n=n+k; k=n; if(k-2>=l&&k+1<=r) { return k; } else if(k-2<l)return dos2(k,r,ks); else if(k+1>r)return dos2(l,k-1,ks); } } return 0;}void dos3(LL l,LL r,LL k){ if(k==1) { cout<<l<<endl; cout<<"1"<<endl; cout<<l<<endl; return; } if(k==2) { cout<<"1"<<endl; cout<<"2"<<endl; if(l&1)l++; cout<<l<<" "<<l+1<<endl; return; } LL len=0; LL n=l; while(n) { len++; n=n/2; } LL a,b; a=b=0; int leap=0; a=b=(((LL)1)<<len); for(LL i=len; i>=0; i--) { if(l&(((LL)1)<<i)) { if(!leap)b+=(((LL)1)<<i); else a+=(((LL)1)<<i); leap++; } } if(b<=r) { cout<<"0"<<endl; cout<<"3"<<endl; cout<<l<<" "<<a<<" "<<b<<endl; } else { cout<<"1"<<endl; cout<<"2"<<endl; if(l&1)l++; cout<<l<<" "<<l+1<<endl; }}int main(){ LL l,r,k; while(~scanf("%I64d%I64d%I64d",&l,&r,&k)) { LL n=r-l+1; if(n<=20) { dos1(l,r,k); continue; } if(k<=3) { dos3(l,r,k); continue; } LL ans=dos2(l,r,k); cout<<"0"<<endl; cout<<"4"<<endl; for(LL i=ans-2; i<=ans+1; i++) { cout<<i; if(i!=ans+1)cout<<" "; else cout<<endl; } } return 0;}
