hzwer出喪題虐人啦 ACM賽制 4/7
A.惱人的青蛙
題目大意：給定N*M矩陣上K個點，定義一條合法路徑為從矩形外一點沿一條直線穿過矩形，每次走相同長度且在矩形内每步都要踩在給定點上，問經過給定點最多的路徑經過幾個點（若小于3輸出0）（N,M,K<=5000）。
思路：把點按橫坐标第一關鍵字縱坐标第二關鍵字排序，f[i][j]表示有一條到i的路徑，i上一個點是j，此時路徑經過點數，每次确定i,j後就可以根據i,j算出j再前一個點的坐标，直接轉移，複雜度O(K^2)。評測機極慢稍微卡卡常才能過。
#include<cstdio>
#include<algorithm>
using namespace std;
#define MN 5000
struct P{int x,y;}p[MN+5];
bool cmp(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
short g[MN+5][MN+5],f[MN+5][MN+5];
int n,m,k,i,j,x,y,ans=0;
inline int G(int x,int y){return x>0&&x<=n&&y>0&&y<=m?g[x][y]:-1;}
inline int cal(int a,int b){return (a<<1)-b;}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=k;++i)scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+k+1,cmp);
for(i=1;i<=k;++i)
{
g[p[i].x][p[i].y]=i;
for(j=1;j<i;++j)
{
x=G(cal(p[j].x,p[i].x),cal(p[j].y,p[i].y));
f[i][j]=x?x<0?2:f[j][x]+1:-k;
if(G(cal(p[i].x,p[j].x),cal(p[i].y,p[j].y))<0&&f[i][j]>ans)ans=f[i][j];
}
}
printf("%d",ans<3?0:ans);
} C.本原串
題目大意：求所有長度為N的01串中有多少個不存在小于N的循環節（循環節長度應能整除N），答案對2008取模（N<=100,000,000）。
思路：長度為N的01串有2^N個，考慮去掉有循環節的，先O(N^0.5)求出N的所有因數，排序，對所有小于N的因數記si=-1表示以該因數為循環節的01串個數對答案貢獻的倍數。從大往小計算，遇到第i個因數ai，答案加上si*2^ai，由于可能被重複統計，對每個i再向前找到第j個因數滿足j<i且aj整除ai，sj-=si，ai的所有因數必然都被n的所有因數包含，這樣即可不重不漏的統計。複雜度不好計算，總之很靠譜，O(能過)。
#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 2008
int pw(int y)
{
int r=1,t=2;
for(;y;y>>=1,t=t*t%MOD)if(y&1)r=r*t%MOD;
return r;
}
#define MN 20000
int n,z[MN+5],zn,s[MN+5];
int main()
{
int i,j,ans;
while(~scanf("%d",&n))
{
for(zn=0,i=1;i*i<n;++i)if(n%i==0)z[++zn]=i,z[++zn]=n/i;
if(i*i==n)z[++zn]=i;
sort(z+1,z+zn+1);
for(ans=pw(n),i=1;i<zn;++i)s[i]=-1;
for(i=zn;--i;)
{
ans=(ans+s[i]*pw(z[i]))%MOD;
for(j=i;--j;)if(z[i]%z[j]==0)s[j]=(s[j]-s[i])%MOD;
}
printf("%d\n",(ans+MOD)%MOD);
}
} D.Optimal Milking
題目大意：K台機器，C頭奶牛，每頭奶牛對應一台機器，每台機器對應不超過M頭奶牛，給出K+C個點的圖，每個點表示一頭奶牛或一台機器，要求最小化奶牛機器成功配對後奶牛到其配對機器路徑長度的最大值，求出這個值。（K<=30,C<=200,M<=15）
思路：二分答案，網絡流check。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x;char c;
while((c=getchar())<'0'||c>'9');
for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0';
return x;
}
#define MN 230
#define ME 6230
#define S MN+1
#define T MN+2
#define INF 0x3FFFFFFF
struct edge{int nx,t,w;}e[ME*2+5];
int h[MN+5],en,n,m,w,g[MN+5][MN+5];
inline void ins(int x,int y,int w)
{
e[++en]=(edge){h[x],y,w};h[x]=en;
e[++en]=(edge){h[y],x,0};h[y]=en;
}
int d[MN+5],q[MN+5],qn,c[MN+5];
bool bfs()
{
int i,j;
memset(d,0,sizeof(d));
for(d[q[i=qn=0]=S]=1;i<=qn;++i)for(j=c[q[i]]=h[q[i]];j;j=e[j].nx)
if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+1;
return d[T];
}
int dfs(int x,int r)
{
if(x==T)return r;
int u=0,k;
for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[x]+1==d[e[i].t])
{
k=dfs(e[i].t,r-u<e[i].w?r-u:e[i].w);
u+=k;e[i].w-=k;e[i^1].w+=k;
if(u==r)return u;
}
return d[x]=0,u;
}
bool check(int x)
{
int i,j,ans=0;
memset(h,0,sizeof(h));en=1;
for(i=1;i<=n;++i)ins(S,i,w);
for(i=1;i<=m;++i)ins(i+n,T,1);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)
if(g[i][j+n]<=x)ins(i,j+n,1);
while(bfs())ans+=dfs(S,INF);
return ans==m;
}
int main()
{
int i,j,k,l,r,mid,ans;
n=read();m=read();w=read();
for(i=1;i<=n+m;++i)for(j=1;j<=n+m;++j)
{
g[i][j]=read();
if(i!=j&&!g[i][j])g[i][j]=INF;
}
for(k=1;k<=n+m;++k)for(i=1;i<=n+m;++i)for(j=1;j<=n+m;++j)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
for(l=0,r=INF;l<=r;)
if(check(mid=l+r>>1))ans=mid,r=mid-1;
else l=mid+1;
printf("%d",ans);
} E.King's Rout
題目大意：1~N的數，M條限制關系，每條要求一個數必須在另一個的前面，求一個方案使得滿足所有限制條件且1在最前面，1位置相同的情況下2在最前面，以此類推。（N<=200,000，M<=400,000）。
思路：拓撲排序，可以發現反過來字典序最大即為題目中要求的方案，用堆維護即可。
#include<cstdio>
#include<queue>
using namespace std;
inline int read()
{
int x=0;char c;
while((c=getchar())<'0'||c>'9');
for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+c-'0';
return x;
}
#define MN 200000
#define MM 400000
priority_queue<int> pq;
struct edge{int nx,t;}e[MM+5];
int h[MN+5],en,r[MN+5],ans[MN+5];
inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}
int main()
{
int n,m,i,j;
n=read();m=read();
while(m--)++r[i=read()],ins(read(),i);
for(i=1;i<=n;++i)if(!r[i])pq.push(i);
for(i=n;i;--i)
{
ans[i]=pq.top();pq.pop();
for(j=h[ans[i]];j;j=e[j].nx)if(!--r[e[j].t])pq.push(e[j].t);
}
for(i=1;i<=n;++i)printf("%d ",ans[i]);
} G.弦圖
題目大意：給定一長為N的字元串，詢問第K小子串，給一個參數T，若T=0則相同子串不重複計算，若T=1則相同子串重複計算。（N<=500,000）
思路：字尾自動機模闆題。
#include<cstdio>
#define MN 500000
#define ND 1000000
char st[MN+5];
int f[ND+5],c[ND+5][26],d[ND+5],tn=1,p=1;
int v[ND+5],s[ND+5],z[MN+5],q[ND+5];
void ins(int x)
{
int np=++tn,q,nq,i;d[np]=d[p]+1;v[np]=1;
for(;p&&!c[p][x];p=f[p])c[p][x]=np;
if(!p)f[np]=1;
else if(d[q=c[p][x]]==d[p]+1)f[np]=q;
else
{
d[nq=++tn]=d[p]+1;f[nq]=f[q];f[q]=f[np]=nq;
for(i=0;i<26;++i)c[nq][i]=c[q][i];
for(;c[p][x]==q;p=f[p])c[p][x]=nq;
}
p=np;
}
void out(int x,int k)
{
if(k<=v[x])return;k-=v[x];
for(int i=0;i<26;++i)
if(k<=s[c[x][i]]){putchar(i+'a');out(c[x][i],k);return;}
else k-=s[c[x][i]];
}
int main()
{
int t,k,i,j;
scanf("%s%d%d",st,&t,&k);
for(i=0;st[i];++i)ins(st[i]-'a');
for(i=1;i<=tn;++i)++z[d[i]];
for(i=MN;i--;)z[i]+=z[i+1];
for(i=1;i<=tn;++i)q[z[d[i]]--]=i;
if(t)for(i=1;i<=tn;--i)v[f[q[i]]]+=v[q[i]];
else for(i=1;i<=tn;++i)v[i]=1;
for(v[1]=0,i=2;i<=tn;++i)s[i]=v[i];
for(i=1;i<=tn;++i)for(j=0;j<26;++j)s[q[i]]+=s[c[q[i]][j]];
if(k>s[1])puts("-1");else out(1,k);
} 轉載于:https://www.cnblogs.com/ditoly/p/20170303C.html