碎碎念
明天不上课，今晚有场 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，橙名的水平。
总体表现还可以再优化一下。
题题意理解出问题了，以为 这种也是合法的。后面才反应过来必须从 开始
题差不多算读完题就会
题想了好久，开始有看到那句纯随机，禁止 ，但没想明白这有什么意义。
然后就往 ， 自动机那方面去想，但又感觉难度不太对。
最后反应过来纯随机是为了什么。差点就开摆了。
题第一反应想到了 ，但没想到用 数组优化。
打算枚举 ，满足不存在 是 的整数倍。这样会优化一些选项（虽然还是 数量级）
然后想到了 预处理。
只能说练习少了，对题目没打 时那么敏感了。
晚上找部电影看看，黑客帝国怎么样。
