UVALive7897 Number Theory Problem （找规律签到）
思路：
8的幂次都是可以的，因为an-1一定能分解成a-1乘上一个多项式。
看不出来也没关系，打表就发现每三个数有一个7的倍数。
代码：
#include <cstdio> using namespace std; int main() { int T, kase = 1; scanf("%d", &T); while (T--) { int N; scanf("%d", &N); printf("Case #%d: %d ", kase++, N/3); } return 0; }
UVALive7899 Mr. Panda and Strips （暴搜+尺取+剪枝）
思路：
我也不知道这是什么做法，神棍剪枝吧-。=
尺取大法好（超大声）
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e3 + 5; const int MAX_C = 1e5 + 5; int N; int C[MAX_N], len[MAX_N]; int ans; bool vis[MAX_C]; inline void reset() { for (int i = 1; i <= N; i++) vis[C[i]] = false; } void init() { cin >> N; for (int i = 1; i <= N; i++) scanf("%d", C+i); C[N+1] = 0; reset(); } inline int jump(int pos, int limit) { int l = pos, r = pos, res = -1; while (r <= N) { while (!vis[C[r]] && r <= N) vis[C[r++]] = true; if (len[l] < limit) break; res = max(res, r-l); while ( vis[C[r]] && l <= r) vis[C[l++]] = false; } for (int i = l; i < r; i++) vis[C[i]] = false; return res; } int main() { int T, kase = 1; cin >> T; while (T--) { init(); for (int i = 1; i <= N; i++, reset()) { len[i] = 0; for (int j = i; j <= N && !vis[C[j]]; j++) len[i]++, vis[C[j]] = true; } len[N+1] = 0; for (int i = N; i >= 1; i--) len[i] = max(len[i], len[i+1]); ans = len[1]; for (int i = 1; i <= N; i++, reset()) for (int j = i; j <= N && !vis[C[j]]; j++) { vis[C[j]] = true; if (ans >= j-i+1 + len[j]) continue; int res = jump(j+1, ans-(j-i+1)); ans = max(ans, j-i+1 + res); } reset(); printf("Case #%d: %d ", kase++, ans); } return 0; } /* 3 8 3 1 2 1 6 1 2 5 3 1 2 3 3 1 1 1 */
UVALive7900 Ice Cream Tower （二分+贪心）
假思路：
贪心地取冰淇淋球，尽可能地早点做出Tower，不能放在之前的冰淇淋上的球当作新的底座。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAX_N = 3e5 + 5; struct QNode{ ll val; int len; QNode(ll v = 0, int l = 0) : val(v), len(l) {} }; ll B[MAX_N]; queue <QNode> Q; int main() { int T, kase = 1; cin >> T; while (T--) { int N, K, ans = 0; cin >> N >> K; for (int i = 1; i <= N; i++) scanf("%lld", B+i); sort(B+1, B+1+N); for (int i = N; i >= 1; i--) { if (Q.empty()) { Q.push(QNode(B[i], 1)); continue; } QNode cur = Q.front(); if (cur.val/2 >= B[i]) { Q.pop(); if (cur.len+1 == K) ans++; else Q.push(QNode(B[i], cur.len+1)); } else { Q.push(QNode(B[i], 1)); } } while (!Q.empty()) Q.pop(); printf("Case #%d: %d ", kase++, ans); } return 0; } /* 3 4 2 1 2 3 4 6 3 1 1 2 2 4 4 6 3 1 1 2 2 3 4 */
自我hack【精通】。。codeforces gym上的数据比较强，上面的代码就不能过了。
1 4 2 2 3 5 10
思路：
二分答案，用上面的贪心法验证。。。。O(Nlog(N/K))
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAX_N = 3e5 + 5; struct Node{ ll val, len; Node(ll v = 0, ll l = 0) : val(v), len(l) {} }; int N, K; ll B[MAX_N]; queue <Node> Q; bool solve(int ans){ while (!Q.empty()) Q.pop(); if (K == 1) return true; for (int i = 1; i <= ans; i++) Q.push(Node(B[i], 1)); for (int i = ans+1; i <= N; i++) { if (Q.empty()) break; Node cur = Q.front(); if (B[i]/2 >= cur.val) { Q.pop(); if (cur.len == K-1) continue; Q.push(Node(B[i], cur.len+1)); } } return Q.empty(); } int main() { int T; cin >> T; for (int kase = 1; kase <= T; kase++) { cin >> N >> K; for (int i = 1; i <= N; i++) scanf("%lld", B+i); sort(B+1, B+1+N); int ansl = 0, ansr = N, ans = 0; while (ansl <= ansr) { int mid = (ansl + ansr) >> 1; if (solve(mid)) { ans = max(ans, mid); ansl = mid+1; } else { ansr = mid-1; } } printf("Case #%d: %d ", kase, ans); } return 0; } /* 3 4 2 1 2 3 4 6 3 1 1 2 2 4 4 6 3 1 1 2 2 3 4 */
UVALive7901 Bet （数学+贪心+高精度除法（long double））
思路：
小学数学题-。=
贪心地选性价比高的队伍，能选多个队伍的条件是这些队伍的A/(A+B)的和小于1。。。。这个精度啊。。比赛的时候WA来WA去就是没想到，Dilthey瞄了一眼题解发现是高精度除法，long double够用。。。换上long double就AC了。。在现场的话，不知道这个高精度估计要悔恨终身了。
#include <bits/stdc++.h> using namespace std; const int MAX_N = 100 + 5; const long double money = 1e3 + 5; const long double eps = 1e-16; long double A[MAX_N], B[MAX_N], C[MAX_N]; int main() { int T; cin >> T; for (int kase = 1; kase <= T; kase++) { int N; cin >> N; for (int i = 1; i <= N; i++) { char x; cin >> A[i] >> x >> B[i]; C[i] = (long double)A[i] / (A[i] + B[i]); } sort(C+1, C+1+N); int cnt = 0; long double sum = 0; while (cnt+1 <= N && sum + C[cnt+1]*money < money-eps) { sum += C[++cnt]*money; } printf("Case #%d: %d ", kase, cnt); } return 0; } /* 3 2 5:3 2:7 2 1:1 1:1.01 3 1:1.1 1:0.2 1.5:1.7 */ /* 10 12 1:10 1:10 1:10 1:10 1:10 1:10 1:10 1:10 1:10 1:10 1:10 1:10 12 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 1:9.9 12 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 1:10.1 */
UVALive7908 Great Cells （数学思维+快速幂）
思路：Dilthey的博客
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007; ll fpow(ll a, ll p) { ll ans = 1; while (p) { if (p&1) ans *= a, ans %= MOD; a *= a, a %= MOD; p >>= 1; } return ans; } int main() { int T; cin >> T; for (int kase = 1; kase <= T; kase++) { ll N, M, K; cin >> N >> M >> K; ll ans = 0; for (ll i = 2; i <= K; i++) ans += fpow(i-1, N-1+M-1), ans %= MOD; ans *= N*M, ans %= MOD; ans *= fpow(K, (N-1)*(M-1)), ans %= MOD; ans += fpow(K, N*M), ans %= MOD; printf("Case #%d: ", kase); cout << ans << endl; } return 0; } /* 3 2 2 2 2 3 2 3 4 5 */
UVALive7908 World Cup （3进制状压+枚举）
思路：
把所有的可能答案都预处理出来，有36个，直接枚举时间复杂度为O(4*36T)。
预处理的时候把比赛结果的可能性：胜负，平局，负胜压成六位三进制数即可。
#include <bits/stdc++.h> using namespace std; const int l[6] = {1, 1, 1, 2, 2, 3}; const int r[6] = {2, 3, 4, 3, 4, 4}; const int len = 729; int pow(int a, int p) { int ans = 1; while (p) { if (p&1) ans *= a; a *= a; p >>= 1; } return ans; } int A[5]; int res[len+1][5]; void init() { memset(res, 0, sizeof res); for (int i = 0; i < len; i++) { int tmp = i;// mod 3 = 0胜，1平，2败。 for (int j = 0; j < 6; j++) { if (tmp % 3 == 0) { res[i][l[j]] += 3; } else if (tmp % 3 == 1) { res[i][l[j]]++; res[i][r[j]]++; } else if (tmp % 3 == 2) { res[i][r[j]] += 3; } tmp /= 3; } } } int main() { init(); int T; cin >> T; for (int kase = 1; kase <= T; kase++) { for (int i = 1; i <= 4; i++) scanf("%d", A+i); int valid = 0; for (int i = 0; i < len; i++) { int j; for (j = 1; j <= 4; j++) if (A[j] != res[i][j]) break; if (j == 5) { valid++; } } printf("Case #%d: ", kase); if (!valid) puts("Wrong Scoreboard"); else { sort(A, A+4); if (valid > 1) puts("No"); else puts("Yes"); } } return 0; } /* 3 9 6 3 0 6 6 6 0 10 6 3 0 */