碎碎念
明天不上课,今晚有场 Codeforce
,想了想还是不打那一场,下午打个 VP 好了。
比赛
A.Password (0:04)
题意
从 个数字中选 个数字,这 个数字各用两次,组成一个四位数(允许前导 )。
求方案数。
分析
对于任意两个数字 ,,能组成的方案为 ,,,,, 共六种方案
方案总数
Code
1 2 3 4 5 6 7 8 9 10 11 12
| void solve() { int n; std::cin >> n; for(int i = 1; i <= n; i++) { int a; std::cin >> a; } int ans = 3 * (10 - n) * (9 - n); std::cout << ans << '\n'; }
|
B. Permutation Value (0:18)
题意
对于长度为 的一个排列,定义 为子段是排列的个数
构造一个排列,让它的 最小
分析
不难发现, 最小为 ,即 和 。
要满足条件,最简单的构造方式为
Code
1 2 3 4 5 6 7 8
| void solve() { int n; std::cin >> n; std::cout << 1 << ' ' << n << ' '; for(int i = 2; i < n; i++) std::cout << i << (i == n - 1 ? '\n' : ' '); }
|
C. Save the Magazines (0:27)
题意
长度为 的数组,权值为 ,权重为
循环 ,当 且 时,可以让 且
求
分析
对于 的情况,当 $a0 > a_101111ja_0 > a{1j}$ 时,进行操作
Code
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
| void solve() { int n; std::cin >> n; std::string s; std::cin >> s; std::vector<int> a(n); for(int i = 0; i < n; i++) std::cin >> a[i]; int ans = 0; int L = 0; while(L < n) { if(s[L] == '0') { int R = L + 1; while(R < n) { if(s[R] == '0') break; if(a[R] < a[L]) break; R++; } if(s[R] == '1') { s[L] = '1'; s[R] = '0'; } L = R; } else L++; } for(int i = 0; i < n; i++) if(s[i] == '1') ans += a[i]; std::cout << ans << '\n'; }
|
D. Problem with Random Tests (1:17)
题意
给一个纯随机的 字符串,从中选择两个子串,子串的价值 为将其视为二进制的值
求
分析
毫无疑问,一定会取整个字符串,因为他一定是所有串中最大的,且最高位为
考虑寻找一个字符串能够尽可能的增大 ,也就是从高位到低位,依次考虑这个位置的 能否通过或运算让它变成
考虑到该字符串为纯随机,每增长一位,备选的字符串数量平均减少一半。
Code
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
| void solve() { int n; std::cin >> n; std::string s; std::cin >> s; bool flag = false; int pos = -1; for(int i = 0; i < n; i++) { if(!flag && s[i] == '1') flag = true; if(flag && s[i] == '0') { pos = i; break; } } if(pos == -1) { flag = false; for(int i = 0; i < n; i++) { if(s[i] == '1') flag = true; if(flag == true) std::cout << s[i]; } if(!flag) std::cout << '0'; return; } std::vector<int> a; for(int i = 0; i < pos; i++) a.push_back(i); for(int i = 0; i < n - pos; i++) { if(s[pos + i] == '1') continue; bool flag = false; for(int x : a) if(s[x + i] == '1') flag = true; if(!flag) continue; std::vector<int> b; for(int x : a) if(s[x + i] == '1') b.push_back(x); a = b; } int K = a[0]; flag = false; for(int i = 0; i < pos; i++) { if(s[i] == '1') flag = true; if(flag) std::cout << s[i]; } for(int i = 0; i < n - pos; i++) std::cout << ((s[pos + i] == '1' || s[K + i] == '1') == 1 ? '1' : '0'); }
|
E. FTL (1:52)
题意
两种武器,各有一个伤害 与冷却时间 。
一个敌人,有血量 与护甲 。
单独使用武器,能造成伤害 。
同时使用两个武器,能造成伤害
求击败敌人的最短时间。
分析
预处理计算 为造成 伤害的最短时间
于是问题转化为无穷背包问题。
对于 的计算,枚举两种武器各使用多少次,并且最后一次为同时使用。
花费时间为 std::max(t1 * i, t2 * j)
造成伤害为 (i - 1) * (p1 - s) + (j - 1) * (p2 - s) + (p1 + p2 - s)
,某一个武器使用次数为 单独考虑。
Code
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
| void solve() { ll p1,p2,h,s; ll t1,t2; std::cin >> p1 >> t1; std::cin >> p2 >> t2; std::cin >> h >> s; for(ll i = 1; i <= h; i++) { f[i] = 1e18; F[i] = 1e18; } for(ll i = 0; i <= h; i++) for(ll j = 0; j <= h; j++) { ll P = 0; if(i > 0 && j > 0) P = (i - 1) * (p1 - s) + (j - 1) * (p2 - s) + (p1 + p2 - s); else if(i > 0) P = i * (p1 - s); else if(j > 0) P = j * (p2 - s); ll T = std::max(t1 * i, t2 * j); if(P > h) P = h; F[P] = std::min(F[P],T); } for(ll i = 0; i < h; i++) { for(ll j = 1; j <= h; j++) { ll k = std::min(h,i + j); f[k] = std::min(f[k], f[i] + F[j]); } } std::cout << f[h] << '\n'; }
|
总结
表现分:2187,橙名的水平。
总体表现还可以再优化一下。
题题意理解出问题了,以为 这种也是合法的。后面才反应过来必须从 开始
题差不多算读完题就会
题想了好久,开始有看到那句纯随机,禁止 ,但没想明白这有什么意义。
然后就往 , 自动机那方面去想,但又感觉难度不太对。
最后反应过来纯随机是为了什么。差点就开摆了。
题第一反应想到了 ,但没想到用 数组优化。
打算枚举 ,满足不存在 是 的整数倍。这样会优化一些选项(虽然还是 数量级)
然后想到了 预处理。
只能说练习少了,对题目没打 时那么敏感了。
晚上找部电影看看,黑客帝国怎么样。