A. Alchemy
分析
暴力就是 (2^n) 的枚举
但是可以发现，如果当前的最大值在左边，那么后面的一步肯定要移动，只递归前面的一步并把后面的贡献加上即可
如果最大值在右边，那么前面的一步肯定已经移动完了，只需要关心后面的一步即可
如果最大值在中间，说明这一步是多余的
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<vector>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=105;
long long ans=0;
int n,t,cnt[maxn],a[maxn][maxn],vis[maxn],jud=0;
long long dfs(int i,int from,int mid,int to){
if(i==0) return 0;
if(vis[i]==mid) return jud=1;
else if(vis[i]==from) return (1LL<<(i-1))+dfs(i-1,from,to,mid);
else return dfs(i-1,mid,from,to);
}
int main(){
t=read();
while(t--){
n=0,ans=0,jud=0;
for(rg int i=1;i<=3;i++){
cnt[i]=read();
n+=cnt[i];
for(rg int j=1;j<=cnt[i];j++) a[i][j]=read(),vis[a[i][j]]=i;
}
rg long long tmp=dfs(n,1,2,3);
if(jud) printf("No
");
else printf("%lld
",tmp);
}
return 0;
}
B. Algebra
分析
暴力的做法是从小到大枚举最后的结果，判断其是否合法
正解的做法是枚举一个 (cnt) ，表示数位的和
求出 (f(x,a)=cnt) 和 (f(x,b)=cnt) 的交集中最小的元素
设 (next(n,k,s)) 求大于等于 (n) 的第一个满足 (f(x,k)=s) 的数
这个可以贪心地从高位向低位填
令 (g(s)) 表示大于等于 (n) 的满足 (f(x,a)=f(x,b)=s) 的整数不小于 (g(s))
简单来说，就是不断迭代使得 (g(s)) 增加到第一个满足 (f(x,a)=f(x,b)=s) 的数
初始的时候令 (g(s)) 等于 (n)
然后把所有的 (cnt) 扔进一个小根堆里，每次取出 (g(s)) 最小的更新为 (max(nxt(g(s),a,cnt),nxt(g(s),b,cnt)))
如果不能更新就输出答案
大概更新 (sqrt{n}) 次就能算出结果
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#define rg register
const int maxn=405;
int t,a,b,num[maxn],numcnt,tmp[maxn],tmpcnt;
long long n;
bool jud(rg int wz,rg int val,rg int sy,rg int bas){
if(val<0 || (wz-1)*(bas-1)<sy) return 0;
rg int pd=0;
for(rg int i=numcnt+1;i>=wz;i--){
if(tmp[i]>num[i]){
pd=1;
break;
} else if(tmp[i]<num[i]){
return 0;
}
}
if(pd) return 1;
for(rg int i=wz-1;i>=1;i--){
if(sy<num[i]) return 0;
if(num[i]!=bas-1){
if(sy>num[i]) return 1;
sy-=num[i];
} else {
sy-=num[i];
}
}
return 1;
}
long long getnxt(rg long long val,rg int bas,rg int cnt){
for(rg int i=1;i<=numcnt+2;i++) num[i]=0;
numcnt=0;
while(val){
num[++numcnt]=val%bas;
val/=bas;
}
if((numcnt+1)*(bas-1)<=cnt){
rg long long nans=0,mi=1;
while(cnt){
if(mi>1e17) return 1e18;
if(cnt>bas-1){
nans+=mi*(bas-1);
cnt-=(bas-1);
} else {
nans+=mi*cnt;
cnt=0;
}
mi*=bas;
}
return nans;
}
tmp[numcnt+2]=0;
for(rg int i=numcnt+1;i>=1;i--){
cnt-=tmp[i+1];
for(tmp[i]=std::min(cnt,bas-1);;tmp[i]--){
if(!jud(i,tmp[i],cnt-tmp[i],bas)){
tmp[i]++;
break;
}
}
if(tmp[i]>std::min(cnt,bas-1)) return 1e18;
}
rg long long nans=0,mi=1;
for(rg int i=1;i<=numcnt+1;i++){
nans+=tmp[i]*mi;
mi*=bas;
}
return nans;
}
struct jie{
int s;
long long gs;
jie(){}
jie(rg int aa,rg long long bb){
s=aa,gs=bb;
}
bool operator < (const jie& A)const{
return gs>A.gs;
}
};
std::priority_queue<jie> q;
void clear(){
std::priority_queue<jie> tmp;
std::swap(q,tmp);
}
int main(){
scanf("%d",&t);
while(t--){
clear();
scanf("%lld%d%d",&n,&a,&b);
for(rg int i=1;i<=400;i++) q.push(jie(i,n));
while(!q.empty()){
rg int tmp1=q.top().s;
rg long long tmp2=q.top().gs;
q.pop();
rg long long tmp3=std::max(getnxt(tmp2,a,tmp1),getnxt(tmp2,b,tmp1));
if(tmp3==tmp2){
printf("%lld
",tmp2);
break;
}
q.push(jie(tmp1,tmp3));
}
}
return 0;
}
C. Anarchy
