A. Dense Array
思路:
数据范围很小,直接暴力统计即可,注意判断条件当二者的商等于2时要特判
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int, int>PII;
int a[N];
void solve()
{
int n;cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i];
int res = 0;
for(int i = 2; i <= n; i ++)
{
int maxv = max(a[i],a[i - 1]);
int minv = min(a[i],a[i - 1]);
if(maxv / minv > 2 || (maxv / minv == 2 && maxv % minv != 0))
{
int cnt = 0;
while(minv < maxv)
{
minv *= 2;
cnt ++;
}
cnt --;
res += cnt;
}
}
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
B. Balanced Remainders
思路:
将所有的值先转化成%3之后的然后将少于平均的存起来,最后再用剩下的去变化
由于我们只能增加,所以对于012而言,应从大到小进行考虑
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int, int>PII;
int a[N];
void solve()
{
int n;cin >> n;
int cnt = n / 3;
map<int,int>mp;
int s = 0;
for(int i = 0; i < n; i ++)
{
int x;cin >> x;
x %= 3;
if(mp[x] < cnt)mp[x] ++;
else a[s ++] = x;
}
sort(a,a + s,greater<int>());
int res = 0;
for(int i = 0; i < s; i ++)
{
if(mp[0] < cnt)
{
mp[0] ++;
if(a[i] == 1)res += 2;
else if(a[i] == 2)res += 1;
}
else if(mp[1] < cnt)
{
mp[1] ++;
if(a[i] == 0)res += 1;
else if(a[i] == 2)res += 2;
}
else if(mp[2] < cnt)
{
mp[2] ++;
if(a[i] == 0)res += 2;
else if(a[i] == 1)res += 1;
}
}
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
C. Sum of Cubes
思路:
暴力枚举一个数,二分出另一个并检查即可
注意二分的范围要设置的小一些,否则会爆long long.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int, int>PII;
int a[N];
void solve()
{
int n;cin >> n;
for(int i = 1; i <= min(n,1ll*10001); i ++)
{
int t = n - i * i * i;
if(t == n || t == 0)continue;//题目的规定
int l = 0,r = 10000;
while(l < r)
{
int mid = l + r >> 1;
if(mid * mid * mid >= t)r = mid;
else l = mid + 1;
}
if(l * l * l == t)
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
D. Permutation Transformation
思路:
模拟上述过程,依次对最大值进行赋值即可
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#pragma GCC optimize(3)
typedef long long LL;
//#define int long long
const int N = 110,M = 2 * N,INF = 0x3f3f3f3f;
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int d[N],a[N],n;
void dfs(int l,int r,int cnt)//每递归一次就会深一层
{
if(l > r)return;
if(l == r)//对叶子结点进行更新
{
d[l] = cnt;
return;
}
int id = l;
for(int i = l,maxv = a[l]; i <= r; i ++)
{
if(a[i] > maxv)
{
maxv = a[i];
id = i;
}
}
d[id] = cnt;//对最大值进行更新
//递归左右子树
dfs(l,id - 1,cnt + 1),dfs(id + 1,r,cnt + 1);
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i];
dfs(1,n,0);
for(int i = 1; i <= n; i ++)cout << d[i] << ' ';
cout << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
E. Accidental Victory
思路:
从后往前考虑,如果前面的前缀和大于等于当前数一定是合法的,就向前推进,否则终止
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#pragma GCC optimize(3)
typedef long long LL;
#define int long long
const int N = 2e5 + 10,M = 2 * N,INF = 0x3f3f3f3f;
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
PII a[N];
int s[N];
//对于排序后的每个数,扫一下当前数的前缀和是否大于等于后一个
//加上后一个之后是否大于再后一个
//反过来想,从后往前考虑,如果前面的前缀和大于等于当前数就向前走
//走到最靠前的位置
void solve()
{
int n;cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i].first,a[i].second = i;
sort(a + 1,a + n + 1);
for(int i = 1; i <= n; i ++)s[i] = s[i - 1] + a[i].first;
vector<int>q;
for(int i = n; i >= 1; i --)
{
if(s[i - 1] - s[0] < a[i].first)
{
q.push_back(a[i].second);
break;
}
q.push_back(a[i].second);
}
sort(q.begin(),q.end());
cout << q.size() << endl;
for(auto x : q)cout << x << ' ';
cout << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
F. Equalize the Array
思路:
统计所有数出现的次数,并将它们从小到大进行排序.
我们从前向后扫依次看他们的贡献,在所有的贡献中取一个最小的即可
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#pragma GCC optimize(3)
typedef long long LL;
#define int long long
const int N = 2e5 + 10,INF = 0x3f3f3f3f;
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N],s[N];
void solve()
{
memset(s,0,sizeof s);
map<int,int>mp;
int n;cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> a[i];
mp[a[i]] ++;
}
int cnt = 0;
for(auto x : mp)a[++ cnt] = x.second;
sort(a + 1,a + cnt + 1);
//for(int i = 1; i <= cnt; i ++)cout << a[i] << " ";
for(int i = 1; i <= cnt; i ++)s[i] = s[i - 1] + a[i];
int res = INF;
for(int i = 1; i <= cnt; i ++)
res = min(res,s[cnt] - s[i] - (cnt - i) * a[i] + s[i - 1] - s[0]);
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
G. Old Floppy Drive
思路:
首先对于我们的x而言,如果在a的前缀和数组中存在大于等于它的位置,直接输出即可。若是没有,我们就要判断转一圈的值是否大于0了,若不大于0,这个过程一定会持续下去。若大于0,我们还要使得转的次数最少,考虑最后一次一定会停在中间的某个位置,我们可以提前让x减去其中最大的位置,然后再让剩余的值转k圈即可。此处有细节,详见代码。对于其中最大的位置,我们可以维护一个最大值数组,然后二分查找到最小的位置
核心:找最小移动次数,我们先找到数组中当前最大的数,减去并转圈,再二分新数的位置。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 2e5 + 10;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N],mx[N];
void solve()
{
int n,m;cin >> n >> m;
int sum = 0;
for(int i = 1; i <= n; i ++)cin >> a[i],sum += a[i],mx[i] = max(mx[i - 1],sum);
for(int i = 1; i <= n; i ++)a[i] += a[i - 1];
while(m --)
{
int x;cin >> x;
if(x <= mx[n])
cout << (lower_bound(mx + 1,mx + n + 1,x) - mx) - 1 << " ";
else
{
if(sum <= 0) cout << -1 << " ";
else
{
int d = x - mx[n];
int k = (d + sum - 1) / sum;//上取整
x -= k * sum;
cout << (lower_bound(mx + 1,mx + n + 1,x) - mx) + k * n - 1 << " ";
}
}
}
cout << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
大佬真的巨强的
我好菜的~