最近有幸膜到了贵省的题目，感觉非常有趣，就来更一发博客骗访问量...
好吧其实主要是这两天早上的校内赛是HNOI的题，所以今天就（抄）订（代）正（码）了一下来显得不是那么浪的样子..
【D1T1】亚瑟王
好神的DP题，自己只会30分..最后还是膜了老司机的代码才知道怎么做..从后往前考虑，令[tex]dp_{i,j}[/tex]表示只考虑[tex]i[/tex]以后的点第[tex]j[/tex]轮的期望贡献。转移分三种情况，后[tex]i[/tex]个点第[tex]j[/tex]轮的贡献产生在后[tex]i-1[/tex]个点的第[tex]j[/tex]轮或第[tex]j+1[/tex]轮以及产生在自己。然后就很好YY了，直接DP就行了。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
double x[500],dp[500][500];
int w[500],n,m;
int main(){
int t; scanf("%d",&t);
for (;t;t--){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%lf%d",&x[i],&w[i]);
}
memset(dp,0x00,sizeof dp);
for (int i=n;i;i--){
double now=1;
for (int j=1;j<=m;j++){
dp[i][j]=dp[i+1][j]*now*(1-x[i])+dp[i+1][j-1]*(1-now)+x[i]*now*w[i];
now=now*(1-x[i]);
}
}
double ans=0;
for (int i=1;i<=m;i++) ans+=dp[1][i];
printf("%.10lf\n",ans);
}
return 0;
}
【D1T2】接水果
这题还是挺简单的..首先整体二分显然，然后考虑求一条链覆盖了多少条标记链。先DFS序，把每一条链用端点的DFS序的二元组表示，那么覆盖一条链[tex](x,\ y)[/tex]的所有链[tex](a,\ b)[/tex]可以用[tex]a \in [l_1,\ r_1],\ b \in [l_2,\ r_2][/tex]的约束来表示。然后问题就转化成了矩形加，求单点的值，这是经典问题，直接差分后排序树状数组就好了。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct bian{
int next,point;
}b[81000];
struct atom{
int x,l,r,w,f;
}x[501000];
struct ask{
int u,v,size,where,now;
}y[41000];
int p[41000],len,n,m,q,dfs[41000],r[41000],sign,A[41000],ans[41000],father[41000][16],d[41000];
void ade(int k1,int k2){
b[++len]=(bian){p[k1],k2}; p[k1]=len;
}
void add(int k1,int k2){
ade(k1,k2); ade(k2,k1);
}
void dfs1(int k1,int k2){
dfs[k1]=++sign; father[k1][0]=k2; d[k1]=d[k2]+1;
for (int i=p[k1];i;i=b[i].next){
int j=b[i].point;
if (j!=k2) dfs1(j,k1);
}
r[k1]=sign;
}
void insert(int k1,int k2,int k3,int k4,int k5){
x[++len]=(atom){k1,k3,k4,k5,1};
x[++len]=(atom){k2+1,k3,k4,k5,-1};
}
void addin(int k1,int k2){
for (;k1<=n;k1+=k1&(-k1)) A[k1]+=k2;
}
int find(int k1){
int ans=0; for (;k1;k1-=k1&(-k1)) ans+=A[k1]; return ans;
}
int compare(atom k1,atom k2){
return k1.x<k2.x;
}
int compare2(ask k1,ask k2){
return k1.u<k2.u;
}
void findans(int l,int r,int k1,int k2,int k3,int k4){
if (l==r){
for (int i=k3;i<=k4;i++) ans[y[i].where]=l; return;
}
int mid=l+r>>1,now=k1;
for (int i=k1;i<=k2;i++) if (x[i].w<=mid) {swap(x[i],x[now]); now++;}
int a=k1; sort(x+k1,x+now,compare); sort(y+k3,y+k4+1,compare2);
for (int i=k3;i<=k4;i++){
while (a<now&&x[a].x<=y[i].u){
addin(x[a].l,x[a].f); addin(x[a].r+1,-x[a].f); a++;
}
y[i].now=find(y[i].v);
}
int num=k3;
for (int i=k3;i<=k4;i++)
if (y[i].size<=y[i].now){
swap(y[i],y[num]); num++;
} else y[i].size-=y[i].now;
for (int i=k1;i<a;i++){
addin(x[i].l,-x[i].f); addin(x[i].r+1,x[i].f);
}
if (num>k3) findans(l,mid,k1,now-1,k3,num-1);
if (num<=k4) findans(mid+1,r,now,k2,num,k4);
}
int findgo(int k1,int k2){
for (int i=16;i>=0;i--) if ((1<<i)<(d[k1]-d[k2])) k1=father[k1][i];
return k1;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for (int i=1;i<n;i++){
int k1,k2; scanf("%d%d",&k1,&k2); add(k1,k2);
}
dfs1(1,0); len=0;
for (int i=1;i<=15;i++)
for (int j=1;j<=n;j++) father[j][i]=father[father[j][i-1]][i-1];
for (;m;m--){
int k1,k2,k4; scanf("%d%d%d",&k1,&k2,&k4);
if (dfs[k1]>dfs[k2]) swap(k1,k2);
if (r[k1]>=r[k2]){
int k3=findgo(k2,k1);
insert(1,dfs[k3]-1,dfs[k2],r[k2],k4);
insert(dfs[k2],r[k2],r[k3]+1,n,k4);
}else insert(dfs[k1],r[k1],dfs[k2],r[k2],k4);
}
m=len;
for (int i=1;i<=q;i++){
scanf("%d%d%d",&y[i].u,&y[i].v,&y[i].size); y[i].where=i;
y[i].u=dfs[y[i].u]; y[i].v=dfs[y[i].v];
if (y[i].u>y[i].v) swap(y[i].u,y[i].v);
}
findans(0,1e9,1,m,1,q);
for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
【D1T3】菜肴制作
猜结论的题..我在考场上可能就磕个70分部分分就弃疗了？感觉我只有校内赛这种轻松愉快的弃疗氛围下才能做这种题啊..答案是把所有边倒过来的最大字典序再反过来..至于这个为什么对我怎么可能知道╭(╯^╰)╮
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
struct bian{
int next,point;
}b[110000];
int p[110000],n,d[110000],m,len,ans[110000];
priority_queue<int>Q;
void add(int k1,int k2){
b[++len]=(bian){p[k1],k2}; p[k1]=len; d[k2]++;
}
int main(){
int t; scanf("%d",&t);
for (;t;t--){
scanf("%d%d",&n,&m); len=0;
memset(d,0x00,sizeof d);
memset(p,0x00,sizeof p);
for (;m;m--){
int k1,k2; scanf("%d%d",&k1,&k2); add(k2,k1);
}
for (int i=1;i<=n;i++) if (d[i]==0) Q.push(i);
len=0;
while (!Q.empty()){
int k=Q.top(); Q.pop(); ans[++len]=k;
for (int i=p[k];i;i=b[i].next){
int j=b[i].point;
d[j]--; if (d[j]==0) Q.push(j);
}
}
if (len!=n) printf("Impossible!\n"); else {
for (int i=n;i;i--) printf("%d ",ans[i]); printf("\n");
}
}
return 0;
}
【D2T1】落忆枫音
有趣的题..可能是因为我看到生成树有种亲近感？首先一个DAG的脉络树的个数一定是除了1号点意外所有节点入度的乘积，这个考虑拓扑序很好证明。然后考虑加上一条边的情况，方法就是除去环的贡献。每一种成环方式对答案的贡献是不在环上的点的入度的乘积，于是就可以直接DP了，不怎么好描述还是看代码把。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
int d[110000],n,m,mo=1e9+7,p[110000],len,u,v,dp[110000],now;
vector<int>A;
struct bian{
int next,point;
}b[210000];
void add(int k1,int k2){
b[++len]=(bian){p[k1],k2}; p[k1]=len;
}
int quick(int k1,int k2){
int k3=1;
while (k2){
if (k2&1) k3=1ll*k3*k1%mo; k2>>=1; k1=1ll*k1*k1%mo;
}
return k3;
}
void dfs(int k){
if (dp[k]!=-1) return;
if (k==u){
dp[k]=1ll*now*quick(d[k],mo-2)%mo; return;
}
dp[k]=0;
for (int i=p[k];i;i=b[i].next){
int j=b[i].point;
dfs(j); dp[k]=(dp[k]+dp[j])%mo;
}
dp[k]=1ll*dp[k]*quick(d[k],mo-2)%mo;
}
int main(){
scanf("%d%d%d%d",&n,&m,&u,&v);
for (;m;m--){
int k1,k2; scanf("%d%d",&k1,&k2); add(k1,k2); d[k2]++;
}
now=1; d[v]++;
for (int i=2;i<=n;i++) now=1ll*now*d[i]%mo;
if (v==1){
printf("%d\n",now); return 0;
}
memset(dp,0xff,sizeof dp); dfs(v);
cout<<(now-dp[v]+mo)%mo<<endl;
return 0;
}
【D2T2】幻想乡开店
然而我并不会一个log的做法。总之我的方法是树剖大法好...显然查询一些关键点距离一个给定点在树上的距离可以直接用树链剖分做..每一个点的权值设置为到父亲那条边的长度，每插入一个点就是给它到根的路径上的所有点加上自己的权值，然后统计就是求出自己到根的所有点的当前值的和然后加加减减脑补一下就没了（大致同ZJOI2015D1T2的部分分）。然后这题就直接把链剖可持久化然后就两个log了，跑的还是不慢的就是空间很捉急。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
struct tree{
int l,r,num;
long long tot;
}t[20000000];
struct bian{
int next,point,w;
}b[310000];
int len,root[160000],n,Q,key,dfs[160000],f[160000],sign,a[160000],p[160000],size[160000],l[160000],where[160000],now,father[160000],tot;
long long d[160000],w[310000],A[310000],B[310000];
void ade(int k1,int k2,int k3){
b[++len]=(bian){p[k1],k2,k3}; p[k1]=len;
}
void add(int k1,int k2,int k3){
ade(k1,k2,k3); ade(k2,k1,k3);
}
void dfs1(int k1,int k2){
size[k1]=1; father[k1]=k2;
for (int i=p[k1];i;i=b[i].next){
int j=b[i].point;
if (j!=k2){
d[j]=d[k1]+b[i].w;
dfs1(j,k1); size[k1]+=size[j];
}
}
}
void dfs2(int k1,int k2,int k3){
int k=0,k4=0; w[++sign]=k3; dfs[k1]=sign;
for (int i=p[k1];i;i=b[i].next){
int j=b[i].point;
if (j!=k2&&size[j]>size[k]) {k=j; k4=b[i].w;}
}
if (k==0) return;
where[k]=where[k1]; dfs2(k,k1,k4);
for (int i=p[k1];i;i=b[i].next){
int j=b[i].point;
if (j!=k2&&j!=k){
now++; l[now]=j; where[j]=now; dfs2(j,k1,b[i].w);
}
}
}
int compare(int k1,int k2){
return f[k1]<f[k2];
}
void addin(int k1,int k2,int k3){
t[k1].num++; t[k1].tot+=w[k3]-w[k2-1];
}
void add(int k1,int k2,int k3,int k4,int k5){
len++; t[len]=t[k1];
if (k2>=k4&&k3<=k5){
addin(len,k2,k3); return;
}
int mid=k2+k3>>1; int now=len;
if (mid>=k4){
t[now].l=len+1; add(t[k1].l,k2,mid,k4,k5);
}
if (mid<k5){
t[now].r=len+1; add(t[k1].r,mid+1,k3,k4,k5);
}
t[now].tot=t[t[now].l].tot+t[t[now].r].tot+1ll*t[now].num*(w[k3]-w[k2-1]);
}
long long find(int k1,int k2,int k3,int k4,int k5){
if (k1==0||k2>k5||k3<k4) return 0;
if (k2>=k4&&k3<=k5) return t[k1].tot;
int mid=k2+k3>>1;
long long ans=find(t[k1].l,k2,mid,k4,k5)+find(t[k1].r,mid+1,k3,k4,k5);
ans+=t[k1].num*(w[min(k3,k5)]-w[max(k4,k2)-1]);
return ans;
}
int find1(int k){
int l=1,r=n+1,ans=n+1;
while (l<r){
int mid=l+r>>1;
if (f[a[mid]]>=k){
ans=mid; r=mid;
} else l=mid+1;
}
return ans;
}
int find2(int k){
int l=1,r=n+1,ans=0;
while (l<r){
int mid=l+r>>1;
if (f[a[mid]]<=k){
ans=mid; l=mid+1;
} else r=mid;
}
return ans;
}
int addin(int k1,int k2){
int root=k1;
while (k2){
int pre=root; root=len+1; add(pre,1,n,dfs[l[where[k2]]],dfs[k2]); k2=father[l[where[k2]]];
}
return root;
}
long long find(int k1,int k2){
long long ans=0;
while (k2){
ans+=find(k1,1,n,dfs[l[where[k2]]],dfs[k2]); k2=father[l[where[k2]]]; tot++;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&Q,&key);
for (int i=1;i<=n;i++){
scanf("%d",&f[i]);
}
for (int i=1;i<n;i++){
int k1,k2,k3; scanf("%d%d%d",&k1,&k2,&k3); add(k1,k2,k3);
}
dfs1(1,0); now=1; where[1]=1; l[1]=1; dfs2(1,0,0);
for (int i=1;i<=n;i++) a[i]=i;
sort(a+1,a+n+1,compare);
for (int i=1;i<=n;i++) w[i]+=w[i-1];
len=0;
for (int i=1;i<=n;i++){
root[i]=addin(root[i-1],a[i]);
}
for (int i=1;i<=n;i++) A[i]=A[i-1]+d[a[i]];
long long lastans=0;
for (;Q;Q--){
int u,l,r; scanf("%d%d%d",&u,&l,&r);
l=(l+lastans)%key; r=(r+lastans)%key;
if (l>r) swap(l,r);
l=find1(l); r=find2(r);
lastans=2*(-find(root[r],u)+find(root[l-1],u))+A[r]-A[l-1]+d[u]*(r-l+1);
printf("%lld\n",lastans);
}
return 0;
}
【D2T3】实验比较
校内赛的时候没有看到相等的一块怎么排列都算同一种，然后就弃疗了..晚上仔细一看发现是傻逼题。首先把所有等于缩起来，小于关系构成了一棵树，令[tex]dp_{i,j}[/tex]表示以[tex]i[/tex]为根的子树分成[tex]j[/tex]个相等的块的方案数，然后直接暴力枚举DP。转移的时候要求把[tex]i[/tex]个有序块和[tex]j[/tex]个有序块合并成[tex]k[/tex]个有序块的方案数，这个可以先大力DP跑出来，听说可以组合数？反正我不会。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct bian{
int next,point;
}b[300];
struct atom{
int k1,k2;
}x[300];
int pd[300],n,m,mo=1e9+7,father[300],dp[110][110][110][4],num[110][110][110],f[110][110],size[110],A[110],len,p[110],F[110];
char ch[10];
int findfather(int k){
if (k==father[k]) return k; father[k]=findfather(father[k]); return father[k];
}
void add(int k1,int k2){
b[++len]=(bian){p[k1],k2}; p[k1]=len;
}
void dfs(int k){
f[k][0]=1; size[k]=0;
for (int i=p[k];i;i=b[i].next){
int j=b[i].point; dfs(j);
memcpy(A,f[k],sizeof f[k]);
memset(f[k],0x00,sizeof f[k]);
for (int k1=0;k1<=size[k];k1++)
for (int k2=0;k2<=size[j];k2++)
for (int k3=0;k3<=k1+k2;k3++) f[k][k3]=(f[k][k3]+1ll*f[j][k2]*A[k1]%mo*num[k1][k2][k3])%mo;
size[k]+=size[j];
}
size[k]++;
for (int i=size[k];i;i--) f[k][i]=f[k][i-1]; f[k][0]=0;
}
int main(){
scanf("%d%d",&n,&m); int now=0;
for (int i=1;i<=n;i++) father[i]=i;
for (;m;m--){
int k1,k2; scanf("%d%s%d",&k1,ch+1,&k2);
if (ch[1]=='='){
k1=findfather(k1); k2=findfather(k2); father[k1]=k2;
} else x[++now]=(atom){k1,k2};
}
for (int i=1;i<=n;i++) if (father[i]!=i) pd[i]=1;
for (int i=1;i<=n;i++) F[i]=findfather(i);
for (int i=1;i<=now;i++){
int k1=findfather(x[i].k1),k2=findfather(x[i].k2);
if (k1==k2){
printf("0\n"); return 0;
}
father[k1]=k2;
add(F[x[i].k1],F[x[i].k2]); pd[F[x[i].k2]]=1;
}
for (int i=1;i<=n;i++) if (pd[i]==0) add(0,i);
dp[0][0][0][3]=1; num[0][0][0]=1;
for (int i=0;i<=n;i++)
for (int j=0;j<=n-i;j++)
for (int k=1;k<=i+j;k++){
if (i) dp[i][j][k][1]=(dp[i][j][k][1]+num[i-1][j][k-1])%mo;
if (j) dp[i][j][k][2]=(dp[i][j][k][2]+num[i][j-1][k-1])%mo;
if (i) dp[i][j][k][1]=(dp[i][j][k][1]+dp[i-1][j][k][0])%mo;
if (j) dp[i][j][k][3]=(dp[i][j][k][3]+dp[i][j-1][k][1])%mo;
for (int k1=0;k1<4;k1++) num[i][j][k]=(num[i][j][k]+dp[i][j][k][k1])%mo;
}
dfs(0);
int ans=0;
for (int i=1;i<=size[0];i++) ans=(ans+f[0][i])%mo;
cout<<ans<<endl; return 0;
}
评论 (0)
