POI2000
T1 迷宫的墙 暴力从后往前判断是否存在相同的即可，相同的话就更新答案
#include<cstdio>
#include<cstring>
#include<map>
#define N 6010
using namespace std;
int n,i,j,ans,w[N],c[N],a[N][3];char s[9];
long long now;map<long long,int>mp;
int main(){
scanf("%d",&n);w[n]=n;ans=n;
for(i=1;i<n;i++){
scanf("%s",s);w[i]=i;
if(s[0]=='C')c[i]=1;else if(s[0]=='Z')c[i]=2;else c[i]=3;
for(j=0;j<3;j++)scanf("%d",&a[i][j]);
}
for(i=n-1;i;i--){
now=c[i];
for(j=0;j<3;j++)a[i][j]=w[a[i][j]],now=now*n+a[i][j]-1;
if(mp[now])w[i]=mp[now],ans--;else mp[now]=i;
}
printf("%d",ans);
}
T2 建造酿酒厂 首先向两边送的分割点肯定是单调的，于是可以$O(n)$转一圈，每次得到这个分割点，然后通过前缀和快速得到答案，为了方便可以把一个环剪成$2*n$的链
#include<cstdio>
#include<algorithm>
#define N 20010
using namespace std;
int n,i,j,x,y,z[N],d[N];
long long f[N],g[N],s[N],now,ans=1e18;
int main(){
scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&z[i],&d[i]),f[i]=f[i-1]+z[i],g[i]=g[i-1]+d[i],s[i]=s[i-1]+z[i]*g[i-1];
for(i=n+1;i<=n*2;i++)z[i]=z[i-n],d[i]=d[i-n],f[i]=f[i-1]+z[i],g[i]=g[i-1]+d[i],s[i]=s[i-1]+z[i]*g[i-1];
for(i=j=1;i<=n;i++){
for(;(g[j-1]-g[i-1])<=(g[n]>>1)&&j<=n*2;j++);
now=s[j-1]-s[i]+g[i-1]*f[i]-(f[j-1]-f[i])*g[i-1]+(g[i-1]+g[n])*(f[n]-f[j-1])-s[n]+s[j-1]-s[i];
if(now<ans)ans=now;
}
printf("%lld",ans);
}
T3 病毒 AC自动机弄出所有danger节点后判一遍是否有环即可
#include<cstdio>
#define N 33333
int n,i,j,c,x,y,k,h,t,cnt,son[N][2],fail[N],q[N],v[N];
bool dg[N],flag;char s[N];
void dfs(int x){
if(dg[x]||flag)return;v[x]=1;
for(int i=0;i<2;i++){
int y=son[x][i];
if(v[y]==1){flag=1;return;}
if(!v[y])dfs(y);
if(flag)return;
}
v[x]=2;
}
int main(){
for(scanf("%d",&n),cnt=son[0][0]=son[0][1]=1;n--;dg[x]=1){
scanf("%s",s);x=1;
for(i=0;s[i];x=son[x][c],i++)if(!son[x][c=s[i]-'0'])son[x][c]=++cnt;
}
for(q[t=1]=1;h<t;)
for(x=q[++h],i=0;i<2;i++){
y=son[x][i];
if(!y){son[x][i]=son[fail[x]][i];continue;}
for(k=fail[x];!son[k][i];k=fail[k]);
fail[y]=son[k][i];
dg[y]|=dg[fail[y]];
q[++t]=y;
}
dfs(1);flag?puts("TAK"):puts("NIE");
}
T4 滑雪 就是一个小小的网络流，由于边的流量只有1，可以直接DFS解决。。
#include<cstdio>
#include<cstring>
#define N 10010
#define M 200020
int n,i,j,k,x,tot,ans,fir[N],pre[N],va[M],la[M],ne[M];bool v[N];
void ins(int x,int y){
la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=1;
la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;va[tot]=0;
}
bool dfs(int x){
v[x]=1;if(x==n)return 1;
for(int i=fir[x];i;i=ne[i])
if(va[i]&&!v[la[i]]){
pre[la[i]]=i;
if(dfs(la[i]))return 1;
}
return 0;
}
int main(){
scanf("%d",&n);tot=1;
for(i=1;i<n;i++){
scanf("%d",&k);ins(i,i+n);
for(j=1;j<=k;j++)scanf("%d",&x),ins(i+n,x);
}
for(;dfs(n+1);ans++){
for(i=n;i!=n+1;i=la[pre[i]^1])va[pre[i]]^=1,va[pre[i]^1]^=1;
memset(v,0,sizeof(v));
}printf("%d",ans);
}
T5 条纹 直接暴力求SG函数就可以了
#include<cstdio>
#include<cstring>
int a,b,c,i,j,x,Q,sg[1111],hash[1111];
int main(){
scanf("%d%d%d",&a,&b,&c);
for(i=1;i<=1000;i++){
memset(hash,0,sizeof(hash));
if(i>=a)for(j=0;j<=i-a;j++)hash[sg[j]^sg[i-a-j]]=1;
if(i>=b)for(j=0;j<=i-b;j++)hash[sg[j]^sg[i-b-j]]=1;
if(i>=c)for(j=0;j<=i-c;j++)hash[sg[j]^sg[i-c-j]]=1;
for(j=0;j<=1000;j++)if(!hash[j]){sg[i]=j;break;}
}
for(scanf("%d",&Q);Q--;sg[x]?puts("1"):puts("2"))scanf("%d",&x);
}
T6 担保 只要判断一下是否有大于等于两个长官担保即可
#include<cstdio>
#define N 510
int n,i,k,x,tot,f,g[N],v[N],s[N],fir[N],ne[N*N],la[N*N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int z){
v[x]=z;s[x]++;
for(int i=fir[x];i;i=ne[i])if(v[la[i]]!=z)dfs(la[i],z);
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%d",&g[i]),k=g[i];k--;)scanf("%d",&x),ins(x,i);
for(i=1;i<=n;i++)if(!g[i])dfs(i,i);
for(i=1;i<=n;i++)if(g[i]&&s[i]<2)printf("%d\n",i),f=1;
if(!f)puts("BRAK");
}
T7 同构 首先如果有偶数环肯定是不合法的，因为这样置换会换到自己爆炸，然后奇数环对答案的贡献是$2^{\frac{cnt-1}{2}}$
奇数环之间的贡献是他们的gcd之和，但暴力求可能会T，可以用计数的思想计出每种个数的数量，然后统计贡献时可以在$nlgn$统计出来
#include<cstdio>
#define N 10010
int n,i,j,x,cnt,ans,tot,w,p,a[N],f[N],to[N];bool v[N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&to[i]);
for(i=1;i<=n;i++)if(!v[i]){
for(v[x=i]=1,cnt=1;!v[to[x]];v[x=to[x]]=1)cnt++;
if(cnt%2==0)return puts("0"),0;
p+=cnt-1;a[cnt]++;
}
for(i=n;i>=1;i--){
for(tot=a[i],j=i+i;j<=n;j+=i)tot+=a[j],f[i]+=f[j];
f[i]=tot*tot-f[i];p+=(f[i]-a[i])*i;
}
for(p>>=1,ans=1,w=2;p;w=w*w%1000,p>>=1)if(p&1)ans=ans*w%1000;
printf("%d",ans);
}
T8请不要提交！
T9 代码 递推后再递归找答案就行了
#include<cstdio>
int i,j,n,k,ln,f[21];char s[21];
void dfs(int l,int r,int k){
int i;for(i=l;i<=r;i++)if(f[i-l]*f[r-i]<=k)k-=f[i-l]*f[r-i];else break;
s[ln++]=i+'a'-1;if(i>l)dfs(l,i-1,k/f[r-i]);if(i<r)dfs(i+1,r,k%f[r-i]);
}
int main(){
scanf("%d%d",&n,&k);n--;
for(f[0]=i=1;i<=k;i++)for(j=0;j<i;j++)f[i]+=f[j]*f[i-j-1];
dfs(1,k,n);printf("%s",s);
}
T10 气垫船 首先找出出现次数最多的数，然后判断一下是否在一边没有数，有的话n++，然后判断一下出现次数最多的数*2是否小于等于n即可
#include<cstdio>
int T,n,p,s,i,a[1001000];bool f1,f2;char ch;
void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
for(read(T);T--;){
read(n);p=f1=f2=0;s=1;
for(i=1;i<=n;i++){
read(a[i]);
if(a[i]==p)s++;else s--;
if(!s)s++,p=a[i];
}
for(s=0,i=1;i<=n;i++)if(a[i]>p)f1=1;else if(a[i]<p)f2=1;else s++;
if(!f1||!f2)n++;
s*2<=n?puts("TAK"):puts("NIE");
}
}
T11 公共串 多串LCM后缀自动机裸题，先对一个串做SAM，然后每个串进去匹配，对于每种状态保留最大值，然后取最大值中的最小值，最后再在每种状态中取最大值
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 222222
using namespace std;
int la,S,i,n,cnt,tmp,p,ans,c,np,q,nq,Q,mn[N],fa[N],step[N],v[N],w[N],cl[N],son[N][26];
char s[N];
void add(int x){
c=s[x]-'a',p=la,la=np=++cnt;step[np]=step[p]+1;
for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
if(!p)fa[np]=S;else{
q=son[p][c];
if(step[p]+1==step[q])fa[np]=q;else{
nq=++cnt;step[nq]=step[p]+1;
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q];fa[np]=fa[q]=nq;
for(;son[p][c]==q;p=fa[p])son[p][c]=nq;
}
}
}
int main(){
scanf("%d",&Q);Q--;
scanf("%s",s);n=strlen(s);la=S=++cnt;
for(i=0;i<n;i++)add(i);
for(i=1;i<=cnt;i++)mn[i]=step[i];
for(i=1;i<=cnt;i++)v[step[i]]++;
for(i=1;i<=n;i++)v[i]+=v[i-1];
for(i=1;i<=cnt;i++)w[v[step[i]]--]=i;
while(Q--){
scanf("%s",s);n=strlen(s);memset(cl,0,sizeof(cl));tmp=0;
for(p=1,i=0;i<n;i++){
c=s[i]-'a';
if(son[p][c])p=son[p][c],tmp++;else{
while(p&&!son[p][c])p=fa[p];
if(!p)p=1,tmp=0;else tmp=step[p]+1,p=son[p][c];
}
cl[p]=max(cl[p],tmp);
}
for(i=cnt;i;i--){
int t=w[i];
mn[t]=min(mn[t],cl[t]);
if(cl[t]&&fa[t])cl[fa[t]]=step[fa[t]];
}
}
for(i=1;i<=cnt;i++)ans=max(ans,mn[i]);
printf("%d",ans);
}
T12 促销 直接set水过
#include<cstdio>
#include<set>
using namespace std;
multiset<int>st;
int n,k,x;long long ans;
int main(){
for(scanf("%d",&n);n--;){
for(scanf("%d",&k);k--;)scanf("%d",&x),st.insert(x);
ans+=(long long)*--st.end()-*st.begin();
st.erase(st.begin());st.erase(--st.end());
}
printf("%lld",ans);
}
感觉这届好水好无聊啊、、
评论 (0)
