NOIP2017模拟赛(二)
T1:
一开始我写的是floyd,题目讨论的时候也是这种
我一开始找环的时候,以为直接搜索即可,结果严重超时。后来我发现,虽然无向图找环是线性的,但有向图并不是,如有50个点:
1 2 3 4 5
25条边全部连
6 7 8 9 10
25条边全部连
……
这样时间就是
CODE:
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=55;
const int oo=1000000001;
int C[maxn][maxn];
bool e[maxn][maxn];
int deg[maxn];
int g[maxn];
int vis[maxn];
bool path[maxn];
bool cir;
int t,n,G;
void Dfs1(int node)
{
path[node]=true;
for (int i=1; i<=n; i++)
if ( e[node][i] && g[node]==g[i] && !vis[i] )
if ( !cir && !path[i] ) Dfs1(i);
else
{
cir=true;
break;
}
path[node]=false;
vis[node]=true;
}
int Dfs2(int node)
{
if (vis[node]) return vis[node];
int temp=1;
for (int i=1; i<=n; i++)
if ( e[node][i] && g[node]<=g[i] && g[i]<=G )
temp=max(temp, Dfs2(i)+1 );
return vis[node]=temp;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
for (int i=0; i<maxn; i++) C[i][0]=1;
for (int i=1; i<maxn; i++)
for (int j=1; j<=i; j++)
{
C[i][j]=C[i-1][j]+C[i-1][j-1];
if (C[i][j]>oo) C[i][j]=oo;
}
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&G);
cir=false;
for (int i=1; i<=n; i++) deg[i]=g[i]=vis[i]=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
{
char c=getchar();
while ( c!='0' && c!='1' ) c=getchar();
if (c=='0') e[i][j]=false;
else e[i][j]=true,deg[i]++;
}
for (int i=1; i<=n; i++)
for (int j=3; j<=deg[i]; j++)
{
g[i]+=C[ deg[i] ][j];
if (g[i]>oo) g[i]=oo;
}
for (int i=1; i<=n; i++)
if ( !cir && 0<g[i] && g[i]<=G && !vis[i] ) Dfs1(i);
if (cir)
{
printf("-1\n");
continue;
}
int ans=0;
for (int i=1; i<=n; i++) vis[i]=0;
for (int i=1; i<=n; i++)
if ( 0<g[i] && g[i]<=G ) ans=max(ans, Dfs2(i) );
printf("%d\n",ans);
}
return 0;
}
T2:
这题是有一种贪心的方法的,我们可以先枚举要买多少员工num,然后一开始就不停地买。当员工达到num个时,就等他们攒钱和荣誉,用算出的天数更新答案。然后我猜测以算出的天数为标准,这是个单峰函数,然而我并不会严格的证明,或许我们可以感性地认识一下:假设买太少员工,攒钱的速度就会很慢,如果买太多,买员工需要耗费的金钱和天数又太多,这样必定会在某个地方取到峰值。于是我就写了个三分A掉了,时间复杂度
CODE:
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,x,y,z,a,b;
int Get(int num)
{
int now=n,day=0,A=0;
while (now<num)
{
while (A<z) A+=x*now,day++;
A+=(3*x*now-z),day+=3,now++;
}
while (A<a) A+=num*x,day++;
return day;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d%d%d%d%d%d",&n,&x,&y,&z,&a,&b);
a+=((b+y-1)/y)*x;
int L=n,R=21;
while (L+2<R)
{
int mL=(L*2+R)/3;
int mR=(L+R*2)/3;
int vL=Get(mL);
int vR=Get(mR);
if (vL<vR) R=mR;
if (vL==vR) L=mL,R=mR;
if (vL>vR) L=mL;
}
int ans=Get(L);
ans=min(ans, Get(L+1) );
ans=min(ans, Get(R) );
printf("%d\n",ans);
return 0;
}
NOIP2017模拟赛(三)
T2:
我在考场上写的是二分答案+Hash,时间
CODE(Hash+尺取法):
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=510;
const int M=300509;
const long long M1=998585857;
const long long M2=311111111;
typedef long long LL;
LL w1[maxn];
LL w2[maxn];
LL val1[maxn<<1][maxn];
LL val2[maxn<<1][maxn];
struct data
{
LL num1,num2;
int id;
} Hash[M];
char s[maxn];
int n,m;
LL Get1(int i,int x,int y)
{
LL v=( val1[i][y]- (val1[i][x-1]*w1[y-x+1])%M1 +M1 )%M1;
return v;
}
LL Get2(int i,int x,int y)
{
LL v=( val2[i][y]- (val2[i][x-1]*w2[y-x+1])%M2 +M2 )%M2;
return v;
}
void Push_in(LL v1,LL v2,int i)
{
LL v=v1*M2+v2*M1;
int x=v%M;
while (Hash[x].id) x=(x+1)%M;
Hash[x].num1=v1;
Hash[x].num2=v2;
Hash[x].id=i;
}
bool Check(LL v1,LL v2)
{
LL v=v1*M2+v2*M1;
int x=v%M;
while ( Hash[x].id && ( Hash[x].num1!=v1 || Hash[x].num2!=v2 ) ) x=(x+1)%M;
if (Hash[x].id) return true;
return false;
}
void Push_out(LL v1,LL v2,int i)
{
LL v=v1*M2+v2*M1;
int x=v%M;
while ( !Hash[x].id || Hash[x].num1!=v1 || Hash[x].num2!=v2 ) x=(x+1)%M;
Hash[x].id=0;
}
bool Work(int x,int y)
{
for (int i=n+1; i<=n+n; i++)
{
LL v1=Get1(i,x,y);
LL v2=Get2(i,x,y);
Push_in(v1,v2,i);
}
bool sol=true;
for (int i=1; i<=n; i++)
{
LL v1=Get1(i,x,y);
LL v2=Get2(i,x,y);
if ( Check(v1,v2) )
{
sol=false;
break;
}
}
for (int i=n+1; i<=n+n; i++)
{
LL v1=Get1(i,x,y);
LL v2=Get2(i,x,y);
Push_out(v1,v2,i);
}
return sol;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
w1[0]=w2[0]=1;
for (int i=1; i<maxn; i++)
w1[i]=(w1[i-1]*27LL)%M1,w2[i]=(w2[i-1]*27LL)%M2;
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
{
scanf("%s",&s);
val1[i][0]=val2[i][0]=0;
for (int j=1; j<=m; j++)
val1[i][j]=( val1[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M1,
val2[i][j]=( val2[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M2;
}
for (int i=n+1; i<=n+n; i++)
{
scanf("%s",&s);
val1[i][0]=val2[i][0]=0;
for (int j=1; j<=m; j++)
val1[i][j]=( val1[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M1,
val2[i][j]=( val2[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M2;
}
for (int i=0; i<M; i++) Hash[i].id=0;
int ans=m,L=1,R=1;
while ( 1 )
{
if ( !Work(L,R) )
if (R==m) break;
else R++;
else ans=min(ans,R-L+1),L++;
}
printf("%d\n",ans);
return 0;
}
CODE(trie):
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxm=250000;
const int maxn=510;
struct Tnode
{
Tnode *son[4];
} tree[maxm];
Tnode *Root;
int cur;
Tnode *que[maxm];
int head,tail;
char s[maxn<<1][maxn];
int n,m;
Tnode *New_node()
{
cur++;
for (int i=0; i<4; i++) tree[cur].son[i]=NULL;
return tree+cur;
}
int Get(char c)
{
if (c=='A') return 0;
if (c=='G') return 1;
if (c=='C') return 2;
if (c=='T') return 3;
}
void Insert(int h,int x)
{
Tnode *P=Root;
for (int i=h; i<m; i++)
{
int to=Get(s[x][i]);
if (!P->son[to]) P->son[to]=New_node();
P=P->son[to];
}
}
int Match(int h,int x)
{
Tnode *P=Root;
int i;
for (i=h; i<m; i++)
{
int to=Get(s[x][i]);
if (P->son[to]) P=P->son[to];
else break;
}
if (i==m) return m;
return i-h+1;
}
int Solve(int h)
{
cur=-1,Root=New_node();
for (int i=n+1; i<=(n<<1); i++) Insert(h,i);
int temp=1;
for (int i=1; i<=n; i++) temp=max(temp, Match(h,i) );
return temp;
}
int main()
{
freopen("c.in","r",stdin);
freopen("my.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=(n<<1); i++) scanf("%s",&s[i]);
int ans=m;
for (int i=0; i<m; i++)
{
ans=min(ans, Solve(i) );
int j=i;
}
printf("%d\n",ans);
return 0;
}
T3:
之前我写的DP时间勉强卡过,而且还要用到组合数,后来在讨论的时候看到kekxy大神写了个四维DP,时间快多了。我们记f[i][j][w][s]表示当前有i个点,j条边,且第i个点向前连边,编号最小的点是w号点,而且i~i-K号点的奇偶性状态为s。我们考虑要不要i向w号点再连一条边,如果再连,就转移到f[i][j-1][w][s^(1
CODE:
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=31;
const int maxk=1<<9;
const int M=1000000007;
int f[maxn][maxn][maxn][maxk];
int n,m,K;
int Get(int x)
{
return 1<<x;
}
int Dfs(int i,int j,int k,int s)
{
if (!j)
if (!s) return 1;
else return 0;
if (i==1)
if ( !j && !s ) return 1;
else return 0;
int &v=f[i][j][k][s];
if (v!=-1) return v;
int gk=Get(K),gki=Get(K+k-i);
v=Dfs(i,j-1,k, s^gk^gki );
if ( k>1 && i-k<K ) v=(v+ Dfs(i,j,k-1,s) )%M;
else if ( !(s&Get(K)) ) v=(v+ Dfs(i-1,j,i-2,s<<1) )%M;
return v;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d%d%d",&n,&m,&K);
memset(f,-1,sizeof(f));
printf("%d\n", Dfs(n,m,n-1,0) );
return 0;
}
NOIP2017模拟赛(四)
T1:
本题我之前用的是low数组+LCA,然而可不可以不用LCA呢?在题目讨论的时候老师给出了一种用二分的方法。
我们同样先DFS出low数组,并记录dfs序,以及每一个点的子树对应的区间。删一条树边(u,v)的时候,假设fa[v]=u。如果a或b的其中一个在v的子树内,另一个不在,就要查看v的low,否则必为yes。那如果删一个点呢?若a,b都在这个点的外面或同一个儿子的子树内,则无影响,否则要查看a,b向上走所到达的c的儿子ax,bx的low。那么我们如何在不向上跳的前提下,知道a是在c的哪个儿子的子树中?我们在c处开一个动态数组vector,保存c的每一个儿子,按它们的子树区间从左到右保存。由于它们的区间互不交叉,且已排好序,我们要查询的时候,就用二分即可。
然而像我这种从来不用STL库的手写党而言,我根本就不会vector的用法。我觉得我写个treap都比写vector快,但这样显得很傻逼,有没有什么既用静态数组二分,又不爆空间的方法呢?我想起了我之前写过的一篇NOIP2016Day1T2的深入思考。当我们有很多个小数组需要二分,总空间不超过某个值时,我们可以把这些小数组映射到一个大数组上:
然后我们再记每一个小数组的起始结束位置L,R即可。时间O(nlog(n))。
CODE:
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100100;
const int maxm=500100;
struct edge
{
int obj;
edge *Next;
} e[maxm<<1];
edge *head[maxn];
int cur=-1;
int bot[maxn<<1];
int L[maxn];
int R[maxn];
int st[maxn];
int ed[maxn];
int Time=0;
int fa[maxn];
int low[maxn];
int n,m,q;
void Add(int x,int y)
{
cur++;
e[cur].obj=y;
e[cur].Next=head[x];
head[x]=e+cur;
}
void Dfs(int node)
{
st[node]=++Time;
low[node]=st[node];
for (edge *p=head[node]; p; p=p->Next)
{
int son=p->obj;
if (son!=fa[node])
{
if (!st[son]) fa[son]=node,Dfs(son);
low[node]=min(low[node],low[son]);
}
}
ed[node]=Time;
}
bool In(int x,int y)
{
return st[x]<=st[y] && st[y]<=ed[x];
}
int Find(int x,int y)
{
int l=L[x],r=R[x];
if (st[y]>ed[ bot[r] ]) return 0;
while (l+1<r)
{
int mid=(l+r)>>1;
if (st[y]<=ed[ bot[mid] ]) r=mid;
else l=mid;
}
if (st[y]>=st[ bot[r] ]) return bot[r];
return 0;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) head[i]=NULL;
for (int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
Add(x,y);
Add(y,x);
}
fa[1]=0;
Dfs(1);
cur=0;
for (int i=1; i<=n; i++)
{
L[i]=R[i]=++cur;
for (edge *p=head[i]; p; p=p->Next)
{
int son=p->obj;
if (fa[son]==i)
{
bot[++cur]=son;
R[i]=cur;
}
}
}
scanf("%d",&q);
while (q--)
{
int id;
scanf("%d",&id);
if (id==1)
{
int a,b,u,v;
scanf("%d%d%d%d",&a,&b,&u,&v);
if ( fa[u]!=v && fa[v]!=u )
{
printf("yes\n");
continue;
}
if (fa[u]!=v) swap(u,v);
if ( In(u,a)^In(u,b) )
if (low[u]!=st[u]) printf("yes\n");
else printf("no\n");
else printf("yes\n");
}
else
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a=Find(c,a);
b=Find(c,b);
if ( a && a==b ) printf("yes\n");
else
{
bool sol=true;
if ( a && low[a]>=st[c] ) sol=false;
if ( b && low[b]>=st[c] ) sol=false;
if (sol) printf("yes\n");
else printf("no\n");
}
}
}
return 0;
}
T3:
这题能不能叫一题多解呢?我觉得不能,因为本质上在求字典序最小的时候都要用到贪心。总之摘录一下别人的方法。
fzh:我也是二分答案+贪心,二分后从小到大枚举。到h[i]的时候,先看一下它是否左右两路都能加进去(h[i]-h[L]<=mid,h[i]-h[R]<=mid),如果有一边不能则返回false。接下来看一下h[i+1]是否两边都能加进,有一边不能(假设是左边,即h[i+1]-h[L]>mid)则要求必须将h[i]加进左边,否则没办法往后做。如果没有要求h[i]必须要加哪边,我们就加到左右两边中高度低的一边(这样肯定比加到高的那边更优)。要求字典序最小的时候,将右边点的尽可能拉到左边,然后从左到右输出即可。
kekxy:先将h[1],h[3],h[5]……加一边;h[2],h[4],h[6]加另一边,得到答案(这样肯定最优)。然后要求字典序最小,我们就从小到大枚举,能加进左边就加,如果它加进左边导致下一个加不进右边,它就要加进右边。
话说,上面的两种方法本质上和我的方法差(yi)不(mu)多(yi)嘛(yang)。于是我就没有写代码……
tututu:我们先二分答案mid,然后拆点(i拆为入点i与出点i+N,i连向i+N,边的容量为1),连边(
%%%网络流大神tututu。
CODE(网络流):
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=52;
const int maxm=10000;
struct edge
{
int obj,cap;
edge *Next,*rev;
} e[maxm];
edge *head[maxn<<1];
edge *nhead[maxn<<1];
int cur;
int level[maxn<<1];
int que[maxn<<1];
int he,ta;
int Left[maxn];
int Right[maxn];
int Lcur,Rcur;
int h[maxn];
int ng,N,t,ans;
void Add(int x,int y,int f)
{
cur++;
e[cur].obj=y;
e[cur].cap=f;
e[cur].rev=&e[cur+1];
e[cur].Next=head[x];
head[x]=e+cur;
cur++;
e[cur].obj=x;
e[cur].cap=0;
e[cur].rev=&e[cur-1];
e[cur].Next=head[y];
head[y]=e+cur;
}
bool Bfs()
{
for (int i=0; i<=t; i++) nhead[i]=head[i],level[i]=0;
he=0,ta=1,que[1]=0,level[0]=1;
while (he<ta)
{
int node=que[++he];
for (edge *p=head[node]; p; p=p->Next)
{
int son=p->obj;
if ( !level[son] && p->cap ) level[son]=level[node]+1,que[++ta]=son;
}
}
return level[N];
}
int Dfs(int node,int maxf)
{
if ( node==N || !maxf ) return maxf;
int nowf=0;
for (edge *&p=nhead[node]; p; p=p->Next)
{
int son=p->obj;
if ( level[son]==level[node]+1 && p->cap )
{
int d=Dfs(son, min(p->cap,maxf) );
nowf+=d;
maxf-=d;
p->cap-=d;
p->rev->cap+=d;
if (!maxf) break;
}
}
if (maxf) level[node]=0;
return nowf;
}
int Dinic()
{
int temp=0;
while ( Bfs() ) temp+=Dfs(0,2);
return temp;
}
bool Judge(int limit)
{
cur=-1;
for (int i=0; i<=t; i++) head[i]=NULL;
for (int i=1; i<N; i++)
for (int j=i+1; j<=N; j++)
if (h[j]-h[i]<=limit) Add(i+N,j,1);
for (int i=1; i<=N; i++) Add(i,i+N,1);
Add(0,N+1,2);
return Dinic()>=2;
}
int Binary()
{
int L=0,R=1001;
while (L+1<R)
{
int mid=(L+R)>>1;
if ( Judge(mid) ) R=mid;
else L=mid;
}
return R;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&ng);
while (ng--)
{
scanf("%d",&N);
for (int i=1; i<=N; i++) scanf("%d",&h[i]);
sort(h+1,h+N+1);
t=N<<1;
ans=Binary();
Lcur=Rcur=0;
Right[++Rcur]=1;
for (int i=2; i<N; i++)
{
cur=-1;
for (int j=0; j<=t; j++) head[j]=NULL;
for (int j=i; j<N; j++)
for (int k=j+1; k<=N; k++)
if (h[k]-h[j]<=ans) Add(j+N,k,1);
for (int j=Right[Rcur]+1; j<=N; j++)
if ( j>i && h[j]-h[ Right[Rcur] ]<=ans ) Add(Right[Rcur]+N,j,1);
for (int j=1; j<=N; j++) Add(j,j+N,1);
Add(0,Right[Rcur]+N,1);
Add(0,i+N,1);
if ( Dinic()>=2 ) Left[++Lcur]=i;
else Right[++Rcur]=i;
}
printf("%d ",h[1]);
for (int i=1; i<=Lcur; i++) printf("%d ",h[ Left[i] ]);
printf("%d ",h[N]);
for (int i=Rcur; i>=2; i--) printf("%d ",h[ Right[i] ]);
printf("\n");
}
return 0;
}
老师的提供的一种做法:双路DP。我们记f[i][j]表示左边的路径最下方的点是i号,右边路径最下方的点是j号时的最大差距。做完f数组之后从小到大枚举i,看看是否有
一开始我想,可不可以不用最后贪心一遍,而是一边做f数组一遍求前驱,最后递归打印呢?然而我试了很多种方法都不行(交上去测顶多20分),感觉这样没办法解决字典序最小问题(主要是有多个相同的f值可以更新f[i][j]不知道应该保留哪个作为前驱)。调了一个下午+晚上最后还是放弃了QAQ。
CODE(双路DP+贪心):
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=55;
const int maxm=1001;
int Left[maxn];
int Right[maxn];
int Lcur,Rcur;
int f[maxn][maxn];
int h[maxn];
int ng,N;
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&ng);
while (ng--)
{
scanf("%d",&N);
for (int i=1; i<=N; i++) scanf("%d",&h[i]);
sort(h+1,h+N+1);
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++) f[i][j]=maxm;
f[N-1][N]=f[N][N-1]=h[N]-h[N-1];
for (int i=N-1; i>=2; i--)
for (int j=i+1; j<=N; j++)
{
f[i-1][j]=min(f[i-1][j], max(f[i][j],h[i]-h[i-1]) );
f[i][i-1]=min(f[i][i-1], max(f[i][j],h[j]-h[i-1]) );
f[i-1][i]=min(f[i-1][i], max(f[j][i],h[j]-h[i-1]) );
f[j][i-1]=min(f[j][i-1], max(f[j][i],h[i]-h[i-1]) );
}
int ans=maxm;
for (int j=2; j<=N; j++)
f[1][j]=max(f[1][j],h[j]-h[1]),
f[j][1]=max(f[j][1],h[j]-h[1]),
ans=min(ans, min(f[1][j],f[j][1]) );
Lcur=Rcur=0;
Right[++Rcur]=1;
for (int i=2; i<N; i++)
{
bool fL=false;
for (int j=i+1; j<=N; j++)
if ( f[i][j]<=ans && h[j]-h[ Right[Rcur] ]<=ans )
fL=true;
if (fL) Left[++Lcur]=i;
else Right[++Rcur]=i;
}
printf("%d ",h[1]);
for (int i=1; i<=Lcur; i++) printf("%d ",h[ Left[i] ]);
printf("%d ",h[N]);
for (int i=Rcur; i>=2; i--) printf("%d ",h[ Right[i] ]);
printf("\n");
}
return 0;
}