距离杯赛已经很久了，然而我现在才打总结。。
我好惨的说..两场才380。。。
DAY 1
第一题 toy
送分题，模拟的时候+一下再mod一下就好。
[当时打完这题就没再看一眼了，好方的说]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 100010 int a[Maxn];
char s[Maxn][]; int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
scanf("%d",&a[i]);
scanf("%s",s[i]);
}
int now=;
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
y%=n;
if(a[now]==&&x==) now=(now+y)%n;
else if(a[now]==) now=(now+n-y)%n;
else if(x==) now=(now+n-y)%n;
else now=(now+y)%n;
}
printf("%s\n",s[now]);
return ;
}
第二题 running
感觉这题是全场最难的【是吧？？
但其实【啊好像也不是很难。。
怎么比赛的时候就脑子那么乱呢
我的方法是，把路径分成两段，然后lca的特殊算。
假如lca在st上面，假设这条路径对z有贡献(z在lca和st之间)，那么dep[z]-dep[st]=w[z] => dep[z]-w[z]=dep[st]
那么对于z来说，就是求经过自己的路径中dep等于dep[z]-w[z]的有多少个。
对于路径，我们在st上打一个加入标记，在lca上打一个删除标记，那么对于z，就是求其子树和（每个点用dfs序做，问题变成求区间和，单点修改，区间询问，可以用树状数组维护）。
对于加入和删除，我们按照st的dep排序，对于每个点，我们按照dep[z]-dep[st]排序，值相等是一起做，这时O(n+m)的。
对于右半边的路径类似，有2*dep[lca]-dep[st]=dep[z]+w[z]。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 300010
#define Maxm 300010 struct node
{
int x,y,next,c;
}t[Maxn*];int len=;
int n,m; struct hp
{
int x,y,c;
}q[Maxm],qq[Maxm],nq[Maxn];
int l1,l2; int first[Maxn]; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} bool cmp(hp x,hp y) {return x.c<y.c;} int son[Maxn],dep[Maxn],sm[Maxn];
int fa[Maxn];
void dfs(int x,int f)
{
sm[x]=;dep[x]=dep[f]+;
fa[x]=f;
son[x]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
int y=t[i].y;
dfs(y,x);
sm[x]+=sm[y];
if(sm[y]>sm[son[x]]) son[x]=y;
}
} int tp[Maxn],dfn[Maxn],rt[Maxn],cnt=;
void dfs2(int x,int tpp)
{
tp[x]=tpp;rt[x]=dfn[x]=++cnt;
if(son[x]) dfs2(son[x],tpp),rt[x]=rt[son[x]];
for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x]&&t[i].y!=son[x])
{
int y=t[i].y;
dfs2(y,y);
rt[x]=rt[y];
}
} int lca(int x,int y)
{
int tt;
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]]) tt=x,x=y,y=tt;
x=fa[tp[x]];
}
if(dep[x]<dep[y]) return x;
return y;
} int w[Maxn],ans[Maxn],c[Maxn]; void add(int x,int y)
{
for(int i=x;i<=n;i+=i&(-i))
c[i]+=y;
} int query(int l,int r)
{
int ans=;
for(int i=r;i>=;i-=i&(-i))
ans+=c[i];
l--;
for(int i=l;i>=;i-=i&(-i))
ans-=c[i];
return ans;
} void ffind()
{
int l,r;
l=,r=;
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
int x=nq[i].x;
if(i==||nq[i].c!=nq[i-].c)
{
for(int j=l;j<r;j++)
{
add(q[j].x,-),add(q[j].y,);
}
l=r;
while(q[l].c<nq[i].c&&l<=l1) l++;
r=l;
}
while(q[r].c==nq[i].c&&r<=l1)
{
add(q[r].x,);add(q[r].y,-);
//printf("add %d\n",r);
r++;
}
ans[x]+=query(dfn[x],rt[x]);
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
for(int i=;i<=n;i++) scanf("%d",&w[i]);
dfs(,);
dfs2(,);
l1=l2=;
memset(ans,,sizeof(ans));
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d",&x,&y);
z=lca(x,y);
q[++l1].x=dfn[x];q[l1].y=dfn[z];q[l1].c=dep[x];
qq[++l2].x=dfn[y];qq[l2].y=dfn[z];qq[l2].c=*dep[z]-dep[x]; if(w[z]==dep[x]-dep[z]) ans[z]++;
}
sort(q+,q++l1,cmp);
for(int i=;i<=n;i++) nq[i].x=i,nq[i].c=dep[i]+w[i];
sort(nq+,nq++n,cmp);
ffind(); for(int i=;i<=l2;i++) q[i]=qq[i];
l1=l2;
sort(q+,q++l1,cmp);
for(int i=;i<=n;i++) nq[i].x=i,nq[i].c=dep[i]-w[i];
sort(nq+,nq++n,cmp);
ffind(); for(int i=;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
return ;
}
第三题 classroom
其实是一个很明显的期望DP。【当时脑抽again = = toxic
状态f[i][j][0]表示前i段，用j次机会，最后一次不使用机会的期望值。
状态f[i][j][1]表示前i段，用j次机会，最后一次使用机会的期望值。
f[i][j][0]=min(f[i-1][j][0]+1.0*dis[c[i-1]][c[i]])
f[i][j][0]=min(f[i-1][j][1]+1.0*dis[d[i-1]][c[i]]*k[i-1]+(1-k[i-1])*dis[c[i-1]][c[i]]);
f[i][j][1]=min(f[i-1][j-1][0]+k[i]*(dis[c[i-1]][d[i]])+(1-k[i])*(dis[c[i-1]][c[i]]));
f[i][j][1]=min(f[i-1][j-1][1]+ k[i]*(dis[d[i-1]][d[i]]*k[i-1]+dis[c[i-1]][d[i]]*(1-k[i-1]))+ (1-k[i])*(dis[d[i-1]][c[i]]*k[i-1]+dis[c[i-1]][c[i]]*(1-k[i-1])));
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define Maxn 2010
#define INF 0xfffffff int c[Maxn],d[Maxn];
double f[Maxn][Maxn][],k[Maxn]; int n,m,v,e; int mmin(int x,int y) {return x<y?x:y;}
double mymin(double x,double y) {return x<y?x:y;} int dis[Maxn][Maxn]; void floyd()
{
for(int l=;l<=v;l++)
for(int i=;i<=v;i++)
for(int j=;j<=v;j++)
dis[i][j]=mmin(dis[i][j],dis[i][l]+dis[l][j]);
} int main()
{
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=;i<=n;i++) scanf("%d",&c[i]);
for(int i=;i<=n;i++) scanf("%d",&d[i]);
for(int i=;i<=n;i++) scanf("%lf",&k[i]);
memset(dis,,sizeof(dis));
for(int i=;i<=e;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
dis[x][y]=mmin(dis[x][y],c);
dis[y][x]=mmin(dis[y][x],c);
}
for(int i=;i<=v;i++) dis[i][i]=;
floyd(); for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
f[i][j][]=f[i][j][]=INF;
double ans=INF;
f[][][]=f[][][]=;f[][][]=;
for(int i=;i<=n;i++)
for(int j=;j<=i&&j<=m;j++)
{
//printf("%.2lf\n",ans);
//bu yong
f[i][j][]=mymin(f[i][j][],f[i-][j][]+1.0*dis[c[i-]][c[i]]);
f[i][j][]=mymin(f[i][j][],f[i-][j][]+1.0*dis[d[i-]][c[i]]*k[i-]+(-k[i-])*dis[c[i-]][c[i]]); //yong
if(j>)
{
f[i][j][]=mymin(f[i][j][],f[i-][j-][]+k[i]*(dis[c[i-]][d[i]])+(-k[i])*(dis[c[i-]][c[i]]));
f[i][j][]=mymin(f[i][j][],f[i-][j-][]+
k[i]*(dis[d[i-]][d[i]]*k[i-]+dis[c[i-]][d[i]]*(-k[i-]))+
(-k[i])*(dis[d[i-]][c[i]]*k[i-]+dis[c[i-]][c[i]]*(-k[i-])));
}
}
for(int i=;i<=m&&i<=n;i++) ans=mymin(ans,f[n][i][]),
ans=mymin(ans,f[n][i][]);
printf("%.2lf\n",ans);
return ;
}
第一天 100+25+55 哭泣
第二题交了纯暴力，第三题错误DP。。
DAY 2
第一题 problem
用杨辉三角搞一搞就好了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define Maxn 2010 int p[Maxn],f[Maxn][Maxn];
int k; int c[Maxn][Maxn],ans[Maxn][Maxn]; void init()
{
for(int i=;i<=;i++) c[i][]=;
for(int i=;i<=;i++)
for(int j=;j<=i;j++)
c[i][j]=(c[i-][j-]+c[i-][j])%k; memset(f,,sizeof(f));
for(int i=;i<=;i++)
{
f[i][]=;
for(int j=;j<=i;j++)
{
f[i][j]=f[i][j-];
if(c[i][j]==) f[i][j]++;
}
for(int j=i+;j<=;j++) f[i][j]=f[i][j-];
}
for(int i=;i<=;i++) ans[][i]=f[][i];
for(int i=;i<=;i++)
for(int j=;j<=;j++) ans[i][j]=ans[i-][j]+f[i][j];
} int main()
{
int T;
scanf("%d%d",&T,&k);
init();
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",ans[n][m]);
}
return ;
}
第二题 earthworm
在暴力的基础上看出来有单调性就可以AC了。
切出来的左边递减，右边也递减，每次取三部分的最大值出来切，注意不要想成全部+q，用一个累加器，然后切出来的那部分-q是一样的。
//代码很丑，因为在洛谷上调TLE，，洛谷好慢的说。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define Maxn 100010
#define Maxm 7000010
#define INF 0xfffffff
#define LL long long int a[Maxn]; LL add=;
LL v1[Maxm],v2[Maxm]; int n,m,q,u,v,t;
int l1,l2; bool cmp(int x,int y) {return x>y;} int main()
{
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
sort(a+,a++n,cmp);
l1=,l2=;
v1[]=v2[]=;
a[]=;
for(LL i=;i<=m;i++)
{ LL now=-INF;
now*=;
if(a[]<=n) now=now>a[a[]]?now:a[a[]];
if(l1<=v1[]) now=now>v1[l1]?now:v1[l1];
if(l2<=v2[]) now=now>v2[l2]?now:v2[l2];
if(a[]<=n&&now==a[a[]]) a[]++;
else if(l1<=v1[]&&now==v1[l1]) l1++;
else if(l2<=v2[]&&now==v2[l2]) l2++;
now+=add; if(i%t==) printf("%lld ",now);
add+=q;
LL x=now*u/v,y=now-x;
v1[++v1[]]=x-add;v2[++v2[]]=y-add;
}
printf("\n");
for(int i=;i<=n+m;i++)
{ LL now=-INF;
now*=;
if(a[]<=n) now=now>a[a[]]?now:a[a[]];
if(l1<=v1[]) now=now>v1[l1]?now:v1[l1];
if(l2<=v2[]) now=now>v2[l2]?now:v2[l2];
if(a[]<=n&&now==a[a[]]) a[]++;
else if(l1<=v1[]&&now==v1[l1]) l1++;
else if(l2<=v2[]&&now==v2[l2]) l2++;
now+=add; if(i%t==) printf("%lld ",now);
}
printf("\n");
return ;
}
第三题 angrybirds
其实就是状压dp啊
注意精度，不要*100然后强转int【我就死在强转int，不然用round也可以
还有一个小地方就是，你可能会枚举两个点，是18^2的，但是其实你可以只枚举一个点，规定这一次一定先把某头猪弄下来（因为你后面总有一次要把这头猪弄下来的，不如现在先做了，反正没什么区别），这样就是一个18，这样就可以过了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define Maxd 300010
#define INF 0xfffffff double xx[],yy[]; int f[Maxd];
int n,m; int gcd(int a,int b)
{
if(b==) return a;
return gcd(b,a%b);
} double fabs(double x) {return x<?-x:x;} int sum;
int get_s(int a,int b,int s)
{
int ss=s;
double A,B;
A=(xx[b]*yy[a]-xx[a]*yy[b])*1.0/(xx[b]*xx[a]*xx[a]-xx[a]*xx[b]*xx[b]);
B=(yy[a]-A*xx[a]*xx[a])*1.0/xx[a];
if(A>=)
{
return -;
}
sum=;
for(int i=;i<=n;i++) if((<<i-)&s)
{
if(fabs(A*xx[i]*xx[i]+B*xx[i]-yy[i])<0.000001) ss^=(<<i-),sum++;
}
return ss;
} int mymin(int x,int y) {return x<y?x:y;} int ffind(int s)
{
if(f[s]!=-) return f[s];
f[s]=INF;
for(int i=;i<=n;i++) if((<<i-)&s)
{
for(int j=i+;j<=n;j++) if((<<j-)&s)
{
int ss=get_s(i,j,s);
if(ss!=-) f[s]=mymin(f[s],ffind(ss)+);
}
break;
}
for(int i=;i<=n;i++) if((<<i-)&s)
{
f[s]=mymin(f[s],ffind(s-(<<i-))+);
break;
}
return f[s];
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
double nx,ny;
scanf("%lf%lf",&nx,&ny);
xx[i]=nx;yy[i]=ny;
}
memset(f,-,sizeof(f));
f[]=;
int ans=ffind((<<n)-);
printf("%d\n",ans);
}
return ;
}
第二天 100+55+70 哭泣
被虐的好惨，主要是还是太傻了，其实题目说难也不是很难的。。。。
上面是bac回的AC代码。。。。
2016-12-07 14:02:45