POJ训练记录
1966.Cable TV Network
枚举源汇求最小割
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define pi acos(-1) #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,m,S,T,cnt,ans; struct edge{ int to,next,v; }e[5005]; int last[105],q[205],h[205],u[5005],v[5005]; void insert(int u,int v,int w) { // cout<<u<<' '<<v<<' '<<w<<endl; e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } void build(int x,int y) { cnt=1;memset(last,0,sizeof(last)); insert(S,x,inf);insert(y+n,T,inf); for(int i=0;i<n;i++) if(i!=x&&i!=y) insert(i,i+n,1); else insert(i,i+n,inf); for(int i=1;i<=m;i++) { insert(u[i]+n,v[i],inf); insert(v[i]+n,u[i],inf); } } bool bfs() { int head=0,tail=1; q[0]=S;memset(h,-1,sizeof(h)); h[S]=0; while(head!=tail) { int now=q[head];head++;//cout<<now; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; // cout<<e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } int dinic() { int ans=0; while(bfs())ans+=dfs(S,inf); return ans; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { T=2*n+1;S=2*n; for(int i=1;i<=m;i++) { u[i]=read(),v[i]=read(); if(u[i]>v[i])swap(u[i],v[i]); } ans=n; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { build(i,j); int tmp=dinic(); // cout<<tmp<<endl; ans=min(ans,tmp); } printf("%d\n",ans); } return 0; } |
2386.Lake Counting
搜索
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define pi acos(-1) #define ll long long #define p(x,y) (x-1)*m+y 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,ans; char a[105][105]; bool vis[105][105]; int xx[8]={0,0,1,1,1,-1,-1,-1},yy[8]={1,-1,0,-1,1,0,-1,1}; void dfs(int x,int y) { if(x<1||y<1||x>n||y>m)return; if(vis[x][y])return; vis[x][y]=1; for(int k=0;k<8;k++) if(a[x+xx[k]][y+yy[k]]=='W')dfs(x+xx[k],y+yy[k]); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!vis[i][j]&&a[i][j]=='W')dfs(i,j),ans++; printf("%d\n",ans); return 0; } |
3863.Business Center
枚举每个电梯，二分求最小值
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define pi acos(-1) #define ll long long #define p(x,y) (x-1)*m+y 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; int solve(int a,int b) { int l=0,r=n,ans=inf,mid; while(l<=r) { mid=(l+r)>>1; int t=mid*a-(n-mid)*b; if(t>0)ans=t,r=mid-1; else l=mid+1; } return ans; } int main() { n=read();m=read(); int ans=inf; for(int i=1;i<=m;i++) { int u=read(),v=read(); ans=min(solve(u,v),ans); } printf("%d\n",ans); return 0; } |
2504.Bounding box
求外心然后旋转n次得到多边形坐标
精度弃坑。。
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define sqr(x) x*x #define pi 3.1415926535897932384626 #define ll long long #define eps 1e-8 using namespace std; int n;double t; struct P{ double x,y; friend double dis(P a){ return sqrt(sqr(a.x)+sqr(a.y)); } friend P operator-(P a,P b){ return (P){a.x-b.x,a.y-b.y}; } friend P operator+(P a,P b){ return (P){a.x+b.x,a.y+b.y}; } }p[55]; P rotate(P a,double t) { double x=a.x,y=a.y; return (P){(x*cos(t)-y*sin(t)),(x*sin(t)+y*cos(t))}; } int main() { int cas=0; while(scanf("%d",&n)) { if(n==0)return 0; for(int i=1;i<=3;i++) scanf("%lf%lf",&p[i].x,&p[i].y); double a1=2*(p[2].x-p[1].x),b1=2*(p[2].y-p[1].y),c1=sqr(p[2].x)-sqr(p[1].x)+sqr(p[2].y)-sqr(p[1].y); double a2=2*(p[3].x-p[1].x),b2=2*(p[3].y-p[1].y),c2=sqr(p[3].x)-sqr(p[1].x)+sqr(p[3].y)-sqr(p[1].y); double Y=(c2-c1*a2/a1)/(b2-b1*a2/a1),X=(c2-b2*Y)/a2; p[1]=p[1]-(P){X,Y}; for(int i=2;i<=n;i++) p[i]=rotate(p[1],(i-1)*2*pi/n); double mx=-1e30,my=-1e30,nx=1e30,ny=1e30; for(int i=1;i<=n;i++) { if(p[i].x>mx)mx=p[i].x; if(p[i].y>my)my=p[i].y; if(p[i].x<nx)nx=p[i].x; if(p[i].y<ny)ny=p[i].y; } printf("Polygon %d: %.3lf\n",++cas,(mx-nx)*(my-ny)); } return 0; } |
3155.Hard Life
最大密度子图+方案
分数规划
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1e10 #define eps 1e-8 #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,m,cnt,T; int last[1505],q[1505],h[1505]; bool vis[1505]; struct edge{ int to,next;double v; }e[10005]; int u[1005],v[1005]; vector<int>ans; void insert(int u,int v,double w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } bool bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=0;h[0]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v>eps&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } double dfs(int x,double f) { if(x==T)return f; double w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(f-used,e[i].v)); e[i].v-=w;e[i^1].v+=w; used+=w;if(abs(f-used)<eps)return f; } if(used<eps)h[x]=-1; return used; } void build(double x) { memset(last,0,sizeof(last)); cnt=1; for(int i=1;i<=n;i++) insert(0,i,x); for(int i=1;i<=m;i++) { insert(u[i],i+n,inf); insert(v[i],i+n,inf); insert(i+n,T,1); } } double dinic() { double ans=0; while(bfs()) ans+=dfs(0,inf); return ans; } void dfs(int x) { vis[x]=1; for(int i=last[x];i;i=e[i].next) if(e[i].v>eps&&!vis[e[i].to])dfs(e[i].to); } int main() { n=read();m=read();T=n+m+1; if(m==0) { puts("1");puts("1"); return 0; } for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(); double l=0,r=m,tmp; for(int i=1;i<=100;i++) { double mid=(l+r)/2; build(mid); bool t=(m-dinic()<=eps); if(t)r=mid; else l=mid,tmp=mid; } build(tmp); dinic(); dfs(0); for(int i=1;i<=n;i++) if(!vis[i])ans.push_back(i); sort(ans.begin(),ans.end()); printf("%lu\n",ans.size()); for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]); return 0; } |
4028.GCD Guessing Game
贪心策略
若想知道对方手中的数字。需要确定是否存在<=n的每一个质数
如n=10，要分别确定2,3,5,7
首先的想法是把小的质数放在一起问
但是发现大质数每个依然要问一次
把大质数和小质数一起问
|
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 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,cnt; int p[2005]; bool mark[10005]; void pre() { for(int i=2;i<=10000;i++) { if(!mark[i])p[++cnt]=i; for(int j=1;p[j]*i<=10000&&j<=cnt;j++) { mark[p[j]*i]=1; if(i%p[j]==0)break; } } } int main() { pre(); memset(mark,0,sizeof(mark)); scanf("%d",&n); int now=1,ans=0; for(int i=cnt;i>=now;i--) if(!mark[i]&&p[i]<=n) { int sum=p[i]; mark[i]=1;ans++; while(sum*p[now]<=n) { sum*=p[now]; mark[now]=1; now++; } } printf("%d\n",ans); return 0; } |
Subscribe