2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly
如果一个正方形有两条边a,b
则a->op(b) b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll 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; int a[5],mark[60],mp[60][60]; int getint(char a,char b) { if(a=='0')return -1; int t=a-'A'; if(b=='-')t+=26; return t; } int op(int x) { return x<26?x+26:x-26; } void dfs(int x) { for(int i=0;i<52;i++) if(!mark[i]&&mp[x][i]) { mark[i]=1; dfs(i); } } int main() { n=read(); char ch[10]; for(int i=1;i<=n;i++) { scanf("%s",ch+1); for(int k=1;k<=4;k++) a[k]=getint(ch[k*2-1],ch[k*2]); for(int j=1;j<=4;j++) for(int k=j+1;k<=4;k++) if(a[j]!=-1&&a[k]!=-1) { int u=a[j],v=a[k]; mp[u][op(v)]=mp[v][op(u)]=1; } } for(int i=0;i<52;i++) { memset(mark,0,sizeof(mark)); dfs(i); if(mark[i]){puts("unbounded");return 0;} } puts("bounded"); return 0; } |
C.Surely You Congest
只有最短路相同的会互相影响
按最短路分组后跑 c 次最大流
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll 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,c,cnt,ans; int last[25005],dis[25005],q[25005],h[25005],id[25005],cur[25005]; int u[50005],v[50005],w[50005]; bool vis[25005]; struct edge{ int to,next,v; }e[200005]; priority_queue<pa,vector<pa>,greater<pa> >pq; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; } void dijkstra() { pq.push(make_pair(0,1)); dis[1]=0;for(int i=2;i<=n;i++)dis[i]=inf; while(!pq.empty()) { int x=pq.top().second;pq.pop(); if(vis[x])continue;vis[x]=1; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&dis[x]+e[i].v<dis[e[i].to]) { dis[e[i].to]=dis[x]+e[i].v; pq.push(make_pair(dis[e[i].to],e[i].to)); } } } bool bfs() { int head=0,tail=1; for(int i=0;i<=n;i++)h[i]=-1; q[0]=0;h[0]=0; while(head!=tail) { int x=q[head];head++; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==-1&&e[i].v) { h[e[i].to]=h[x]+1; q[tail++]=e[i].to; } } return h[1]!=-1; } int dfs(int x,int f) { if(x==1)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) if(h[x]+1==h[e[i].to]&&e[i].v) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; if(e[i].v)cur[x]=i; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } void solve(int a,int b) { cnt=1;for(int i=0;i<=n;i++)last[i]=0; int tmp = 0; for(int i=a;i<=b;i++) if(dis[id[i]]<inf) { insert(0,id[i],1); insert(id[i],0,0); tmp++; } if(tmp<=1) { ans+=tmp; return; } for(int i=1;i<=m;i++) { int a=u[i],b=v[i],c=w[i]; insert(b,a,1); insert(a,b,0); } while(bfs()) { for(int i=0;i<=n;i++)cur[i]=last[i]; ans+=dfs(0,inf); } } bool cmp(int a,int b) { return dis[a]<dis[b]; } int main() { n=read();m=read();c=read(); for(int i=1;i<=m;i++) { u[i]=read(),v[i]=read(),w[i]=read(); insert(u[i],v[i],w[i]); insert(v[i],u[i],w[i]); } for(int i=1;i<=c;i++)id[i]=read(); dijkstra(); int t=0; for(int i=1;i<=m;i++) { if(dis[u[i]]>dis[v[i]])swap(u[i],v[i]); if(dis[u[i]]+w[i]==dis[v[i]]) { t++; swap(u[t],u[i]); swap(v[t],v[i]); swap(w[t],w[i]); } } m=t; sort(id+1,id+c+1,cmp); for(int i=1,j;i<=c;i=j) { for(j=i;dis[id[j]]==dis[id[i]]&&j<=c;j++); solve(i,j-1); } printf("%d\n",ans); return 0; } |
D.Factors
爆搜前16个素数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll unsigned long long #define inf (1ULL<<63) using namespace std; ll n; ll pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; ll c[65][65]; map<ll,ll>ans; void pre() { c[0][0]=1; for(int i=1;i<=62;i++) { c[i][0]=1; for(int j=1;j<=i;j++) if(c[i-1][j-1]<inf&&c[i-1][j]<inf) c[i][j]=c[i-1][j]+c[i-1][j-1]; else c[i][j]=inf; } } void dfs(ll n,ll now,ll tot,int k) { if(tot>0) if(ans[n]==0||now<ans[n]) ans[n]=now; ll t=now,cnt=0; while(1) { if(pri[k]>inf/t) break; t*=pri[k];cnt++; if(c[tot+cnt][cnt]<=inf/n) dfs(n*c[tot+cnt][cnt],t,tot+cnt,k+1); } } int main() { pre(); dfs(1,1,0,0); while(scanf("%llu",&n)!=EOF) { printf("%llu %llu \n",n,ans[n]); } return 0; } |
F.Low Power
二分答案贪心检验
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll 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,K,m; int a[1000005]; bool mark[1000005]; bool check(int mid) { memset(mark,0,sizeof(mark)); int now=0,t=0,p=0; for(int i=1;i<m;i++) if(!mark[i]&&now<n&&a[i+1]-a[i]<=mid) { mark[i]=mark[i+1]=1; now++; } if(now!=n)return 0; for(int i=m;i;i--) if(!mark[i])t++; else { p++; if(t<p*(K-1))return 0; } return 1; } int main() { n=read();K=read();m=2*n*K; for(int i=1;i<=m;i++)a[i]=read(); sort(a+1,a+m+1); int l=0,r=1000000000; while(l<=r) { int mid=(l+r)>>1; if(check(mid))r=mid-1; else l=mid+1; } printf("%d\n",l); return 0; } |
H:Матрëшка
预处理\(f(i,j)\)表示将 i 到 j 全部套在一起的最小代价，枚举断点
合并两组套娃，不用拆开的情况是某一个套娃比另一组的最小套娃还小
维护前缀和，前缀后缀的最小值，能够\(O(1)\)完成转移
\(g(i)\)表示把前 i 个套娃套成若干完整套娃的最小代价，转移显然
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; int v[505],sum[505][505],LG[505],f[505][11],n,a[505],i,j,M1,M2,dp[505][505],k,DP[505],sum2,MAX; int MIN(int l,int r) { int t=LG[r-l+1]; return min(f[l][t],f[r-(1<<t)+1][t]); } int main() { scanf("%d",&n); for (i=1; i<=n; i++) scanf("%d",&a[i]); for (i=1; i<=n; i++) sum[i][a[i]]=1; for (i=1; i<=n; i++) for (j=1; j<=500; j++) sum[i][j]+=sum[i-1][j]; for (i=1; i<=n; i++) for (j=1; j<=500; j++) sum[i][j]+=sum[i][j-1]; for (i=1; i<=n; i++) f[i][0]=a[i]; for (i=1; i<=n; i++) LG[i]=int(log(i)/log(2)+0.000000001); for (i=1; i<=LG[n]; i++) for (j=1; j<=n-(1<<i)+1; j++) f[j][i]=min(f[j][i-1],f[j+(1<<i-1)][i-1]); for (i=1; i<n; i++) for (j=1; j<=n-i; j++) { dp[j][i+j]=453266144; for (k=j; k<i+j; k++) { M1=MIN(j,k); M2=MIN(k+1,i+j); dp[j][i+j]=min(dp[j][i+j],dp[j][k]+dp[k+1][i+j]+i+1-sum[i+j][M1]+sum[k][M1]-sum[k][M2]+sum[j-1][M2]); } } for (i=1; i<=n; i++) { DP[i]=453266144; MAX=0; sum2=0; for (j=i; j>=1; j--) { if (v[a[j]]==i) break; v[a[j]]=i; MAX=max(MAX,a[j]); sum2+=a[j]; if (MAX*(MAX+1)/2==sum2) DP[i]=min(DP[i],DP[j-1]+dp[j][i]); } } if (DP[n]>=453266144) cout<<"Impossible";else cout<<DP[n]; return 0; } |
I.Pirate Chest
用单调栈把暴力优化成\(O(n^3)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; ll read() { ll 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; } ll ans; ll a,b,m,n; int h[505][505],val[505]; int q[505]; int l[505],r[505],mn[505][505]; void solve(int x,int y) { if(y>a&&y>b)return; int lim=max(a,b); if(y>a)lim=a; else if(y>b)lim=b; for(int k=1;k<=m;k++)val[k]=mn[y][k]=min(mn[y-1][k],h[x][k]); int top=0;val[0]=-1; for(int i=1;i<=m;i++) { while(val[i]<=val[q[top]])top--; l[i]=q[top];q[++top]=i; } top=0;q[++top]=m+1;val[m+1]=-1; for(int i=m;i;i--) { while(val[i]<=val[q[top]])top--; r[i]=q[top];q[++top]=i; } for(int i=1;i<=m;i++) { ll len=min(lim,r[i]-l[i]-1); ll h=(n*m*val[i]-1)/(n*m-y*len); ans=max(ans,y*h*len); } } int main() { memset(mn,127,sizeof(mn)); a=read();b=read();n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) h[i][j]=read(); for(int i=n;i;i--) for(int j=n-i+1;j;j--) solve(i,j); printf("%lld\n",ans); return 0; } |
J.Pollution Solution
辛普森积分
但是可能被构造卡掉，可以把积分的范围调整一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define eps 1e-8 #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; struct P{ double x, y; P(){} P(double _x, double _y):x(_x), y(_y){} friend P operator-(P a, P b){ return P(a.x - b.x, a.y - b.y); } friend double operator*(P a, P b){ return a.x * b.y - a.y * b.x; } }p[105]; struct L{ P a, b; }l[105]; vector<double> ve; int n; double R; void add(double X, L l) { if(l.a.x < X - eps && l.b.x < X - eps)return; if(l.a.x > X + eps && l.b.x > X + eps)return; if(fabs(X - l.a.x) < eps && fabs(X - l.b.x) < eps)return; double t; if(fabs(l.b.x - X) < eps)t = l.b.y; else t = (X - l.a.x) / (l.b.x - X); ve.push_back(l.a.y + (l.b.y - l.a.y) * t / (t + 1)); } double F(double X) { if(abs(X) > R)return 0; ve.clear(); for(int i = 1; i <= n; i++) add(X, l[i]); double U = sqrt(R * R - X * X), ANS = 0; sort(ve.begin(), ve.end()); bool flag = 0; for(int i = 0; i < (int)ve.size() - 1; i++) { flag ^= 1; if(ve[i] > U)break; if(flag) ANS += min(ve[i + 1], U) - ve[i]; } return ANS; } double cal(double fl, double fm, double fr, double L) { return (fl + fm * 4 + fr) * L / 6; } double simpson(double l, double r, double fl, double fm, double fr, double S, int dep) { double mid = (l + r) / 2; double m1 = (l + mid) / 2, m2 = (r + mid) / 2; double f1 = F(m1), f2 = F(m2); double g1 = cal(fl, f1, fm, mid - l), g2 = cal(fm, f2, fr, r - mid); if(fabs(g1 + g2 - S) < 1e-12 && dep >= 10)return g1 + g2; return simpson(l, mid, fl, f1, fm, g1, dep + 1) + simpson(mid, r, fm, f2, fr, g2, dep + 1); } double solve(double l, double r) { if(l > r)return 0; double mid = (l + r) / 2; return simpson(l, r, 0, F(mid), 0, (F(l) + F(r) + F(mid) * 4) * (r - l) / 6, 0); } int main() { scanf("%d%lf", &n, &R); for(int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); p[n + 1] = p[1]; for(int i = 1; i <= n; i++) l[i].a = p[i], l[i].b = p[i + 1]; double ANS = solve(-R, -2) + solve(-2, 1) + solve(1, R); printf("%.10lf\n", ANS); return 0; } |
计数器 9774120
OI 课件=>
OI 课件=>
又是一年WF时