这套题的难度还是十分兹磁的！
这真是水能载舟，亦可赛艇。
按Ctrl+A有福利。如果你能看到这句话就说明你是一个SB
T1
有两个人X、Y各有k/2（k为偶数）辆火车排列在长度为n的轨道上，从左向右火车依次属于X、Y、X、Y……，每次可以将1~m辆自己的火车分别移动若干距离，不能移出铁轨或越过相邻火车，首先无法操作的人败，求先手必胜的火车排布方案数。
昨天晚上看了一道阶梯博弈感觉自己萌萌哒！
然而写了一个和m完全没有关系的蒜法，结果cheat多了30分。。。
结论1：当所有火车都紧靠在一起时，先手必败。
证明：假设X将火车移动了x个单位，那么Y可以跟着移动x个单位，保持紧靠状态。
结论2：X只会将火车向右移，Y只会将火车向左移。
证明：若X将火车左移x个单位长度，那么Y可以将其右端的火车移动相邻的火车左移x个单位长度回到原来局面。
如果先手必败，这样操作不会使得答案更优；如果先手必胜，不会这样操作给自己增加变数。
结论3：每对相邻的火车是独立的，可以分开考虑。
证明略。
那么问题就转化为有k/2堆石子，每次可以选取1~m堆石子分别取出若干个，先取完者胜。
石子数即为两火车间的空位数。
结论4：如果每堆石子数量转化为二进制后每位1的个数都是(m+1)的倍数，那么先手必败。
证明：对于每个二进制位，若X将x个1变成了0，Y可以将(m-x+1)个1变成0；若X将x个0变成了1，Y可以再将它们变回0。
那么就可以利用dp统计答案。
令dp[i][j]表示确定了二进制前i位，放置了j个石子的先手必败方案数。
枚举每一位有q*(m+1)个1，那么：
[tex]dp[i+1][j+q*(m+1)*2^i]+=dp[i][j]*C_{\frac{k}{2}}^{q*(m+1)}[/tex]
最后用总方案数减去先手必败方案数即可。
T2
给出一个无向图，求x只经过边权小于等于y的边联通的第k大点权，强制在线。
送分题+码农题。（同BZOJ3551）
首先按照边权从小到大加边，然后用并查集维护，构建合并树（即若两点不连通就弄个新点作为这两个集合的父亲）。
对于每个询问，先用倍增爬到不超过y的最高祖先，然后在该祖先的子树中询问第k大。
直接处理出dfs序，然后可持久化线段树直接上啊！
T3
[tex]F[i]=\prod^{j^2<i}_{j=0}(i-j^2)[/tex]
给出l,r,p，求出有多少i满足i∈[l,r]且p|F[i]。
先挖个坑，待填。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int mod=1000000007;
int n,m,K,i,j,k,c[10010][1010];
ll ans,dp[16][10010];
int main(){
scanf("%d%d%d",&n,&K,&m);
K/=2;
for (i=0;i<=n;i++)c[i][0]=1;
for (i=1;i<=n;i++)
for (j=1;j<=min(i,2*K);j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
dp[0][0]=1;
for (i=0;i<=14;i++)
for (j=0;j<=n-2*K;j++){
for (k=0;j+k*(m+1)*(1<<i)<=n-2*K&&k*(m+1)<=K;k++)
dp[i+1][j+k*(m+1)*(1<<i)]=(dp[i+1][j+k*(m+1)*(1<<i)]+dp[i][j]*c[K][k*(m+1)]%mod)%mod;
}
for (i=0;i<=n-2*K;i++)ans=(ans+dp[15][i]*c[n-i-K][K]%mod)%mod;
printf("%lld\n",(c[n][K*2]-ans+mod)%mod);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,m,Q,x,y,k,i,Root,time,edgenum,cnt,ans;
int a[M],b[M],c[M],d[M],f[M],head[M],vet[M],next[M],st[M],ed[M],seq[M],root[M],mx[M][20],fa[M][20];
struct shit{int x,y,len;}e[M*3];
struct node{int l,r,w;}tree[M*20];
bool cmp(int x,int y){return a[x]<a[y];}
bool Cmp(shit x,shit y){return x.len<y.len;}
int search(int x){
if (f[x]!=x)f[x]=search(f[x]);
return f[x];
}
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
}
void dfs(int u,int pre){
int i,e,v;
st[u]=++time;seq[time]=c[u];
fa[u][0]=pre;
if (pre==0)mx[u][0]=1000000007;else mx[u][0]=max(d[u],d[pre]);
for (i=1;i<=18;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
mx[u][i]=max(mx[u][i-1],mx[fa[u][i-1]][i-1]);
}
for (e=head[u];e;e=next[e]){
v=vet[e];
dfs(v,u);
}
ed[u]=time;
}
int solve(int x){
int l=1,r=m;
while (l<r){
int mid=l+r+1>>1;
if (y<e[mid].len)r=mid-1;else l=mid;
}
return l;
}
void update(int x,int l,int r,int &p){
tree[++cnt]=tree[p];p=cnt;tree[p].w++;
if (l==r)return;
int mid=l+r>>1;
if (x<=mid)update(x,l,mid,tree[p].l);
else update(x,mid+1,r,tree[p].r);
}
int query(int x,int y,int l,int r,int k){
if (l==r)return l;
int mid=l+r>>1,tmp=tree[tree[y].l].w-tree[tree[x].l].w;
if (tmp>=k)return query(tree[x].l,tree[y].l,l,mid,k);
else return query(tree[x].r,tree[y].r,mid+1,r,k-tmp);
}
int main(){
scanf("%d%d%d",&n,&m,&Q);
for (i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=i;
sort(b+1,b+n+1,cmp);
for (i=1;i<=n;i++)c[b[i]]=i,d[i]=i;
for (i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].len);
sort(e+1,e+m+1,Cmp);
for (i=1;i<=n;i++)f[i]=i;
cnt=n;
for (i=1;i<=m;i++){
int p=search(e[i].x),q=search(e[i].y);
if (p!=q){
cnt++;
f[cnt]=cnt;
c[cnt]=n+1;
d[cnt]=n+i;
addedge(cnt,p);
addedge(cnt,q);
f[p]=cnt;
f[q]=cnt;
}
}
for (i=1;i<=cnt;i++){if (f[i]==i)dfs(i,0);}
for (i=1;i<=time;i++){
root[i]=root[i-1];
update(seq[i],1,n+1,root[i]);
}
while (Q--){
scanf("%d%d%d",&x,&y,&k);
y=solve(y)+n;
for (i=18;i>=0;i--)
if (mx[x][i]<=y)x=fa[x][i];
int l=st[x],r=ed[x];
k=(r-l+2)/2-k+1;
if (k<=0){ans=-1;puts("-1");continue;}
printf("%d\n",ans=a[b[query(root[l-1],root[r],1,n+1,k)]]);
}
}
评论 (0)
