NOIP2017提高组 模拟赛 26（总结）
程序员文章站
2022-03-14 19:22:08
...
NOIP2017提高组 模拟赛 26（总结）
第一题 种花 （构造法/上下界的网络流）
【题目描述】
【解题思路】
①构造法：
假设现在有m个点，删除一个点，剩下的m-1个点都已经确定，那么删除的这个点应该染什么颜色。
假如这个点所在的行的点数为奇数，那么点的染色只与它所在的列有关（若列有偶数个点，那么这个点的颜色就可以确定了，哪种颜色少选哪种。否则随便选）
假如这个点所在的列的点数为奇数，与上面类似。
若不存在这样的点呢？
那么剩下的一定是所有行和列的点数皆为偶数。
那就随便选择一个点i。把它删掉。然后递归去求剩下m-1个点的情况。
那么，点i所在的行和列的点数皆为奇数，假设现在的行（除去点i）的染色是红>白，点i一定是白色。除去这个行，剩下的所有的点的红白相等。除去这个列，红白也相等。所以现在的列（除去点i）的染色也必定是红>白。所以点i为白色是可行的。（若染色情况是白>红，结果也是一样的）
递归求解即可，时间复杂度：O(n^2)。
②上下界的网络流。
S与行连边，下界为行数/2，上界为(行数+1)/2。
把每个点拆成一条边(ai,bi)，下界为0，上界为1。（若有流量，则选红色）
T与列连边，下界为列数/2，上界为(列数+1)/2。
ai与点i所在的行连边，下界为0，上界为1。bi与点i所在的列连边，下界为0，上界为1。
关于上下界网络流的构图解析
【代码】
//构造法
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1500;
struct data { int a,b; } d[N];
int w[N],n,T,row[N],lie[N],vis[N];
data ry[N],ly[N];
bool cmp1(int a,int b) { return (d[a].a<d[b].a); }
bool cmp2(int a,int b) { return (d[a].b<d[b].b); }
void dfs(int x)
{
if(x>n) return;
bool ff=1; int yu=-1,ia,ib;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
yu=i;
ia=d[i].a; ib=d[i].b;
if(row[ia]&1 || lie[ib]&1)
{
vis[i]=1;
row[ia]--; lie[ib]--;
dfs(x++);
row[ia]++; lie[ib]++;
if(!(row[ia]&1))
{
if(ry[ia].a<ry[ia].b) ry[ia].a++,ly[ib].a++,vis[i]=2;
else ry[ia].b++,ly[ib].b++,vis[i]=3;
} else
{
if(ly[ib].a<ly[ib].b) ry[ia].a++,ly[ib].a++,vis[i]=2;
else ry[ia].b++,ly[ib].b++,vis[i]=3;
}
ff=0;
break;
}
}
if(ff && yu!=-1)
{
ia=d[yu].a; ib=d[yu].b;
vis[yu]=1;
row[ia]--; lie[ib]--;
dfs(x++);
row[ia]++; lie[ib]++;
if(ly[ib].a<ly[ib].b) ry[ia].a++,ly[ib].a++,vis[yu]=2;
else ry[ia].b++,ly[ib].b++,vis[yu]=3;
}
}
int main()
{
freopen("2084.in","r",stdin);
freopen("2084.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
row[i]=lie[i]=vis[i]=0;
ry[i].a=ry[i].b=0;
ly[i].a=ly[i].b=0;
}
for(int i=1;i<=n;i++) scanf("%d%d",&d[i].a,&d[i].b),w[i]=i;
sort(w+1,w+1+n,cmp1);
int la=d[w[1]].a; d[w[1]].a=1; row[d[w[1]].a]++;
for(int i=2;i<=n;i++)
{
int v=w[i];
if(d[v].a==la) d[v].a=d[w[i-1]].a; else la=d[v].a,d[v].a=d[w[i-1]].a+1;
row[d[v].a]++;
}
sort(w+1,w+1+n,cmp2);
la=d[w[1]].b; d[w[1]].b=1; lie[d[w[1]].b]++;
for(int i=2;i<=n;i++)
{
int v=w[i];
if(d[v].b==la) d[v].b=d[w[i-1]].b; else la=d[v].b,d[v].b=d[w[i-1]].b+1;
lie[d[v].b]++;
}
dfs(1);
for(int i=1;i<=n;i++) printf("%c",(vis[i]==2)?('W'):('R'));
printf("\n");
}
return 0;
}//上下界网络流
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define imin(a,b) (((a)<(b))?(a):(b))
#define row(i) (i)
#define ia(i) (n+i)
#define ib(i) (n+n+i)
#define lie(i) (n+n+n+i)
using namespace std;
typedef long long ll;
const int inf=1e9;
const int N=1500;
struct data { int a,b; } d[N];
int w[N],n,Tt,row[N],lie[N];
int mh,ml,red[N];
const int nn=1005000;
int to[nn],h[nn],ne[nn],val[nn],tt;
int lev[nn],vis[nn];
int S,T,Sd,Td,ru[nn],bfstime;
int q[nn],head,tail;
bool cmp1(int a,int b) { return (d[a].a<d[b].a); }
bool cmp2(int a,int b) { return (d[a].b<d[b].b); }
void addedge(int a,int b,int c)
{
to[++tt]=b; ne[tt]=h[a]; val[tt]=c; h[a]=tt;
to[++tt]=a; ne[tt]=h[b]; val[tt]=0; h[b]=tt;
}
void ready()
{
memset(vis,0,sizeof(vis));
memset(to,0,sizeof(to));
memset(ne,0,sizeof(ne));
memset(h,0,sizeof(h));
memset(lev,-1,sizeof(lev));
memset(ru,0,sizeof(ru));
memset(val,0,sizeof(val));
tt=1; head=tail=0;
S=lie(n)+10; T=S+1;
Sd=T+1; Td=Sd+1;
for(int i=1;i<=n;i++) row[i]=lie[i]=0;
bfstime=0;
}
bool bfs()
{
head=tail=1;
q[head]=Sd; vis[Sd]=++bfstime; lev[Sd]=1;
while(head<=tail)
{
int u=q[head++];
for(int p=h[u];p;p=ne[p])
{
int v=to[p];
if(vis[v]==bfstime || !val[p]) continue;
q[++tail]=v;
vis[v]=bfstime; lev[v]=lev[u]+1;
}
}
return (vis[Td]==bfstime);
}
int dfs(int now,int maxf)
{
int ret=0,t;
if(now==Td || !maxf) return maxf;
for(int p=h[now];p;p=ne[p])
{
int v=to[p];
if(!val[p] || lev[v]!=lev[now]+1) continue;
t=dfs(v,imin(maxf,val[p]));
val[p]-=t;
val[p^1]+=t;
maxf-=t;
ret+=t;
}
if(maxf) lev[now]=-1;
return ret;
}
int dinic()
{
int ret=0;
while(bfs()) ret+=dfs(Sd,inf);
return ret;
}
int main()
{
freopen("2084.in","r",stdin);
freopen("2084.out","w",stdout);
scanf("%d",&Tt);
while(Tt--)
{
scanf("%d",&n); ready();
for(int i=1;i<=n;i++) scanf("%d%d",&d[i].a,&d[i].b),w[i]=i;
sort(w+1,w+1+n,cmp1);
int la=d[w[1]].a; d[w[1]].a=1; row[d[w[1]].a]++;
for(int i=2;i<=n;i++)
{
int v=w[i];
if(d[v].a==la) d[v].a=d[w[i-1]].a; else la=d[v].a,d[v].a=d[w[i-1]].a+1;
row[d[v].a]++;
} mh=d[w[n]].a;
sort(w+1,w+1+n,cmp2);
la=d[w[1]].b; d[w[1]].b=1; lie[d[w[1]].b]++;
for(int i=2;i<=n;i++)
{
int v=w[i];
if(d[v].b==la) d[v].b=d[w[i-1]].b; else la=d[v].b,d[v].b=d[w[i-1]].b+1;
lie[d[v].b]++;
} ml=d[w[n]].b;
for(int i=1;i<=mh;i++)
{
ru[S]-=row[i]>>1;
ru[row(i)]+=row[i]>>1;
if(row[i]&1) addedge(S,row(i),1);
}
for(int i=1;i<=ml;i++)
{
ru[T]+=lie[i]>>1;
ru[lie(i)]-=lie[i]>>1;
if(lie[i]&1) addedge(lie(i),T,1);
}
for(int i=1;i<=n;i++)
{
addedge(ia(i),ib(i),1);
red[i]=tt;
addedge(row(d[i].a),ia(i),1);
addedge(ib(i),lie(d[i].b),1);
}
if(ru[S]>0) addedge(Sd,S,ru[S]); else
if(ru[S]<0) addedge(S,Td,-ru[S]);
if(ru[T]>0) addedge(Sd,T,ru[T]); else
if(ru[T]<0) addedge(T,Td,-ru[T]);
for(int i=1;i<=mh;i++)
{
if(ru[row(i)]>0) addedge(Sd,row(i),ru[row(i)]); else
if(ru[row(i)]<0) addedge(row(i),Td,-ru[row(i)]);
}
for(int i=1;i<=ml;i++)
{
if(ru[lie(i)]>0) addedge(Sd,lie(i),ru[lie(i)]); else
if(ru[lie(i)]<0) addedge(lie(i),Td,-ru[lie(i)]);
}
addedge(T,S,inf);
int maxflow=dinic();
for(int i=1;i<=n;i++) printf("%c",(val[red[i]]?('W'):('R')));
printf("\n");
}
return 0;
}第二题 X之谜 （背包DP）
【题目描述】
【解题思路】
①首先确定的是，顺序是没关系的，只需求出来选数的方案数就成。因为选好了，一定可以按题意排好序的。
②把数按照模k的值分类。因为对答案有影响的也只是模数而已。
③背包DP。F[i][j][h]表示做到了模为i的数，已经选了j个数，模数为h的方案数。
那么，假设在模为i的数中选了g个数，选法有w种。
F[i][j+g][(h+g*i)%k]+=F[i-1][j][h]*w;
那，w怎么求？
假设，模为i的有s个数。
那么，就相当于把g个小球放入s个桶的方案数。
建立g个小球，再加入s-1个挡板。第i个挡板到第i-1个挡板之间的球就是桶i里的小球个数，第s个桶的小球数为剩下的小球数（第s-1个挡板之后的小球）
只需求出放挡板的方案数，就是小球放入桶里的方案数。
方案数=C(s+g-1,s-1)，也就是C(s+g-1,g)
④因为C(n+m,n)=C(n+m,m)，拓展证出，交换n,m的值，答案不变。
算组合方案时，要用到逆元……
【代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mods=2017;
int T,n,m,k;
int c[55],cs[5];
ll f[55][55][55],sq[5][55];
ll Pow(ll x,ll y)
{
ll s=1;
for(;y;y>>=1)
{
if(y&1) s=s*x%mods;
x=x*x%mods;
}
return s;
}
int main()
{
freopen("2085.in","r",stdin);
freopen("2085.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
if(n<m) swap(n,m);
memset(f,0,sizeof(f));
for(int i=0;i<k;i++) c[i]=0;
int yc=n/k; cs[0]=yc; cs[1]=yc+1; yc=n%k;
for(int i=0;i<=yc;i++) c[i]=1;
for(int i=0;i<2;i++)
{
ll sd; int yr=cs[i];
for(int j=0;j<=m;j++)
{
sd=1ll;
for(int h=1;h<=j;h++)
sd=sd*(yr+j-h)%mods*Pow(h,mods-2)%mods;
sq[i][j]=sd;
}
}
for(int i=0;i<=m;i++) f[0][i][0]=sq[c[0]][i];
for(int i=0;i<k-1;i++)
for(int j=0;j<=m;j++)
for(int h=0;h<k;h++)
if(f[i][j][h])
{
for(int co=0;co<=m-j;co++)
{
int yu=(h+(i+1)*co%k)%k;
(f[i+1][j+co][yu]+=(f[i][j][h]*sq[c[i+1]][co])%mods)%=mods;
}
}
printf("%lld\n",f[k-1][m][0]);
}
return 0;
}第三题 大数开方 （模拟题）
【题目描述】
【解题思路】
按照题意模拟即可。
【代码】
#include<cstdio>
#include<algorithm>
#include<cstring>
int l,w;
int ans[1500];
int work(int o,char *O,int I)
{
char c,*D=O;
if(o>0)
{
for(l=0;D[l];D[l++]-=10)
{
D[l++]-=120;
D[l]-=110;
while(!work(0,O,l)) D[l]+=20;
ans[++w]=((D[l]+120-48)/20);
}
}
else
{
if(I>=0) c=o+(D[I]+130-48)%10-(I>l/2)*(D[I-l+I]+120-48)/10-9;
if(I>=0) D[I]+=!(o=work(c/10,O,I-1))*((c+999)%10-(D[I]+140-48)%10);
}
return o;
}
int main()
{
freopen("2086.in","r",stdin);
freopen("2086.out","w",stdout);
char s[1200];s[0]='0';
scanf("%s",s+1);
int sl=strlen(s);
char sp[]="0000000000000000000000";
strcat(s,sp);
if(sl&1) work(2,s+1,0); else work(2,s,0);
if(ans[w]>4) ans[w-1]++;
for(int i=1;i<=w-11;i++) printf("%d",ans[i]);
printf(".");
for(int i=w-10;i<=w-1;i++) printf("%d",ans[i]);
printf("\n");
return 0;
}