Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)[A - D]
| A | Parallel Projectionstandard input/output1 s, 512 MB |
|---|---|
| B | Going to the Cinemastandard input/output2 s, 512 MB |
| C | Equal Frequenciesstandard input/output2 s, 512 MB |
| D | Many Perfect Squaresstandard input/output4 s, 512 MB |
过题记录
| When | Who | Problem | Lang | Verdict | Time | Memory |
|---|---|---|---|---|---|---|
| Jan/27/2023 22:09UTC+8 | xjsc01# | C - Equal Frequencies | GNU C++17 | Accepted | 31 ms | 300 KB |
| Jan/27/2023 22:08UTC+8 | xjsc01# | C - Equal Frequencies | GNU C++17 | Wrong answer on test 1 | 0 ms | 100 KB |
| Jan/27/2023 21:14UTC+8 | xjsc01# | B - Going to the Cinema | GNU C++17 | Accepted | 62 ms | 2400 KB |
| Jan/27/2023 20:39UTC+8 | xjsc01# | A - Parallel Projection | GNU C++17 | Accepted | 31 ms | 0 KB |
A Parallel Projection
Example
Input
5
55 20 29
23 10 18 3
20 10 5
1 5 2 5
15 15 4
7 13 10 10
2 1000 2
1 1 1 999
10 4 10
7 1 2 1
Output
47
8
14
1002
17
思路
朝着四个方向枚举
代码
#include <bits/stdc++.h>
using namespace std;
int w, d, h, a, b, f, g;
int dist(int x, int y)
{
return abs(x - a) + abs(y - b);
}
int main()
{
int T;
cin >> T;
while(T --)
{
scanf("%d%d%d", &w, &d, &h);
scanf("%d%d%d%d", &a, &b, &f, &g);
int ans = 0x3f3f3f3f;
int d1 = 0;
int d2 = 0;
//
d1 = f;
d2 = dist(0, g);
ans = min(ans, d1 + d2 + h);
//
d1 = g;
d2 = dist(f, 0);
ans = min(ans, d1 + d2 + h);
//
d1 = w - f;
d2 = dist(w, g);
ans = min(ans, d1 + d2 + h);
//
d1 = d - g;
d2 = dist(f, d);
ans = min(ans, d1 + d2 + h);
printf("%d\n", ans);
}
return 0;
}
B Going to the Cinema
Example
Input
4
2
1 1
7
0 1 2 3 4 5 6
8
6 0 3 3 6 7 2 7
5
3 0 0 3 3
Output
2
1
3
2
思路
首先需要排序。
容易知道，如果有\(x \le y\)，如果 y 选中了，那么 x 也一定需要选中。
所以从低位到高位进行选择
代码
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 2e5 + 20;
int a[N];
struct Node{//预处理，按顺序，i=a[i]，num表示有多少个
int i, num;
};
Node d[N];
int main()
{
int T;
cin >> T;
while(T --)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
sort(a + 1, a + 1 + n);
d[1] = {a[1], 1};
int pos = 1;
for(int i = 2; i <= n; i++){
if(a[i] == d[pos].i) d[pos].num ++;
else{
pos++;
d[pos].i = a[i];
d[pos].num = 1;
}
}
int tot = 0;
int ans = 0;
for(int i = 1; i <= pos; i++)
{
if(tot + d[i].num - 1 >= d[i].i && (i < pos && tot+d[i].num < d[i+1].i || i == pos)) {
ans ++;
tot += d[i].num;
}
else{
tot += d[i].num;
}
}
if(d[1].i != 0 ) ans ++;
//|| ( d[1].num + d[2].num - 1 < d[2].i )
printf("%d\n", ans);
// for(int i = 1; i <= pos; i++){
// printf("%d %d\t", d[i].i, d[i].num);
// }
}
return 0;
}
C Equal Frequencies
Example
Input
4
5
hello
10
codeforces
5
eevee
6
appall
Output
1
helno
2
codefofced
1
eeeee
0
appall
思路
首先忽略原本的字母，把每一个字母具体出现多少次全部抽取出来，现在枚举得到的结果中有多少种字母（注意种类数必须 整除 字符串长度），计算最小移动次数。
然后求最优结果的方案数
代码
#include <bits/stdc++.h>
using namespace std;
int N;
#define N 100020
char s[N];
int a[128];
int b[30];
int len;
pair<int, char> c[128];
int del[128];
vector<char> ins;
int solve(int &min_diff)
{
int k;
int mindiff = 0x3f3f3f3f;
for(int i = 1; i <= 26; i++){
if(len % i) continue;
int num = len / i;
int diff = 0;
for(int j = 1; j <= 26; j ++){
if(j <= i){
diff += max(num - b[j], 0);
}
}
if(diff < mindiff){
mindiff = diff;
k = i;
}
}
min_diff = mindiff;
return k;
}
int main()
{
int T;
cin >> T;
while(T --)
{
scanf("%d", &len);
scanf("%s", s + 1);
memset(a, 0, sizeof a);
memset(c, 0, sizeof c);
memset(b, 0, sizeof b);
memset(del, 0, sizeof del);
ins.clear();
for(int i = 1; i <= len; i++){
a[s[i]] ++;
}
for(int i = 1; i <= 26; i++){
b[i] = a[i + 'a' - 1];
}
for(int i = 1; i <= 26; i++){
c[i].first = a[i + 'a' - 1];
c[i].second = i + 'a' - 1;
}
sort(b + 1, b + 1 + 26);
reverse(b + 1, b + 1 + 26);
sort(c + 1, c + 1 + 26);
reverse(c + 1, c + 1 + 26);
int mindff;
int k = solve(mindff);
//for(int i = 1; i <= 26; i ++) cout << b[i] << '\t';
//cout << k << "\t";
int num = len / k;
for(int i = 1; i <= 26; i++){
int tmp;
if(i <= k) tmp = num;
else tmp = 0;
if(c[i].first == tmp) continue;
if(c[i].first > tmp){
del[c[i].second] += c[i].first - tmp;
}
else{
for(int u = 1; u <= tmp - c[i].first; u++) ins.push_back(c[i].second);
}
}
printf("%d\n", mindff);
for(int i = 1; i <= len; i++){
if(del[s[i]]){
putchar(ins.back());
ins.pop_back();
del[s[i]]--;
}
else{
putchar(s[i]);
}
}
puts("");
}
return 0;
}
D Many Perfect Squares
Example
Input
4
5
1 2 3 4 5
5
1 6 13 22 97
1
100
5
2 5 10 17 26
Output
2
5
1
2
Note
In the first test case, for x=0 the set contains two perfect squares: 1 and 4. It is impossible to obtain more than two perfect squares.
In the second test case, for x=3 the set looks like 4,9,16,25,100, that is, all its elements are perfect squares.
思路
在这一道题目中，明显可以使用暴力，但是怎么样暴力是一种艺术。
首先，保底的结果就是有一个数字加 x 之后是完全平方数（把第一个数挪一挪就行了）
如果要是直接枚举 x ，必定超时。
我们考虑如果结果是大于等于 2 的所有结果。
容易知道：必定有两个经过加x之后是完全平方数
so：
产生的因数真的很少：
计算方法：分解质因数，进行乘法原理。
1e9以内的数字分解质因数最大也就10个（\(2*3*5*7*..\)的值增长很快）
即使对于最小的质数 2 ，次方数也不超过36
所以总共的因子很少
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
const int N = 55;
ll a[N];
inline bool isdouble(ll x)// 判断x是不是完全平方数
{
ll y = sqrt(x);
return y * y == x;
}
ll ck(ll x)// 检验增加x之后有多少个数字是完全平方数
{
ll res = 0;
//cout << x << " ";
for(int i = 1; i <= n; i++){
if(isdouble(x + a[i])) res++;
}
return res;
}
int main()
{
int T;
cin >> T;
while(T --)
{
scanf("%lld", &n);
for(int i = 1; i <= n; i++){
scanf("%lld", a + i);
}
ll ans = 1;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j ++){
ll d = a[j] - a[i];
for(int x = 1; x <= sqrt(d); x ++){
if(d % x) continue;
ll y = d / x;
if(x+y & 1 || y-x & 1) continue;// 必须是偶数
if((x+y)*(x+y)/4-a[j] >= 0)// 由于是公式计算x，所以可能有负数
ans = max(ans, ck((x+y)*(x+y)/4-a[j]));
}
}
}
cout << ans << "\n";
}
return 0;
}