看来我有时候还是会把简单的问题想复杂。
A. Dense Array
题意
给出一个数组，向数组中插入尽可能少的整数，使得max(num[i+1],num[i])/min(num[i+1],num[i])<=2，求插入整数的数量。
题解
签到题，直接模拟。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
void swap(ll* a, ll* b) {
int swapp = *a;
*a = *b;
*b = swapp;
}
ll max(ll a, ll b) {
if (a > b) return a;
return b;
}
ll min(ll a, ll b) {
if (a < b) return a;
return b;
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int n;
cin>>n;
ll re=0;
int last,now;
cin>>last;
for(int i=1;i<n;i++){
cin>>now;
if((double)max(now,last)/(double)min(last,now)<=2){
last=now;
continue;
}
else{
if(now>last){
while(!((double)now/(double)last<=2)){
re++;
last=last*2;
}
last=now;
}
else{
int l=now;
swap(now,last);
while(!((double)now/(double)last<=2)){
re++;
last=last*2;
}
last=l;
}
}
}
cout<<re<<endl;
}
return 0;
}
B. Balanced Remainders
题意
给出一个长度为n（n为3的倍数）的数组，在每次操作中，你可以对数组中任意一个元素+1，最终使得数组中模3为0、1、2的数的个数相等。
题解
既然一个少了，我们就要用多的去补上，由于只能相加，所以模0的数+1是模1的数、+2是模2的数，模1的数+1是模2的数、+2是模0的数，模2的数+1是模0的数、+2是模1的数。
入门贪心，用少的去补多的，然后追求操作次数最小。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int n;
cin>>n;
int s;
int a0=0,a1=0,a2=0;
for(int i=0;i<n;i++){
cin>>s;
if(s%3==0) a0++;
else if(s%3==1) a1++;
else a2++;
}
ll re=0;
if(a0<n/3&&a1<n/3){
re=(n/3-a0)+2*(n/3-a1);
}
else if(a0<n/3&&a2<n/3){
re=(n/3-a2)+2*(n/3-a0);
}
else if(a1<n/3&&a2<n/3){
re=(n/3-a1)+2*(n/3-a2);
}
else if(a0<n/3){
re=(a2-n/3)+2*(a1-n/3);
}
else if(a1<n/3){
re=(a0-n/3)+2*(a2-n/3);
}
else if(a2<n/3){
re=(a1-n/3)+2*(a0-n/3);
}
cout<<re<<endl;
}
return 0;
}
C. Sum of Cubes
题意
求x是否为两个数的立方和。
题解
开始想到了费马大定理，不过最后看了别人的代码，发现就是暴力枚举。
枚举a，然后令num=x-a*a*a，对num开立方，如果开立方得到的数乘回去还是num，就是yes。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll n;
cin>>n;
bool f=0;
for(ll i=1;i<8000;i++){
ll s=n-i*i*i;
ll u = cbrtl(s);
if (u > 0 && u * u * u == s) f = 1;
}
if(f==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
D. Permutation Transformation
题意
给出整数n的排列，我们将其转换为一颗二叉树。最大的数放在第一层，然后我们将最大的数的左边区间和右边区间中分别作为他的左子树和右子数，区间中最大值分别作为左子节点和右子节点，依次类推，求每个元素在二叉树的哪一层。
题解
看一下数据范围只有100，递归模拟。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int re[200],num[200],n;
void bsearch(int c,int l,int r){
int mx=0,mxi;
if(l==r){
re[l]=c;
return;
}
for(int i=l;i<=r;i++){
if(num[i]>mx){
mx=num[i];
mxi=i;
}
}
// for(int i=1;i<=n;i++) cout<<re[i]<<" ";
// cout<<endl;
// cout<<l<<" "<<r<<endl;
// int s;
//cin>>s;
re[mxi]=c;
if(mxi-1>=1&&l<=mxi-1)bsearch(c+1,l,mxi-1);
if(mxi+1<=n&&mxi+1<=r)bsearch(c+1,mxi+1,r);
return;
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
cin>>n;
memset(re,0,sizeof(re));
for(int i=1;i<=n;i++) {
cin>>num[i];
}
bsearch(0,1,n);
for(int i=1;i<=n;i++) cout<<re[i]<<" ";
cout<<endl;
}
return 0;
}
E. Accidental Victory
题意
n个人在玩游戏，代币多的会胜过代币少的，平局则随机选择一方获胜，并且胜利一方获得失败一方的代币，只有一个人有代币的时候，有代币的那个人胜利，输出所有可能胜利的人。
题解
按照代币数量排序之后，求前缀和。如果i的前缀和小于i，则i前面的都不可能获胜，记录最后一个前缀和大于自己的人，则这个人之后的人都可能获胜。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll n;
cin>>n;
vector<pair<ll,ll> > m;
pair<ll,ll> s;
for(int i=0;i<n;i++){
cin>>s.first;
s.second=i;
m.push_back(s);
}
sort(m.begin(),m.end());
vector<ll> re;
ll sum=m[0].first,mx=-1;
for(int i=1;i<n;i++){
if(sum>=m[i].first&&mx==-1) mx=i-1;
else if(mx!=-1&&sum<m[i].first) mx=-1;
sum+=m[i].first;
}
if(mx==-1) mx=n-1;
//cout<<mx<<endl;
for(int i=mx;i<n;i++) re.push_back(m[i].second);
sort(re.begin(),re.end());
cout<<re.size()<<endl;
for(int i=0;i<re.size();i++) cout<<re[i]+1<<" ";
cout<<endl;
}
return 0;
}
F. Equalize the Array
题意
给出一个数组，你可以移除任意个数，使得数组中每个数字都出现c次，你需要让移除的数最少。
题解
我们先统计数字个数，排序。例如[1,3,2,1,4,2,2]，为数组l[3,2,1,1] (3个2，2个1，1个3，1个4）。统计前缀个数，移除数量为n-i*l[i-1]（这里和以下的i为l下标，从0开始）。
更详细一点，当数字个数发生变化时，当前个数的的数字全部保留，没到当前个数的要全部删掉，多余的也要删除到当前个数。所以数组中存在i个l[i-1]个数，需要删掉n-i*l[i-1]个数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
void swap(ll* a, ll* b) {
int swapp = *a;
*a = *b;
*b = swapp;
}
ll max(ll a, ll b) {
if (a > b) return a;
return b;
}
ll min(ll a, ll b) {
if (a < b) return a;
return b;
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int n,s;
cin>>n;
vector<int> num;
for(int i=0;i<n;i++){
cin>>s;
num.push_back(s);
}
sort(num.begin(),num.end());
vector<int> l;
int last=num.front(),nums=1;
ll sum=0;
for(int i=1;i<num.size();i++){
if(last==num[i]) nums++;
else{
l.push_back(nums);
nums=1;
last=num[i];
}
}
l.push_back(nums);
sort(l.rbegin(),l.rend());
ll re=lmax,bak=1;
for(int i=1;i<l.size();i++){
if(last!=l[i]){
re=min(re,n-i*l[i-1]);
//cout<<"re"<<re<<endl;
}
bak++;
}
re=min(re,n-l.size()*l.back());
cout<<re<<endl;
}
return 0;
}
