整个寒假+3月份 都在开发OJ，好久没写题解了。
解法一：
预处理前缀和 sum[N] , 对于通用序列 （ a(i+1), a(i+2), ... a(n), a(1) ... a(i) ），将其分为 ( a(i+1) ... a(n) ), ( a(1)...a(i) )\
两段， 此循环是以 a(i+1) 为起始的序列， 若其所有前缀和要满足条件，则
Min{ sum(1)...sum(i) } + sum(n)-sum(i+1) >= 0
MIN{ sum(i+1)...sum(n) } - sum(i) >= 0
解法二： (解题报告所给)
将序列扩成2倍，解决循环问题， 然后预处理前缀和后，从n往1扫，在每个位置维护之后的n个值，
这里需要使用队列优化，但是不能用系统STL的priority_queue 会出TLE。
这里给出解法一的代码：
View Code
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #define MIN(a,b) (a)<(b)?(a):(b) const int N = 2000010; int a[N], b[N], left[N], right[N]; int n; int main(){ while( scanf("%d", &n), n ) { a[0]=b[0]=left[0]=right[0]; for(int i = 1; i <= n; i++) scanf("%d", &a[i] ); for(int i = 1; i <= n; i++) b[i] = b[i-1]+a[i]; left[1] = b[1]; right[n] = b[n]; for(int i = 2; i <= n; i++) left[i] = MIN( left[i-1], b[i] ); for(int i = n-1; i >= 1; i-- ) right[i] = MIN( right[i+1], b[i] ); int res = 0; for(int i = n; i >= 1; i-- ){ int tmp = MIN( right[i]-b[i-1] , left[i-1]+(b[n]-b[i-1]) ); if( tmp >= 0 ) res++; } printf("%d\n", res ); } return 0; }
第二题 拯救猫咪
没写，解题报告上说是模拟题，一秒一秒模拟能够过。
第三题 兔纸的难题
比赛时，以为是规律题，各种推，后果很惨淡~~
状态 dp( i, j ) 表示外面还有 i只兔子，栈中还有 j只兔子时的方案数。
从外面跳入一只兔子到栈中，只会导致两种情况： 一是消去3个，二是增加1个
所以转移方程为：
dp( i, j ) = dp( i+1, j-1 ) + dp( i+1, j+2 )
另外，当栈中剩2只兔子时，颜色是可以不限定的，其他情况是限定的
所以有
dp( i, j ) = dp( i+1, j-1 ) + 2*dp( i+1, j+2 )
代码实现时，初始化 只有dp( n, 0 ) = 1 ,其他都为0 ，注意，对于任意i 要枚举 J
解题代码
View Code
#include<stdio.h> #include<string.h> #include<stdlib.h> const int N = 1010; const int mod = 1e9+7; int dp[N][N]; int n; int main() { while( scanf("%d", &n) != EOF) { if( n == -1 ) break; if( n%3 != 0 ){ printf("0\n"); continue; } memset( dp, 0, sizeof( dp ) ); dp[n][0] = 1; for(int i = n-1; i >= 0; i-- ) { for(int j = 0; j <= n; j++ ) { if( j-1 >= 0 ) dp[i][j-1] = (dp[i][j-1]+dp[i+1][j])%mod; if( j+2 <= n ){ dp[i][j+2] = (dp[i][j+2]+dp[i+1][j])%mod; if( j == 0 ) dp[i][j+2] = (dp[i][j+2]+dp[i+1][j])%mod; } } } printf("%d\n", dp[0][0] ); } return 0; }
第四题 二哥的内存
行列相互独立，使用数组记录当前行原本是哪行即可。列一样。
View Code
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<map> using namespace std; const int N = 1e5+10; map<int, int> mp[N]; int row[N], col[N]; int n, m; int main() { while( scanf("%d", &n) != EOF ) { if( n == -1 ) break; for(int i = 0; i < N; i++) { row[i] = col[i] = i; mp[i].clear(); } for(int i = 0; i < n; i++) { int a, b, c; scanf("%d%d%d", &a,&b,&c); mp[a][b] = c; } scanf("%d", &m); int tmp; for(int i = 0; i < m; i++) { int op, x, y; scanf("%d%d%d",&op,&x,&y); switch( op ){ case 0: tmp = row[x]; row[x] = row[y]; row[y] = tmp; break; case 1: tmp = col[x]; col[x] = col[y]; col[y] = tmp; break; default: x = row[x]; y = col[y]; if( mp[x].count(y) == 0 ){ printf("0\n"); } else printf("%d\n", mp[x][y] ); } } } return 0; }
第五题 Wally World
简单几何， 判断线段相交
View Code
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<math.h> using namespace std; typedef double PointType; #define MIN(a,b) (a)<(b)?(a):(b) struct point { PointType x,y; void input(){ scanf("%lf%lf", &x,&y); } }; PointType Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线 { return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y); } bool On_Segment(point pi,point pj,point pk) { if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y)) return 1; return 0; } bool Segment_Intersect(point p1,point p2,point p3,point p4) { PointType d1=Direction(p3,p4,p1),d2=Direction(p3,p4,p2),d3=Direction(p1,p2,p3),d4=Direction(p1,p2,p4); if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0))) return 1; if(d1==0&&On_Segment(p3,p4,p1)) return 1; if(d2==0&&On_Segment(p3,p4,p2)) return 1; if(d3==0&&On_Segment(p1,p2,p3)) return 1; if(d4==0&&On_Segment(p1,p2,p4)) return 1; return 0; } double dis( point p1, point p2 ){ return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) ); } int main(){ point p1, p2, p3, p4; int x1, y1, x2, y2, Case = 1; while( scanf("%d%d%d%d", &x1, &y1, &x2, &y2) != EOF) { if( (x1==0)&&(y1==0)&&(x2==0)&&(y2==0) ) break; p1.x = x1, p1.y = y1; p2.x = x2, p2.y = y2; p3.input(); p4.input(); double res; if( Segment_Intersect( p1, p2, p3, p4 ) ){ res = MIN( dis(p1,p3)+dis(p2,p3), dis(p1,p4)+dis(p2,p4) ); } else{ res = dis(p1,p2); } printf("Case %d: ", Case++ ); printf("%.3lf\n", res/2. ); } return 0; }
第六题 小云过生日
贪心，考虑间隔
View Code
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; const int N = 200008; int a[N], Q[N]; int m, n, s; int main() { while( scanf("%d%d%d", &m,&n,&s), n+m+s ) { for(int i = 0; i < s; i++) scanf("%d", &a[i] ); sort( a, a+s ); s = unique( a, a+s ) - a; int cnt = 0; for(int i = 0; i < s-1; i++) { int t = a[i+1]-a[i]-1; if( t ) Q[cnt++] = t; } if( m >= (cnt+1) ) printf("%d\n", s ); else{ sort( Q, Q+cnt ); int tmp = 0; for(int i = 0; i < ((cnt+1)-m); i++) tmp += Q[i]; printf("%d\n", tmp+s ); } } return 0; }
第七题 数学
预处理前缀乘积和后缀乘积，然后避免除法，就可以使用同余定理了。
View Code
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> typedef long long LL; const int mod = 1e9+7; const int N = 1e5+10; LL A[N],B[N], left[N],right[N]; int n; int main() { while( scanf("%d", &n), n ) { left[0] = right[n+1] = 1; for(int i = 1; i <= n; i++) scanf("%lld", &A[i] ); for(int i = 1; i <= n; i++) { left[i] = left[i-1]*A[i]%mod; right[n+1-i] = right[n+2-i]*A[n+1-i]%mod; } for(int i = 1; i <= n; i++) B[i] = left[i-1]*right[i+1]%mod; for(int i = 1; i <= n; i++) printf( (i==1)?"%lld":" %lld", B[i] ); puts(""); } return 0; }
第八题 跳格子
考虑要走固定步长到终点，其实只有到终点后还剩余步长时，如何处理。 奇偶判定即可，因为
从当前点走出去再走回来必定是偶数步。 所以BFS时可以标记，这样就不会超内存了。
View Code
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<iostream> #include<algorithm> using namespace std; const int N = 10; int n, m, s; int dir[4][2] = { {0,-1},{0,1},{1,0},{-1,0} }; bool vis[N][N]; char mp[N][N]; struct node{ int x, y, step; }st,ed,cur,nxt; queue<node> Q; bool legal( int x, int y ) { if( (x>=0)&&(x<n)&&(y>=0)&&(y<m) ) return true; return false; } bool BFS(){ while( !Q.empty() ) Q.pop(); memset( vis, 0, sizeof(vis) ); // vis[st.x][st.y] = true; Q.push( st ); while( !Q.empty() ){ cur = Q.front(); Q.pop(); if( (mp[ cur.x ][ cur.y ] == 'D') && cur.step == s ) return true; for(int i = 0; i < 4; i++) { nxt.x = cur.x+dir[i][0]; nxt.y = cur.y+dir[i][1]; if( legal( nxt.x, nxt.y ) && (!vis[nxt.x][nxt.y]) && (cur.step < s) && (mp[nxt.x][nxt.y] != 'X') ){ nxt.step = cur.step+1; vis[nxt.x][nxt.y] = true; if( mp[nxt.x][nxt.y] == 'D' ){ if( (nxt.step==s) || !((s-nxt.step)&1) ) return true; else return false; } Q.push( nxt ); } } } return false; } int main() { while( scanf("%d%d%d",&n,&m,&s) != EOF ) { if( n+m+s == 0 ) break; for(int i = 0; i < n; i++) scanf("%s", mp[i] ); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if( mp[i][j] == 'S' ) st.x = i, st.y = j, st.step = 0; if( mp[i][j] == 'D' ) ed.x = i, ed.y = j, ed.step = 0; } bool flag = BFS(); puts( flag ? "YES" : "NO" ); } return 0; }