从不能忘记当年NOIP时候的我，急速的做完第一题快排，迷失在第二题的字符串和第三题的DP。每个人心里都有那么一个梦，梦之所以美好，是因为挣脱了现实的束缚，所以从某种意义上来说，去实现心中的梦往往是把它硬生生的拽回现实，然后遍体鳞伤。
然而这并不能抵挡人们实现梦想的冲击，至少我对此免疫。从接触NOIP开始，到现在的ICPC，差不多七年了，七年里体验过懵懂，经历过绝望，品味过惊喜，游趟过迷惘。闭上眼，这些依稀浮现在眼前，只是从前的我从来没有好好去感受。能为一个梦坚持了七年，不是说我有多牛逼，多坚韧不拔，只是单纯的不死心。
明天去马尼拉，参加今年最后一场regional，或许也是我人生中最后一场regional。我相信我能把那个梦系上气球，然后放回宇宙，不再受现实的煎熬。从前，从未拿过第一，无论是数学物理化学信息学ACMIBMIntelCup，似乎千年老二的阴影总是挥之不去。希望马尼拉的太阳，能把一切阴霾散去，也不枉其那么靠近赤道。
晚安，香港。
早安，我的梦。
RT!
/* Nearly forget how to write bellman_ford... * System of difference constraints * for i-j <= t, add a edge(j,i)=t * add a src node and add edges (src, i)=0 for all node i * run bellman ford * a good pratice on dfs !! */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int dx[4]={-1,0,0,1}; const int dy[4]={0,-1,1,0}; int C[5][5]; char S[5][5][6][5]; int B[4][4]; int n,N; int G[10][10]; int U[100],V[100],W[100],E,D[10]; bool Bellman_Ford(int src) { for(int i=0;i<=N;i++) D[i]=1<<29; D[src]=0; for(int i=0;i<N;i++) for(int j=0;j<E;j++) if(D[U[j]]+W[j]<D[V[j]]) D[V[j]]=D[U[j]]+W[j]; for(int j=0;j<E;j++) if(D[U[j]]+W[j]<D[V[j]]) return false; int low=1<<29, high=-(1<<29); for(int i=0;i<N;i++) { low=min(low,D[i]); high=max(high,D[i]); } if(high-low>9) return false; else for(int i=0;i<N;i++) D[i]-=low; return true; } bool dfs(int now) { int nx=now/n,ny=now%n; if(now==N) { E=0; for(int i=0;i<N;i++) { for(int j=i+1;j<N;j++) if(G[i][j]==1) U[E]=j, V[E]=i, W[E]=-1, E++; //G[i][j]==1 i<j ==> i-j<=-1 else if(G[i][j]==0) U[E]=i, V[E]=j, W[E]=-1, E++; //G[i][j]==0 j<i ==> j-i<=-1 U[E]=N, V[E]=i, W[E]=0, E++; } for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<4;k++) { int tx=i+dx[k], ty=j+dy[k], tn=tx*n+ty, sn=i*n+j; if(tx>=0 && tx<n && ty>=0 && ty<n && G[sn][tn]==-1) { U[E]=sn, V[E]=tn, W[E]=0, E++; } } if(Bellman_Ford(N)) return true; return false; } else { int a[4],b[4],an=0,t,tx,ty,tn; for(int k=0;k<4;k++) { tx=nx+dx[k]; ty=ny+dy[k]; tn=tx*n+ty; if(tx>=0 && tx<n && ty>=0 && ty<n && G[now][tn]==-1) a[an++]=tn; } if(an<B[nx][ny]) return false; if(B[nx][ny]==0) return dfs(now+1); for(int k=0;k<C[an][B[nx][ny]];k++) { for(int i=0;i<B[nx][ny];i++) { t=S[an][B[nx][ny]][k][i]-48; G[a[t]][now]=0; G[now][a[t]]=1; } if(dfs(now+1)) return true; for(int i=0;i<B[nx][ny];i++) { t=S[an][B[nx][ny]][k][i]-48; G[a[t]][now]=G[now][a[t]]=-1; } } return false; } } void init() { C[1][1]=1; strcpy(S[1][1][0],"0"); C[2][1]=2; strcpy(S[2][1][0],"0"); strcpy(S[2][1][1],"1"); C[2][2]=1; strcpy(S[2][2][0],"01"); C[3][1]=3; strcpy(S[3][1][0],"0"); strcpy(S[3][1][1],"1"); strcpy(S[3][1][2],"2"); C[3][2]=3; strcpy(S[3][2][0],"01"); strcpy(S[3][2][1],"12"); strcpy(S[3][2][2],"02"); C[3][3]=1; strcpy(S[3][3][0],"012"); C[4][1]=4; strcpy(S[4][1][0],"0"); strcpy(S[4][1][1],"1"); strcpy(S[4][1][2],"2"); strcpy(S[4][1][3],"3"); C[4][2]=6; strcpy(S[4][2][0],"01"); strcpy(S[4][2][1],"02"); strcpy(S[4][2][2],"03"); strcpy(S[4][2][3],"12"); strcpy(S[4][2][4],"13"); strcpy(S[4][2][5],"23"); C[4][3]=4; strcpy(S[4][3][0],"012"); strcpy(S[4][3][1],"013"); strcpy(S[4][3][2],"023"); strcpy(S[4][3][3],"013"); C[4][4]=1; strcpy(S[4][4][0],"0123"); } int main() { init(); scanf("%d",&n); N=n*n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&B[i][j]); memset(G,-1,sizeof(G)); if(dfs(0)) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) printf("%d ",D[i*n+j]); printf("\n"); } } else { printf("NO SOLUTION\n"); } return 0; } |
/* Shortest Path Vairant * Don't be scared!!! * Greedy strategy is still applied. * Just do it! */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int g[305][305],it[305],bt[305],pt[305],d[305],p[305]; int src,dst,n,m; bool used[305]; char ic[305]; void Current(int nowT, int at, char &fromC, int &remC) { if(nowT<it[at]) { fromC=ic[at]; remC=it[at]-nowT; } else { nowT-=it[at]; nowT%=(bt[at]+pt[at]); if(ic[at]=='P') { //Careful! if(nowT<bt[at]) { fromC='B'; remC=bt[at]-nowT; } else { fromC='P'; remC=pt[at]-(nowT-bt[at]); } } else { if(nowT<pt[at]) { fromC='P'; remC=pt[at]-nowT; } else { fromC='B'; remC=bt[at]-(nowT-pt[at]); } } } } int calWait(int nowT, int from, int to) { char fromC,toC; int fromR,toR,nextFT,nextTT,nnextFT,nnextTT; //printf("!!%d %d %d = %d\n",nowT,from,to); Current(nowT,from,fromC,fromR); //printf("--CurrentF %d %d %c %d\n",nowT,from,fromC,fromR); Current(nowT,to,toC,toR); //printf("--CurrentT %d %d %c %d\n",nowT,to,toC,toR); //printf("--%d %d %d %d\n",fromC, toC, fromR, toR); if(fromC==toC) return 0; else { if(fromR<toR) return fromR; else if(fromR>toR) return toR; else { if(fromC=='B') nextFT=pt[from]; else nextFT=bt[from]; if(fromC=='B') nnextFT=bt[from]; else nnextFT=pt[from]; if(toC=='B') nextTT=pt[to]; else nextTT=bt[to]; if(toC=='B') nnextTT=bt[to]; else nnextTT=pt[to]; if(nextTT+nnextTT==nextFT+nnextFT) return -1; if(nextTT==nextFT) return fromR+nextFT+min(nnextFT,nnextTT); else return fromR+min(nextFT,nextTT); } } } void print(int x) { if(p[x]!=x) print(p[x]); printf("%d ",x); } int main() { char str[100]; int u,v,w; scanf("%d %d",&src,&dst); scanf("%d %d",&n,&m); gets(str); for(int i=1;i<=n;i++) { scanf("%s %d %d %d",str,&it[i],&bt[i],&pt[i]); ic[i]=str[0]; } for(int i=1;i<=m;i++) { scanf("%d %d %d",&u,&v,&w); g[u][v]=g[v][u]=w; } memset(used,0,sizeof(used)); for(int i=1;i<=n;i++) d[i]=1<<29; d[src]=0; p[src]=src; for(int cc=1;cc<n;cc++) { int md=1<<29,mp=0; for(int i=1;i<=n;i++) if(!used[i]&&d[i]<md) { md=d[i]; mp=i; } if(!mp) break; else used[mp]=true; for(int i=1;i<=n;i++) if(!used[i]&&g[mp][i]) { int wait=calWait(d[mp],mp,i); //printf("wait=%d\n",wait); if(wait<0) continue; if(d[i]>wait+d[mp]+g[mp][i]) { d[i]=wait+d[mp]+g[mp][i]; p[i]=mp; } } } //for(int i=1;i<=n;i++) printf("%d ",d[i]); printf("\n"); if(d[dst]<(1<<29)) printf("%d\n",d[dst]); print(dst); return 0; } |
/* Hamiltonian Path Finding. * If each vertex of a simple graph has degree >= n/2 * There must be Hamiltonian Path/Cycle * Algorithm go like this: * Step 1: Init a path, add start point in * Step 2: Find any unused vertex which is reachable * BOTH from the head of the path and the tail of the path !!Attention: BOTH!! * and insert it front head or after tail * Step 3: Continue Step2 until cannot find any more * Step 4: The formed path can become a cycle, i.e. path = a[1]a[2]...a[m], there must exist ai, s.t. edge(a[1],a[i+1]) && edge(a[i],a[m]) The path can be changed to a[1]...a[i]a[m]...a[i+1]a[1] * Step 5: If the cycle contains all the vertices, we've done. Otherwise, for any unused point P, there must be some edge(a[k],P) Reform the cycle to be a path like Pa[k]...a[end]a[begin]..a[k-1] * Step 6: Go to Step 2 * * Linked List are used for faster reverse and insert * To Reverse a linked list, simply swap each node's (Previous, Next) * Good Practice! */ bool m[1005][1005]={0}; //Graph Map m int vis[1005],n; int L[1005],R[1005],X[1005],root,count; void FindHamiltonCycle() //check connectivity first { memset(vis,0,sizeof(vis)); root=count=0; X[++count]=1; L[count]=root; R[root]=count; L[root]=count; R[count]=root; vis[1]=true; bool updated; int head,headPos,newHead; int tail,tailPos,newTail; int start,addin,temp; while(1) { do { head=X[R[root]]; headPos=R[root]; updated=false; tail=X[L[root]]; tailPos=L[root]; updated=false; for(int i=1;i<=n;i++) if(!vis[i]&&m[head][i]&&m[tail][i]) { newHead=i; vis[newHead]=updated=true; X[++count]=newHead; R[count]=headPos; L[headPos]=count; L[count]=root; R[root]=count; break; } } while(updated); head=X[R[root]]; tail=X[L[root]]; headPos=R[root]; tailPos=L[root]; for(int ptr=R[root];ptr!=root;ptr=R[ptr]) { if(m[head][X[R[ptr]]] && m[tail][X[ptr]]) { start=R[ptr]; while(1) { temp=L[start]; L[start]=R[start]; R[start]=temp; if(L[start]==root) { L[start]=ptr; R[R[ptr]]=root; L[root]=R[ptr]; R[ptr]=start; break; } else start=L[start]; } break; } } if(count==n) break; else { for(int i=1;i<=n;i++) if(!vis[i]) { addin=i; break; }; for(int ptr=R[root];ptr!=root;ptr=R[ptr]) { if(m[X[ptr]][addin]) { X[++count]=addin; vis[addin]=true; tailPos=L[root]; headPos=R[root]; R[root]=count; if(L[ptr]!=root) { L[root]=L[ptr]; R[L[ptr]]=root; R[tailPos]=headPos; L[headPos]=tailPos; } L[count]=root; R[count]=ptr; L[ptr]=count; break; } } } } printAns(1); } |
/* Gemo rotation and translation * Originally use equations to solve for center, but failed due to the precision * Rotation is easier */ #include <cstdio> #include <algorithm> #include <cmath> using namespace std; #define EPS 1e-6 #define feq(x,y) (fabs((x)-(y))<EPS) #define fgt(x,y) ((x)>((y)+EPS)) #define fge(x,y) (((x)+EPS)>(y)) const double pi = acos(-1.0); typedef struct Pt{ double x,y; Pt(){} Pt(double x,double y):x(x),y(y){} Pt operator+(const Pt&p){ return Pt(x+p.x,y+p.y); } Pt operator-(const Pt&p){ return Pt(x-p.x,y-p.y); } Pt operator*(double k){ return Pt(x*k,y*k); } double operator*(const Pt&p){ return x*p.x+y*p.y; } double operator^(const Pt&p){ return x*p.y-y*p.x; } double len2(){ return x*x+y*y; } double len(){ return sqrt(len2()); } bool operator==(const Pt&p){ return feq(x,p.x)&&feq(y,p.y); } void eat(){ scanf("%lf%lf",&x,&y); } void out(){ printf("%.6lf %.6lf\n",feq(x,0)?0:x,feq(y,0)?0:y); } } Pt; int N,N1,N2; Pt p[200],Center,pN1,pN2,P; double totalAngle, eachAngle, R; Pt rotate(Pt P, double angle) { double c=cos(angle); double s=sin(angle); return Pt(P.x*c+P.y*s, P.y*c-P.x*s); } int main() { double halfAngle,a,b,A,B,C,D,x1,x2,y1,y2,t; int tmp; //Get Input scanf("%d %d %d",&N, &N1, &N2); if(N1 > N2) { tmp=N1; N1=N2; N2=tmp; pN2.eat(); pN1.eat(); } else { pN1.eat(); pN2.eat(); } //Get Radius totalAngle = 2*pi; eachAngle = totalAngle/N; halfAngle = (N2-N1)*eachAngle/2; R = (pN1-pN2).len()/2/sin(halfAngle); //Rotate for center halfAngle = pi/2-halfAngle; P=rotate(pN2-pN1, halfAngle); Center = pN1 + P*(R/P.len()); //printf("Get Radius = %lf\n",R); //printf("Get Center = "); Center.out(); p[0]=pN1; P=pN1-Center; for(int i=1;i<N;i++) { //printf("before rotate P="); P.out(); P=rotate(P,eachAngle); //printf("after rotate P="); P.out(); p[i]=Center+P; } for(int i=1;i<=N;i++) p[(i-N1+N)%N].out(); return 0; } |
/* Note that f(A1*A2) = f(f(A1)*f(A2)) * and f(A1+A2) = f(f(A1)+f(A2)) * So use recursion */ #include<cstdio> int n,x[1005]; int d(int x) { int s=0; while(x>0) s+=x%10, x/=10; if(s<10) return s; else return d(s); } int f(int i) { if(i==n-1) return d(x[i]); else return d(d(x[i])*d(1+f(i+1))); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",x+i); printf("%d\n",f(0)); } return 0; } |
// compute (x^m)%k int pow(int x,int m, int k) { if(m==0) return 1; else if(m&1) return pow(x,m-1,k)*x%k; else { int t=pow(x,m/2,k); return t*t%k; } } |
/* Prime Generate and DP * Good Pratice, remember to see the output format! */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; bool is[10005]={0}; int superPrime[205],pn=0,spn=0; int n,k; bool dp[10005]={0}; int num[10005],pre[10005],ans[10005],an=0; void getAns(int now, int before) { if(now==0) return; ans[an++]=now-before; getAns(before,pre[before]); } int main() { /* Prime Gen */ is[0]=is[1]=true; for(int i=2;i<=10000;i++) if(!is[i]) { ++pn; if(!is[pn]) superPrime[spn++]=i; for(int j=i+i;j<=10000;j+=i) is[j]=true; } /* DP Start */ scanf("%d",&n); dp[0]=true; num[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<spn;j++) { k=i-superPrime[j]; if(k>=0 && dp[k]) { if(dp[i]==false) { dp[i]=true; num[i]=num[k]+1; pre[i]=k; } else if(num[i] > num[k]+1) { num[i]=num[k]+1; pre[i]=k; } } else if(k<0) break; } /* Output*/ if(dp[n]) { printf("%d\n",num[n]); an=0; getAns(n,pre[n]); sort(ans,ans+an); for(int i=an-1;i>=0;i--) if(i) printf("%d ",ans[i]); else printf("%d\n",ans[i]); } else puts("0"); return 0; } |
/* Compute the day name in a week by dd/mm/yyyy * Zeller Formular * c : century, first 2 bits of year * y : year , last 2 bits of year * m : month , if(m<3) m=m+12, y=y-1 * d : days * return : 1-6 for Mon, Tue, Wed ..., 0 for Sun. */ #include<cstdio> int allow[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; //only for 2001. typo WA here...WTF int getWeek(int c, int y, int m, int d) { return (y + y/4 + c/4 - 2*c + (26*(m+1))/10 + d - 1)%7; } int main() { int n,m,t; scanf("%d %d",&n,&m); if(m>12 || n<1 || m<1 || n>allow[m]) printf("Impossible\n"); else { if(m<3) t=getWeek(20,00,m+12,n); else t=getWeek(20,01,m,n); if(t>0) printf("%d\n",t); else if(t<0) printf("%d\n",t+7); else printf("7\n"); } return 0; } |