A.小盆友的游戏
感觉题解解释的很牵强啊……还是打表找规律比较靠谱
对于每个人，它构造了一个期望函数$f(x)$，设它的跟班个数为$cnt[x]$，那么令$f(x)=2^{cnt[x]}-1$(？？鬼知道为什么要等于这个)
然后再定义当前局面的期望函数为每个人期望函数之和。
然后你会发现每次猜拳后局面期望函数变化量都是1
那么期望步数其实就是终止局面期望函数值-初始局面期望函数值
$ans=2^{n-1}-1-\sum (2^{cnt[x]}-1)$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int n,a[100005],cnt[100005];
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
cnt[a[i]]++;
}
ll ans=qpow(2,n-1)-1;ans=(ans+mod)%mod;
for(int i=1;i<=n;i++)
ans-=qpow(2,cnt[i])-1,ans=(ans+mod)%mod;
printf("%lld\n",ans);
return 0;
}
B.花
垃圾dp。考场上想麻烦了。kuku。
$dp[i][0/1]$表示前i个字符，已经/没有出现过Triple Kill的方案数
转移就行了……
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int T,n;
ll m,dp[100005][2];
void work()
{
scanf("%d%lld",&n,&m);
if(n<3){puts("0");return ;}
memset(dp,0,sizeof(dp));
dp[1][0]=m;dp[2][0]=m*m%mod;dp[3][0]=m*m%mod*m%mod;dp[3][0]=(dp[3][0]-m+mod)%mod;dp[3][1]=m;
for(int i=4;i<=n;i++)
{
(dp[i][0]+=dp[i-1][0]*(m-1)%mod)%=mod;
(dp[i][0]+=dp[i-2][0]*(m-1)%mod)%=mod;
(dp[i][1]+=dp[i-1][1]*(m-1)%mod)%=mod;
(dp[i][1]+=dp[i-2][1]*(m-1)%mod)%=mod;
(dp[i][1]+=dp[i-3][0]*(m-1)%mod)%=mod;
//cout<<i<<' '<<dp[i][0]<<' '<<dp[i][1]<<endl;
}
printf("%lld\n",dp[n][1]);
} int main()
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
scanf("%d",&T);
while(T--)work();
return 0;
}
C.表格
正解不会。闲的没事自主研发了个指针二维线段树的板子拿了个部分分。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int base=1001,M=2002,inf=0x3f3f3f3f;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int maxx=-inf,minx=inf,maxy=-inf,miny=inf,ans;
int n;
struct node
{
node *ls,*rs;
node *ys;
int v;
node()
{
ls=rs=NULL;
v=0;
}
/*void down()
{
if(this->ls!=NULL)this->ls->v=this->v;
if(this->rs!=NULL)this->rs->v=this->v;
}*/
};
node *root;
void judge(node *&k)
{
if(k==NULL)k=new node();
}
void upy(node *&k,int l,int r,int x,int y,int xx,int yy,int val)
{
if(y<=l&&yy>=r)
{
k->v=val;return ;
}
int mid=l+r>>1;
if(y<=mid)
{
judge(k->ls);
upy(k->ls,l,mid,x,y,xx,yy,val);
}
if(yy>mid)
{
judge(k->rs);
upy(k->rs,mid+1,r,x,y,xx,yy,val);
} } void upx(node *&k,int l,int r,int x,int y,int xx,int yy,int val)
{
if(x<=l&&xx>=r)
{
judge(k->ys);
upy(k->ys,1,M,x,y,xx,yy,val);
return ;
}
int mid=l+r>>1;
if(x<=mid)
{
judge(k->ls);
upx(k->ls,l,mid,x,y,xx,yy,val);
}
if(xx>mid)
{
judge(k->rs);
upx(k->rs,mid+1,r,x,y,xx,yy,val);
}
}
void asky(node *&k,int l,int r,int x,int y)
{
ans=max(ans,k->v);
if(l==r)return ;
int mid=l+r>>1;
if(y<=mid)
{
judge(k->ls);
asky(k->ls,l,mid,x,y);
}
else
{
judge(k->rs);
asky(k->rs,mid+1,r,x,y);
}
}
void askx(node *&k,int l,int r,int x,int y)
{
judge(k->ys);
asky(k->ys,1,M,x,y);
if(l==r)return ;
int mid=l+r>>1;
if(x<=mid)judge(k->ls),askx(k->ls,l,mid,x,y);
else judge(k->rs),askx(k->rs,mid+1,r,x,y);
}
int vis[100005];
#define F
int main()
{
#ifdef F
freopen("excel.in","r",stdin);
freopen("excel.out","w",stdout);
#endif
n=read();root=new node();
for(int q=1;q<=n;q++)
{
int x=read()+base+1,y=read()+base+1,xx=read()+base,yy=read()+base;
swap(x,y);swap(xx,yy);
minx=min(minx,x);maxx=max(maxx,xx);
miny=min(miny,y);maxy=max(maxy,yy);
upx(root,1,M,x,y,xx,yy,q);
}
int cnt=1;
for(int i=minx;i<=maxx;i++)
{
//puts(" ");
for(int j=miny;j<=maxy;j++)
{
ans=0;askx(root,1,M,i,j);
if(ans&&!vis[ans])vis[ans]=1,cnt++;
//cout<<ans<<' ';
}
} printf("%d\n",cnt);
return 0;
}