最近实验室装修搬东西有点忙,就一直拖到现在。。。
A. Garbage Classification
solved at 00:14
签到题,垃圾分类 ## B. Shorten IPv6 Address
solved at 00:48(+1)
给你一个二进制表示的ipv6地址,求最短表示
模拟即可,不用考虑最短且字典序最小怎么做,枚举出来就行了
D. Move
solved at 03:46(+8)
有K个箱子和n个物品,物品大小为\(v_i\),箱子容量都一样,求最小容量使得物品能按照如下方法装到箱子里:
首先找能装到当前箱子里的最大物品,装到箱子里,重复这一过程直到箱子装不下任何东西为止,然后装下一个箱子(\(1<=K,n,v_i<=1000\))
看上去像个二分,但是就是不能二分。。。
n = 15, K = 5
39 39 39 39 39 60 60 60 60 60 100 100 100 100 100
199可以装下,但200和201都不行。。。
考虑下界肯定是\(max(max(v_i), ceil(sum[n]/k))\)
然后往上一个个直接check就好了,最多1000次肯定可以了(事实上数据很难造有人说100次够了)
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
| #include <bits/stdc++.h> using namespace std; const int N = 1010; int T, n, a[N], K, sum[N], cas, mx; multiset<int> s; bool check(int vol) { static multiset<int> s; s = ::s; int tot = 0, tmp; while(!s.empty()) { tmp = 0; while(tmp < vol) { auto p = s.upper_bound(vol - tmp); if(p == s.begin()) break; --p; tmp += *p; s.erase(p); } if(++tot > K) return false; } return true; } int main() { scanf("%d", &T); while(T--) { s.clear(); mx = -1e9; scanf("%d%d", &n, &K); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); s.insert(a[i]); sum[i] = sum[i - 1] + a[i]; mx = max(mx, a[i]); } int l = max(mx, 1 + (sum[n] - 1) / K), r = sum[n], ans; for(int i = l; i <= r; ++i) { if(check(i)) { ans = i; break; } } printf("Case #%d: %d\n", ++cas, ans); } return 0; }
|
E. Androgynos
upsolved
给你\(n\),问你存不存在\(n\)个点的自补图,存在则输出任意一个并输出其对应关系\((1<=n<=2000)\)
首先肯定\(n\%4\le1\)才会有解
考虑\(n=4\),很容易手推出来
然后考虑\(n=4k\), 将\(n\)个点分为4堆,每堆\(k\)个,有两堆是完全图,剩下两个全是孤立点,然后把这4堆看出4个点以\(n=4\)的方法连接就好了(因为团的补图是独立集)
如果\(n=4k+1\),直接把剩下那个点向团连边(事实上任意两堆都可以)
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
| #include <bits/stdc++.h> using namespace std;
const int N = 2010;
int G[N][N], T, n, cas, ans[N];
int main() { scanf("%d", &T); while(T--) { scanf("%d", &n); printf("Case #%d: ", ++cas); if(n % 4 > 1) { puts("No"); continue; } puts("Yes"); int m = n / 4; memset(G, 0, sizeof(G)); for(int i = 0; i < m; ++i) { for(int j = 0; j < m; ++j) { G[i][j] = 1; G[j][i] = 1; G[m + i][m + j] = 1; G[m + j][m + i] = 1; G[i][2 * m + j] = 1; G[2 * m + j][i] = 1; G[m + i][3 * m + j] = 1; G[3 * m + j][m + i] = 1; G[2 * m + i][3 * m + j] = 1; G[3 * m + j][2 * m + i] = 1; } } if(n % 4 == 1) { for(int i = 0; i < m; ++i) { G[i][n - 1] = G[n - 1][i] = 1; G[m + i][n - 1] = G[n - 1][m + i] = 1; } } for(int i = 0; i < 2 * m; ++i) G[i][i] = 0, ans[i] = i + 2 * m; for(int i = 2 * m; i < 3 * m; ++i) G[i][i] = 0, ans[i] = i - m; for(int i = 3 * m; i < 4 * m; ++i) G[i][i] = 0, ans[i] = i - 3 * m; if(n % 4 == 1) G[n - 1][n - 1] = 0, ans[n - 1] = n - 1; for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) printf("%d", G[i][j]); puts(""); } for(int i = 0; i < n; ++i) printf("%d%c", ans[i] + 1, " \n"[i == n - 1]); } return 0; }
|
G. Is Today Friday?
upsolved
你知道A-J表示0-9,但是不知道对应关系,你有\(n\)个日期,每个都是星期五,求字典序最小的对应关系
搜索就完事了,注意要去重,否则会T
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
| #include <bits/stdc++.h> using namespace std;
int ans[12], ok[12]; unordered_set<string> s; char ss[15]; int T, n, cas, found, stat; int ma[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool isfriday(int y, int m, int d) { return (1461 * (y + 4800 + (m - 14) / 12) / 4 + 367 * (m - 2 - (m - 14) / 12 * 12) / 12 - 3 * ((y + 4900 + (m - 14) / 12) / 100) / 4 + d - 32075) % 7 == 4; }
inline bool is29(int y) { return (!(y % 4) && (y % 100)) || !(y % 400); }
inline bool isvalid(int y, int m, int d) { if(y < 1600) return false; if(m < 1 || m > 12) return false; if(d < 1) return false; return d <= ma[m] + (m == 2 && is29(y)); }
bool check() { for(auto si: s) { int y = 1000 * ans[(si[0] - 'A')] + 100 * ans[(si[1] - 'A')] + 10 * ans[(si[2] - 'A')] + ans[(si[3] - 'A')]; int m = 10 * ans[(si[5] - 'A')] + ans[(si[6] - 'A')]; int d = 10 * ans[(si[8] - 'A')] + ans[(si[9] - 'A')]; if(!isvalid(y, m, d) || !isfriday(y, m, d)) return false; } return true; }
int main() { scanf("%d", &T); while(T--) { scanf("%d", &n); found = false; s.clear(); for(int i = 0; i < 10; ++i) ans[i] = i, ok[i] = (1 << 10) - 1; for(int i = 1; i <= n; ++i) { scanf("%s", ss); s.insert(ss); ok[ss[0] - 'A'] &= 0x3FE; ok[ss[5] - 'A'] &= 0x3; ok[ss[8] - 'A'] &= 0xF; } printf("Case #%d: ", ++cas); do { bool flag = true; for(int i = 0; i < 10; ++i) { if(!((ok[i] >> ans[i]) & 1)) { flag = false; break; } } if(!flag) continue; if(check()) { found = 1; for(int i = 0; i < 10; ++i) printf("%d", ans[i]); puts(""); break; } } while(next_permutation(ans, ans + 10)); if(!found) puts("Impossible"); } return 0; }
|
J. Upgrading Technology
solved at 02:17(+4)
本来让队友做的,不知道他在做什么。。。我怎么一发就过了。。。
点技能树,\(n\)个技能,每个\(m\)级,将技能\(i\)从\(j-1\)级点到\(j\)级需要代价\(c[i][j]\),所有技能都升到\(j\)级之后会获得\(d[j]\)的收益,初始都是\(0\),代价和收益都有正有负,求最大的钱币数\((1<=n,m<=1000)\)
枚举最低技能等级,再枚举哪个技能正好是这个等级,\(O(1)\)得出答案,总复杂度\(O(nm)\),需要预处理几个数组
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
| #include <bits/stdc++.h> using namespace std;
const int N = 1010; const long long inf = 1e18;
long long mx[N][N], c[N][N], d[N], pre[N][N], suf[N][N], ans, sum[N][N], sd[N]; int T, n, m, cas;
int main() { scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { scanf("%lld", &c[i][j]); c[i][j] = -c[i][j]; sum[i][j] = sum[i][j - 1] + c[i][j]; } } for(int j = 1; j <= m; ++j) { scanf("%lld", &d[j]); sd[j] = sd[j - 1] + d[j]; } for(int i = 1; i <= n; ++i) { mx[i][m + 1] = -inf; for(int j = m; ~j; --j) { mx[i][j] = max(mx[i][j + 1], sum[i][j]); } } for(int j = 0; j <= m; ++j) { pre[0][j] = suf[n + 1][j] = 0; for(int i = 1; i <= n; ++i) pre[i][j] = pre[i - 1][j] + mx[i][j]; for(int i = n; i; --i) suf[i][j] = suf[i + 1][j] + mx[i][j]; } ans = 0; for(int low = 0; low <= m; ++low) { for(int i = 1; i <= n; ++i) ans = max(ans, sd[low] + pre[i - 1][low] + suf[i + 1][low] + sum[i][low]); } printf("Case #%d: %lld\n", ++cas, ans); } return 0; }
|