Codeforces Round #666 (Div. 2)
A. Juggling Letters
判断各字母出现次数之和是否能被n整除。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 100;
typedef long long LL;
const int inf = 0x3f3f3f3f;
int t, n;
char s[MAXN];
int cnt[100];
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++) {
scanf("%s", s);
for (int j = 0; j < strlen(s); j++) {
cnt[s[j] - 'a']++;
}
}
int flag = 0;
for (int i = 0; i <= 26; i++) {
if (cnt[i] % n != 0) flag++;
}
printf("%s
", flag ? "NO" : "YES");
}
}
B. Power Sequence
首先可以考虑到一个较优的情况:C=1,此时答案至多为1e5*1e9=1e14
算了一下,如果c=2时,不超过1e14的幂应该是46左右(不超过50)。
那么就可以暴力所有数,算它的50以内的次方的答案,来和c=1的答案比,取最优。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 100;
typedef long long LL;
const LL inf = 0x3f3f3f3f3f3f3f3f;
int n;
LL a[MAXN];
int main() {
scanf("%d", &n);
LL x = 1, ans = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
ans += abs(a[i] - 1);
}
sort(a+1, a+1+n);
LL c = 2;
while(c <= 1000000) {
LL t = 1, cnt = 0, tmp = 0;
for (int i = 1; i <= min(n, 50); i++) {
cnt += abs(t - a[i]);
//printf("%lld
", cnt);
t *= c;
if (t <= tmp) {
cnt = inf;
break;
}
tmp = t;
if (cnt > ans) break;
}
ans = min(ans, cnt);
c++;
}
printf("%lld
", ans);
}
C. Multiples of Length
我构造的方法是,先把前n-1个变为n的倍数,再消除第n个,最后把n个整体消除(因为都是n的倍数了)。
如何把前n-1个变为n的倍数呢?
如果令(a_i=B,n-1=A,n=M),那么这个问题就变成了求(Ax+B≡0(mod M)),可以用扩展欧几里得快速求出。因为((A,M))恒(=1),所以((A,M)|B)一定成立,故原式一定有解。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 100;
typedef long long LL;
const LL inf = 0x3f3f3f3f3f3f3f3f;
LL extgcd(LL a,LL b,LL& x,LL& y){
if(b){
LL r=extgcd(b,a%b,y,x);
y-=x*(a/b); return r;
} else { x=1; y=0; return a; }
}
LL solve(LL a,LL b,LL M){
LL x,y,r=extgcd(a,M,x,y);
if(b%r) return -1; else x=(x+M)%M*b/r;
return x%(M/r);
}
int n;
LL a[MAXN];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
if (n == 1) {
printf("1 1
%d
", -a[1]);
printf("1 1
0
1 1
0
");
return 0;
}
printf("%d %d
", 1, n-1);
for (int i = 1; i <= n-1; i++) {
printf("%lld%c", solve(n-1, n-(a[i]%n), n) * (n-1), i == n-1 ? '
' : ' ');
}
printf("%d %d
", n, n);
printf("%lld
", -a[n]);
printf("%d %d
", 1, n);
for (int i = 1; i <= n-1; i++) {
printf("%lld ", -(a[i] + solve(n-1, n-(a[i]%n), n)*(n-1)));
}
printf("0
");
}
D. Stoned Game
因为上一个题写着写着死机了,所以这个题只剩下了6分钟。
其实结论很好想。当有一堆石子数大于其他堆之和时,T就可以先占领这一堆获胜。
否则就一定会形成每堆都为1的局面,所以直接判石子之和的奇偶性即可。
写完这个题wa了一发,两分钟后再交就contest finished了。我心态炸了。
下面的代码没提交上,不保证正确。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 100;
typedef long long LL;
const LL inf = 0x3f3f3f3f3f3f3f3f;
int t, n;
int a[MAXN];
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int maxX = 0, sum = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
maxX = max(maxX, a[i]);
sum += a[i];
}
if (maxX > sum-maxX) {
printf("T
");
} else {
printf("%s
", (sum) % 2 ? "T" : "HL");
}
}
}
E. Monster Invaders
too vegetable to solve