在度被黄大队坑。。。。
1001 水题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | /************************************************************************* > File Name: 1001.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月14日 星期日 12时11分06秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MAXN 100005 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; char s[MAXN]; void work() { int len = strlen(s); string tmp = s; for (int i = 0; i < len; i ++) { if (i + 5 <= len) { string str = tmp.substr(i, 5); if (str == "Apple") { printf("MAI MAI MAI!\n"); } } if (i + 6 <= len) { string str = tmp.substr(i, 6); if (str == "iPhone") { printf("MAI MAI MAI!\n"); } } if (i + 4 <= len) { string str = tmp.substr(i, 4); if (str == "iPod" || str == "iPad") { printf("MAI MAI MAI!\n"); } if (str == "Sony") { printf("SONY DAFA IS GOOD!\n"); } } } } int main() { while (gets(s)) { work(); } return 0; } |
1003 dp，因为是
，所以不同的颜色不能超过
，复杂度
。卡常数卡的好厉害
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | /************************************************************************* > File Name: 1003.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月14日 星期日 15时15分52秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MAXN 50005 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; const int INF = 0x3fffffff; int N, a[MAXN], b[MAXN]; int dp[MAXN][240], keep[MAXN], ans[MAXN]; map <int, int> ma; void work() { ma.clear(); for (int i = 1; i <= N; i ++) { scanf("%d", &a[i]); if (ma.find(a[i]) == ma.end()) { ma.insert(mp(a[i], ma.size() + 1)); } } for (int i = 1; i <= N; i ++) { a[i] = ma[a[i]]; } int M; for (M = 1; M * M <= N; M ++); fill(dp[0], dp[0] + 240, INF); fill(keep, keep + MAXN, 0); fill(ans, ans + MAXN, INF); ans[0] = 0; for (int i = 1; i <= N; i ++) { fill(dp[i], dp[i] + 240, INF); dp[i][1] = i; for (int j = 1; j <= M; j ++) { if (dp[i - 1][j] != INF) { int l = keep[a[i]]; if (l < dp[i - 1][j]) { dp[i][j + 1] = Min(dp[i][j + 1], dp[i - 1][j]); } else { dp[i][j] = Min(dp[i][j], dp[i - 1][j]); } } } for (int j = 1; j <= M; j ++) { ans[i] = Min(ans[dp[i][j] - 1] + j * j, ans[i]); } keep[a[i]] = i; } printf("%d\n", ans[N]); } int main() { while (scanf("%d", &N) != EOF) { work(); } return 0; } |
1005 瞎了的Nim博弈。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | /************************************************************************* > File Name: 1005.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月14日 星期日 19时53分44秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MAXN 100005 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; int N, a[MAXN]; void work() { LL sum = 0; for (int i = 1; i <= N; i ++) { scanf("%d", &a[i]); sum ^= (LL)a[i]; } if (sum) { printf("Win\n"); } else { printf("Lose\n"); } } int main() { while (scanf("%d", &N) != EOF) { work(); } return 0; } |
1006 BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | /************************************************************************* > File Name: 1006.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月14日 星期日 14时06分07秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; bool vis[50005]; int len[50005], start, end; struct Node { int s[7]; } a, b; int change[4][7] = { {0, 4, 3, 1, 2, 5, 6}, {0, 3, 4, 2, 1, 5, 6}, {0, 6, 5, 3, 4, 1, 2}, {0, 5, 6, 3, 4, 2, 1} }; int bfs() { memset(vis, false, sizeof(vis)); memset(len, 0, sizeof(len)); queue <int> Q; Q.push(start); vis[start] = true; len[start] = 0; if (start == end) { return 0; } int state[7] = {}, tmp[7] = {}; while (!Q.empty()) { int now = Q.front(), keep; Q.pop(); keep = now; for (int i = 1; i <= 6; i ++) { state[i] = now % 6; now /= 6; } for (int i = 0; i < 4; i ++) { for (int j = 1; j <= 6; j ++) { tmp[j] = state[change[i][j]]; } int next = 0, six = 1; for (int j = 1; j <= 6; j ++) { next = next + tmp[j] * six; six *= 6; } if (!vis[next]) { Q.push(next); len[next] = len[keep] + 1; vis[next] = true; if (next == end) { return len[next]; } } } } return -1; } void work() { start = 0, end = 0; int six = 1; for (int i = 1; i <= 6; i ++) { scanf("%d", &b.s[i]); start = start + (a.s[i] - 1) * six; end = end + (b.s[i] - 1) * six; six *= 6; } printf("%d\n", bfs()); } int main() { while (scanf("%d %d %d %d %d %d", &a.s[1], &a.s[2], &a.s[3], &a.s[4], &a.s[5], &a.s[6]) != EOF) { work(); } return 0; } |
1008 构造题，大队给我说了下想法，然后说你敲吧。。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | /************************************************************************* > File Name: 1008.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月14日 星期日 13时36分54秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MAXN 100005 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; int N, a[MAXN], b[MAXN], ans[MAXN]; struct Node { int v, pos; bool operator < (const Node &a) const { return v < a.v; } } d[MAXN]; void gao(int n) { if (n < 0) return ; int pos; for (int i = 0; ; i ++) { if ((1 << i) - 1 >= d[n].v) { pos = (1 << i) - 1; break; } } int c = d[n].v ^ pos; gao(c - 1); for (int i = c; i <= n; i ++) { int x = d[i].v; ans[d[i].pos] = x ^ pos; } } void work() { for (int i = 0; i <= N; i ++) { scanf("%d", &a[i]); d[i].v = a[i], d[i].pos = i; } sort(d, d + N + 1); gao(N); LL c = 0; for (int i = 0; i <= N; i ++) { c += ans[i] ^ a[i]; } cout << c << endl; for (int i = 0; i <= N; i ++) { if (i) printf(" "); printf("%d", ans[i]); } printf("\n"); } int main() { while (scanf("%d", &N) != EOF) { work(); } return 0; } |
1009 矩阵快速幂，1005被大队坑了，一看，这就是水题啊。。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | /************************************************************************* > File Name: 1009.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月14日 星期日 13时12分38秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MOD 10000007 #define N 20 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; int n, m; LL a[N]; struct Matrix { int n, m; LL c[N][N]; Matrix() {} Matrix(LL a[][N], int n1, int m1) { for (int i = 0; i < N; i ++) { for (int j = 0; j < N; j ++) { c[i][j] = a[i][j]; } } n = n1, m = m1; } Matrix operator * (const Matrix &a) const { LL c1[N][N] = {}; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= a.m; j ++) { for (int k = 1; k <= m; k ++) { c1[i][j] += (c[i][k] * a.c[k][j]); c1[i][j] %= MOD; } } } return Matrix(c1, n, a.m); } }; Matrix Power(Matrix a, LL m) { LL c[N][N] = {}; for (int i = 1; i <= n + 2; i ++) { c[i][i] = 1; } Matrix ans = Matrix(c, n + 2, n + 2); while (m) { if (m & 1) ans = ans * a; a = a * a; m >>= 1; } return ans; } void work() { for (int i = 1; i <= n; i ++) { cin >> a[i]; } LL tmp[N][N] = {}; for (int i = 1; i <= n + 2; i ++) { if (i == 1) { tmp[i][1] = 1; } if (i == 2) { tmp[i][1] = 233; } if (i > 2) { tmp[i][1] = a[i - 2]; } } LL mul[N][N] = {}; mul[1][1] = 1; mul[2][1] = 3, mul[2][2] = 10; for (int i = 1; i <= n; i ++) { for (int j = 2; j <= i + 2; j ++) { mul[i + 2][j] = 1; } } Matrix now = Power(Matrix(mul, n + 2, n + 2), m); Matrix ans = now * Matrix(tmp, n + 2, 1); cout << ans.c[n + 2][1] << endl; } int main() { while (scanf("%d %d", &n, &m) != EOF) { work(); } return 0; } |
涛哥啊，再度的“再”写成“在”啦~