int main(){
while(模拟赛) 降智++;
return inf;
}
T1
刚看到题时还以为不可做，重新看了几遍之后才发现以前好像做过……
做法很显然吧……
由于第一行存在 $1-n$ 的数各一个，我们可以先把列 按照第一行的数从大到小排序，这样第 $i$ 列第 $1$ 行的数就是 $i$ 了，方便后续操作。
容易发现，如果第 $2$ 或 第 $3$ 行不存在某个数，那第一行的这个数肯定匹配不上 $2$、$3$ 行相同的数，把这个数在第一行所在的那一列删掉。
然后删掉一列之后，第 $2$、$3$ 行就各少了一个数，那第 $2$ 或 第 $3$ 行就有可能又出现一个不存在的数。重复上述删除过程即可。
可以把要删除的列的编号扔进一个队列，挨个取出后操作。时间复杂度是列数级别，即 $O(n)$。
1 #include<bits/stdc++.h> 2 using namespace std; 3 inline int read(){ 4 int x=0; bool f=1; char c=getchar(); 5 for(;!isdigit(c);c=getchar()) if(c=='-') f=0; 6 for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0'); 7 if(f) return x; 8 return 0-x; 9 } 10 int n; 11 struct num{ 12 int v[4]; 13 bool operator <(const num &x)const{ 14 return v[0]<x.v[0]; 15 } 16 }a[100002]; 17 int cnt[100002],_cnt[100002],ans; 18 bool del[100002]; 19 int main(){ 20 freopen("avogadro.in","r",stdin); 21 freopen("avogadro.out","w",stdout); 22 n=read(); 23 int i,j; 24 for(i=0;i^3;++i) 25 for(j=1;j<=n;++j) 26 a[j].v[i]=read(); 27 sort(a+1,a+n+1); 28 for(i=1;i<=n;++i) ++cnt[a[i].v[1]], ++_cnt[a[i].v[2]]; 29 queue<int>Q; 30 for(i=1;i<=n;++i) if(!cnt[i] || !_cnt[i]) Q.push(i), del[i]=1; 31 int u; 32 while(!Q.empty()){ 33 u=Q.front(), Q.pop(); 34 ++ans; 35 //printf("%d %d %d %d ",u,a[u].v[1],a[u].v[2],ans); 36 if(--cnt[a[u].v[1]]==0 && !del[a[u].v[1]]) del[a[u].v[1]]=1, Q.push(a[u].v[1]); 37 if(--_cnt[a[u].v[2]]==0 && !del[a[u].v[2]]) del[a[u].v[2]]=1, Q.push(a[u].v[2]); 38 } 39 printf("%d ",ans); 40 return 0; 41 }
T2
讲道理，这题的做法以前讲过……
我们发现，我们只需要考虑所有人的连通情况，所以可以设 $dp(i,s)$ 表示考虑到第 $i$ 条边，点的划分（$n!$ 那种）集合为 $s$ 时，所有人在各自集合中都能互相联系的概率。
转移：
下一条线路不能联系 $dp(i,s)+=dp(i-1,s)*p_i$
下一条线路能联系 $dp(i,新线路连接的两个集合)+=dp(i-1,s)*(1-p_i)$
复杂度 $O(n!*m)$。
1 #include<algorithm> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<ctime> 7 #include<iomanip> 8 #include<iostream> 9 #include<map> 10 #include<queue> 11 #include<stack> 12 #include<vector> 13 #define rep(i,x,y) for(register int i=(x);i<=(y);i++) 14 #define dwn(i,x,y) for(register int i=(x);i>=(y);i--) 15 #define maxn 10 16 #define maxm 90 17 #define maxs 363000 18 using namespace std; 19 int read() 20 { 21 int x=0,f=1;char ch=getchar(); 22 while(!isdigit(ch)&&ch!='-')ch=getchar(); 23 if(ch=='-')f=-1,ch=getchar(); 24 while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); 25 return x*f; 26 } 27 void write(int x) 28 { 29 int f=0;char ch[20]; 30 if(!x){putchar('0'),putchar(' ');return;} 31 if(x<0)x=-x,putchar('-'); 32 while(x)ch[++f]=x%10+'0',x/=10; 33 while(f)putchar(ch[f--]); 34 putchar(' '); 35 } 36 int mul[maxn],tmp[maxn],tmp2[maxn],eu[maxm],ev[maxm],n,m; 37 long double ew[maxm],p[2][maxs]; 38 int gx(int x,int y){return (x-1)*mul[y-1];} 39 void bac(int S) 40 { 41 dwn(i,n,1) 42 { 43 tmp[i]=S/mul[i-1]+1; 44 S%=mul[i-1]; 45 } 46 } 47 int gets() 48 { 49 int s=0; 50 rep(i,1,n) 51 { 52 s+=gx(tmp2[i],i); 53 } 54 return s; 55 } 56 /* 57 int maxs; 58 void getst(int x) 59 { 60 if(x==10) 61 { 62 int s=0; 63 rep(i,1,9) 64 { 65 s+=gx(fa[i],i); 66 } 67 if(yes[s]){cout<<s<<"nooooooo";exit(0);} 68 // else cout<<"+"<<s<<endl; 69 bac(s); 70 yes[s]=1; 71 maxs=max(maxs,s); 72 return; 73 } 74 rep(i,1,x) 75 { 76 fa[x]=i; 77 getst(x+1); 78 } 79 }*/ 80 int main() 81 { 82 freopen("connect.in","r",stdin); 83 freopen("connect.out","w",stdout); 84 mul[0]=1; 85 rep(i,1,9)mul[i]=mul[i-1]*i; 86 //getst(1); 87 //cout<<maxs; 88 n=read(),m=read(); 89 rep(i,1,m) 90 { 91 eu[i]=read(),ev[i]=read(); 92 if(eu[i]>ev[i])swap(eu[i],ev[i]); 93 double w;scanf("%lf",&w); 94 ew[i]=w; 95 } 96 rep(i,1,n)tmp2[i]=i; 97 int nows=gets(); 98 p[0][nows]=1.0; 99 //cout<<nows<<endl; 100 rep(i,1,m) 101 { 102 //cout<<"i:"<<i<<endl; 103 int now=i&1,pre=now^1; 104 rep(u,0,nows)p[now][u]=0; 105 rep(u,0,nows) 106 { 107 if(p[pre][u]==0.0000)continue; 108 bac(u);//cout<<"tmp:"<<p[i][u]<<endl; 109 //rep(j,1,n)cout<<tmp[j]<<" ";cout<<endl; 110 int ss=tmp[eu[i]],tt=tmp[ev[i]]; 111 if(ss==tt){p[now][u]+=p[pre][u];continue;} 112 if(ss>tt)swap(ss,tt); 113 rep(j,1,n) 114 { 115 if(tmp[j]==tt)tmp2[j]=ss; 116 else tmp2[j]=tmp[j]; 117 } 118 int nxt=gets(); 119 // cout<<"nxt:"; 120 //rep(j,1,n)cout<<tmp2[j]<<" "; 121 //cout<<endl; 122 p[now][nxt]+=p[pre][u]*(1.0-ew[i]); 123 p[now][u]+=p[pre][u]*ew[i]; 124 //cout<<p[i][nxt]<<endl; 125 } 126 } 127 double ans=p[m&1][0]; 128 printf("%.3lf",ans); 129 return 0; 130 }
T3
超纲题
跟韩爷出的血小板题差不多，可以爆卡。
只不过直接记录走过的横坐标长和纵坐标长的 $bfs$ 有问题，比如说
4
0000
0000
0010
0100
对于上面这个图，举个例子，$(3,1)$ 到欧几里得距离最近的豆子应该是 $(4,2)$。
但当你更新 $(3,2)$ 时，不同的行走顺序可能导致更新它的点不一样。如果这个点脸黑被 $(3,3)$ 先更新了，由于 $(4,2)$ 到 $(3,2)$ 的欧几里得距离 与 $(3,3)$ 到 $(3,2)$ 的相同，后来的 $(4,2)$ 点就刷不掉它，那 $(3,1)$ 这个点的最短距离就被更新错了，因为 $(3,1)$ 到 $(4,2)$ 的欧几里得距离更近。
不过可能是数据较水的缘故，如果改为向周围 $8$ 格扩展最短距离的话好像能避免上述问题。因为不存在多个起点到相邻两格的距离相等的问题，加个斜向扩展可以避免它旁边有一个格子更新冲突而导致它被更新错的情况。复杂度……好像是 $O(n^2*log(n))$ 的，爆卡卡过了……
1 #include<bits/stdc++.h> 2 #define rep(i,x,y) for(register int i=(x);i<=(y);i++) 3 #define dwn(i,x,y) for(register int i=(x);i>=(y);i--) 4 #define maxn 1510 5 #define maxnum (maxn*maxn) 6 #define maxm 300010 7 using namespace std; 8 int read() 9 { 10 int x=0,f=1;char ch=getchar(); 11 while(!isdigit(ch)&&ch!='-')ch=getchar(); 12 if(ch=='-')f=-1,ch=getchar(); 13 while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); 14 return x*f; 15 } 16 void write(int x) 17 { 18 int f=0;char ch[20]; 19 if(!x){putchar('0'),putchar(' ');return;} 20 if(x<0)x=-x,putchar('-'); 21 while(x)ch[++f]=x%10+'0',x/=10; 22 while(f)putchar(ch[f--]); 23 putchar(' '); 24 } 25 char s[maxn][maxn]; 26 int qx[maxnum],qy[maxnum],dis[maxn][maxn],vis[maxn][maxn],fx[maxn][maxn],fy[maxn][maxn],n,m,num; 27 typedef struct node{int x,y,w;bool operator <(const node &z)const{return w>z.w;}}stnd; 28 priority_queue<stnd>q; 29 stnd make(int x,int y,int w){stnd tmp;tmp.x=x,tmp.y=y,tmp.w=w;return tmp;} 30 int dx[8]={0,1,1,1,0,-1,-1,-1},dy[8]={1,0,-1,1,-1,0,-1,1}; 31 int d(int xa,int ya,int xb,int yb){return (xa-xb)*(xa-xb)+(ya-yb)*(ya-yb);} 32 int yes(int x,int y){if(x>=1&&x<=n&&y>=1&&y<=n)return 1;return 0;} 33 int main() 34 { 35 freopen("dist.in","r",stdin); 36 freopen("dist.out","w",stdout); 37 srand(time(0)); 38 n=read(); 39 memset(dis,0x7f,sizeof(dis)); 40 rep(i,1,n) 41 { 42 scanf("%s",s[i]+1); 43 rep(j,1,n) 44 if(s[i][j]=='1') 45 { 46 fx[i][j]=i,fy[i][j]=j,dis[i][j]=0; 47 q.push(make(i,j,0)); 48 } 49 rep(j,1,n)if(s[i][j]=='1')qx[++num]=i,qy[num]=j; 50 } 51 m=read(); 52 if(n<=300&&(m<=300||num*m<=100000000)) 53 { 54 while(m--) 55 { 56 int x=read(),y=read(),ans=2147483647; 57 rep(i,1,num)if(d(x,y,qx[i],qy[i])<ans)ans=d(x,y,qx[i],qy[i]); 58 write(ans); 59 } 60 return 0; 61 } 62 while(!q.empty()) 63 { 64 int ux=q.top().x,uy=q.top().y; 65 if(q.top().w>dis[ux][uy]){q.pop();continue;} 66 q.pop(); 67 rep(i,0,7) 68 { 69 int nx=ux+dx[i],ny=uy+dy[i]; 70 if(!yes(nx,ny))continue; 71 if(dis[nx][ny]==d(fx[ux][uy],fy[ux][uy],nx,ny)&&(fx[ux][uy]!=fx[nx][ny]||fy[ux][uy]!=fy[nx][ny])) 72 { 73 if(rand()&1)fx[nx][ny]=fx[ux][uy],fy[nx][ny]=fy[ux][uy]; 74 } 75 if(dis[nx][ny]>d(fx[ux][uy],fy[ux][uy],nx,ny)) 76 { 77 dis[nx][ny]=d(fx[ux][uy],fy[ux][uy],nx,ny); 78 fx[nx][ny]=fx[ux][uy],fy[nx][ny]=fy[ux][uy]; 79 // cout<<"nx:"<<nx<<" ny:"<<ny<<" dis:"<<dis[nx][ny]<<endl; 80 q.push(make(nx,ny,dis[nx][ny])); 81 } 82 } 83 } 84 while(m--) 85 { 86 int x=read(),y=read(); 87 write(dis[x][y]); 88 } 89 return 0; 90 }
当然更暴力的就直接 $KDTree$ 了（好短啊）……
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int MX = 1500 * 1500 + 10; const LL inf = 1e18; struct Point { int xy[2], l, r, id; } P[MX]; int cmpw; LL ans; char grid[1510][1510],inh[1510][1510]; bool cmp(const Point &a, const Point &b) {return a.xy[cmpw] < b.xy[cmpw];} int build(int l, int r, int w) { int m = (l + r) >> 1; cmpw = w; nth_element(P + l, P + m, P + 1 + r, cmp); P[m].l = l != m ? build(l, m - 1, !w) : 0; P[m].r = r != m ? build(m + 1, r, !w) : 0; return m; } LL dist(LL x, LL y = 0) {return x * x + y * y;} void query(int rt, int w, LL x, LL y) { LL temp = dist(x - P[rt].xy[0], y - P[rt].xy[1]); if(temp) ans = min(ans, temp); if(P[rt].l && P[rt].r) { bool sign = !w ? (x <= P[rt].xy[0]) : (y <= P[rt].xy[1]); LL d = !w ? dist(x - P[rt].xy[0]) : dist(y - P[rt].xy[1]); query(sign ? P[rt].l : P[rt].r, !w, x, y); if(d < ans) query(sign ? P[rt].r : P[rt].l, !w, x, y); } else if(P[rt].l) query(P[rt].l, !w, x, y); else if(P[rt].r) query(P[rt].r, !w, x, y); } int main() { freopen("dist.in","r",stdin); freopen("dist.out","w",stdout); int n,nm = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%s",grid[i] + 1); for(int j = 1; j <= n; j++) { if(grid[i][j] == '1') { nm++; P[nm].xy[0] = i; P[nm].xy[1] = j; inh[i][j] = 1; } } } int rt = build(1, nm, 0); int q;scanf("%d",&q); while(q--) { int x = read(),y = read(); if(inh[x][y]){puts("0");continue;} ans = inf; query(rt, 0, x, y); printf("%lld ", ans); } }
老师的做法……其实是斜率优化 $dp$。
就是说，可以先预处理出每个数在自己那一行上到离他最近的豆子的距离，然后再推出每个数在竖列上的最优取值：
$dis_{i,j}=min{dis_{i',j}^2+(i-i')^2} space | space i'le i$
（当然，从下往上还得推一次）
上式转化得到 $dis_{i,j}=min{dis_{i',j}^2 - 2 imes i imes i' + i'^2}+i^2 space | space i'le i$
去掉 $min$，$-2 imes i$ 是 斜率$k$，$i'$ 就是 $x$，其余的项合起来就是截距 $b$。具体实现什么的不说了。