A.签到题
#include <cstdio> double a[] = {0.4, 0.16, 0.063, 0.025, 0.010, 0.004}; int main() { int n; double m; scanf("%d", &n);; for(int i = 1;i <= n;i ++) { scanf("%lf", &m); printf("Case #%d: ", i); if(m >= 1) puts("Too Bright"); else if(m < 0.004) puts("Invisible"); else for(int j = 0;j < 6;j ++) { if(m >= a[j]) { printf("%d ", j + 1); break; } } } return 0; }
B.很明显的一个做法是我们把 n 个exchange 按 Ri 从小到大排序
对于每个exchage查询获得Ri的最少时间 tim = min( time[Ri] , time[max_money] )
再用 tim + Ti 尝试更新获得Vi需要的最少时间即可
最后ans = min( time[m], time[max_money] )
实现方法则是 sort + 线段树
另外一种奇特的实现方法把线段树换成了树状数组
我们可以看到查询是向后查询，修改是向前修改
而常见的树状数组多为向前查询 i -= lowbit(i)，向后修改 i += lowbit(i)...
所以那个我没有看懂...或者可以倒过来？
但是我们找到了另一种思路，类似于堆优化dijkstra的思路
我们对 n 个 exchange 同上述方法排序
小根堆中元素为 pair (s, time) ，time为关键字
time表示获得 s 的最小时间
显然会有每次堆顶元素中， s 严格单增
然后我们用 last_s < Ri <= now_s 的所有 exchange 尝试进行更新即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct node { int v, r, t; bool operator < (const node &a) const { return r < a.r; } }a[100010]; struct Node { int s; ll tim; bool operator < (const Node &a) const { return tim > a.tim; } }; int t, n, m; priority_queue <Node> q; int main() { ios::sync_with_stdio(false); ll ans; Node tmp; cin >> t; int i, st; for(int p = 1;p <= t;p ++) { ans = -1; cin >> n >> m; while(!q.empty()) q.pop(); for(i = 1;i <= n;i ++) cin >> a[i].v >> a[i].r >> a[i].t; sort(a + 1, a + n + 1); q.push((Node){1, 0}), st = 1; while(!q.empty()) { tmp = q.top(); q.pop(); if(tmp.s >= m) { ans = tmp.tim; break; } for(i = st;i <= n;i ++) { if(a[i].r > tmp.s) break; if(a[i].v <= tmp.s) continue; q.push((Node){a[i].v, tmp.tim + a[i].t}); } st = i; } printf("Case #%d: %lld ", p, ans); } return 0; }
C.签到题...看清题，大根堆和小根堆都合法，居然还有左大右小的 bst 也可以...
#include <iostream> using namespace std; int n, t, a[1111]; char s[][10] = {"Neither", "Heap", "BST", "Both"}; int is_greater_heap() { for(int i = 1;i * 2 <= n;i ++) if((i * 2 + 1 <= n && a[i * 2 + 1] < a[i]) || a[i * 2] < a[i]) return 0; return 1; } int is_less_heap() { for(int i = 1;i * 2 <= n;i ++) if((i * 2 + 1 <= n && a[i * 2 + 1] > a[i]) || a[i * 2] > a[i]) return 0; return 1; } int is_greater_bst() { for(int i = 1;i * 2 <= n;i ++) if((i * 2 + 1 <= n && a[i * 2 + 1] < a[i]) || a[i * 2] > a[i]) return 0; return 2; } int is_less_bst() { for(int i = 1;i * 2 <= n;i ++) if((i * 2 + 1 <= n && a[i * 2 + 1] > a[i]) || a[i * 2] < a[i]) return 0; return 2; } int main() { ios::sync_with_stdio(false); cin >> t; for(int i = 1;i <= t;i ++) { cin >> n; for(int j = 1;j <= n;j ++) cin >> a[j]; printf("Case #%d: %s ", i, s[is_greater_heap() | is_less_heap() | is_greater_bst() | is_less_bst()]); } return 0; }
D.
E.
F.你就数对各个字母
然后看到前一个的最后 'g' 可以被下一个再用一次就行了
#include <iostream> using namespace std; int main() { ios::sync_with_stdio(false); int t, g, o, d, m, n, r, i, k; string s; cin >> t, getline(cin, s); for(int p = 1;p <= t;p ++) { getline(cin, s); g = o = d = m = n = r = i = k = 0; for(int j = 0;j < s.size();j ++) { g += (s[j] == 'g'); o += (s[j] == 'o'); d += (s[j] == 'd'); m += (s[j] == 'm'); n += (s[j] == 'n'); r += (s[j] == 'r'); i += (s[j] == 'i'); k += (s[j] == ' '); } printf("Case #%d: %d ", p, min(min(min(g - 1, o / 3), min(d, m)), min(min(n / 2, r), min(i, k)))); } return 0; }
G.
H.
I.
J.
K.一个比较直观的东西是
min(A & (~B), A & B)至少能去掉 A 中一半的1对吧...所以很快就能变成0了
看到了比较适合本菜鸡的最良心的题解在这里
#include <cstdio> typedef unsigned long long uint; int t, n; uint a[1010]; uint min(uint x, uint y){ return x < y ? x : y; } uint dfs(uint k, int i) { if(i > n) return k; return min(dfs(k & a[i], i + 1), dfs(k & (~a[i]), i + 1)); } int main() { scanf("%d", &t); for(int p = 1;p <= t;p ++) { scanf("%d", &n); for(int i = 1;i <= n;i ++) scanf("%llu", &a[i]); if(n > 6) { printf("Case #%d: 0 ", p); continue; } printf("Case #%d: %llu ", p, min(dfs(a[1], 2), dfs(~a[1], 2))); } return 0; }