Codeforces Round #702 (Div. 3) A—G
A. Dense Array
直接模拟即可。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PIL pair<int, ll>
#define endl '\n'
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << " and " << #y << " = " << y << endl
#define Pi acos(-1)
using namespace std;
const int N = 3e5 + 100;
int a[N];
int f(int a, int b)
{
if(a > b) swap(a, b);
int res = 0;
while(a * 2 < b)
{
res ++;
a *= 2;
}
return res;
}
int main()
{
int t;
cin >> t;
while(t --)
{
int n;
int ans = 0;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 1; i < n; i ++)
ans += f(a[i - 1], a[i]);
cout << ans << endl;
}
return 0;
}
B. Balanced Remainders
可以把模 3 为0 ，1 ， 2 看成三个箱子，很容易发现只要对任意一个箱子里的数加1，就可以将这个数移动到它右边的箱子里（2的右边是0），所以我们只用先求出 总数 / 3 —— 每个箱子里应有得个数，然后从左向右推一遍，再从右向左推一边就可以将所有箱子里得个数都变为3 / n，每移动一个数字，ans 就 + 1。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PIL pair<int, ll>
#define endl '\n'
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << " and " << #y << " = " << y << endl
#define Pi acos(-1)
using namespace std;
const int N = 3e5 + 100;
int c[3];
int main()
{
int t;
cin >> t;
while(t --)
{
memset(c, 0, sizeof(c));
int n, num;
ll ans = 0;
int mid;
cin >> n;
mid = n / 3;
for(int i = 0; i < n; i ++) cin >> num, c[num % 3] ++;
for(int i = 0; i < 3; i ++)
if(c[i] > mid) ans += c[i] - mid, c[(i + 1) % 3] += c[i] - mid, c[i] = mid;
for(int i = 2; i >= 0; i --)
if(c[i] > mid) ans += c[i] - mid, c[(i + 1) % 3] += c[i] - mid, c[i] = mid;
cout << ans << endl;
}
return 0;
}
C. Sum of Cubes
假设 x 是 y 的三次方，因为 1 ≤ x ≤ 1012，所以y的范围实际上也就是1到104。我们不妨将1到104所有数的三次方存入set，然后枚举y，对于每个y来说，如果x - y3在set中存在，说明YES，否则NO。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PIL pair<int, ll>
#define endl '\n'
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << " and " << #y << " = " << y << endl
#define Pi acos(-1)
using namespace std;
const int N = 3e5 + 100;
int main()
{
set<ll> S;
for(ll i = 1; i <= 10000; i ++)
S.insert((i * i * i));
int t;
cin >> t;
while(t --)
{
int bj = 0;
ll x;
cin >> x;
for(ll i = 1; i <= 10000; i ++)
{
if(S.count(x - i * i * i))
{
bj = 1;
cout << "YES" << endl;
break;
}
}
if(!bj) cout << "NO" << endl;
}
return 0;
}
D. Permutation Transformation
这种二叉树其实有一个名字，叫做笛卡尔树，详情见笛卡尔树。
我们可以通过递归建树，每次找到最大值所在的位置，并记录此位置的深度。本题数据范围很小，我们可以用暴力的方法找到某个分段区间中最大值所在的位置，总时间复杂度为O(n2)。
当然我们可以用线段树或者ST表来优化此过程，总时间复杂度为O(nlogn)。
当然也有更优秀的建树方法，只需要O(n)的时间复杂度，详情见—— ACM算法日常 - 算法合集 | 神奇的笛卡尔树。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PIL pair<int, ll>
#define endl '\n'
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << " and " << #y << " = " << y << endl
#define Pi acos(-1)
using namespace std;
const int N = 3e5 + 100;
int deep[150], a[150];
void creat(int l, int r, int d)
{
if(r < l) return;
if(l == r) {
deep[l] = d;
return;
}
int m = l;
for(int i = l; i <= r; i ++) if(a[i] > a[m]) m = i;
deep[m] = d;
if(l < m)
creat(l, m - 1, d + 1);
if(m < r)
creat(m + 1, r, d + 1);
}
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
memset(deep, 0, sizeof deep);
creat(1, n, 0);
for(int i = 1; i <= n; i ++) cout << deep[i] << " ";
cout << endl;
}
int main()
{
int t;
cin >> t;
while(t --)
solve();
return 0;
}
E. Accidental Victory
题意：
有n个人，每个人有自己的价值ai，现有n - 1次比赛，比赛规则是：如果双方价值不相等，价值高的那方赢；如果价值相等的话，随机让一个人赢。每次比赛赢的那方会夺走输的那方的所有价值，输的那方将不能再参加比赛比赛，当最后只剩下一个人价值不为0的时候，比赛结束。
询问这n个人里有哪些人有机会可以赢得比赛，并输出这些人的编号， 编号需要排序。
题解：
因为每个人只能现对比自己小的下手，我们不妨对n个人的价值排序，然后到每个人位置的价值前缀和就是每个人能够从所有不超过它的人得到的价值总和（包括自身），然后向后遍历，只要当前的总和 ≥ 下一个人价值（这里有等于是因为我们贪心的考虑比赛，只要相等，随机赢的一定是“ 挑战者 ”），但是这样得话实际上我们需要对每一个人都进行一次循环判断是否能赢到最后，复杂度很高，接近n2。
我们来可以看看能不能进行什么优化，能发现其实对于一个 i 来说，只要 i 能够赢，那么对于 i + 1 来说，也进行同样的策略也能够赢，所以我们只需要找到第一个能够赢得比赛的 i ，那么 i + 1 一直到 n都是 必赢的。所以就变成了一个二分的问题，排序完过后，然后对下标进行二分，找到能够赢得比赛的第一个下标，将 i 到 n 的 人的编号存下来排序输出就可以。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PIL pair<int, ll>
#define endl '\n'
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << " and " << #y << " = " << y << endl
#define Pi acos(-1)
using namespace std;
const int N = 2e5 + 100;
PIL a[N];
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i].second, a[i].first = i;
sort(a + 1, a + n + 1, [&](PIL a, PIL b) {return a.second < b.second;});
int l = 1, r = n;
while(l < r)
{
int m = (l + r) >> 1;
ll now = 0;
for(int i = 1; i <= m; i ++) now += a[i].second;
int f = 0;
for(int i = m + 1; i <= n; i ++)
{
if(now < a[i].second)
{
f = 1;
break;
}
now += a[i].second;
}
if(!f) r = m;
else l = m + 1;
}
set<int> V;
for(int i = l; i <= n; i ++) V.insert(a[i].first);
cout << V.size() << endl;
for(auto i = V.begin(); i != V.end(); i ++) cout << *i << " ";
cout << endl;
}
int main()
{
IOS;
int t;
cin >> t;
while(t --)
solve();
return 0;
}
F. Equalize the Array
题意：
现有一个n个数的序列，问最少删除多少个数字之后，剩下的序列中的所有数都出现C次，原序列中的某些数可以全部删除。
比如：1 3 2 1 4 2，可以删除3 和 4， 留下 1 1 2 2，满足题意。
题解：
目删除的最小个数，但是好像并不能贪心的删除，那么我们能不能换一个方向想呢？既然最后每个数字要么剩余C个，要么剩余0个，那么我们不妨枚举所有的数字初始存在的个数X，如果当前数字的可以在新序列中留下X个（即初始个数大于等于C），那么我们就将这个数字的个数 - X，放入ans里;如果当前的数字的初始个数不足X，那么我们就不将这个数字放入新序列中了，ans里加上这个数字的初始个数。最后得到一个新序列，每次更新ans的最小值。
记得离散化。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PIL pair<int, ll>
#define endl '\n'
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << " and " << #y << " = " << y << endl
#define Pi acos(-1)
using namespace std;
const int N = 2e5 + 100;
void solve()
{
map<int, int> MP;
int ans = inf;
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
int num;
scanf("%d", &num);
MP[num] ++; //离散化
}
vector<int> d;
set<int> S;
for(auto i = MP.begin(); i != MP.end(); i ++) d.push_back(i->second), S.insert(i->second);
sort(d.begin(), d.end()); //将出现次数排序
reverse(d.begin(), d.end());
for(auto i = S.begin(); i != S.end(); i ++) //出现次数只需要枚举初始已有的，枚举不存在的出现次数是没有意义的
//比如 1 1 2 2 2 2 ，枚举最后出现 3 次的情况和最后出现 4 次相比，
//只会让删除的值变多，不满足尽量少删的题意
{
int sum = 0; // sum为需要删除的数的个数。
for(int j = 0; j < d.size(); j ++)
{
if(d[j] >= *i) sum += d[j] - *i; //如果出现次数够，最后会留下部分或全部
else sum += d[j]; //出现次数不够，最后会全部删除
}
ans = min(sum, ans);
}
printf("%d\n", ans);
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
solve();
return 0;
}
G. Old Floppy Drive
题意：
有一个循环数组，周期为n，有m次询问，每次询问给出一个x，需要输出第一个前缀和 ≥ x 的 位置。
题解：
先不考虑循环，我们考虑对于一个前缀和数组pre来说，只有pre[i] > ma(设ma为 0 到 i - 1 中 最大的pre）时，a[i] 才有可能 ≥ x，因为如果pre[i] ≤ ma的话，实际上答案并不会后移。
所以我们可以先找出所有满足这个条件的位置，然后将其值和位置放入vector中，同时记录下这些位置中最大的值是多少。然后二分找到第一个 ≥ x 的 位置， 如果二分返回的x的位置等于了vector的size的话，就说明 x 不存在当前的循环节中，需要向后面的循环节找，怎么找呢？
我们可以发现pre的每向后一个循环节的每个位置上都会增加d，这个d实际上就等于pre[n - 1]（下标从0开始）。所以我们就可以根据这个d，来确定当前的x应该处于哪一个循环节中。
首先如果d ≤ 0的话，说明如果在第一段里不存在，之后的每一段都不可能存在，也就是说答案为-1;
而如果d > 0的话，我们就可以通过round_num = (x - ma) / d 来判断，但是边界情况不是很清楚，这个时候我们就可以画一画来看看是需要 + 1 还是 - 1。比如：x = 7， ma = 4， d = 3， 那么其实pre会有这样的循环情况：……4 5 6 7 8 9 10 ……，也就是说，当x = 5，6，7的时候，d应该相同，但是我们发现x - ma 分别为 1， 2， 3，而d = 3，最后得到的循环节编号分别是 0， 0， 1，所以我们需要将其变为（x - ma - 1），然后我们定义的循环节是第0节，第1节 …… ，所以需要将（x - ma - 1) 最后得数再加上1，也就是说最终的 round_num = （x - ma - 1）+ 1。
之后依然对vector进行二分，但是需要查找的值改变了，变为了 x - d * round_num，需要注意的是我们找到的位置并不是最终位置，还需要加上 n * round_num！
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PIL pair<int, ll>
#define endl '\n'
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << " and " << #y << " = " << y << endl
#define Pi acos(-1)
using namespace std;
const int N = 2e5 + 100;
ll a[N], pre_sum[N];
const int INF = 1e12;
void solve()
{
int n, m;
ll ma = -INF;
scanf("%d%d", &n, &m);
vector<pair<ll, int>> K;
for(int i = 0; i < n; i ++)
{
scanf("%lld", &a[i]);
if(!i) pre_sum[i] = a[i];
else pre_sum[i] = pre_sum[i - 1] + a[i];
if(pre_sum[i] > ma)
{
K.push_back(make_pair(pre_sum[i], i));
ma = pre_sum[i];
}
}
ll d = pre_sum[n - 1];
while(m --)
{
ll x;
scanf("%lld", &x);
int it = lower_bound(K.begin(), K.end(), make_pair(x, 0)) - K.begin();
if(it < K.size())
{
printf("%d ", K[it].second);
continue;
}
if(d <= 0)
{
printf("-1 ");
continue;
}
ll round_n = (x - ma - 1) / d + 1;
it = lower_bound(K.begin(), K.end(), make_pair(x - round_n * d, 0)) - K.begin();
printf("%lld ", K[it].second + n * round_n);
}
puts("");
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
solve();
return 0;
}