其实十一就写好了，然而这近两个月我沉迷微积分无法自拔x
UVa1589
注意这个题里面可以把帅和车等同处理嘛
对每个棋子不仅要考虑竖着将，也要考虑横着将
可能是近期（。）写的比较长的题了，虽然实现还能更简单点的
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END const int maxn = 15; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; //up, down, left, right const int dx2[] = {-2, -2, 2, 2, -1, 1, -1, 1}; const int dy2[] = {-1, 1, -1, 1, -2, -2, 2, 2}; //up-left, up-right, down-left, down-right, left-up, left-down, right-up, right-down int n; pii black, red[maxn]; //st: r, nd: c int kind[maxn], m[256]; bool Check() { //(1, 4) (1, 5) (1, 6) //(2, 4) (2, 5) (2, 6) //(3, 4) (3, 5) (3, 6) int x = black.st, y = black.nd; //where black general is FOR (i, 0, 3) { int tx = x + dx[i], ty = y + dy[i]; //where black general goes if (tx < 1 || tx > 3 || ty < 4 || ty > 6) CT; bool flag = true; //there is a way to avoid being checkmated FOR (j, 1, n) { //check each piece if (!flag) BK; if (red[j].st == tx && red[j].nd == ty) CT; //same point if (kind[j] <= 2) { //general and chariot if (ty == red[j].nd) { //1-9 int cnt = 0; FOR (k, 1, n) { if (red[k].nd != ty || j == k) CT; if (red[k].st > min(tx, red[j].st) && red[k].st < max(tx, red[j].st)) ++ cnt; } if (!cnt) flag = false; } else if (tx == red[j].st) { //1-10 int cnt = 0; FOR (k, 1, n) { if (red[k].st != tx || j == k) CT; if (red[k].nd > min(ty, red[j].nd) && red[k].nd < max(ty, red[j].nd)) ++ cnt; } if (!cnt) flag = false; } } else if (kind[j] == 3) { //horse int x2 = red[j].st, y2 = red[j].nd, dir = -1; FOR (k, 0, 7) { int tx2 = x2 + dx2[k], ty2 = y2 + dy2[k]; if (tx2 < 1 || tx2 > 10 || ty2 < 1 || ty2 > 9) CT; if (tx == tx2 && ty == ty2) { dir = k; BK; } } if (dir != -1) { int tx2 = x2 + dx[dir >> 1], ty2 = y2 + dy[dir >> 1]; bool ok = false; FOR (k, 1, n) if (tx2 == red[k].st && ty2 == red[k].nd) { ok = true; BK; } if (!ok) flag = false; } } else if (kind[j] == 4) { //cannon if (ty == red[j].nd) { //1-9 int cnt = 0; FOR (k, 1, n) { if (red[k].nd != ty || j == k) CT; if (red[k].st > min(tx, red[j].st) && red[k].st < max(tx, red[j].st)) ++ cnt; } if (cnt == 1) flag = false; } else if (tx == red[j].st) { //1-10 int cnt = 0; FOR (k, 1, n) { if (red[k].st != tx || j == k) CT; if (red[k].nd > min(ty, red[j].nd) && red[k].nd < max(ty, red[j].nd)) ++ cnt; } if (cnt == 1) flag = false; } } } if (flag) RT false; //not checkmated } RT true; //checkmated } int main() { //freopen("input.txt", "r", stdin); m['G'] = 1, m['R'] = 2, m['H'] = 3, m['C'] = 4; //general: 1 //chariot: 2 //horse: 3 //cannon: 4 while (true) { Scan(n, black.st, black.nd); //printf("%d %d %d\n", n, black.st, black.nd); if (!n) BK; FOR (i, 1, n) { char ch; cin >> ch; Scan(red[i].st, red[i].nd); //scanf("%c%d%d", &ch, &red[i].st, &red[i].nd); kind[i] = m[ch]; } printf("%s\n", Check() ? "YES" : "NO"); } RT 0; } //imagasaikou! UVa201 //TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END const int maxn = 10; int n, m; bool gh[maxn][maxn][maxn], gv[maxn][maxn][maxn]; int main() { //freopen("input.txt", "r", stdin); int kase = 0; while (cin >> n >> m) { if (kase) cout << endl << "**********************************" << endl << endl; CLR(gh, 0), CLR(gv, 0); FOR (i, 1, n) FOR (j, 1, n) gh[i][j][j] = true; FOR (i, 1, n) FOR (j, 1, n) gv[i][j][j] = true; FOR (i, 1, m) { int x, y; char dir; cin >> dir >> x >> y; if (dir == 'H') gh[x][y][y + 1] = true; else gv[x][y][y + 1] = true; } FOR (i, 1, n) FOR (j, 1, n) FOR (k, j + 1, n) gh[i][j][k] = gh[i][j][k - 1] && gh[i][k - 1][k]; FOR (i, 1, n) FOR (j, 1, n) FOR (k, j + 1, n) gv[i][j][k] = gv[i][j][k - 1] && gv[i][k - 1][k]; //FOR (i, 1, n) FOR (j, 1, n) FOR (k, j + 1, n) if (gh[i][j][k]) printf("(%d, %d) and (%d, %d) are connected\n", i, j, i, k); //FOR (i, 1, n) FOR (j, 1, n) FOR (k, j + 1, n) if (gv[i][j][k]) printf("(%d, %d) and (%d, %d) are connected\n", j, i, k, i); bool flag = false; printf("Problem #%d\n\n", ++ kase); FOR (i, 1, n - 1) { int cnt = 0; FOR (j, 1, n - i) FOR (k, 1, n - i) if (gh[j][k][k + i] && gh[j + i][k][k + i] && gv[k][j][j + i] && gv[k + i][j][j + i]) ++ cnt; //(j, k) (j, k + i) //(j + i, k) (j + i, k + i) if (cnt) { printf("%d square (s) of size %d\n", cnt, i); flag = true; } } if (!flag) puts("No completed squares can be found."); } RT 0; } //imagasaikou!UVa220
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}; const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; const char m[] = {'W', 'B'}; int T; char brd[10][10]; bool cur; vector<pii> ans; bool Check(int x, int y) { if (brd[x][y] != '-') RT false; FOR (i, 0, 7) { int tx = x + dx[i], ty = y + dy[i]; if (!brd[tx][ty]) CT; if (brd[tx][ty] == m[!cur]) { while (brd[tx][ty] != '-' && brd[tx][ty]) { if (brd[tx][ty] == m[cur]) RT true; tx += dx[i], ty += dy[i]; } } } RT false; } int main() { //freopen("input.txt", "r", stdin); Scan(T); while (T --) { FOR (i, 1, 8) FOR (j, 1, 8) cin >> brd[i][j]; char ch; cin >> ch; //true: B, false: W cur = (ch == 'B'); while (cin >> ch) { if (ch == 'L') { //L bool flag = false; FOR (i, 1, 8) FOR (j, 1, 8) { if (Check(i, j)) { if (!flag) { flag = true; printf("(%d,%d)", i, j); } else printf(" (%d,%d)", i, j); } } if (!flag) printf("No legal move."); puts(""); } else if (ch == 'M') { //M int x = getchar() - '0', y = getchar() - '0'; if (!Check(x, y)) cur = !cur; brd[x][y] = m[cur]; FOR (i, 0, 7) { int tx = x + dx[i], ty = y + dy[i]; if (!brd[tx][ty]) CT; if (brd[tx][ty] == m[!cur]) { bool flag = false; while (brd[tx][ty] != '-' && brd[tx][ty]) { if (brd[tx][ty] == m[cur]) { flag = true; BK; } tx += dx[i], ty += dy[i]; } if (flag) { tx = x + dx[i], ty = y + dy[i]; while (brd[tx][ty] != m[cur]) { brd[tx][ty] = m[cur]; tx += dx[i], ty += dy[i]; } } } } int black = 0, white = 0; FOR (i, 1, 8) FOR (j, 1, 8) if (brd[i][j] == 'B') ++ black; else if (brd[i][j] == 'W') ++ white; printf("Black - - White - -\n", black, white); cur = !cur; } else { //Q FOR (i, 1, 8) puts(brd[i] + 1); BK; } } if (T) puts(""); } RT 0; } //imagasaikou! UVa253枚举转法，模拟实现
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END bool Same(char* s1, char* s2) { FOR (i, 1, 6) if (s1[i] != s2[i]) RT false; RT true; } char s[15], s1[15], s2[15]; int main() { //freopen("input.txt", "r", stdin); while (cin >> s + 1) { FOR (i, 1, 6) s1[i] = s[i], s2[i] = s[i + 6]; s1[7] = s2[7] = '\0'; //cout << s1 + 1 << ' ' << s2 + 1 << endl; bool flag = false; FOR (i, 0, 3) FOR (j, 0, 3) FOR (k, 0, 3) { //i: 1-6, j: 2-5, k: 3-4 //transform s1 to s3 char s3[15], t[15]; FOR (l, 1, 6) s3[l] = s1[l]; s3[7] = '\0'; FOR (l, 1, i) { t[1] = s3[1], t[2] = s3[4], t[3] = s3[2], t[4] = s3[5], t[5] = s3[3], t[6] = s3[6]; FOR (o, 1, 6) s3[o] = t[o]; } //123456 -> 142536 FOR (l, 1, j) { t[1] = s3[4], t[2] = s3[2], t[3] = s3[1], t[4] = s3[6], t[5] = s3[5], t[6] = s3[3]; FOR (o, 1, 6) s3[o] = t[o]; } //123456 -> 421653 FOR (l, 1, k) { t[1] = s3[2], t[2] = s3[6], t[3] = s3[3], t[4] = s3[4], t[5] = s3[1], t[6] = s3[5]; FOR (o, 1, 6) s3[o] = t[o]; } //123456 -> 263415 //printf("i = %d, j = %d, k = %d, s3 = %s\n", i, j, k, s3 + 1); if (Same(s3, s2)) { flag = true; BK; } } printf("%s\n", flag ? "TRUE" : "FALSE"); } RT 0; } //imagasaikou! UVa1590实现不难，倒是这个ip地址什么的想了一下子啊
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END const int maxn = 1010; int n, ip[maxn][4], bit[maxn][1 << 5], ans1[4], ans2[4]; int main() { //freopen("input.txt", "r", stdin); while (cin >> n) { CLR(ans1, 0), CLR(ans2, 0); FOR (i, 1, n) scanf("%d.%d.%d.%d", &ip[i][0], &ip[i][1], &ip[i][2], &ip[i][3]); int dig = 32; FOR (i, 1, n) { ROF (j, 31, 0) { //0.1.2.3 -> 0, 1, 2, ..., 30, 31 bit[i][j] = ip[i][j >> 3] & 1; ip[i][j >> 3] >>= 1; } FOR (j, 0, 31) if (j < dig && bit[1][j] != bit[i][j]) dig = j; //from high to low } FOR (i, dig, 31) bit[1][i] = 0; int mul; ROF (i, 31, 0) { if (i % 8 == 7) mul = 1; ans1[i >> 3] += bit[1][i] * mul; mul <<= 1; } ROF (i, 31, 0) { if (i % 8 == 7) mul = 1; if (i < dig) ans2[i >> 3] += mul; mul <<= 1; } printf("%d.%d.%d.%d\n", ans1[0], ans1[1], ans1[2], ans1[3]); printf("%d.%d.%d.%d\n", ans2[0], ans2[1], ans2[2], ans2[3]); } RT 0; } //imagasaikou! UVa508初见题目觉得好麻烦啊
不过C++有string类，实现就很暴力了，囧rz
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END map<char, string> morse; map<string, string> dict; void GetTable() { char c; string s; while (cin >> c && c != '*') { cin >> s; morse[c] = s; } } void GetContext() { string s; while (cin >> s && s != "*") { string t = ""; FOR (i, 0, s.size() - 1) t += morse[s[i]]; dict[s] = t; } } void Solve() { string s; while (cin >> s && s != "*") { string ans; int cnt = 0; for (map<string, string> :: iterator it = dict.begin(); it != dict.end(); ++ it) if (it -> nd == s) if (!(cnt ++)) ans = it -> st; if (cnt > 1) cout << ans << "!"; else if (cnt == 1) cout << ans; else if (!cnt) { int delta = INF; for (map<string, string> :: iterator it = dict.begin(); it != dict.end(); ++ it) { string s1 = it -> nd, s2 = s; if (s1.size() > s2.size()) swap(s1, s2); if (s1 == s2.substr(0, s1.size())) if (s2.size() - s1.size() < delta) { delta = s2.size() - s1.size(); ans = it -> st; } } cout << ans << "?"; } cout << endl; } } int main() { //freopen("input.txt", "r", stdin); GetTable(); GetContext(); Solve(); RT 0; } //imagasaikou!UVa509
主要问题还是理解题意...然而我已经忘记1个多月前写的东西是什么意思了...
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END int d, s, b; //disk, size, block char mode, dat[6][7000]; //E: even, O: odd bool Read() { cin >> d; if (!d) RT false; cin >> s >> b; cin >> mode; FOR (i, 0, d - 1) cin >> dat[i]; //DEBUG; //FOR (i, 0, d - 1) cout << dat[i] << endl; //DEBUG; RT true; } bool Check() { int len = s * b - 1; FOR (i, 0, len) { int res = 0, cnt = 0, pos; FOR (j, 0, d - 1) if (dat[j][i] == '1') res ^= 1; else if (dat[j][i] == 'x') { ++ cnt; pos = j; } if ((cnt > 1) || (!cnt && ((mode == 'E' && res) || (mode == 'O' && !res)))) RT false; else if (cnt == 1) { if (mode == 'E') dat[pos][i] = (res ? '1' : '0'); else dat[pos][i] = (res ? '0' : '1'); } } RT true; } void Solve() { if (!Check()) { cout << "invalid." << endl; RT; } cout << "valid, contents are: "; cout << hex; int cnt = 0, ans = 0; FOR (i, 0, b - 1) { FOR (j, 0, d - 1) { if (j == i % d) CT; FOR (k, i * s, (i + 1) * s - 1) { ans = (ans << 1) + (dat[j][k] == '1'); cnt = (cnt + 1) % 4; if (!cnt) { printf("%X", ans); //cout << ans; ans = 0; } } } } if (cnt) printf("%X", ans << (4 - cnt)); //if (cnt) cout << (ans << (4 - cnt)); cout << endl; RT; } int main() { //freopen("input.txt", "r", stdin); int kase = 0; while (Read()) { printf("Disk set %d is ", ++ kase); Solve(); } RT 0; } //imagasaikou!UVa12108
竟然当时一时没想到靠谱算法...于是选择设置一个阈值以停止了
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END int n, a[15], b[15], c[15]; int main() { //freopen("input.txt", "r", stdin); int kase = 0; while (scanf("%d", &n) == 1 && n) { FOR (i, 1, n) Scan(a[i], b[i], c[i]); int ans = -1; FOR (i, 1, 1000000) { int cnt = 0; //awake FOR (j, 1, n) if (c[j] <= a[j]) ++ cnt; if (cnt == n) { ans = i; BK; } FOR (j, 1, n) { if (c[j] == a[j] + b[j] || (c[j] == a[j] && cnt >= n - cnt)) c[j] = 0; ++ c[j]; } } printf("Case %d: %d\n", ++ kase, ans); } RT 0; } //imagasaikou!UVa1591
注意偏移也是有范围的，所以直接枚举，看是否存的下
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <climits> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END int n, sp, sq; int main() { //freopen("input.txt", "r", stdin); while (scanf("%d%d%d", &n, &sp, &sq) == 3) { LL k = LLONG_MAX; int a, b; FOR (i, 0, 31) FOR (j, 0, 31) { //i: a, j: b LL t = (((LL)sp * (n - 1) + ((LL)sp * (n - 1) << i)) >> j) + sq; if (t >= n * sq && t < k) { k = t; a = i; b = j; } } cout << k << ' ' << a << ' ' << b << endl; } RT 0; } //imagasaikou!UVa815
想象把这个网格形拆成n*n个小方块，然后按照海拔排列
显然水会从低到高的淹没，按这个原理算就行了
//TEMPLATE BEGIN #include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <climits> //#include <ctime> #include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++ (i)) #define ROF(i, a, b) for (int (i) = (a); (i) >= (b); -- (i)) #define FOREDGE(i, u, head, next) for (int (i) = (head[(u)]); (i); (i) = (next[(i)])) #define RT return #define BK break #define CT continue #define CLR(a, b) memset((a), (b), sizeof (a)) #define CPY(a, b) memcpy((a), (b), sizeof (a)) #define DEBUG cerr << "debug" << endl #define STAR cerr << "**********" << endl #define HEAP priority_queue #define st first #define nd second #define pf push_front #define pb push_back #define ppf pop_front #define ppb pop_back #define mp make_pair typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef long double LDB; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; typedef map<int, int> mii; typedef map<LL, LL> mll; typedef map<int, LL> mil; typedef map<LL, int> mli; const int INF(0x3f3f3f3f); const DB DINF(1e20); const DB EPS(1e-12); const DB PI(acos(-1.0)); template<class T> inline void Scan(T& x) { //int, LL char c; for (c = getchar(); c <= ' '; c = getchar()) ; bool ngt(c == '-'); if (ngt) c = getchar(); for (x = 0; c > ' '; c = getchar()) x = (x << 3) + (x << 1) + c - '0'; if (ngt) x = -x; } template<class T> inline void Scan(T& x, T& y) { Scan(x), Scan(y); } template<class T> inline void Scan(T& x, T& y, T& z) { Scan(x), Scan(y), Scan(z); } //TEMPLATE END int m, n, a[1000]; DB h; int main() { //freopen("input.txt", "r", stdin); int kase = 0; while (cin >> m >> n && m && n) { int tot = 0; FOR (i, 1, m) FOR (j, 1, n) cin >> a[++ tot]; cin >> h; h /= 100; DB ans = 0.0; sort(a + 1, a + tot + 1); //FOR (i, 1, tot) cout << a[i] << ' '; cout << endl; a[tot + 1] = INF; FOR (i, 0, tot) { //printf("now, rest h is %.2lf\n", h); if ((a[i + 1] - a[i]) * i <= h) { //(a[i + 1] - a[i]) * 10 * 10 * i <= V ans += a[i + 1] - a[i]; h -= (a[i + 1] - a[i]) * i; } else { ans += h / i; BK; } } printf("Region %d\n", ++ kase); printf("Water level is %.2lf meters.\n", ans); int cnt = 0; FOR (i, 1, tot) cnt += (a[i] <= ans); printf("%.2lf percent of the region is under water.\n\n", 100.0 * cnt / (n * m)); } RT 0; } //imagasaikou! 一个多月前写的东西现在果然还是不记得了...代码可读性感人啊