POJ训练记录5
3074.Sudoku
数独。。dancing link经典题
|
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 |
#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 #define pa pair<ll,int> #define rp(x,y) x*9+y+81 #define cp(x,y) x*9+y+162 #define pp(x,y) x*9+y+243 using namespace std; char ch[105]; int id,tot,ans[105]; int L[300005],R[300005],u[300005],d[300005]; int h[1005],C[300005],X[300005],s[1005]; bool mark[1005],mp[1005][1005]; struct data{ int pos,val; }a[300005],q[105]; void del(int c) { L[R[c]]=L[c];R[L[c]]=R[c]; for(int i=d[c];i!=c;i=d[i]) { for(int j=R[i];j!=i;j=R[j]) u[d[j]]=u[j],d[u[j]]=d[j],s[C[j]]--; } } void add(int c) { L[R[c]]=R[L[c]]=c; for(int i=u[c];i!=c;i=u[i]) for(int j=L[i];j!=i;j=L[j]) u[d[j]]=d[u[j]]=j,s[C[j]]++; } void link(int r,int c) { s[c]++;C[++tot]=c;X[tot]=r; u[tot]=c;d[tot]=d[c]; u[d[tot]]=tot;d[u[tot]]=tot; if(h[r]==-1) h[r]=L[tot]=R[tot]=tot; else { L[tot]=h[r];R[tot]=R[h[r]]; L[R[tot]]=tot;R[L[tot]]=tot; } } bool dance(int k) { if(R[0]==0) { for(int i=1;i<=81;i++) ans[q[i].pos]=q[i].val; for(int i=1;i<=81;i++)printf("%d",ans[i]); return 1; } int mn=inf,c=R[0][;; for(int i=R[0];i;i=R[i]) if(s[i]<mn)mn=s[i],c=i; del(c); for(int i=d[c];i!=c;i=d[i]) { q[k+1]=a[X[i]]; for(int j=R[i];j!=i;j=R[j])del(C[j]); if(dance(k+1))return 1; for(int j=L[i];j!=i;j=L[j])add(C[j]); } add(c); return 0; } int main() { while(scanf("%s",ch+1)) { if(ch[1]=='e')return 0; id=tot=0; memset(h,-1,sizeof(h)); memset(mark,0,sizeof(mark)); for(int i=0;i<=4*81;i++) { L[i+1]=i,R[i]=i+1; u[i]=d[i]=i;s[i]=0; } L[0]=4*81;R[4*81]=0;tot=4*81; for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(ch[i*9+j+1]!='.') { int t=ch[i*9+j+1]-'0',p=i/3*3+j/3; mark[rp(i,t)]=mark[cp(j,t)]=mark[pp(p,t)]=1; } for(int i=0;i<9;i++) for(int j=0;j<9;j++) { int t=ch[i*9+j+1]-'0',p=i/3*3+j/3; if(ch[i*9+j+1]=='.')t=0; if(t!=0) { id++;a[id].pos=i*9+j+1;a[id].val=t; link(id,i*9+j+1); link(id,rp(i,t)); link(id,cp(j,t)); link(id,pp(p,t)); } else for(int t=1;t<=9;t++) if(!mark[rp(i,t)]&&!mark[cp(j,t)]&&!mark[pp(p,t)]) { id++;a[id].pos=i*9+j+1;a[id].val=t; link(id,i*9+j+1); link(id,rp(i,t)); link(id,cp(j,t)); link(id,pp(p,t)); } } dance(0); puts(""); } return 0; } |
3252.Round Numbers
简单数位dp
f(i,j,x,y)表示最高的i位，0比1多j个，是否已小于n，高位是否有1
然后转移显然。。。
|
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<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 bin[40]; int a,b; int f[40][65][2][2]; int solve(ll x) { memset(f,0,sizeof(f)); f[0][30][0][0]=1; int t=1;while(bin[t]<=x)t++; for(int i=0;i<t;i++) { int p=(bin[t-i-1]&x)>0; for(int j=0;j<=60;j++) for(int x=0;x<=1;x++) for(int y=0;y<=1;y++) if(f[i][j][x][y]) for(int k=0;k<=1;k++) if(k<=p||x==1) f[i+1][j+(k==0?1*y:-1)][x|(k<p)][y|(k==1)]+=f[i][j][x][y]; } int ans=0; for(int i=30;i<=60;i++) ans+=f[t][i][1][1]; return ans; } int main() { bin[0]=1;for(int i=1;i<=35;i++)bin[i]=bin[i-1]<<1; a=read();b=read(); printf("%d\n",solve(b+1)-solve(a)); return 0; } |
1665.Biker’s Trip Odometer
阅读题
|
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 |
#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 #define eps 1e-7 #define pi 3.1415927 using namespace std; double d,r,T; int cas; int main() { while(1) { cas++; scanf("%lf%lf%lf",&d,&r,&T); if(r==0)return 0; printf("Trip #%d: ",cas); d=d/12/5280; printf("%.2lf %.2lf\n",d*pi*r,d*pi*r/(T/3600)); if(r==0)return 0; } return 0; } |
1930.Dead Fraction
丧心病狂。。枚举循环节
|
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 |
#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 #define eps 1e-7 #define pi 3.1415927 using namespace std; char ch[10005]; ll ans1,ans2; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } void solve(ll a,ll b,ll c,ll d) { ll t1=a*d+b*c,t2=b*d,t=gcd(t1,t2); t1/=t;t2/=t; if(t2<ans2)ans2=t2,ans1=t1; } int main() { while(1) { ans2=(ll)1e60; scanf("%s",ch+1); int n=strlen(ch+1); if(n==1)break; ll b=1,a=0; for(int i=3;i<=n-3;i++) a=a*10+ch[i]-'0',b*=10; ll t=b/10*9; for(ll i=10;i<=b;i*=10,t=t+(b/i)*9) solve(a/i,b/i,a%i,t); printf("%lld/%lld\n",ans1,ans2); } return 0; } |
1970.The Game
|
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 |
#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 #define eps 1e-7 #define pi 3.1415927 using namespace std; int T; int a[25][25]; int xx[]={1,1,0,-1},yy[]={0,1,1,1}; bool check(int x,int y,int k) { int t=a[x][y]; for(int i=-1;i<=5;i++) { int nx=x+xx[k]*i,ny=y+yy[k]*i; if(i!=5&&i!=-1) { if(nx<1||ny<1||nx>19||ny>19||a[nx][ny]!=t)return 0; } else { if(nx<1||ny<1||nx>19||ny>19)continue; if(a[nx][ny]==t)return 0; } } return 1; } void solve() { for(int j=1;j<=19;j++) for(int i=1;i<=19;i++) if(a[i][j]!=0) for(int k=0;k<4;k++) if(check(i,j,k)) { printf("%d\n",a[i][j]); printf("%d %d\n",i,j); return; } puts("0"); } int main() { scanf("%d",&T); while(T--) { for(int i=1;i<=19;i++) for(int j=1;j<=19;j++) scanf("%d",&a[i][j]); solve(); } return 0; } |
1185.炮兵阵地
每一行的合法放置状态只有60种
f(i,j,k)表示到第i行，前两行的状态为j，k，简单状压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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#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; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,top,mx; int bin[20],q[2000]; int s[105],f[105][65][65]; char a[105][15]; int cal(int x) { int ans=0; for(int i=0;i<m;i++) if(bin[i]&x)ans++; return ans; } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read();m=read(); for(int i=0;i<bin[m];i++) if((i&(i>>1))==0&&(i&(i>>2))==0)q[++top]=i; for(int i=1;i<=n;i++) { scanf("%s",a[i]+1); for(int j=1;j<=m;j++) if(a[i][j]=='H')s[i]+=bin[j-1]; } for(int i=1;i<=top;i++) if((q[i]&s[1])==0)f[1][i][1]=cal(q[i]); for(int i=1;i<n;i++) for(int j=1;j<=top;j++) for(int k=1;k<=top;k++) if(f[i][j][k]!=-1) for(int x=1;x<=top;x++) if((q[x]&s[i+1])==0) if((q[j]&q[x])==0&&(q[k]&q[x])==0) f[i+1][x][j]=max(f[i+1][x][j],f[i][j][k]+cal(q[x])); for(int j=1;j<=top;j++) for(int k=1;k<=top;k++) mx=max(mx,f[n][j][k]); printf("%d\n",mx); return 0; } |
Subscribe