POJ 1753
Tip1：枚举法，C(0,16)+C(1,16)+C(2,16)+...+C(16,16)=2^16，且最后一次不需要，根据题目意思，后一半也不需要。这题最关键的就是要注意到选2次以上没有意义，所以要么选，要么不选，这样就可以穷举了。
Tip2：这题跑了120ms，如果不用双参数的dfs穷举上一个排列数，而是单参数穷举，那GG，能穷举组合数就不要穷举全排列
#include<iostream> #include<cstring> using namespace std; int a[4][4]; int b[4][4]; int m[16]; const int dl[] = {-1, 0, 1, 0, 0}; const int dr[] = {0, -1, 0, 1, 0}; bool vis[16]; string str; bool ok() { for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { if((b[i][j] % 2) != (b[0][0] % 2)) return false; } } return true; } bool dfs(int cur, int tot, int p) { if(cur == tot) { memcpy(b, a, sizeof(b)); for(int i = 0; i < 16; i++) { if(vis[i]) { int l = i / 4; int r = i % 4; for(int i = 0; i < 5; i++) { if(l+dl[i] >= 0 && l+dl[i] < 4 && r + dr[i] >= 0 && r + dr[i] < 4)b[l+dl[i]][r+dr[i]]++; } } } if(ok())return true; } else { for(int i = p; i < 16; i++) { if(!vis[i]) { vis[i] = true; if(dfs(cur + 1, tot, i + 1)) return true; vis[i] = false; } } } return false; } int main(){ freopen("input.txt", "r", stdin); for(int i = 0; i < 4; i++) { cin >> str; for(int j = 0; j < 4; j++) { if(str[j] == 'b') a[i][j] = 1; } } memcpy(b, a, sizeof(b)); int flag = 0; if(ok()) { cout << 0 << endl; flag = 1; } else for(int i = 1; i < 9; i++) { if(dfs(0, i, 0)) { flag = 1; cout << i << endl; break; } } if(flag == 0) cout << "Impossible" << endl; return 0; }
POJ 2965
Tip1：一样的思路，但是！刚刚穷举0-8，现在穷举1-16，因此循环必须是i<17！这里因为i<16一直在WA！c(0,16)到c(0,16)一共是17个数字！组合数穷举格式见下
#include<iostream> #include<cstring> using namespace std; int a[4][4]; int b[4][4]; int m[16]; bool vis[16]; string str; bool ok() { for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { if(b[i][j] % 2 != 0) return false; } } return true; } bool dfs(int cur, int tot, int p) { if(cur == tot) { memcpy(b, a, sizeof(b)); for(int i = 0; i < 16; i++) { if(vis[i]) { int l = i / 4; int r = i % 4; b[l][r]++; for(int i = 0; i < 4; i++) { b[l][i]++; b[i][r]++; } } } if(ok())return true; } else { for(int i = p; i < 16; i++) { if(!vis[i]) { vis[i] = true; if(dfs(cur + 1, tot, i + 1)) return true; vis[i] = false; } } } return false; } int main() { freopen("input.txt", "r", stdin); for(int i = 0; i < 4; i++) { cin >> str; for(int j = 0; j < 4; j++) { if(str[j] == '+') a[i][j] = 1; } } for(int i = 1; i < 17; i++) { if(dfs(0, i, 0)) { cout << i << endl; for(int j = 0; j < 16; j++) { if(vis[j]) { int l = (j / 4) + 1; int r = (j % 4) + 1; cout << l << " " << r << endl; } } break; } } return 0; }POJ 1328
Tip1：问题看清楚！再转化为熟悉的问题！不能想当然的贪心！
Tip2：粉皮P233
区间选点问题：n个闭区间，选最少的点，使得每个区间上都有一个点
按区间的右端排列，然后按次序判断其左端点即可。
不能想当然的贪心！必须要比划一下证明！
#include<iostream> #include<algorithm> #include<cmath> using namespace std; int n, d; const int MAXN = 1000 + 5; struct Node { int x, y; double l, r; bool init() { cin >> x >> y; if(y > d)return true; l = x - sqrt(d*d - y*y); r = x + sqrt(d*d - y*y); return false; } }node[MAXN]; bool operator < (const Node& a, const Node& b) { if(b.r != a.r)return a.r < b.r; else return a.l < b.l; } int main() { freopen("input.txt", "r", stdin); int kase = 0, ans; while(cin >> n >> d) { if(n == 0 && d == 0)break; int ans = 1; for(int i = 0; i < n; i++) { if(node[i].init()) ans = -1; } if(ans != -1) { sort(node, node + n); double p = node[0].r; for(int i = 1; i < n; i++) { if(node[i].l > p) { p = node[i].r; ans++; } } } cout << "Case " << ++kase << ": " << ans << endl; } return 0; }POJ 2109
Tip1：个别oj不加<stdio>就使用printf会报错（devcpp不会）
Tip2：所谓贪心不是一种特定的算法，而是怎样巧妙的方法刚巧能得到我们要的答案。不能遇到指数就想到对数，还应该想到1/n次方
Tip3：printf输出double用%f不用%lf！切记！
Tip4：printf输出double如果不要小数点，只要%.0f即可
Tip5：double的有效数字是15-16位，大小范围在正负十的308次方之间！不要看到超过long的就想string，也要想到double！
Tip6：有效数字意思是保证十进制下的前15位有效数字正确，而题目只到前9位，所以误差可以忽略
#include<iostream> #include<cmath> #include<cstdio> using namespace std; int main() { freopen("input.txt", "r", stdin); double n, p; while(cin >> n >> p) { printf("%.0f\n", pow(p, 1/n)); } return 0; } java 二分高精度：（此题数据有问题，这里关于ok的判断根本不必加）
import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); BigInteger p = sc.nextBigInteger(); int l = 1, r = 1000000001; boolean ok = false; while(l < r) { int mid = (l + r)/2; BigInteger q = BigInteger.valueOf(mid).pow(n); int zz = q.compareTo(p); if(zz == 0) { ok = true; System.out.println(mid); break; } else if(zz == -1) { l = mid + 1; } else { r = mid; } } if(!ok) { while(BigInteger.valueOf(l).pow(n).compareTo(p)==-1)l++; System.out.println(l-1); } } } }POJ 2586
这题唯一难点是英文
回溯剪枝：219ms
//回溯剪枝 #include<iostream> using namespace std; int s, d; int ans; int a[12]; void dfs(int cur) { if(cur == 12) { int sum = a[0] + a[1] + a[2] + a[3] + a[4]; if(sum >= 0)return; for(int i = 5; i < 12; i++) { sum += a[i]; sum -= a[i-5]; if(sum >= 0)return; } sum = 0; for(int i = 0; i < 12; i++) sum += a[i]; if(sum > ans) ans = sum; } else { a[cur] = s; dfs(cur + 1); a[cur] = -d; dfs(cur + 1); } } int main() { freopen("input.txt", "r", stdin); while(cin >> s >> d) { ans = -1; dfs(0); if(ans == -1) cout << "Deficit" << endl; else cout << ans << endl; } return 0; } 剪得更夸张一点：129ms#include<iostream> using namespace std; int s, d; int ans; int a[12]; void dfs(int cur) { if(cur == 12) { int sum = 0; for(int i = 0; i < 12; i++) sum += a[i]; if(sum > ans) ans = sum; } else { a[cur] = s; if(cur >= 4) { int sum = 0; for(int i = 0; i < 5; i++) { sum += a[cur - i]; } if(sum < 0) dfs(cur + 1); } else { dfs(cur + 1); } a[cur] = -d; if(cur >= 4) { int sum = 0; for(int i = 0; i < 5; i++) { sum += a[cur - i]; } if(sum < 0) dfs(cur + 1); } else { dfs(cur + 1); } } } int main() { //freopen("input.txt", "r", stdin); while(cin >> s >> d) { ans = -1; dfs(0); if(ans == -1) cout << "Deficit" << endl; else cout << ans << endl; } return 0; }
POJ 3295
回溯穷举
Tip1：当算法没有问题时，检查细节，某些变量逻辑上的错误，比如我这里return true的判断一开始是'b'，其实不然，应该是任何为假的字符，因为多层嵌套导致我没有一下子转过弯来
从左往右：
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<vector> using namespace std; char str[105]; map<char, int> M; bool zz[7]; bool ac(char t) { if(t >= 'A' && t <= 'Z') return true; else return false; } bool dfs(int cur) { if(cur == 5) { vector<char> v; int len = strlen(str); bool ok = false; for(int i = 0; i < len; i++) { v.push_back(str[i]); while(!v.empty()) { if(v.size() > 1) { if(v[v.size() - 2] == 'N' && !ac(v[v.size() - 1])) { char tmp = v[v.size() - 1]; v.pop_back(); v.pop_back(); if(zz[M[tmp]]) v.push_back('b'); else v.push_back('a'); continue; } } if(v.size() > 2) { char c1 = v[v.size() - 3]; char c2 = v[v.size() - 2]; char c3 = v[v.size() - 1]; if(ac(c1) && !ac(c2) && !ac(c3)) { v.pop_back(); v.pop_back(); v.pop_back(); if(c1 == 'K') { if(zz[M[c2]] && zz[M[c3]]) v.push_back('a'); else v.push_back('b'); } if(c1 == 'A') { if(!zz[M[c2]] && !zz[M[c3]]) v.push_back('b'); else v.push_back('a'); } if(c1 == 'C') { if(zz[M[c2]] && !zz[M[c3]]) v.push_back('b'); else v.push_back('a'); } if(c1 == 'E') { if(zz[M[c2]] == zz[M[c3]]) v.push_back('a'); else v.push_back('b'); } continue; } } break; } } if(!zz[M[v[0]]]) return true; } else { zz[cur] = false; if(dfs(cur+1))return true; zz[cur] = true; if(dfs(cur+1))return true; } return false; } int main() { //freopen("input.txt", "r", stdin); M['p'] = 0; M['q'] = 1; M['r'] = 2; M['s'] = 3; M['t'] = 4; M['a'] = 5; M['b'] = 6; zz[5] = true; zz[6] = false; while(scanf("%s", str) != EOF && str[0] != '0') { if(dfs(0)) printf("not\n"); else printf("tautology\n"); } return 0; } 从右往左：#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<stack> using namespace std; char str[105]; map<char, int> M; bool zz[7]; bool ac(char t) { if(t >= 'A' && t <= 'Z') return true; else return false; } bool dfs(int cur) { if(cur == 5) { stack<char> v; int len = strlen(str); bool ok = false; for(int i = 0; i < len; i++) { v.push(str[len-1-i]); if(ac(v.top())) { if(v.top() == 'N') { v.pop(); char tmp = v.top(); v.pop(); if(zz[M[tmp]]) v.push('b'); else v.push('a'); continue; } char c1 = v.top(); v.pop(); char c2 = v.top(); v.pop(); char c3 = v.top(); v.pop(); if(c1 == 'K') { if(zz[M[c2]] && zz[M[c3]]) v.push('a'); else v.push('b'); } if(c1 == 'A') { if(!zz[M[c2]] && !zz[M[c3]]) v.push('b'); else v.push('a'); } if(c1 == 'C') { if(zz[M[c2]] && !zz[M[c3]]) v.push('b'); else v.push('a'); } if(c1 == 'E') { if(!zz[M[c2]] && !zz[M[c3]]) v.push('a'); else if(zz[M[c2]] && zz[M[c3]]) v.push('a'); else v.push('b'); } } } if(!zz[M[v.top()]]) return true; } else { zz[cur] = false; if(dfs(cur+1))return true; zz[cur] = true; if(dfs(cur+1))return true; } return false; } int main() { freopen("input.txt", "r", stdin); M['p'] = 0; M['q'] = 1; M['r'] = 2; M['s'] = 3; M['t'] = 4; M['a'] = 5; M['b'] = 6; zz[5] = true; zz[6] = false; while(scanf("%s", str) != EOF && str[0] != '0') { if(dfs(0)) printf("not\n"); else printf("tautology\n"); } return 0; }
POJ 1068
直接模拟
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #define sf(a) scanf("%d", &a) using namespace std; int T; int n; int a[22]; vector<int> v; int main() { freopen("input.txt", "r", stdin); sf(T); while(T--) { v.clear(); sf(n); for(int i = 0; i < n; i++) sf(a[i]); int last = 0; for(int i = 0; i < n; i++) { int tmp = a[i]-last; last = a[i]; for(int j = 0; j < tmp; j++) v.push_back(0); v.push_back(1); } bool flag = true; int tot = 0; for(int i = 0; i < v.size(); i++) { if(v[i] == 1) { int pos = i - 1; int ans = 1; while(v[pos] != 0) { if(v[pos] == 2) ans++; pos--; } v[pos] = 2; if(flag) flag = false; else printf(" "); printf("%d", ans); } } printf("\n"); } return 0; } POJ 2632
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<set> #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sfs(a) scanf("%s", a) using namespace std; const int MAXN = 100 + 5; int kase, a, b, n, m; char str[2]; int rob[MAXN]; int ins[MAXN]; int rep[MAXN]; int ra[MAXN]; int rb[MAXN]; int rt[MAXN]; const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; struct Node { int x, y; Node(int _x, int _y): x(_x), y(_y){} }; bool operator < (const Node& a,const Node& b) { if(a.x == b.x) return a.y < b.y; else return a.x < b.x; } set<Node> S; int main() { freopen("input.txt", "r", stdin); sf(kase); while(kase--) { S.clear(); int flag = -1; sf2(a, b); sf2(n, m); for(int i = 0; i < n; i++) { sf(ra[i]); sf(rb[i]); S.insert(Node(ra[i], rb[i])); sfs(str); switch(str[0]) { case 'N':rt[i] = 0;break; case 'E':rt[i] = 1;break; case 'S':rt[i] = 2;break; case 'W':rt[i] = 3;break; } } for(int i = 0; i < m; i++) { sf(rob[i]);rob[i]--; sfs(str); sf(rep[i]); switch(str[0]) { case 'F':ins[i] = 0;break; case 'L':ins[i] = 1;break; case 'R':ins[i] = 2;break; } } // for(int i = 0; i < m; i++) cout << rob[i] << endl; for(int i = 0; i < m; i++) { if(ins[i] == 0) { int x = ra[rob[i]], y = rb[rob[i]]; S.erase(S.find(Node(x, y))); while(rep[i]--) { x += dx[rt[rob[i]]]; y += dy[rt[rob[i]]]; if(x < 1 || x > a || y < 1 || y > b) { flag = -2; printf("Robot %d crashes into the wall\n", rob[i] + 1); break; } if(S.count(Node(x, y)) == 1) { for(int j = 0; j < n; j++) { if(ra[j] == x && rb[j] == y) { flag = j; break; } } printf("Robot %d crashes into robot %d\n", rob[i] + 1, flag + 1); break; } } if(flag != -1)break; ra[rob[i]] = x; rb[rob[i]] = y; S.insert(Node(x, y)); } else { rep[i] %= 4; while(rep[i]--) { rt[rob[i]]+=(ins[i] == 2)?1:3; rt[rob[i]]%=4; } } } if(flag == -1) printf("OK\n"); } return 0; } POJ 1573
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<set> #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfs(a) scanf("%s", a) #define clr(a, b) memset(a, b, sizeof(a)) using namespace std; const int MAXN = 12; int row, col, beg; char str[MAXN]; int grid[MAXN][MAXN]; int vis[MAXN][MAXN]; const int dr[] = {-1, 0, 1, 0}; const int dc[] = {0, 1, 0, -1}; int main() { freopen("input.txt", "r", stdin); while(sf3(row, col, beg) != EOF && row != 0) { clr(vis, 0); clr(grid, 0); for(int i = 1; i <= row; i++) { sfs(str); for(int j = 1; j <= col; j++) { switch(str[j-1]) { case 'N':grid[i][j] = 0;break; case 'E':grid[i][j] = 1;break; case 'S':grid[i][j] = 2;break; case 'W':grid[i][j] = 3;break; } } } int gr = 1, gc = beg, lr, lc; int tot = 0; vis[gr][gc] = 1; int flag = 1; int sum; while(true) { tot++; lr = gr; lc = gc; gr += dr[grid[lr][lc]]; gc += dc[grid[lr][lc]]; if(gr < 1 || gr > row || gc < 1 || gc > col) { printf("%d step(s) to exit\n", tot); break; } if(vis[gr][gc] == 1 && flag == 1) { flag = 0; sum = tot; } if(vis[gr][gc] == 2) { printf("%d step(s) before a loop of %d step(s)\n", sum + sum - tot, tot-sum); break; } vis[gr][gc]++; } } return 0; } POJ 2993
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<set> #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfs(a) scanf("%s", a) #define clr(a, b) memset(a, b, sizeof(a)) using namespace std; const int MAXN = 10; char m[MAXN][MAXN]; char str[100]; char a[2] = {'.', ':'}; int main() { freopen("input.txt", "r", stdin); gets(str); for(int i = 7; i < strlen(str); i++) { if(str[i] == ',') { int r = 9 - str[i-1] + '0'; int c = str[i-2] - 'a' + 1; if(str[i-4] == ',' || str[i-4] == ' ') m[r][c] = str[i-3]; else m[r][c] = 'P'; } } if(strlen(str) > 7) { int r = 9 - str[strlen(str)-1] + '0'; int c = str[strlen(str)-2] - 'a' + 1; if(str[strlen(str)-4] == ',' || str[strlen(str)-4] == ' ') m[r][c] = str[strlen(str)-3]; else m[r][c] = 'P'; } gets(str); for(int i = 7; i < strlen(str); i++) { if(str[i] == ',') { int r = 9 - str[i-1] + '0'; int c = str[i-2] - 'a' + 1; if(str[i-4] == ',' || str[i-4] == ' ') m[r][c] = str[i-3] + 32; else m[r][c] = 'p'; } } if(strlen(str) > 7) { int r = 9 - str[strlen(str)-1] + '0'; int c = str[strlen(str)-2] - 'a' + 1; if(str[strlen(str)-4] == ',' || str[strlen(str)-4] == ' ') m[r][c] = str[strlen(str)-3] + 32; else m[r][c] = 'p'; } for(int i = 1; i <= 8; i++) { printf("+---+---+---+---+---+---+---+---+\n"); for(int j = 1; j <= 8; j++) { printf("|%c", a[(i+j)%2]); if(m[i][j] == 0) printf("%c", a[(i+j)%2]); else printf("%c", m[i][j]); printf("%c", a[(i+j)%2]); } printf("|\n"); } printf("+---+---+---+---+---+---+---+---+\n"); return 0; } POJ 2996 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<set> #include<map> #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfs(a) scanf("%s", a) #define clr(a, b) memset(a, b, sizeof(a)) using namespace std; const int MAXN = 10; char m[MAXN][MAXN]; char str[100]; map<char, int> M; struct Node { char zz; int row, col; Node(int _row = 0, int _col = 0, char _zz = 0):row(_row), col(_col), zz(_zz){} }s1[40], s2[40]; int t1, t2; //* bool cmp1(const Node& p, const Node& q) { if(M[p.zz] != M[q.zz]) return M[p.zz] < M[q.zz]; else if(p.row != q.row) return p.row > q.row; else return p.col < q.col; } bool cmp2 (const Node& p, const Node& q) { if(M[p.zz] != M[q.zz]) return M[p.zz] < M[q.zz]; else if(p.row != q.row) return p.row < q.row; else return p.col < q.col; } //*/ int main() { freopen("input.txt", "r", stdin); M['K'] = 1; M['Q'] = 2; M['R'] = 3; M['B'] = 4; M['N'] = 5; M['P'] = 6; M['k'] = 11; M['q'] = 12; M['r'] = 13; M['b'] = 14; M['n'] = 15; M['p'] = 16; for(int i = 0; i < 34; i++) getchar(); for(int i = 0; i < 8; i++) { getchar(); for(int j = 0; j < 8; j++) { getchar(); m[i+1][j+1] = getchar(); getchar(); getchar(); } getchar(); for(int i = 0; i < 34; i++) getchar(); } for(int i = 1; i <= 8; i++) { for(int j = 1; j <= 8; j++) { //cout << m[i][j]; if(m[i][j] != '.' && m[i][j] != ':') { if(m[i][j] <= 'Z') s1[t1++] = Node(i, j, m[i][j]); else s2[t2++] = Node(i, j, m[i][j]); } } //cout << endl; } sort(s1, s1 + t1, cmp1); sort(s2, s2 + t2, cmp2); printf("White: "); int flag = 1; for(int i = 0; i < t1; i++) { if(flag == 0) printf(","); else flag = 0; if(s1[i].zz != 'P') printf("%c", s1[i].zz); printf("%c%d", s1[i].col + 'a' - 1, 9-s1[i].row); } printf("\n"); printf("Black: "); flag = 1; for(int i = 0; i < t2; i++) { if(flag == 0) printf(","); else flag = 0; if(s2[i].zz != 'p') printf("%c", s2[i].zz - 32); printf("%c%d", s2[i].col + 'a' - 1, 9-s2[i].row); } printf("\n"); return 0; }
至此，POJ题目分类 初级-一、基本算法已刷完
POJ题目分类 初级-二、图算法 暂且先放一放
先准备JSCPC
