0+30+40+90, 菜。。。。。
T1 取石子
考试扔了将近两个小时，最后也没有回忆起博弈论的相关内容。。
现在只会50pts。正解待补。
#include<bits/stdc++.h>
using namespace std;
int n,a[500001],ans;
signed main()
{ freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{ ans=0;
for(int j=1;j<=n;++j)
{ int tmp=a[j];
ans^=tmp%(i+1); }
if(ans)printf("Alice ");
else printf("Bob ");
}
}
T2 大鱼吃小鱼
时间有限，快速拿了暴力30，然后走人。
其实线段树都码好了。在暴跳的过程中我认为就是暴跳，并没有分析出最多跳 $log$ 次，于是放弃了线段树。
改题时长时间困顿于吃完鱼节点的复原，其实节点不超过 $log^2$ 个，于是暴力修改即可。
要增强分析时间复杂度的能力。。
回归正题，一个明显的贪心是吃自己能吃的最大的鱼，找到第一个比自己体积大于等于的鱼（吃不了的），开吃，最终体积要先超过它，然后继续跳，直到吃不下了。因为每吃两次鱼体积要翻一倍，所以跳的次数是 $log$ 的。
线段树二分加上暴跳，复杂度 $O(nlog^2n)$。
#include<bits/stdc++.h>
#define int long long
#define N 1000500
using namespace std;
int n,q,w[N],san[N<<3],tot,ans,zhi,now,ne,tong1[N<<3];
bool bo=1,vis[N<<3],vvv=1;
struct jj
{int opt,s,k,w;}Q[N];
multiset<int>st;
struct tt{int sum,siz,tag;}tmp[N<<3];
struct zxb
{int sum[N<<3],siz[N<<3],tag[N<<3];
inline void pushup(int x)
{ if(!vis[x] and vvv){tong1[++zhi]=x,tmp[zhi]=(tt){sum[x],siz[x],tag[x]},vis[x]=1;}
sum[x]=sum[x<<1]+sum[x<<1|1];
siz[x]=siz[x<<1]+siz[x<<1|1];
return;
}
inline void pushdown(int x)
{
if(!vis[x<<1]){tong1[++zhi]=x<<1,tmp[zhi]=(tt){sum[x<<1],siz[x<<1],tag[x<<1]},vis[x<<1]=1;}
if(!vis[x<<1|1]){tong1[++zhi]=x<<1|1,tmp[zhi]=(tt){sum[x<<1|1],siz[x<<1|1],tag[x<<1|1]},vis[x<<1|1]=1;}
sum[x<<1]=sum[x<<1|1]=siz[x<<1]=siz[x<<1|1]=0;tag[x<<1]=tag[x<<1|1]=1;tag[x]=0;
}
inline void ins(int x,int l,int r,int pos,int val)
{ if(l==r)
{ siz[x]+=val;
sum[x]+=san[l]*val;
return;
}
int mid=(l+r)>>1;
if(mid<pos)ins(x<<1|1,mid+1,r,pos,val);
else ins(x<<1,l,mid,pos,val);
pushup(x);
}
inline int query(int x,int l,int r,int L,int R)
{ if(L>R)return 0;
if(l>=L and r<=R)return sum[x];
int mid=(l+r)>>1,res=0;
if(tag[x])pushdown(x);
if(mid<R and sum[x<<1|1])res+=query(x<<1|1,mid+1,r,L,R);
if(mid>=L and sum[x<<1])res+=query(x<<1,l,mid,L,R);
return res;
}
inline void calc(int x,int l,int r,int L,int R)
{ if(l==r and sum[x]>=ne)
{ if(!vis[x])
{tong1[++zhi]=x,tmp[zhi]=(tt){sum[x],siz[x],tag[x]},vis[x]=1;}
siz[x]-=(ne/san[l])+(ne%san[l]!=0); ans+=(ne/san[l])+(ne%san[l]!=0);
now+=((ne/san[l])+(ne%san[l]!=0))*san[l];ne-=((ne/san[l])+(ne%san[l]!=0))*san[l];
bo=0;
sum[x]=siz[x]*san[l];
return;
}
if(r<=R)
{ if(sum[x]<=ne)
{ ne-=sum[x];now+=sum[x];
if(ne<=0)bo=1;ans+=siz[x];
if(!vis[x])
{tong1[++zhi]=x,tmp[zhi]=(tt){sum[x],siz[x],tag[x]},vis[x]=1;}
sum[x]=0;siz[x]=0;tag[x]=1;
return;
}
}
int mid=(l+r)>>1;
if(tag[x])pushdown(x);
if(mid>=R){(void)calc(x<<1,l,mid,L,R);pushup(x);return ;}
if(bo and sum[x<<1|1])calc(x<<1|1,mid+1,r,L,R);
if(bo and sum[x<<1])calc(x<<1,l,mid,L,R);
pushup(x);
}
}tree;
inline void work(int s,int k)
{ int need=k-s,val;now=s;ans=0;zhi=0;
while(need>0 and now<k)
{ auto it=st.lower_bound(now);
if(it==st.end())val=999999999999999999;
else val=*it;
ne=min(need,val-now+1);int lst=ne;
int pos=lower_bound(san+1,san+1+tot,now)-san;bo=1;--pos;
if(pos)tree.calc(1,1,tot,1,pos);
else break;
if(ne>0)break;if(it==st.end())break;
need-=(lst-ne);
}
if(ne>0)puts("-1");
else printf("%lld\n",ans);
for(int i=1;i<=zhi;++i)
{ int x=tong1[i];
vis[x]=0;
tree.sum[x]=tmp[i].sum;
tree.siz[x]=tmp[i].siz;
tree.tag[x]=0;
}
}
signed main()
{ freopen("fish.in","r",stdin);
freopen("fish.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;++i)scanf("%lld",&w[i]),san[++tot]=w[i],st.insert(w[i]);
scanf("%lld",&q);
for(int i=1;i<=q;++i)
{ scanf("%lld",&Q[i].opt);
if(Q[i].opt==1)scanf("%lld%lld",&Q[i].s,&Q[i].k),san[++tot]=Q[i].s;
if(Q[i].opt==2)scanf("%lld",&Q[i].w),san[++tot]=Q[i].w;
if(Q[i].opt==3)scanf("%lld",&Q[i].w),san[++tot]=Q[i].w;
}
sort(san+1,san+1+tot);
tot=unique(san+1,san+1+tot)-san-1;
san[++tot]=999999999999999999;
for(int i=1;i<=n;++i)
{ int pos=lower_bound(san+1,san+1+tot,w[i])-san;
vvv=0;
tree.ins(1,1,tot,pos,1);
}
vvv=1;
for(int i=1;i<=q;++i)
{ if(Q[i].opt==1)
{ if(Q[i].s>=Q[i].k){puts("0");continue;}
work(Q[i].s,Q[i].k);
}
if(Q[i].opt==2)
{ vvv=0;
int pos=lower_bound(san+1,san+1+tot,Q[i].w)-san;
tree.ins(1,1,tot,pos,1);st.insert(Q[i].w);
vvv=1;
}
if(Q[i].opt==3)
{ vvv=0;
int pos=lower_bound(san+1,san+1+tot,Q[i].w)-san;
tree.ins(1,1,tot,pos,-1);st.erase(st.find(Q[i].w));
vvv=1;
}
}
}
T3 黑客
我竟然错过了一道水题，难受。。。。。
暴力循环做除法。。复杂度 $O(999^2)$ 。不算gcd。
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int a,b,c,d,ans,maxn;
signed main()
{ freopen("hacker.in","r",stdin);
freopen("hacker.out","w",stdout);
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
for(int i=2;i<=999;++i)
{ for(int j=1;j<i;++j)
{ int base1=j,base2=i-j;
if(__gcd(base1,base2)!=1)continue;
int a1=a/base1+(a%base1!=0),b1=b/base1;
int a2=c/base2+(c%base2!=0),b2=d/base2;
int l=max(a1,a2),r=min(b1,b2);
if(l>r)continue;
ans=(ans+i*(r-l+1)%mod)%mod;
}
}
printf("%lld\n",ans);
}
T4 黑客
这是续集，一眼数位 dp，然后开冲，冲完了一发过小样例，爽！
然后打开大样例，测了一下跑的贼 jb 快，信心倍增，然后查看输出结果，。。。。。。。。。
WOC，md 高精，不是 mod 1e9+7 吗？？？！！！
然后经历了极其漫长的调试过程。。最后 tmd 0 0 没 jb 输出掉了十分！！
#include<bits/stdc++.h>
using namespace std;
pair<int,int>dp[502][1<<9];
int n,m,k,sta[11],tot=1;
bool f[502][1<<9];
int gao[131002+10][978];
long long work[978];
inline void add(int i1,int i2)
{ for(int i=1;i<=gao[i2][0];++i)gao[i1][i]+=gao[i2][i];
gao[i1][0]=max(gao[i1][0],gao[i2][0]);
for(int i=1;i<=gao[i1][0];++i)
{ if(gao[i1][i]>=10)
{ if(i==gao[i1][0])++gao[i1][0];
gao[i1][i+1]+=gao[i1][i]/10;
gao[i1][i]%=10;
}
}
}
inline void add1(int i1)
{ for(int i=1;i<=work[0];++i)gao[i1][i]+=work[i];
gao[i1][0]=max(1ll*gao[i1][0],work[0]);
for(int i=1;i<=gao[i1][0];++i)
{ if(gao[i1][i]>=10)
{ if(i==gao[i1][0])++gao[i1][0];
gao[i1][i+1]+=gao[i1][i]/10;
gao[i1][i]%=10;
}
}
}
inline void www(int zhi)
{ int tt=work[0];
for(int i=1;i<=tt;++i)
work[i]*=zhi;
for(int i=1;i<=work[0];++i)
if(work[i]>=10)
{ if(work[0]==i)++work[0];
work[i+1]+=work[i]/10;
work[i]%=10;
}
}
inline void caonima(int i1,int base)
{ memset(work,0,sizeof(work));
for(int i=0;i<=gao[i1][0];++i)work[i]=gao[i1][i];
if(base)for(int i=work[0];i;--i)work[i+base]=work[i],work[i]=0;
work[0]+=base;
}
inline pair<int,int>dfs(int x,int lim)
{ if(f[x][lim])return dp[x][lim];
f[x][lim]=1;
int tmp1=++tot,tmp2=++tot;
if(x==n+1) return dp[x][lim]=make_pair(1,0); for(int i=1;i<=k;++i)
if(!(lim&(1<<i-1)))
{ pair<int,int>tmp=dfs(x+1,lim|sta[i]);
add(tmp1,tmp.first);
add(tmp2,tmp.second);
caonima(tmp.first,n-x);
www(i);
add1(tmp2);
}
return dp[x][lim]=make_pair(tmp1,tmp2);
}
signed main()
{ freopen("hacker2.in","r",stdin);
freopen("hacker2.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;++i)
{ int a,b;
scanf("%d%d",&a,&b);
sta[a]|=(1<<b-1);
}
gao[1][0]=1;gao[1][1]=1;
pair<int,int>ans=dfs(1,0);
int id1=ans.first,id2=ans.second;
if(!gao[id1][0])
{ cout<<0<<endl<<0<<endl;
return 0;
}
for(int i=gao[id1][0];i;--i)cout<<gao[id1][i];cout<<endl;
for(int i=gao[id2][0];i;--i)cout<<gao[id2][i];cout<<endl;
}
