Div2 A
建议评分：橙。
我的做法：不管，这是一道高精题（确信，使用高精模板即可。
时间复杂度(O(k+lg x))，空间复杂度(O(k))。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll SIZE=505;
ll x,k,ans[SIZE];
void print(ll *a){
ll i;
for(i=SIZE-1;i>0;i--) if(a[i]>0) break;
for(;i>=0;i--) cout<<a[i]; cout<<endl;
}
int main(){
cin>>x>>k;
ans[x]=1;
ans[0]+=k;
for(ll i=1;ans[i-1]>=10;i++){
ans[i]+=ans[i-1]/10;
ans[i-1]%=10;
}
print(ans);
return 0;
}
Div2 B
建议评分：黄。
结论题。
我们有如下几个结论：
- 对于任意给定的(a,b)，我们可以用一次(1)操作和一次(2)操作变成0。
证明：我们可以先用(1)操作，使得一个数变成(0)，另一个数变成一个非负数，然后再用(2)操作，将(0)乘上(x)，另一个数除以(x)，只要取(x)充分大可以全为(0)。
- 对于任意给定的(a,b)，我们可以用两次(2)操作变成0。
证明：我们可以先用(2)操作，使得一个数变成(0)，另一个数变成一个非负数，然后再用(2)操作，将(0)乘上(x)，另一个数除以(x)，只要取(x)充分大可以全为(0)。
- 当(a=b)时，可以只用一次(1)操作变成0。
证明：显然。
- 当(a=0)或(b=0)时，可以只用一次(2)操作变成0.
证明：使用一次(2)操作，将(0)乘上(x)，另一个数除以(x)，只要取(x)充分大可以全为(0)。
- 当(a=b=0)时，不需要任何操作。
证明：显然。
时空复杂度均为(O(1))。
代码：
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,ans;
int main(){
cin>>a>>b>>c>>d;
ans=min(c+d,d*2);
if(a==0&&b==0)ans=0;
if(a==0||b==0)ans=min(ans,d);
if(a==b)ans=min(ans,c);
cout<<ans<<endl;
return 0;
}
Div1 A
建议评分：蓝。
考虑贪心，我们可以发现对于每一个二进制位来说，我们更希望他是(1)，即使后面全都是(0)。
于是我们预处理出每一位上(0)的个数和(1)的个数，在查询的时候我们只要考虑如果这一位填(1)会不会导致后面无法填，这显然可以用前缀和维护一下。
具体地，令(sum_{i,j})表示(x)二进制下的第(i)位填(j)的贡献，(min_i)表示只考虑前(i)位的情况下，(sum(a_ioperatorname{xor}x))的最小值。
这里(sum_{i,j})可以暴力预处理，(min_i)就是(min{sum_{i,0},sum_{i,1}})的前缀和。
考虑从第一位开始往后填，设填到第(i)位时的要求为(m)，则只要(mge min_{i-1}+sum_{i,0})，就可以填(1)，否则填(0)。
时间复杂度(O((n+q)log m))，空间复杂度(O(n+log m))。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const ll N=100005,M=50;
ll n,q,m,a[N],sum[M][2],mi[M];
inline int getbit(ll x,int p){return (x&(1LL<<p))>>p;}
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
inline void read(ll&x){
x=0;char s=gc();
while(!isdigit(s))s=gc();
while(isdigit(s))x=x*10+(s^'0'),s=gc();
}
void print(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+'0');
}
int main(){
read(n);
for(ll i=1;i<=n;i++)read(a[i]);
for(ll i=0;i<M;i++)
for(ll j=1;j<=n;j++)
sum[i][getbit(a[j],i)]+=(1LL<<i);
mi[0]=min(sum[0][0],sum[0][1]);
for(ll i=1;i<M;i++)mi[i]=mi[i-1]+min(sum[i][0],sum[i][1]);
for(read(q);q--;){
read(m);
if(m<mi[M-1]){puts("-1");continue;}
ll ans=0;
for(ll i=M-1;i>=0;i--){
if(i==0&&m>=sum[i][0]||i>0&&m>=mi[i-1]+sum[i][0])ans|=(1LL<<i),m-=sum[i][0];
else m-=sum[i][1];
}
print(ans),puts("");
}
return 0;
}
Div1 B
暂时还不会。
Div1 C
暂时还不会。
Div1 D
暂时还不会。