1003Mine
让人无限伤心的一道题。
这题是一道简单的sg函数取石子的题,题目中有几处需要注意的。
首先这不是传统意义上的扫雷的走法,白格的八向联通的。
然后是不存在同时属于两个白格范围的格子,也就是不存在同时属于两个石堆的石子。
我们把单独的格子记为1,雷记为0,白格区域周围有偶数格的话和单独的格子效果一样,记为1
周围是奇数个的话则会产生转换,记为2。
然后计算就行了。
比赛的时候的代码距离AC只差三个字符,极度伤心T_T(DFS的时候可能会暴栈,建议自定义栈大小)
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <map> #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; int n,m,k; int sum[1005][1005]; bool used[1005][1005]; int s[1000005]; int shu,shuk,ans; int dx[10] = {1,1,0,-1,-1,-1,0,1}; int dy[10] = {0,-1,-1,-1,0,1,1,1}; int sx[5] = {1,0,-1,0}; int sy[5] = {0,-1,0,1}; void dfs(int x,int y) { used[x][y] = 1; for(int i=0; i<8; i++) { if(x + dx[i] >= 0 && x + dx[i] < n &&y + dy[i] >= 0&&y + dy[i] < m) { if(used[x + dx[i]][y + dy[i]] == 0&&sum[x + dx[i]][y + dy[i]] == 0) { dfs(x + dx[i],y + dy[i]); } } } for(int i=0; i<8; i++) { if(x + dx[i] >= 0 && x + dx[i] < n &&y + dy[i] >= 0&&y + dy[i] < m) { if(used[x + dx[i]][y + dy[i]] == 0&&sum[x + dx[i]][y + dy[i]] > 0) { used[x + dx[i]][y + dy[i]] = 1; shuk++; } } } } int main() { int t,counter; int a,b; while(scanf("%d",&t) != EOF) { counter = 0; while(t--) { counter++; scanf("%d%d%d",&n,&m,&k); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { sum[i][j] = 0; used[i][j] = 0; } } for(int i=0; i<k; i++) { scanf("%d%d",&a,&b); for(int j=0; j<8; j++) { if(a + dx[j] >= 0 && a + dx[j] < n &&b + dy[j] >= 0&&b + dy[j] < m) { sum[a + dx[j]][b + dy[j]]++; } } used[a][b] = 1; } shu = 0; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(used[i][j] == 0) { if(sum[i][j] == 0) { shuk = 0; dfs(i,j); s[shu] = shuk % 2 + 1;//就是这里最初差了三个字符T_T shu++; } } } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(used[i][j] == 0) { s[shu] = 1; shu++; } } } ans = 0; for(int i=0; i<shu; i++) { //cout<<s[i]<<endl; ans ^= s[i]; } printf("Case #%d: ",counter); if(ans) { printf("Xiemao\n"); } else { printf("Fanglaoshi\n"); } } } return 0; }
1004Terrorist’s destroy
一道比较明显的树DP,就是写法比较繁琐
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <map> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x7fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define infA(a) for (int i = 0 ; i <= n ; ++ i)a[i] = inf ; #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; inline void RD(int &ret) { char c; do { c = getchar(); } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); } inline void OT(int a) { if(a >= 10)OT(a / 10) ; putchar(a % 10 + '0') ; } #define N 1000005 int n , m ; struct kdq { int s , e , l , id ; } ed1[N] ; int dis[N] , vis[N] ,qe[N * 10] ; struct ee { int e , next ,id ; } ed[N * 5] ; int ST , EN ; int path[N] , pre[N] ; int head[N] , num ; void init() { mem(head, -1) ; num = 0 ; } void add(int s ,int e ,int id) { ed[num].e = e ; ed[num].id = id ; ed[num].next = head[s] ; head[s] = num ++ ; } int bfs(int pos) { for (int i = 0 ; i <= n ; i ++ ) { dis[i] = inf ; vis[i] = 0 ; } vis[pos] = 1 ; dis[pos] = 0 ; int h = 0 , t = 0 ; qe[h ++ ] = pos ; int ans = 0 ; int index = -1 ; while(h > t) { int tp = qe[t ++ ] ; for (int i = head[tp] ; ~i ; i = ed[i].next) { int e = ed[i].e ; if(dis[e] > dis[tp] + 1 && !vis[e]) { dis[e] = dis[tp] + 1 ; pre[e] = tp ; path[e] = i ; vis[e] = 1 ; if(dis[e] > ans) { ans = dis[e] ; index = e ; } qe[h ++ ] = e ; } } } return index ; } int main() { int T ; cin >> T ; int ca = 0 ; while(T -- ) { cin >> n ; init() ; for (int i = 1 ; i <= n - 1 ; i ++ ) { scanf("%d%d%d",&ed1[i].s ,&ed1[i].e , &ed1[i].l) ; ed1[i].id = i ; add(ed1[i].s , ed1[i].e , i) ; add(ed1[i].e , ed1[i].s , i) ; } ST = bfs(1) ; bfs(ST) ; int mm = 0 ; for (int i = 1 ; i <= n ; i ++ ) { if(mm < dis[i]) { mm = dis[i] ; EN = i ; } } int xx = 0 ; int yy = mm - 1 ; int MM = inf ; int index = -1 ; for (int i = EN ; i != ST ; i = pre[i]) { int c = ed1[ed[path[i]].id].l ; int cc = max(xx , yy) ; if(MM > c * cc) { MM = c * cc ; index = ed[path[i]].id ; } else if(MM == c * cc) { index = min(index ,ed[path[i]].id) ; } xx ++ ,yy -- ; } printf("Case #%d: %d\n",++ca , index) ; } return 0 ; }
1006string
全场最水的一道,不多说
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <map> #define Rep(i, a, b) for(int i = (a); i <= (b); ++i) #define LL long long using namespace std; const int N = 1111; char A[N]; char B[N]; char C[N]; int qian[N][N]; int hou[N][N]; vector<pair<int, int> >atA; vector<pair<int, int> >atB; int main() { int T; scanf("%d", &T); for(int t=1; t<=T; ++t) { scanf("%s%s%s", A+1, B+1, C+1); int lA = strlen(A+1); int lB = strlen(B+1); int lC = strlen(C+1); memset(qian, 0, sizeof(qian)); memset(hou, 0, sizeof(hou)); for(int i=1; i<=lA; ++i) { for(int j=1; j<=lB; ++j) { qian[i][j] = qian[i-1][j-1]+(A[i]==B[j]?1:0); qian[i][j] = max(qian[i][j], qian[i-1][j]); qian[i][j] = max(qian[i][j], qian[i][j-1]); } } for(int i=lA; i>=1; --i) { for(int j=lB; j>=1; --j) { hou[i][j] = max(hou[i+1][j], hou[i][j+1]); hou[i][j] = max(hou[i][j], hou[i+1][j+1]+(A[i]==B[j]?1:0)); } } atA.clear(); atB.clear(); for(int i=1; i<=lA; ++i) { if(A[i]==C[1]) { int j=2, ii=i+1; for(; j<=lC; ) { while(ii<=lA && A[ii]!=C[j]) ++ii; if(ii>lA) break; ++ii; ++j; } if(j>lC) { atA.push_back(make_pair(i, ii-1)); } } } for(int i=1; i<=lB; ++i) { if(B[i]==C[1]) { int j=2, ii=i+1; for(; j<=lC;) { while(ii<=lB && B[ii]!=C[j]) ++ii; if(ii>lB) break; ++ii; ++j; } if(j>lC) atB.push_back(make_pair(i, ii-1)); } } int aa = atA.size(); int bb = atB.size(); int ans = 0; for(int i=0; i<aa; ++i) { for(int j=0; j<bb; ++j) { ans = max(ans, qian[atA[i].first-1][atB[j].first-1]+hou[atA[i].second+1][atB[j].second+1]); } } printf("Case #%d: %d\n", t, ans+lC); } return 0; }