首页 > 代码库 > UESTC 2014 Summer Training #6 Div.2
UESTC 2014 Summer Training #6 Div.2
又是只过两水题,不过状态有些回升,也是差点一血.
Problem A SPOJ AMR11A
显然的dp?就一抖就想到尝试从(R,C)推到(1,1),正着推的话,只能检查某一种解可不可行(就有人想出了二分+DP的神奇方法。。刚卡过。。不过上界是把所有龙加起来。。不闲麻烦的话。。可以按照贪心的方法先跑一个上界，就每一步选当前最优)
倒着推，龙的话，就加上，药水的话，减去？不够，和1取最大值；某一个点的f[i][j]就是两种策略取最小值；
f[i][j] = min{ max(1, f[i+1][j]-s[i][j]) , max(1, f[i][j+1]-s[i][j] }
题外话: 自己是12:24提交的这代码。。不过不是scanf，是cin，然后又提交了一个递推的，还是TLE。。。于是就去写水题，写了水题回来写。。。居然会去写搜索。。主要看大家都没怎么过。。以为不是这么简单的dp 0 0 写了好几个小时，想到了求出那个上界的方法，以后搜索优化也许可以用。。不过对这题没什么帮助，后来又去研究卡时。。总之挂很惨。。差一点一血啊
(记忆化)
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;const int maxn = 500+10;const int inf = ~0u >> 2;int T, r, c, ans;int f[maxn][maxn], s[maxn][maxn];int dp(int x, int y){ // cout << "dp " << x << ‘ ‘ << y << endl; if(x > r || y > c) return inf; if(f[x][y] != inf) return f[x][y]; return f[x][y] = min(max(dp(x+1, y)-s[x][y], 1), max(dp(x, y+1)-s[x][y], 1));}int main(){#ifdef LOCAL freopen("A.in", "r", stdin);#endif cin >> T; while(T--) { cin >> r >> c; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) f[i][j] = inf; f[r][c] = 1; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) scanf("%d", s[i]+j); cout << dp(1, 1) << endl; } return 0;}
Problem B SPOJ AMR11B
大意是给你圆（圆心+半径）、三角形（三点）、正方形（左下角和边长），球出覆盖的点数，只用考虑整数，包括给的数据
由于数据很小，我们可以求出其外接?的矩形，枚举点再来判定是否在图形内，需要做判重处理。
圆用x^2+y^2=R^2这种公式就行了，正方形直接枚举的点就是图形内的（包括边界），主要是三角形比较麻烦，需要用到前几天考察过的计算几何的知识（我都还没写解题报告。。）
判断三个小三角形面积和是否等于大三角形面积。面积的求法只能暂且记住，好像算是线性代数的知识0 0 都没印象。
S=|(y3-y1)*(x2-x1)-(y2-y1)*(x3-x1)|/2 (在这道题的情况下,就别/2咯)
奥，把坐标系移动下，c语言数组不好处理负数呢
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <ctype.h>using namespace std;const int maxn = 400;int T, n, cnt;bool used[maxn][maxn];void calcSquare(){ int x, y, l; scanf("%d%d%d", &x, &y, &l); x += 100; y += 100; for(int i = 0; i <= l; i++) for(int j = 0; j <= l; j++) if(!used[x+i][y+j]) { used[x+i][y+j] = 1; cnt++; }} void calcCircle(){ int x0, y0, r; scanf("%d%d%d", &x0, &y0, &r); x0 += 100; y0 += 100; int x = x0-r, y = y0-r, l = 2*r; for(int i = 0; i <= l; i++) for(int j = 0; j <= l; j++) {// if(i == 1 && j == 2) cout << ( !used[x+i][y+i] && (x+i-x0)*(x+i-x0)+(y+j-y0)*(y+j-y0) <= r*r ) << endl;// int a = (x+i-x0)*(x+i-x0)+(y+j-y0)*(y+j-y0), b = r*r;// cout << x+i << ‘ ‘ << y+j << ‘ ‘ << a << ‘ ‘ << b << endl; if(!used[x+i][y+j] && (x+i-x0)*(x+i-x0)+(y+j-y0)*(y+j-y0) <= r*r) {// if( (x+i-x0)*(x+i-x0)+(y+j-y0)*(y+j-y0) > r*r) //if(a > b) continue;// cout << "COUNT" << endl;// cout << "Change " << x+i << ‘ ‘ << y+j << endl; used[x+i][y+j] = 1;// cout << "Change " << x+i << ‘ ‘ << y+j << endl; cnt++; } }}int area(int x1, int y1, int x2, int y2, int x3, int y3){ //notice real area is this one divide 2 return abs((y3-y1)*(x2-x1)-(y2-y1)*(x3-x1));}void calcTriangle(){ int x1, x2, x3, y1, y2, y3; scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3); x1 += 100; y1 += 100; x2 += 100; y2 += 100; x3 += 100; y3 += 100; int a, b, c, d; a = min(x1, min(x2, x3)); b = min(y1, min(y2, y3)); c = max(x1, max(x2, x3)); d = max(y1, max(y2, y3)); for(int i = a; i <= c; i++) for(int j = b; j <= d; j++) if(!used[i][j]) { if(area(i, j, x1, y1, x2, y2) + area(i, j, x2, y2, x3, y3) + area(i, j, x1, y1, x3, y3) != area(x1, y1, x2, y2, x3, y3)) continue; used[i][j] = 1; cnt++; }}int main(){#ifdef LOCAL freopen("B.in", "r", stdin);#endif scanf("%d", &T); while(T--) { scanf("%d", &n); cnt = 0; memset(used, 0, sizeof(used)); while(n--) { char c; while(!isalpha(c = getchar())) ; switch(c) { case ‘C‘: calcCircle(); break; case ‘T‘: calcTriangle(); break; case ‘S‘: calcSquare(); break; default: break; } } printf("%d\n", cnt); } return 0;}
Problem E SPOJ AMR11E
找出第n个幸运数(因子中至少能找出3个不同的质数)
由于n比较小,我直接打表出1000个幸运数。。。打表写得比较渣。一开始还写错了。代码不贴咯。
Problem G SPOJ AMR11G
就水题。。。判断下有没D vjudge爬虫代码估计渣了，Sample Input格式有点问题，害得我代码调了很久
// cin.getline(str, [length], [endcharacter])(会读入endcharacter)
#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>using namespace std;const int maxn = 100;int T, N;char c;int main(){#ifdef LOCAL freopen("G.in" , "r", stdin);#endif cin >> T; cin.ignore(); while(T--) { { char s[maxn]; cin.getline(s, maxn);// cout << s << endl;// cin.ignore(); bool ok = true; for(unsigned int i = 0; i < strlen(s); i++) if(s[i] == ‘D‘) { ok = false; break; } if(!ok) cout << "You shall not pass!" << endl; else cout << "Possible" << endl; } } return 0;}
Problem J SPOJ AMR11J
比较裸的bfs，数据量不大，不用担心什么，关键是策略写对没。
主要问题在于两个部落同时expand到一点时，会冲突，标记为‘*‘，而bfs是有先后的，除非多线程？
所以需要延时处理，记录要更新的地点，记录下要更新 为 的标记：另开一个数组，先到先标记，后到发现已标记就置为‘*’
!!!!这里思路就又错了，逻辑不紧哎。 发现标记不同才置为‘*‘
否则会出现b.b -> b*b
(可能是vector降低了效率，跑得比较慢)
#include<iostream>#include<cstdio>#include<cstdlib>#include<vector>#include<queue>#include<utility>#include<cstring>using namespace std;const int maxn = 500+10;const int dx[] = {1, -1, 0, 0};const int dy[] = {0, 0, 1, -1};typedef pair<int, int> pii;int T, R, C;char m[maxn][maxn], ocp[maxn][maxn];vector<pii> v;queue<pii> q;void update(){ for(int i = 0, t = v.size(); i < t; i++) { int x = v[i].first, y = v[i].second; if(m[x][y] == ‘.‘) { m[x][y] = ocp[x][y]; q.push(make_pair(x, y)); } } v.clear();}bool can_move(int x, int y){ return x >= 1 && x <= R && y >= 1 && y <= C && m[x][y] == ‘.‘;}void bfs(){ for(int i = 1; i <= R; i++) for(int j = 1; j <= C; j++) if(m[i][j] <= ‘z‘ && m[i][j] >= ‘a‘) q.push(make_pair(i, j)); while(!q.empty()) { pii tmp = q.front(); q.pop(); int x = tmp.first, y = tmp.second; for(int i = 0; i < 4; i++) { int nx = x+dx[i], ny = y+dy[i]; if(can_move(nx, ny)) { if(ocp[nx][ny] && ocp[nx][ny] != m[x][y]) m[nx][ny] = ‘*‘; else { v.push_back(make_pair(nx, ny)); ocp[nx][ny] = m[x][y]; } } } if(q.empty()) update(); }}int main(){#ifdef LOCAL freopen("J.in", "r", stdin);#endif cin >> T; while(T--) { cin >> R >> C; while(!q.empty()) q.pop(); v.clear(); memset(ocp, 0, sizeof(ocp)); for(int i = 1; i <= R; i++) cin >> (m[i]+1); bfs(); for(int i = 1; i <= R; i++) cout << (m[i]+1) << endl; } return 0;}
A题瞄一眼思路就来了,所以直接写的A,无奈犯傻逼,数据量高达500*500=250000 25W啊 TLE得没办法
然后去跟榜做E、G，E题打表因为自己没读透题，浪费很多时间，这一来一去心态乱了很多。总感觉自己能写A，再去搞没办法又搜索又减枝，反正搞到快4点也一直TLE
心态真的崩了，一开始以为能做的题，结果卡了这么久，我交了43发。。。彻底蒙了。还有一丝理智，去看J，又慌了！根本不用考虑time的，还去傻逼写优先队来保证每次出队是time最小的，其实就是跟新完一圈又跟新下一圈。不过无伤大雅，有个小错误没时间去发现了。2题GG。rank又垫底。
心态这玩意，真的不是一两天能改好的，也要看比赛的重要性，多加控制吧。
自己读题问题也很大的，时常没考虑好就去写。写完样例一跑就傻逼。
策略：
问题在于有灵感想出大概思路的时候，不要抢着去写，再读题，再跑样例，理清思路再写代码，最后思考极限数据（也可以一开始就有考虑）
其实这种策略不是一次想提出，关键是自己执行力度，容易忘掉。
经常总结才行！