题目链接
A. Juggling Letters
题意：
给定 (n) 个字符串，可以任意改变字符的位置（从一个字符串插入到另一个字符串的任意位置），问能否将 (n) 个字符串变得一样？
思路：
统计每个字符出现的次数，如果是 (n) 的倍数，那么就可以均分，否则不行。
代码：
/*
* @Author : nonameless
* @Date : 2020-09-02 15:08:08
* @LastEditors : nonameless
* @LastEditTime : 2020-09-02 15:16:36
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f;
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a * b / gcd(a, b); }
int cnt[30];
char s[1010];
int main(){
int t;
scanf("%d", &t);
while(t --){
memset(cnt, 0, sizeof cnt);
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%s", s + 1);
int len = strlen(s + 1);
for(int j = 1; j <= len; j ++) cnt[s[j] - 'a'] ++;
}
int mark = 1;
for(int i = 0; i < 26; i ++)
if(cnt[i] % n){
mark = 0;
break;
}
if(mark) puts("Yes");
else puts("No");
}
return 0;
}
B. Power Sequence
题意：
给定一个整数的数列。你可以通过以下两种操作来使其变成一个等比数列（以1为首项）
- 可以任意交换两个数的位置
- 花费1的代价使 (a_i) 变为 (a_i + 1) 或 (a_i - 1)
问最小代价可以是多少？
思路：
枚举公差 (q) 。
代码：
/*
* @Author : nonameless
* @Date : 2020-09-02 15:43:08
* @LastEditors : nonameless
* @LastEditTime : 2020-09-02 16:26:15
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f;
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a * b / gcd(a, b); }
const int N = 1e5 + 10;
int a[N];
int main(){
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
sort(a + 1, a + n + 1);
long long ans = LNF;
for(int c = 1; ; c ++){
long long tmp = 0;
long long s = 1;
for(int i = 1; i <= n; i ++){
tmp += abs(a[i] - s);
s *= c;
if(s > 1e14) { tmp += ans; break; }
}
if(tmp > ans) break;
ans = tmp;
}
cout << ans << endl;
return 0;
}
C. Multiples of Length
题意：
给定一个整数数组，你要做三次操作使得数组中的每个数都为零。
- 选定一段连续区间，设 $len = $ 区间长度，你可以使区间中的每个数都加上 (len) 的整数倍（包括负数）。
思路：
要在三次操作中解决，那么显然我们在两次操作中要将区间 ([1, n]) 的数都变为 (n) 的整数倍（第三次就可以完成要求），单独对某个数来看有：(a_i = a_i + k imes len)。
要将 (a_i) 变为 (n) 的整数倍，显然上式就应该出现 (n)，那么我们就必须考虑消去 (a_i)，观察可以发现当 (len = n - 1, k = a_i) 时，可以满足上述要求。此时 (a_i = a_i imes n)。
- 第一次操作区间为 ([1, n - 1])，每个数加上 (a_i imes(n- 1))。
- 第二次操作将 (a_n) 变为 0。
- 第三次操作区间为 ([1, n])。
代码：
/*
* @Author : nonameless
* @Date : 2020-09-02 18:50:52
* @LastEditors : nonameless
* @LastEditTime : 2020-09-02 19:00:13
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f;
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a * b / gcd(a, b); }
const int N = 1e5 + 10;
int a[N];
int main(){
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
if(n == 1){
printf("1 1
%d
1 1
0
1 1
0
", -a[1]);
return 0;
}
printf("1 %d
", n - 1);
for(int i = 1; i < n; i ++) printf("%lld ", 1ll * a[i] * (n - 1));
puts("");
printf("%d %d
", n, n);
printf("%d
", -a[n]);
printf("1 %d
", n);
for(int i = 1; i < n; i ++) printf("%lld ", -1ll * a[i] * n);
puts("0");
return 0;
}
D. Stoned Game
题意：
有 (n) 堆石子，两个人轮流每次取一颗，要求不能从上个人取的那堆里取，取不到石子的人失败，问在最优策略下，谁会获胜？
思路：
- 考虑一种特殊情况，有一堆石子比其他堆加起来还多，那么第一个取的人获胜。
- 其他情况在最优策略下，肯定会取完所有的石子，那么根据石子总数的奇偶就可以判断，奇数先手赢，偶数后手赢。
代码：
/*
* @Author : nonameless
* @Date : 2020-09-02 19:22:54
* @LastEditors : nonameless
* @LastEditTime : 2020-09-02 19:24:45
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f;
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a * b / gcd(a, b); }
int main(){
int t; scanf("%d", &t);
while(t --){
int n; scanf("%d", &n);
int mx = 0, sum = 0;
for(int i = 1; i <= n; i ++){
int x; scanf("%d", &x);
mx = max(mx, x);
sum += x;
}
if(mx > sum - mx || sum & 1) puts("T");
else puts("HL");
}
return 0;
}