ZAFUACM - 7.10个人赛补题 A - C & E & H
A - 黑崎x护 - CodeForces 501B
题意
给出任意组数据,每组包含两个字符串,当 A 组的第二个字符串等于 B 组的第一个字符串时,将 A 组的第一个字符串转换成 B 组的第二个字符串,输出全部转换后还剩多少组数据,每组数据分别是什么
思路
二重循环,每修改一次就把被修改的那一组做个标记(我是把被修改的那组的第一个字符串换成‘ ’表示这一组一会儿不用输出了)
代码
|
B - 中野x乃 - CodeForces 519C
题意
分组每组三个人,必须是一个大佬 + 两个菜鸡 or 一个菜鸡 + 两个大佬,给出大佬菜鸡的人数,问最多能组多少队
思路
贪心,每次判断大佬和菜鸡人数多少,当前大佬多就选2大佬1菜鸡,否则相反
代码
|
C - x笠·阿克曼 - CodeForces 501C
题意
给出点的个数,每个点给出两个信息 d 和 s,d 表示度,s 表示与该点相邻的所有点的异或和,问这个图长啥样
思路
参考了某大佬的代码,先找到所有度为 1 的点,这些点的 s 就等于该点的邻接点,然后修改邻接点的 d 和 s,继续操作直到没有度为 1 的点
代码
|
E - x条悟 - CodeForces 405D
题意
给定 s = 1e6,给出若干个 x,要求 Σ(x - 1) = Σ(s - y)
,x y 不能重复,输出 y 的数量和 y 的值
思路
与 i
对应的就是 s - i + 1
,如果这个值不在 x 中,直接输出,如果在,就输出两个等距离的没被用过的
代码
|
H - 比企谷x幡 - CodeForces 710E
题意
一个人只会打一个字母,添加或删除一个字母耗时 x,复制已经写过的耗时 y,这个人一共要打 n 个字母,问最短耗时
思路
这题赛时耗了好久,开始摆烂,最后一分钟改了个炸裂的写法提交了,居!然!AC!了!
(炸裂的写法放在最后)
接下来是参考的大佬的思路:贪心,分奇偶讨论,具体看代码吧~
代码
|
已经不知道自己怎么会这么写的代码了…
using namespace std;
typedef long long LL;
int n, x, y;
vector<LL> cost;
int main()
{
cin >> n >> x >> y;
cost.push_back(0);
cost.push_back(x);
for (int i = 2; i <= N; i ++ )
{
if (i % 2 == 0)
{
cost.push_back(min(cost[i / 2] + y, cost[i - 1] + x));
}
else cost.push_back(cost[i - 1] + x);
}
bool flag = false;
int idx = 1;
while (flag || idx)
{
idx = 0;
flag = false;
for (int i = N - 1; i >= 1; i -- )
{
if (cost[i] > cost[i + 1] + x)
{
cost[i] = cost[i + 1] + x;
flag = true;
}
}
for (int i = 2; i <= N; i ++ )
{
if (i % 2 == 0)
{
if (cost[i] > cost[i / 2] + y)
{
cost[i] = cost[i / 2] + y;
flag = true;
}
if (cost[i] > cost[i - 1] + x)
{
cost[i] = cost[i - 1] + x;
flag = true;
}
}
else
{
if (cost[i] > cost[i - 1] + x)
{
cost[i] = cost[i - 1] + x;
flag = true;
}
}
}
}
cout << cost[n];
return 0;
}