CodeForces 484E Sign on FenceUVALive 7469 Distance on TriangulationHDU 4812 D TreeCodeForces 97B SupersetOpenJ_POJ C15C Rabbits FestivalHDU 5721 PalaceHDU 5755 Gambler Bo

CodeForces 484E Sign on Fence

填坑

UVALive 7469 Distance on Triangulation

给一个三角剖分后的凸包(n<=50000)，10^5次询问，问你某2点的最短路。 选一条边AB把图分成2半，那么如果 两个点不在同侧，那么最短路至少经过A,B中的一个，可以用2次bfs搞定， 两个点在同侧但经过A或B，也可以如此搞定 两个点在同侧但不经过A或B，分治做下去 我这里用的是重构图的方法

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (100000+10) int n; struct edge{ int u,v; edge(int _u,int _v):u(_u),v(_v){} edge(){} }; struct ask{ int l,r,i; ask(int _l,int _r,int _i):l(_l),r(_r),i(_i){} ask(){} }; int ans[MAXN]; bool inside(int i,int l,int r) { if (l<=r) return l<=i&&i<=r; else return i>=l||i<=r; } int len(int l,int r,int n){ if (l<=r) return r-l+1; return n-(l-r-1); } vi e[MAXN]; void bfs(vector<edge> &edges,vector<int> &d,int n,int s) { queue<int> q; Rep(i,n) d[i]=INF; d[s]=0; q.push(s); int sz=edges.size(); Rep(i,sz) { e[edges[i].u].pb(edges[i].v); e[edges[i].v].pb(edges[i].u); } Rep(i,n) e[i].pb((i+1)%n),e[(i+1)%n].pb(i); while(!q.empty()) { int x=q.front(); q.pop(); Rep(j,e[x].size()) { int v=e[x][j]; if (d[v]==INF) { d[v]=d[x]+1; q.push(v); } } } Rep(i,n) e[i].clear(); } void work(vector<edge> &edges,int n,vector<ask> &q) { if (edges.empty()) { int sz2=SI(q); Rep(i,sz2) { ask now=q[i]; ans[now.i]=min(ans[now.i],min(len(now.l,now.r,n)-1,len(now.r,now.l,n)-1)); } return; } int sz=SI(edges); int r=0; Rep(i,sz) { int u=edges[i].u,v=edges[i].v; if (max(len(u,v,n),len(v,u,n))<max(len(edges[r].u,edges[r].v,n),len(edges[r].v,edges[r].u,n))) { r=i; } } int L=edges[r].u,R=edges[r].v; if(L>R) swap(L,R); int sz2=SI(q); vi d(n); bfs(edges,d,n,L); Rep(i,sz2) ans[q[i].i]=min(ans[q[i].i],d[q[i].l]+d[q[i].r]); bfs(edges,d,n,R); Rep(i,sz2) ans[q[i].i]=min(ans[q[i].i],d[q[i].l]+d[q[i].r]); vector<edge> e1,e2; vector<ask> q1,q2; Rep(i,sz2) { ask now=q[i]; if (now.l==L||now.r==L||now.l==R||now.r==R) continue; int fl=inside(now.l,L,R),fl2=inside(now.r,L,R); if (fl&&fl2) { q1.pb(ask(now.l-L,now.r-L,now.i)); } int fl3=inside(now.l,R,L),fl4=inside(now.r,R,L); if (fl3&&fl4){ q2.pb(ask((now.l-R+n)%n,(now.r-R+n)%n,now.i)); } } Rep(i,sz) if (i^r) { int u=edges[i].u,v=edges[i].v; int fl=inside(u,L,R),fl2=inside(v,L,R); if (fl&&fl2) { e1.pb(edge(u-L,v-L)); } else { e2.pb(edge((u-R+n)%n,(v-R+n)%n)); } } work(e1,len(L,R,n),q1); work(e2,len(R,L,n),q2); } vector<edge> edges; vector<ask> q; int main() { // freopen("data.out","r",stdin); // freopen("B.out","w",stdout); while(cin>>n) { edges.clear();q.clear(); Rep(i,n-3) { int u=read(),v=read(); u--,v--; edges.pb(edge(u,v)); } int m=read(); For(i,m) { int l=read(),r=read(); l--,r--; q.pb(ask(l,r,i)); } For(i,m) ans[i]=INF; work(edges,n,q); For(i,m) printf("%d\n",ans[i]); } return 0; }

HDU 4812 D Tree

树上每一个点有一个数字，找一条链使其上的数乘积mod F=K(F是质数) 经典题 Hint：树分治，对每一个节点Hash乘积，显然 dp[x]∗v[root]=K∗dp[y]−1(modF)

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") #define F (1000003) #define MAXN (100000+10) #define MAXM (200000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int n; int edge[MAXM],Next[MAXM]={0},pre[MAXN]={0},size=0; void addedge(int u,int v) { edge[++size]=v; Next[size]=pre[u]; pre[u]=size; } void addedge2(int u,int v){addedge(u,v),addedge(v,u);} int v[MAXN],K; int opt[MAXN],siz[MAXN],val[MAXN]={0},all[MAXN],tot=0; void dfs(int x,int fa) { siz[x]=1;opt[x]=0;all[++tot]=x; Forp(x) { int &v=edge[p]; if (v^fa&&!val[v]) { dfs(v,x);siz[x]+=siz[v]; opt[x]=max(opt[x],siz[v]); } } } int h[F]={0},b[F]={0}; int cas=0; ll pow2(ll a,int b,ll p) //a^b mod p { if (b==0) return 1%p; if (b==1) return a%p; ll c=pow2(a,b/2,p)%p; c=c*c%p; if (b&1) c=c*a%p; return c%p; } ll Inv(ll a,ll p) { //gcd(a,p)=1 return pow2(a,p-2,p); } ll inv[F]; void prework() { Rep(i,F) inv[i]=Inv(i,F); } void dfs_calc(int x,int fa,ll t,int cas) { t=mul(t,v[x]); if (b[t]!=cas||h[t]>x) h[t]=x,b[t]=cas; Forp(x) { int &v=edge[p]; if (v^fa&&!val[v]) { dfs_calc(v,x,t,cas); } } } pi ans; void upd(pi &v,pi t) { if (t.se==t.fi) return; if (t.se<t.fi) swap(t.se,t.fi); v=min(v,t); } void dfs_calc2(int x,int fa,ll t,int cas) { t=mul(t,inv[v[x]]); if (b[t]==cas) { upd(ans,mp(x,h[t])); } Forp(x) { int &v=edge[p]; if (v^fa&&!val[v]) { dfs_calc2(v,x,t,cas); } } } void solve(int root,int l) { tot=0,dfs(root,0); int minopt=INF,minoptx=0; For(i,tot) { int u=all[i]; opt[u]=max(opt[u],tot-siz[u]); if (minopt>opt[u]) minopt=opt[u],minoptx=u; } val[root=minoptx]=l; ++cas; Forp(root) { int &V=edge[p]; if (!val[V]) { dfs_calc2(V,root,K,cas); dfs_calc(V,root,v[root],cas); } } if (b[K]==cas) upd(ans,mp(root,h[K])); Forp(root) { int &v=edge[p]; if (!val[v]) solve(v,l+1); } } int main() { // freopen("D.in","r",stdin); prework(); while(cin>>n>>K) { MEM(edge) MEM(Next) MEM(pre) size=0; MEM(opt) MEM(siz) MEM(val) For(i,n) v[i]=read(); For(i,n-1) { int u,v; scanf("%d%d",&u,&v); addedge2(u,v); } ans=mp(INF,INF); solve(1,1); if (ans==mp(INF,INF)) puts("No solution"); else { printf("%d %d\n",ans.fi,ans.se); } } return 0; }

CodeForces 97B Superset

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int n; #define MAXN (200000+10) pi a[MAXN]; int t[MAXN]; int find(int x) { return lower_bound(t,t+n,x)-t;} void f(int l,int r) { if (l==r) return; int m=(l+r)/2; Fork(i,l,r) a[n++]=mp(a[m].fi,a[i].se); if (l<=m) f(l,m); if (m+1<=r) f(m+1,r); } int main() { // freopen("E.in","r",stdin); // freopen(".out","w",stdout); cin>>n; Rep(i,n) a[i].fi=read(),a[i].se=read(); sort(a,a+n); f(0,n-1); sort(a,a+n); int m=unique(a,a+n)-a; cout<<m<<endl; Rep(i,m) cout<<a[i].fi<<' '<<a[i].se<<endl; return 0; }

OpenJ_POJ C15C Rabbit’s Festival

给一张无向图0 ≤ N, 0 ≤ M ≤ 200000,有K天，第i条路第 ci 天关闭 K ≤ 100000 求每天互相可达的点对数

并查集+cdq 记得必须按秩合并，回滚数组（不然会是 O(n2lognα(n)) 的）

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") #define MAXN (100000+10) #define MAXM (200000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } struct node{ int u,v,szu,szv,rku,rkv; node(int u,int v,int szu,int szv,int rku,int rkv):u(u),v(v),szu(szu),szv(szv),rku(rku),rkv(rkv){} node(){} }; class bingchaji { public: int father[MAXN],sz[MAXN],n,rank[MAXN]; node S[MAXN]; int siz; ll c; void mem(int _n) { n=_n; c=0; siz=0; For(i,n) father[i]=i,sz[i]=1,rank[i]=1; } int getfather(int x) { if (father[x]==x) return x; return getfather(father[x]); } void unite(int x,int y) { x=getfather(father[x]); y=getfather(father[y]); if (x==y) return; if (rank[x]>rank[y]) swap(x,y); S[++siz]=node(x,y,sz[x],sz[y],rank[x],rank[y]); c+=(ll)sz[x]*sz[y]; sz[y]+=sz[x]; sz[x]=0; rank[y]=max(rank[x]+1,rank[y]); father[x]=y; } void back(int x) { while(siz>x){ node now=S[siz]; int u=now.u,v=now.v; c-=(ll)now.szu*now.szv; father[u]=u; father[v]=v; sz[u]=now.szu; sz[v]=now.szv; rank[u]=now.rku; rank[v]=now.rkv; --siz; } } bool same(int x,int y) { return getfather(x)==getfather(y); } }S; struct edge{ int u,v; edge(int _u=0,int _v=0):u(_u),v(_v){} }; vector<edge> edges[MAXN]; int n,m,k; void work(int l,int r) { Fork(i,l,r) { int sz=SI(edges[i]); Rep(j,sz) { S.unite(edges[i][j].u,edges[i][j].v); } } } void cdq(int l,int r) { if (l==r) { printf("%lld\n",S.c); return; } int m=(l+r)>>1; int top=S.siz; work(m+1,r); cdq(l,m); S.back(top); work(l,m); cdq(m+1,r); } int main() { // freopen("F.in","r",stdin); // freopen(".out","w",stdout); while(scanf("%d%d%d",&n,&m,&k)==3) { S.mem(n); For(i,m) { int u=read(),v=read(),c=read(); if (c>k) S.unite(u,v); else edges[c].pb(edge(u,v)); } cdq(1,k); For(i,n) edges[i].clear(); } return 0; }

HDU 5721 Palace

10^5个点(x,y)，每次拿掉一个点，求最近公共点对距，把所有点各拿走一遍，求和。 SB题

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF ((ll)(1e20)) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long long ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } ld sqr(ld a){return a*a;} #define MAXN (100000+10) class P{ public: ld x,y; P(){} P(ld x,ld y):x(x),y(y){} friend long double dis2(P A,P B){return sqr(A.x-B.x)+sqr(A.y-B.y); } friend ll dis(P A,P B){return dis2(A,B); } friend bool operator<(P A,P B) { return A.x<B.x; } }a[MAXN],a2[MAXN]; int t[MAXN]; int cmp(const void *x,const void *y) { return a[*(int*)x].y-a[*(int*)y].y; } ll Abs(ll a){return (a<0)?-a:a;} pi p; ll ans=INF; ll bsearch(int l,int r) { int m=(l+r)/2; if (l==r) return (ll)(1e20); ll d=min(bsearch(l,m),bsearch(m+1,r)); int k=0; Fork(i,l,r) { if (Abs(a[m].x-a[i].x)<=d) { t[++k]=i; } } qsort(t+1,k,sizeof(int),cmp); For(i,k) { Fork(j,i+1,k) { if (a[t[j]].y-a[t[i]].y>d) break; ll d2=dis(a[t[i]],a[t[j]]); if (d2<d) { d=d2; if (ans>d2) ans=d2,p=mp(t[i],t[j]); } } } return d; } int main() { // freopen("G.in","r",stdin); // freopen(".out","w",stdout); int T=read(); while(T--) { int n=read(); For(i,n) a[i].x=read(),a[i].y=read(); sort(a+1,a+1+n); ans=INF; ll dis=bsearch(1,n); dis*=(ll)n-2; memcpy(a2,a,sizeof(a)); int t=p.se; swap(a[p.fi],a[n]); sort(a+1,a+n); dis+=bsearch(1,n-1); memcpy(a,a2,sizeof(a)); swap(a[t],a[n]); sort(a+1,a+n); dis+=bsearch(1,n-1); cout<<dis<<endl; } return 0; }

HDU 5755 Gambler Bo

给一个30*30的矩阵，求电灯开关问题的一个合法解 高斯消元 容易证明复杂度是O(N^2h)=O(n^5)的

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (3) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (900+10) typedef int Matrix[MAXN][MAXN]; void gauss_elimination(Matrix A, int n) { //假设系数矩阵A可逆 A[0..n-1,0..n] //运行结束后A[i][i]极为第i个变量的值 Rep(i,n) { int r=i; Fork(j,i+1,n-1) { if (fabs(A[j][i])>fabs(A[r][i])) r=j; } if (r>i) { Rep(j,n+1) swap(A[r][j],A[i][j]); } Fork(k,i+1,n-1) { while(A[k][i]) ForkD(j,i,n) {A[k][j] += A[i][j]; A[k][j]%=3; } } } RepD(i,n-1) { Fork(j,i+1,n-1) A[i][n] -= A[j][n] * A[i][j]; A[i][n] *= A[i][i]; A[i][n]=sub(A[i][n],0); } } Matrix A; int a[MAXN][MAXN],n,m; int id(int i,int j){return i*m+j;} bool inside(int i,int j){return 0<=i&&i<n&&0<=j&&j<m; } int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int main() { // freopen("H.in","r",stdin); // freopen(".out","w",stdout); int T=read(); while(T--) { MEM(A) n=read(),m=read(); Rep(i,n) Rep(j,m) { a[i][j] = read(); } Rep(i,n) Rep(j,m) { int id1=id(i,j); Rep(d,4) { int x=i+dir[d][0],y=j+dir[d][1]; if (!inside(x,y)) continue; int id2=id(x,y); A[id1][id2]=1; } A[id1][id1]=2; A[id1][n*m]=(3-a[i][j])%3; } gauss_elimination(A,n*m); vector<pi> v; Rep(i,n*m) Rep(j,A[i][n*m]) v.pb(mp(i/m+1,i%m+1)); cout<<SI(v)<<endl; Rep(i,SI(v)) printf("%d %d\n",v[i].fi,v[i].se); cout<<endl; } return 0; }