POI2003
T1 Trinomial $(x^2+x+1)^n=((x+1)+x^2)^n$，枚举有几个$x^2$，就可以组合数算出对第i项的贡献，不过暴力算T了QAQ
在施大爷的帮助下拿到了标程，可还是不知道是怎么回事，好神啊，为什么求$C(n*2,m)*(m\ mod\ 2+1)$就行了呢?
#include<cstdio>
int n,x,i,q,ans;
int get(int n,int m){if(m>n)return 0;return n==2&&m==1?2:1;}
int C(int n,int m){return !m?1:C(n/3,m/3)*get(n%3,m%3)%3;}
int main(){
for(scanf("%d",&q);q--;printf("%d\n",ans))
for(scanf("%d%d",&n,&x),ans=i=0;i<=n&&i*2<=x;i++)ans=(ans+C(n,i)*C(n-i,x-i*2))%3;
}
#include<stdio.h>
int f[3]={1,1,2};long long n,m,t;
int C(int n,int m){return m>n?0:f[n]*f[m]*f[n-m]%3;}
int L(long long n,long long m){return m?C(n%3,m%3)*L(n/3,m/3)%3:1;}
int main(){
for(scanf("%lld",&t);t--;){
scanf("%lld%lld",&n,&m);
printf("%d\n",L(2*n,m)*(m%2+1)%3);
}
}
T2 Connections 就是一道求第$K$短路的题，要用到A*+优先队列，估价函数的值为从终点反着走到该点的值+走到目前的的值，每次选一个估价最小的点扩展，当终点扩展到第K次时就求得了第K短路，这样的时间复杂度是$O(nklgn)$的
一开始直接写了个裸求第K短路的，结果T了，然后看了下数据，发现起点终点相同的点很多，只要把答案排下序就可以了，不过要卡还是能被卡掉的。。实在不知道究竟怎样才能求单源K短路，这种算法只能求两点间的K短路啊。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 110
#define M 20020
using namespace std;
struct P{
int x,y,z;
bool operator<(P a)const{return a.x<x;}
};
struct E{int x,y,z,id;}p[M];
bool cmp(E a,E b){return a.x<b.x||a.x==b.x&&a.y<b.y||a.x==b.x&&a.y==b.y&&a.z<b.z;}
int n,m,i,j,k,x,y,z,tot,q,s,t,ans[N],cnt[N],d[N][N],fir[N],a[M],la[M],ne[M],va[M];
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;}
void getk(int s,int t){
priority_queue<P>Q;if(d[t][s]>1e9)return;
for(memset(cnt,0,sizeof(cnt)),Q.push(P{d[t][s],0,s});!Q.empty();){
P x=Q.top();Q.pop();
if(++cnt[x.z]>k)continue;
if(x.z==t)ans[cnt[t]]=x.x;
for(int i=fir[x.z];i;i=ne[i])Q.push(P{d[t][la[i]]+x.y+va[i],x.y+va[i],la[i]});
}
}
int main(){
for(memset(d,63,sizeof(d)),scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),d[y][x]=min(d[y][x],z);
for(i=1;i<=n;i++)d[i][i]=0;
for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(scanf("%d",&q),i=1;i<=q;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z),p[i].id=i;
for(sort(p+1,p+q+1,cmp),i=1;i<=q;i++)
if(p[i].x!=p[i+1].x||p[i].y!=p[i+1].y){
memset(ans,-1,sizeof(ans));
s=p[i].x;t=p[i].y;k=p[i].z;if(s==t)k++;getk(s,t);
for(j=i;p[j].x==p[j-1].x&&p[j].y==p[j-1].y;j--)a[p[j].id]=s==t?ans[p[j].z+1]:ans[p[j].z];
a[p[j].id]=s==t?ans[p[j].z+1]:ans[p[j].z];
}
for(i=1;i<=q;i++)printf("%d\n",a[i]);
}
T3 Chocolate 考虑每切一次将会付出的代价为另一个方向当前的总和，只要考虑切哪一边就可以了，很明显切最大值最大的一边花费的代价会更小
#include<cstdio>
#include<algorithm>
#define N 10010
using namespace std;
int n,m,i,p,q,ans,a[N],b[N];
int main(){
for(scanf("%d%d",&n,&m),n--,m--,i=1;i<=n;i++)scanf("%d",&a[i]),p+=a[i];
for(i=1;i<=m;i++)scanf("%d",&b[i]),q+=b[i];
for(ans=p+q,sort(a+1,a+n+1),sort(b+1,b+m+1);n+m;)if(a[n]>b[m])ans+=q,p-=a[n--];else ans+=p,q-=b[m--];
printf("%d",ans);
}
T7 Sequences without Stammers 呵呵。。太傻逼了
#include<cstdio>
int n;
int main(){
scanf("%d",&n);
if(n==1)puts("1");else if(n<=3)puts("2");else puts("3");
}
T8 Smugglers 对1号点正着做一遍最短路，反着做一遍最短路，取两个最短路的值+物品价值/2的最小值就是答案
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5050
#define M 100200
using namespace std;
int n,m,i,x,y,z,h,t,tot,top,ans,fir[N],fi2[N],a[N],q[N],d[N],e[N],va[M],v2[M],la[M],ne[M],l2[M],n2[M];bool v[N];
void in1(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void in2(int x,int y,int z){l2[++top]=y;v2[top]=z;n2[top]=fi2[x];fi2[x]=top;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(scanf("%d",&m);m--;)scanf("%d%d%d",&x,&y,&z),in1(x,y,z),in2(y,x,z);
for(memset(d,63,sizeof(d)),q[t=1]=1,v[1]=1,d[1]=0;h^t;)
for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]]){
d[y]=d[x]+va[i];
if(!v[y])v[q[t=t%n+1]=y]=1;
}
for(memset(e,63,sizeof(e)),memset(v,0,sizeof(v)),h=0,q[t=1]=1,v[1]=1,e[1]=0;h^t;)
for(i=fi2[x=q[h=h%n+1]],v[x]=0;i;i=n2[i])if(e[x]+v2[i]<e[y=l2[i]]){
e[y]=e[x]+v2[i];
if(!v[y])v[q[t=t%n+1]=y]=1;
}
for(ans=1e9,i=1;i<=n;i++)ans=min(ans,d[i]+e[i]+a[i]/2);
printf("%d",ans);
}
T11 Monkeys 因为只有删边操作，就可以倒着加边并查集判断，如果加入的边在一个并查集中则不用管，在不同并查集中时，如果一个和1在一个并查集，则要把另一个遍历一遍更新答案，如果都不和1在一个并查集中，要连一条边，这样每个点只会遍历一遍，所以复杂度是$O(m)$的
#include<cstdio>
#define N 202000
int n,m,i,j,tot,ans[N],c[N][2],q[N<<1][2],fa[N],fir[N],ne[N<<2],la[N<<2];bool v[N][2];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void dfs(int x,int fa,int z){
ans[x]=z;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,z);
}
void ins(int x,int y,int z){
int p=gf(x),q=gf(y);
if(y<0||p==q)return;
if(p==gf(1))dfs(y,x,z);else if(q==gf(1))dfs(x,y,z);else ins(x,y),ins(y,x);
fa[p]=q;
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d",&c[i][0],&c[i][1]),fa[i]=i;
for(i=0;i<m;i++)scanf("%d%d",&q[i][0],&q[i][1]),q[i][1]--,v[q[i][0]][q[i][1]]=1;
for(i=1;i<=n;i++)for(j=0;j<2;j++)if(!v[i][j])ins(i,c[i][j],-1);
for(i=m-1;~i;i--)ins(q[i][0],c[q[i][0]][q[i][1]],i);
for(puts("-1"),i=2;i<=n;i++)printf("%d\n",ans[i]);
}
T13 Sums 考虑最短路建图，$d[i]$表示拼出$x$中最小的满足$x\ mod\ a[1]==i$的值，然后最短路建图，$d[x]$向$d[(x+a[i])\ mod\ m]$连一条价值为$a[i]$的边，对于每个询问$x$，如果$d[x\ mod\ m]\leq x$则合法，否则不合法
#include<cstdio>
#include<cstring>
#define N 50500
int n,m,i,h,t,x,y,Q,a[N],d[N],q[N];bool v[N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(m=a[1],memset(d,63,sizeof(d)),d[0]=0,q[t=1]=0,v[0]=1;h!=t;)
for(v[x=q[h=h%m+1]]=0,i=1;i<=n;i++)if(d[x]+a[i]<d[y=(x+a[i])%m]){
d[y]=d[x]+a[i];
if(!v[y])v[q[t=t%m+1]=y]=1;
}
for(scanf("%d",&Q);Q--;puts(d[x%m]<=x?"TAK":"NIE"))scanf("%d",&x);
}
T14 Shuffle 题目的意思就是给出$k$和置换$b$，求置换$a$使得$a^k=b$
设一个置换$a$的长度是$L$，求它的$k$次，是$gcd(L,k)$个长度为$\frac{L}{gcd(L,k)}$的循环
现在我们已经知道置换$b$的长度$P$，则$P=\frac{L}{gcd(L,k)}$，我们的目标就是求得这个最小的L
$L$取到最小值时对于$P$的任何一个质因子$p$，$p$在$L$中出现的次数等于$p$在$P$中出现的次数和在$k$中出现次数之和
这样就求出了最小的$L$，将$\frac{L}{gcd(L,k)}$个长度为$P$的循环合并就可以了~
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 1001000
using namespace std;
int n,k,i,j,u,t,p,L,a[N],ans[N];bool v[N];
vector<int>st[N];
bool cmp(vector<int> a,vector<int> b){return a.size()<b.size();}
int get(int x,int y){
int i=2,ans=1;
for(;i*i<=x;i++)if(x%i==0){
for(;x%i==0;x/=i)ans*=i;
for(;y%i==0;y/=i)ans*=i;
}
if(x!=1)for(ans*=x;y%x==0;y/=x)ans*=x;
return ans;
}
int main(){
for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)if(!v[i])for(v[p=i]=1,st[++t].push_back(i);!v[a[p]];v[p]=1)st[t].push_back(p=a[p]);
for(sort(st+1,st+t+1,cmp),i=1;i<=t;i+=p){
for(L=get(st[i].size(),k),p=__gcd(L,k),j=0;j<p;j++)
for(u=0;u<st[i+j].size();u++)
a[(j+(long long)u*k)%L]=st[i+j][u];
for(j=0;j<L;j++)ans[a[j]]=a[(j+1)%L];
}
for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}
除了一道神题，剩下的题都1A或者0A，不切啦~
评论 (0)
