比赛时，自己搞了两题，黄大队搞了两题，还有一题正在搞，没有搞出来，就先把自己搞得先贴出来。后面的题慢慢补上
1003
求多少个不同进制下，该数的表示形式只能有3,4,5,6组成。
唉，才开始没有看提示，所以判-1的情况判错了。。结果WA了两次。才开始设的中界限太低，TLE了一次。
思路是在小于某个数内直接判断，大于某个数时，很明显位数很小，所以可以利用状态压缩枚举3,4,5,6。来判断，这里设的中界为50000
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 126 127 128 129 130 131 132 133 134 135 136 137 | /************************************************************************* > File Name: 1003.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月12日 星期二 13时00分53秒 ************************************************************************/ #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> #include <vector> #include <cstring> using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 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;} int T, Cas = 1; LL n, f; bool Test(LL n, LL base) { while (n) { LL x = n % base; n /= base; if (x < 3 || x > 6) return false; } return true; } LL check(LL n) { LL ans = 0; for (int i = 2; i <= f; i ++) { if (Test(n, i)) ans ++; } return ans; } LL solve(int state, LL base) { LL ans = 0, d = 1; while (state) { int x = state % 5; LL y; state /= 5; if (x == 0) { y = 0; } else if (x == 1) { y = 3; } else if (x == 2) { y = 4; } else if (x == 3) { y = 5; } else { y = 6; } ans = ans + y * d; d = d * base; } return ans; } LL Judge(int state) { LL l = f, r = n + 1; while (r - l > 1) { LL mid = (l + r) / 2; LL tmp = solve(state, mid); if (tmp == n) return mid; if (tmp > n) { r = mid - 1; } else { l = mid + 1; } } if (solve(state, r) == n) return r; if (solve(state, l) == n) return l; return -1; } bool is(int state) { vector <int> tmp; tmp.clear(); while (state) { tmp.pb(state % 5); state /= 5; } for (int i = 0; i < tmp.size(); i ++) { if (tmp[i] == 0) return false; } return true; } LL gao(LL n) { LL ans = 0; for (int i = 0; i < 625; i ++) { if (!is(i)) continue; LL x = Judge(i); if (x > f) { ans ++; } } return ans; } void work() { printf("Case #%d: ", Cas ++); cin >> n; if (n == 1 || n == 2) { printf("0\n"); return ; } if (n == 3 || n == 4 || n == 5 || n == 6) { printf("-1\n"); return ; } f = 50000; if (n <= f) { cout << check(n) << endl; } else { cout << (check(n) + gao(n)) << endl; } } int main() { scanf("%d", &T); while (T --) { work(); } return 0; } |
1007
水题。不过还是敲的太保险了。
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: 1007.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月12日 星期二 12时15分42秒 ************************************************************************/ #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <set> #include <iostream> using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 #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;} int T, Cas = 1, K, C, W, Q, N, M, X, Y, A, B, bx[MAXN], by[MAXN]; map <pair <int, int> , int> Map; map <int, int> Mx, My; void Swap(int &x, int &y) { int tmp = x; x = y; y = tmp; } void work() { printf("Case #%d:\n", Cas ++); Map.clear(), Mx.clear(), My.clear(); scanf("%d %d %d", &N, &M, &K); for (int i = 1; i <= K; i ++) { bx[i] = i, by[i] = i; } for (int i = 1; i <= K; i ++) { scanf("%d %d %d", &X, &Y, &C); X ++, Y ++; if (Mx.find(X) == Mx.end()) { Mx.insert(mp(X, Mx.size() + 1)); } if (My.find(Y) == My.end()) { My.insert(mp(Y, My.size() + 1)); } Map.insert(mp(mp(Mx[X], My[Y]), C)); } scanf("%d", &W); for (int i = 1; i <= W; i ++) { scanf("%d %d %d", &Q, &A, &B); A ++, B ++; if (Q == 1) { if (Mx.find(A) == Mx.end() || Mx.find(B) == Mx.end()) { continue; } int a = Mx[A], b = Mx[B]; Swap(bx[a], bx[b]); } else if (Q == 2) { if (My.find(A) == My.end() || My.find(B) == My.end()) { continue; } int a = My[A], b = My[B]; Swap(by[a], by[b]); } else { if (Mx.find(A) == Mx.end() || My.find(B) == My.end()) { printf("0\n"); continue; } int a = bx[Mx[A]], b = by[My[B]]; pair <int, int> Point = mp(a, b); if (Map.find(Point) == Map.end()) { printf("0\n"); } else { printf("%d\n", Map[Point]); } } } } int main() { //freopen("in", "r", stdin); scanf("%d", &T); while (T --) { work(); } return 0; } |