本场链接:[Codeforces Round #666 (Div. 2)]
闲话
早上起来打的,CD整体不是那么难,就是稍微有点卡思维.
A. Juggling Letters
题目大意:给定(n)个不定长度的字符串,并且可以把里面的元素任意交换位置,问是否可以让所有字符串都相等.注意先后长度可以变换.只需要输出是否可行,不需要输出具体方案.
数据范围:(1 leq n leq 1000)
思路
显然由于任意交换的条件过于强大,所以直接对所有的字符统计,并check字符的数量是否都是(n)的倍数,如果有一个不是就说明无法分配,即不能使所有相同.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;cin >> T;
while(T--)
{
int n;cin >> n;
map<char,int> cnt;
for(int i = 1;i <= n;++i)
{
string s;cin >> s;
int len = s.size();
for(int j = 0;j < len;++j)
++cnt[s[j]];
}
int ok = 1;
for(char a = 'a';a <= 'z';++a)
if(cnt[a] % n)
{
ok = 0;
break;
}
if(ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
B. Power Sequence
题目大意:给定给一个长度为(n)的序列(a),以下标0为开始.定义一个序列是牛逼的,当且仅当序列(a)里的元素满足(a_i=c^i).其中(c)为某个任意整数,只要有一个(c)满足即可(即c不是指定的,存在一个c满足即可).现在可以任意重排整个序列,并用(1)的代价使序列里任意一个元素的值增加一或减少一,问把整个序列变成一个牛逼的序列最少需要多少的代价.
数据范围:
(1 leq n leq 10^5)
(1 leq a_i leq 10^9)
思路
第一步题目给定了一个重排的操作,显然因为一个牛逼的序列一定是一个上升的序列(除了(c=1)的特殊情况,其他的都是严格上升的),所以一个比较直接的想法就是把整个序列按升序排序,再枚举所有可能的(c),算出每个值的消耗,因为排序之后比不排序一定更好,所以算出来的结果一定正确.那么这里有一个问题:(c)的取值范围是多少.
从直觉上来说,这个题目的数据范围相当的大,(c)的取值也一定和(a)序列的和有关,而且可以猜到(c)的取值范围是很有限的,而这个和可以到达(10^{14}).不过一个牛逼序列,同时是一个等比数列,在(c)增大的过程中整个牛逼序列的和会上升的非常快,因此上界会很快的达到.那么对于单个的(c)的上界,不妨就按(1e18)作为(INF),之后因为是一个等比数列,一共有(n)项,那么(c)的上界设置成是(INF^{frac{1}{n}}),因为整个牛逼序列的和不能过大,这样就可以保证了,当然这个上界并不准确,而且运算过程中可能会爆掉(ll).所以在具体写的时候,是一步一步的计算出当前的和,如果已经超过了答案,那么就直接过掉,避免溢出.其次可以猜测这个复杂度是比较正常的,因为(c)并不会有多少个取值.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
const ll INF = 1e18;
int a[N];
int main()
{
int n;scanf("%d",&n);ll res = INF,s = 0;
for(int i = 1;i <= n;++i) scanf("%d",&a[i]),s += a[i];
sort(a + 1,a + 1 + n);
int limit = pow(INF,1.0/n);
for(ll c = 1;c <= limit;++c)
{
ll loc = llabs(1 - a[1]),k = 1;
for(int i = 2;i <= n;++i)
{
k *= c;loc += llabs(a[i] - k);
if(loc > res) break;
}
res = min(res,loc);
}
printf("%lld",res);
return 0;
}
C. Multiples of Length
题目大意:给定一个长度为(n)的序列.给定一种操作:每次选择一个长度为(len)的区间,并且可以让整个区间里的每一个数都减掉一个(len)的倍数(注意并不是所有的都减掉一个相同的倍数,而是可以不同的,并且可以减0倍).问是否可以在恰好三次操作之后把整个序列里的所有的数变成(0).注意是恰好三次,即使当前序列已经是(0)序列了,但是还是要恰好三次操作.
数据范围:
(1 leq n leq 10^5)
(-10^9 leq a_i leq 10^5)
思路
由于操作数只有(3)次,因此如何快速的把所有的值全部消掉就成了这个题目的关键目标.首先一个简单的想法就是看能不能直接把整个序列,即按(n)的倍数全部消掉.显然这个序列一开始肯定不会是恰好都有(n)的倍数的,所以先预支一次操作尝试把所有的元素变成(n)的倍数,那么变成多少呢.一个比较好的构造方式是把所有的元素变成(n * a_i)那么对每个数来说,需要增加一个(a_i * (n - 1)).想到这里,先把第一步操作具体出来:对([1,n-1])的每个元素,增加自己的(n-1)倍,因为你想要增加(n-1)倍,那么长度只能是(n-1),不能直接对整个(n)长度的序列增加,这一点只能退而求其次.
那么现在还有两次操作,([1,n-1])的所有元素现在是(n*a_i),距离这个题目的终极目标:所有元素都要有(n)的公共因数,还差一个(a_n),那么由于可以让增加的倍数是(0),就可以操作([2,n])这个序列,并且不动前面的所有的元素,只动最后一个(a_n)把他如法炮制即可在两次操作之后得到一个新序列,其中每个元素都是之前的元素的(n)倍.那么最后一次操作,直接把所有的元素减掉自己的(a_i)倍,就能让所有的元素都是(0)了.恰好在三步完成.
不过分析到这里,可以想到一个边界问题:当(n=1)的时候,显然是没有所谓的第一个元素和最后一个元素的,这种情况只能特判掉.需要特别注意一下.
代码
我的代码跟上面的思路实际上有一点出入,不过影响不大.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e5+7;
int a[N];
signed main()
{
int n;scanf("%lld",&n);
if(n == 1)
{
scanf("%lld",&a[1]);
printf("1 1
%lld
",-a[1]);
printf("1 1
0
");
printf("1 1
0
");
return 0;
}
for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
printf("1 %lld
",n-1);
for(int i = 1;i < n;++i) printf("%lld ",a[i] * (n - 1)),a[i] += a[i] * (n - 1);
printf("
%lld %lld
%lld",n,n,a[n] * (n - 1)),a[n] += (n - 1) * a[n];
printf("
1 %lld
",n);
for(int i = 1;i <= n;++i) printf("%lld ",-a[i]);
return 0;
}
D. Stoned Game
题目大意:有两个人在玩博弈游戏,一共有(n)堆石子,每堆有(a_i)个石子.每次可以从任意一堆里选出一个石子,但是不能从对手上一轮选过的堆里选石子,首先不能操作的人输.先手TL,后手H.输出胜者.
数据范围:
(1 leq n leq 100)
(1 leq a_i leq 100)
思路
拿到这个题,有一个很想当然的想法:既然不能选对手取过的堆,那么对先手的人来说,拿最多石子的堆显然是最好的,因为选择一个最多的石碓,显然可以比对手更晚的选择一个别的石碓,而选择一个更少的会使局面不那么有利.那么对后手来说也是如此想当然的吗.可以推理猜测一下,假设说后手并不选择整个石子里面第二大的石碓,那么选择一个较小的石碓会让局面更不利,因为先手的人总是占着一个较大的石碓,他总是能占优势,而快速的让整个局面跳到只有两堆石子或者只有一堆石子的时候都是不利的,因此后手也只能是选当前最大的石碓.
经过这样的一个感性分析,可以确定两个人的策略实际上都是选整个局面里面最大的堆,那么继续往下可以发现整个局面的结果是唯一确定的,只需要维护一个(pq),并且记录上一轮的人选择的是哪一堆就可以模拟整个对局了.由于整个序列长度以及个数都非常的小,所以复杂度就可以乱搞搞.这个模拟做法也是跑得飞快.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int a[N];
typedef pair<int,int> pii;
#define x first
#define y second
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
priority_queue<pii> pq;
for(int i = 1;i <= n;++i) scanf("%d",&a[i]),pq.push({a[i],i});
int cur = 1,last = -1;
while(!pq.empty())
{
pii _t = pq.top(),_t2;pq.pop();
int u = _t.x,p = _t.y;
if(p == last)
{
if(pq.empty()) break;
_t2 = pq.top();pq.pop();pq.push(_t);
u = _t2.x;p = _t2.y;
}
if(u == 0) break;
cur ^= 1;pq.push({--u,p});last = p;
}
if(cur) puts("HL");
else puts("T");
}
return 0;
}
E. Monster Invaders
题目大意:有个(n)列敌人,每一列有(a_i)个小兵和(1)个boss,血量分别为1和2.手上有三种武器,第一种对一个当前列的第一个敌人造成一点伤害,第二种对一列的敌人造成伤害,第三种直接消灭第一个敌人.三种武器的代价分别是(r_1,r_2,r_3).当你通过第一种或者第二种武器对boss造成伤害并且没有直接消灭它的时候,你会被强制往相邻的格子移动.移动的代价是(d).不允许在移动的同时射击,每秒只能选择一个武器射击.求消灭所有敌人的最小花费.
数据范围:
(1 leq n leq 10^6)
(1 leq d leq 10^9)
(1 leq r1 leq r2 leq r3 leq 10^9)
思路
首先注意到数据范围比较大,还会爆int,先留个心眼.在模拟完样例之后可以抽象这个题目的具体流程,发现他就是一个决策的过程,在某个位置,当前这一列的boss的血量和相应的决策会产生什么结果,自然可以尝试(dp)求解.由于关键的信息就是当前在哪一列以及当前列的boss的血量,先就直接把这两个信息放到数组里尝试一下能不能做.
状态:(f[i][j])表示当前人在第(i)列,且当前列的boss血量为(j).不难想到说这个状态划分是只和上一位的状态有关的,也就是说最多有两列相邻的boss是存活的,因为再多的时候不如当时就解决掉.
入口:(f[1][0] = a[1] * r_1,f[1][1] = min((a[1] + 1) * r_1,r_2))要注意的是第二种武器是同时会对boss造成伤害的.
那么这里就有一个问题了,这个状态定义的是人就在第(i)列,那么从前一个位置转移过来的时候,(f[i - 1][1])应该要表示的是一个(i-1)列被攻击了的状态,但是如果(i-1)列被攻击了,那么按照定义来说他是要被强制移动的,但是如果把这个(d)的花费加进来又有一个问题,因为你根本不知道这个位置是到了左边还是到了右边,因此一个解决办法就是直接把他挪进转移的表达式里再进行计算.
具体一点来说就是对于(f[i][0])的计算里,如果要用到(f[i-1][1])那么就额外的加一个(d)在他后面,同时在算(f[i][1])的时候并不把(d)给他直接加上,因为那样在严格的定义之下,他的位置是发生了变化的.我看别的题解并没有对这一点进行说明,补充一点.
转移:
-
先定义两种最基本的操作:第一种是直接消灭整列的敌人,这个可以通过(a[i]*r_1+r_3)做到,其次是把boss打到一点血,这个时候实际上有两种情况存在,要么就用第二种武器直接打到boss,要么就先用第一种武器(a[i])次再加一次射击boss:(min((a[i]+1)*r_1,r_2)).
-
对于(f[i][0])来说
-
从前面一个全空的状态转移到一个全空的状态,直接消灭所有敌人
(f[i][0] = f[i - 1][0] + d + (a[i] + 1) * r_1 + r_3)
-
从(i-1)剩余一个1血量的状态转移而来,首先要给(f[i-1][1])加一个d,表示这个状态被强制移动到了(i)位置,再对这个(i)列的boss打成残血,那么这个时候就有两种做法,也就是之前说的第二种基本操作,注意在这次操作之后会被强制移动,选择移动到(i-1)再次增加一个(d),由于(i-1)的boss没死,给他补一枪(r_1)再回到(i)又要增加一次(d)的移动代价,现在(i)列的boss也没死需要再补一枪,于是再补一个(r_1)给这个地方.那么总的方程也就出来了.
(f[i][0] = f[i - 1][1] + d + r_1 + d + min((a[i] + 1) * r_1,r_2) + d + r_1)
-
同样是从前面过来,只不过直接先消灭所有(i)列的敌人,那么前面的部分保持不变,还是(f[i-1][1]+d)之后来到了第(i)列,支付第一种基本操作的代价把(i)列清空,再走到(i-1)补一枪(r_1)最后再回到(i).
(f[i][0] = f[i - 1][1] + d + r_1 + d + a[i] * r_1 + r_3 + d)
-
-
对于(f[i][1])来说
-
一定要抠定义,不能随便增加条件,定义的就是人在(i)位置,那么就不能随便变换.第一种是前面的一列就是空的,那么从前面一列走过来就没什么负担,不会出现多列都没清空的情况,这部分走过来的代价就是(f[i-1][0]+d)那么还需要把第(i)列的boss打残,需要支付第二个基本操作的代价.注意这里按题目意思来说是会被强制移动的,但是从定义出发你根本不知道要被移动到哪里,所以这里状态计算的时候实际上没有把这个强制移动的代价算进去,而是在前面说的,计算别的状态的时候再把他补充进去考虑.
(f[i][1] = f[i - 1][0] + min((a[i] + 1) * r_1,r_2) + d)
-
那么另外一种就是先走过来,把第(i)列的射残,走到(i-1)列补一枪,再走回(i)列.跟前面是类似的可以比对过来.
(f[i][1] = f[i - 1][1] + d + r_1 + d + min((a[i] + 1) * r_1,r_2) + d)
-
出口:
其中一个比较简单就是(f[n][0])另外一种应该是从(f[n-1][1])转移而来的,由于末尾一位移动的时候不能向后移动了,因此直接用(f[n][0])不能覆盖所有情况,还需要额外算一下另外一种(f[n - 1][1] + d + r_1 + a[n] * r_1 + r_3)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7;
ll f[N][2],a[N];
int main()
{
ll n,r1,r2,r3,d;cin >> n >> r1 >> r2 >> r3 >> d;
for(int i = 1;i <= n;++i) cin >> a[i];
f[1][0] = a[1] * r1 + r3,f[1][1] = min((a[1] + 1) * r1,r2);
for(int i = 2;i <= n;++i)
{
ll op1 = a[i] * r1 + r3;
ll op2 = min((a[i] + 1) * r1,r2);
f[i][0] = f[i - 1][0] + op1 + d;
f[i][0] = min(f[i][0],f[i - 1][1] + 3 * d + 2 * r1 + op2);
f[i][0] = min(f[i][0],f[i - 1][1] + r1 + 3 * d + op1);
f[i][1] = f[i - 1][0] + op2 + d;
f[i][1] = min(f[i][1],f[i - 1][1] + op2 + 3 * d + r1);
}
ll res = min(f[n][0],f[n - 1][1] + (a[n] + 1) * r1 + r3 + 2 * d);
cout << res << endl;
return 0;
}