POJ训练记录3
1379.Run Away
模拟退火裸题
|
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 |
#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 using namespace std; int T,n; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int X,Y;double ans,ansx,ansy; struct P{ double x,y; }p[1005]; double dis(P a,P b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double getval(P a) { double mn=1e60; for(int i=1;i<=n;i++) mn=min(mn,dis(a,p[i])); return mn; } double val[5]; void solve(double sx,double sy) { double now=getval((P){sx,sy}); double d=100; for(int i=1;i<=70;i++) { int id=-1; for(int k=0;k<4;k++) { double tx=sx+d*xx[k],ty=sy+d*yy[k],tmp; tmp=getval((P){tx,ty}); if(tx>X||ty>Y||tx<0||ty<0)continue; if(tmp>now)now=tmp,id=k; } if(id!=-1)sx+=d*xx[id],sy+=d*yy[id]; d*=0.8; } if(now>ans)ans=now,ansx=sx,ansy=sy; } int main() { scanf("%d",&T); srand(500); while(T--) { scanf("%d%d%d",&X,&Y,&n); ans=0; for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); for(int i=1;i<=30;i++) solve(rand()%X,rand()%Y); printf("The safest point is (%.1lf, %.1lf).\n",ansx,ansy); } return 0; } |
2758.Checking the Text
暴力+哈希
|
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 |
#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 B 233 using namespace std; vector<char>c; int n,m; ll pos[50005],H[100005],bin[100005]; char ch[50005]; ll get(int l,int r) { return H[r]-H[l-1]*bin[r-l+1]; } void pre() { for(int i=1;i<c.size();i++) H[i]=H[i-1]*233+c[i]; } int cal(int a,int b) { int l=0,r=min(c.size()-a,c.size()-b),ans=0; while(l<=r) { int mid=(l+r)>>1; if(get(a,a+mid-1)==get(b,b+mid-1)) ans=mid,l=mid+1; else r=mid-1; } return ans; } int main() { bin[0]=1;for(int i=1;i<=100000;i++)bin[i]=bin[i-1]*B; scanf("%s",ch+1); n=strlen(ch+1); c.push_back('I'); for(int i=1;i<=n;i++)c.push_back(ch[i]); for(int i=1;i<=n;i++)pos[i]=i; pre(); scanf("%d",&m); int x,y; while(m--) { scanf("%s",ch+1); if(ch[1]=='Q') { scanf("%d%d",&x,&y); printf("%d\n",cal(pos[x],pos[y])); } else { scanf("%s%d",ch+1,&x); if(x>c.size())x=c.size(); c.insert(c.begin()+x,ch[1]); pre(); for(int j=1;j<=n;j++) if(pos[j]>=x)pos[j]++; } } return 0; } |
poj3156.Interconnect
由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化
|
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 |
#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 mod 5614657 using namespace std; vector<char>c; int n,m,tot,fa[35],size[35]; struct data{ int l,v[35]; data(){ l=0; memset(v,0,sizeof(v)); } }; double mp[6000005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int get(data a) { int ans=1; for(int i=1;i<=a.l;i++) ans=(ans*17+a.v[i])%mod; return ans; } double dp(data a) { int H=get(a); if(mp[H])return mp[H]; if(a.l==1)return 0; double p=0,q=0; for(int i=1;i<=a.l;i++) p+=a.v[i]*(a.v[i]-1)/2; p=1-p/tot; for(int i=1;i<=a.l;i++) for(int j=i+1;j<=a.l;j++) { data b; for(int k=1;k<=a.l;k++) if(k!=j&&k!=i)b.v[++b.l]=a.v[k]; b.v[++b.l]=a.v[i]+a.v[j]; sort(b.v+1,b.v+b.l+1); q+=((double)a.v[i]*a.v[j]/tot*dp(b)/p); } return mp[H]=q+1/p; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)size[i]=1,fa[i]=i; tot=n*(n-1)/2; for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); int p=find(u),q=find(v); if(p!=q)size[p]+=size[q],fa[q]=p; } data a; for(int i=1;i<=n;i++) if(i==fa[i])a.v[++a.l]=size[i]; sort(a.v+1,a.v+a.l+1); printf("%.6f",dp(a)); return 0; } |
1837.Balance
f(i,j)前i个力矩为j的方案,dp
|
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 |
#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 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,a[25],c[25]; ll f[25][10005]; int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)c[i]=read(); f[0][5000]=1; for(int i=0;i<m;i++) for(int j=0;j<10000;j++) if(f[i][j]) for(int k=1;k<=n;k++) f[i+1][j+c[i+1]*a[k]]+=f[i][j]; printf("%lld\n",f[m][5000]); return 0; } |
3609.Reset Sequence
状压+bfs
初始集合是0-n-1
每个指令会使得集合中的一些元素消失，目标状态是只有一个0
|
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 |
#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 using namespace std; int n,m; int a[25][25]; int dis[70005],q[70005],pre[70005],ed[70005]; int tran(int x,int y) { int ans=0; for(int i=1;i<=n;i++) if((1<<(i-1))&x) ans|=(1<<a[i][y]); return ans; } void bfs() { memset(dis,-1,sizeof(dis)); dis[(1<<n)-1]=0; int head=0,tail=1; q[0]=(1<<n)-1; while(head!=tail) { int now=q[head];head++; for(int i=1;i<=m;i++) { int t=tran(now,i); if(dis[t]==-1) { dis[t]=dis[now]+1; pre[t]=now;ed[t]=i; q[tail++]=t; } } } } int main() { scanf("%d%d",&n,&m); char ch[2]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%s",ch+1); if(ch[1]>='a'&&ch[1]<='z')a[i][j]=ch[1]-'a'+10; else a[i][j]=ch[1]-'0'; } bfs(); if(dis[1]==-1)puts("impossible"); else { vector<int>ans; for(int i=1,t=1;i<=dis[1];i++) ans.push_back(ed[t]),t=pre[t]; for(int i=ans.size()-1;i>=0;i--) { ans[i]--; if(ans[i]>=10) printf("%c",ans[i]-10+'a'); else printf("%d",ans[i]); } } return 0; } |
1981.Circle and Points
以每个点为圆心画单位圆
枚举每个圆，求其它圆与它交的弧，被覆盖最多的弧即为答案
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define eps 1e-8 #define pa pair<int,int> #define ll long long using namespace std; int n,ans; struct P{ double x,y; }p[305]; double dis(P a,P b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } vector<pair<double,double> >q,point; void add(P a,P b) { double d=dis(a,b),t1,t2; if(d>2)return; t1=atan2(b.y-a.y,b.x-a.x); t2=acos(d/2); q.push_back(make_pair(t1-t2,t1+t2)); } void solve(int x) { q.clear();point.clear(); for(int i=1;i<=n;i++)if(i!=x)add(p[x],p[i]); int t=q.size(); for(int i=0;i<t;i++) { if(q[i].first<0)q[i].first+=2*pi; if(q[i].second<0)q[i].second+=2*pi; if(q[i].first>q[i].second) { q.push_back(make_pair(0,q[i].second)); q[i].second=2*pi; } } double now=0; t=1; for(int i=0;i<q.size();i++) { point.push_back(make_pair(q[i].first,1)); point.push_back(make_pair(q[i].second,-1)); } sort(point.begin(),point.end()); for(int i=0;i<point.size();i++) { t+=point[i].second; ans=max(t,ans); } } int main() { while(scanf("%d",&n)) { if(n==0)break; for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); ans=1; for(int i=1;i<=n;i++) solve(i); printf("%d\n",ans); } return 0; } |
Subscribe
计数器 9320920
OI 课件=>
OI 课件=>