首页 > 代码库 > [APIO2011]
[APIO2011]
来自FallDream的博客，未经允许，请勿转载，谢谢。
------------------------------------------------------
A.[Apio2011]方格染色
Sam和他的妹妹Sara有一个包含n × m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2 × 2的方形区域都包含奇数个（1 个或 3 个）红色方格。例如，右图是一个合法的表格染色方案（在打印稿中，深色代表蓝色，浅色代表红色） 。 可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？ $n,m,k\leqslant 10^{6}$
题解：打表观察了一波，除了答案貌似是2的倍数,很经常是$2^{n+m-1}$以外都不懂，无奈看题解。
我们可以把限制条件当作异或关系式，（我不懂怎么打异或，就用$\veebar$ 代替吧）即对于$x>1且y>1,S[x][y]\veebar S[x][y-1]\veebar S[x-1][y]\veebar S[x-1][y-1]=1$，对于一个在$(a,b),a>1,b>1$的已经有颜色的块，我们把所有$x\leqslant a,y\leqslant b$的异或关系式塔起来，得到$Sab\veebar S[a][1]\veebar S[1][b]\veebar S[1][1]=Color(a,b)$这个式子只有在ab都是偶数的时候，才等于1。假如确定了$(1,1)$的颜色，那我们就能用一个异或方程表示第a行和第b列的关系。那我们就直接枚举$(1,1)$的颜色，通过并查集维护就可以啦。在维护的时候，如果出现矛盾，说明无解，否则假设联通块有num个，答案是$2^{num-1}$
#include<iostream> #include<cstdio> #define MN 1000000 #define mod 1000000000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar();} while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x * f; } int n,m,k,fa[MN*2+5],g[MN*2+5],ans=0; struct limit{int x,y,z;}s[MN+5]; int pow(int x,int k) { int sum=1; for(int i=x;k;k>>=1,i=1LL*i*i%mod) if(k&1) sum=1LL*sum*i%mod; return sum; } int getfa(int x) { if(fa[x]==x) return x; int t=getfa(fa[x]);g[x]^=g[fa[x]]; return fa[x]=t; } int calc() { for(int i=1;i<=m+n;i++) fa[i]=i,g[i]=0;fa[n+1]=1; for(int i=1;i<=k;i++) { if(s[i].x+s[i].y<=2) continue; int x=getfa(s[i].x),y=getfa(s[i].y+n),t=g[s[i].x]^g[s[i].y+n]^s[i].z; if(x!=y){fa[x]=y;g[x]=t;} else if(t) return 0; } int num=0; for(int i=1;i<=n+m;i++) if(fa[i]==i) num++; return pow(2,num-1); } int main() { n=read();m=read();k=read(); bool flag[2]; for(int i=1;i<=k;i++) { s[i].x=read();s[i].y=read();s[i].z=read(); if(s[i].x+s[i].y<3) flag[s[i].z]=1; if(!(s[i].x&1||s[i].y&1)) s[i].z^=1; } if(!flag[1]) ans+=calc(); if(!flag[0]) { for(int i=1;i<=k;i++) if(s[i].x>1&&s[i].y>1)s[i].z^=1; ans+=calc(); } cout<<ans%mod; return 0; }
B.寻路
一个二维平面上有很多个矩形，你要从一个给定的点向上下左右任意方向出发，然后只能在矩形的边上或者角上转弯，问到达另一个点的最短路径。
20组数据，每组矩形数量不超过1000
题解：我们考虑最短路，直接建图最多只会有n^2个点，但是它们不全是有用的，所以我们考虑从每一个矩形的角上向四周出发连边，这样最多只有12n个点，跑最短路就行了。建图稍微复杂点。
复杂度Tnlogn
#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<queue> #define ll long long #define INF 20000000000000LL #define MN 1000 #define mp(x,y) make_pair((x),(y)) #define pa pair<ll,int> using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar();} while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x * f; } int n,cnt,lcnt,cn,head[MN*100]; inline int abs(int x){return x<0?-x:x;} struct L{ int l,r,x; vector<int> s; L(){} L(int l,int r,int x):l(l),r(r),x(x){s.clear();} bool operator<(const L&b)const{return x<b.x;} }r[MN*5+5],c[MN*5+5]; struct P { int x,y; P(int x=0,int y=0):x(x),y(y){} friend int dis(P x,P y){return abs(x.x-y.x)+abs(x.y-y.y);} bool operator==(const P&b)const{return x==b.x&&y==b.y;} }p[MN*MN+5]; bool cmp(int x,int y){return p[x].x==p[y].x?p[x].y<p[y].y:p[x].x<p[y].x;} struct edge{int to,next,w;}e[MN*100+5]; inline void ins(int f,int t,int w){e[++cn]=(edge){t,head[f],w};head[f]=cn;}; priority_queue<pa,vector<pa>,greater<pa> > q; ll d[MN*100];bool mark[MN*100]; void dij() { memset(d,127,sizeof(d));memset(mark,0,sizeof(mark)); d[1]=0;q.push(mp(0,1)); while(!q.empty()) { int now=q.top().second;q.pop(); if(mark[now]) continue;mark[now]=1; for(int i=head[now];i;i=e[i].next) if(d[now]+e[i].w<d[e[i].to]) { d[e[i].to]=d[now]+e[i].w; q.push(mp(d[e[i].to],e[i].to)); } } } int main() { int T=read(); while(T--) { memset(head,0,sizeof(head)); cnt=lcnt=cn=0;int fx=read(),fy=read(),tx=read(),ty=read(); p[++cnt]=P(fx,fy);p[++cnt]=P(tx,ty); if(fx==tx||fy==ty) ins(1,2,dis(p[1],p[2])),ins(2,1,dis(p[1],p[2])); n=read(); for(int i=1;i<=n;i++) { int x1=read(),y1=read(),x2=read(),y2=read(); if(x1>x2) swap(x1,x2);if(y1>y2) swap(y1,y2); p[++cnt]=P(x1,y1);p[++cnt]=P(x1,y2); p[++cnt]=P(x2,y1);p[++cnt]=P(x2,y2); c[++lcnt]=L(cnt-3,cnt-1,y1);r[lcnt]=L(cnt-3,cnt-2,x1); c[++lcnt]=L(cnt-2,cnt,y2);r[lcnt]=L(cnt-1,cnt,x2); } sort(c+1,c+lcnt+1);sort(r+1,r+lcnt+1); for(int i=cnt;i;--i) { int j,id;P now; j=lower_bound(c+1,c+lcnt+1,L(0,0,p[i].y))-c-1; for(;j&&!(p[c[j].l].x<=p[i].x&&p[c[j].r].x>=p[i].x);--j); if(j) { now=P(p[i].x,c[j].x); if(now==p[c[j].l]) id=c[j].l; else if(now==p[c[j].r]) id=c[j].r; else p[id=++cnt]=now; ins(i,id,dis(now,p[i])); ins(id,i,dis(now,p[i])); c[j].s.push_back(id); } j=upper_bound(c+1,c+lcnt+1,L(0,0,p[i].y))-c; for(;j<=lcnt&&!(p[c[j].l].x<=p[i].x&&p[c[j].r].x>=p[i].x);++j); if(j<=lcnt) { now=P(p[i].x,c[j].x); if(now==p[c[j].l]) id=c[j].l; else if(now==p[c[j].r]) id=c[j].r; else p[id=++cnt]=now; ins(i,id,dis(now,p[i])); ins(id,i,dis(now,p[i])); c[j].s.push_back(id); } j=lower_bound(r+1,r+lcnt+1,L(0,0,p[i].x))-r-1; for(;j&&!(p[r[j].l].y<=p[i].y&&p[r[j].r].y>=p[i].y);--j); if(j<=lcnt) { now=P(r[j].x,p[i].y); if(now==p[r[j].l]) id=r[j].l; else if(now==p[r[j].r]) id=r[j].r; else p[id=++cnt]=now; ins(i,id,dis(now,p[i])); ins(id,i,dis(now,p[i])); r[j].s.push_back(id); } j=upper_bound(r+1,r+lcnt+1,L(0,0,p[i].x))-r; for(;j<=lcnt&&!(p[r[j].l].y<=p[i].y&&p[r[j].r].y>=p[i].y);++j); if(j<=lcnt) { now=P(r[j].x,p[i].y); if(now==p[r[j].l]) id=r[j].l; else if(now==p[r[j].r]) id=r[j].r; else p[id=++cnt]=now; ins(i,id,dis(now,p[i])); ins(id,i,dis(now,p[i])); r[j].s.push_back(id); } } for(int i=1;i<=lcnt;i++) { sort(c[i].s.begin(),c[i].s.end(),cmp); for(int j=1;j<c[i].s.size();j++) { ins(c[i].s[j],c[i].s[j-1],dis(p[c[i].s[j]],p[c[i].s[j-1]])); ins(c[i].s[j-1],c[i].s[j],dis(p[c[i].s[j]],p[c[i].s[j-1]])); } sort(r[i].s.begin(),r[i].s.end(),cmp); for(int j=1;j<r[i].s.size();j++) { ins(r[i].s[j],r[i].s[j-1],dis(p[r[i].s[j]],p[r[i].s[j-1]])); ins(r[i].s[j-1],r[i].s[j],dis(p[r[i].s[j]],p[r[i].s[j-1]])); } } dij(); if(d[2]<INF) printf("%lld\n",d[2]); else puts("No Path"); } return 0; }
C题不知道什么鬼，solve=0,貌似数据都是错的，不玩了
[APIO2011]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。