文章目录
Codeforces Round #702 (Div. 3)
A. Dense Array
链接
题意：如果序列 a的任意相邻两项中，较大者不大于较小者的二倍，则 Polycarp 称 a 是一个密集序列。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int all[N] ;
int T , n ;
int main()
{
cin>>T;
while(T --)
{
cin>>n;
for(int i = 0 ; i < n ; i ++) cin>>all[i];
int res = 0 ;
for(int i = 0 ; i < n - 1 ; i ++)
{
int aa = min(all[i] , all[i + 1]);
int bb = max(all[i] , all[i + 1 ]);
while(aa * 2 < bb )
{
aa *=2;
res ++ ;
}
}
cout<<res<<endl;;
}
return 0 ;
}
B. Balanced Remainders
链接
题意：
本题有 t 组数据。
有一个长度为 n 的非负整数序列。
每次操作你可以选择一个元素并将其加 1，问最少需要多少次操作，可以使得序列中对 3 取模分别等于 0、1、2 的元素个数相等。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3 * 10e4 + 10;
int all[N],c1 , c2 , c0, t , n,res;
int main()
{
cin>>t;
while(t--)
{
c1 = 0 , c0 = 0 ,c2 = 0,res= 0 ;
cin>>n;
for(int i = 0 ; i < n ; i ++) cin >>all[i];
for(int i = 0 ; i < n ; i++ )
{
if(all[i] % 3 ==0 ) c0++;
else if(all[i] % 3 == 1) c1++;
else c2++;
}
while(c2 != c1 || c1 != c0 || c0 != c1 )
{
if(c2 >=c1 && c2 >=c0) c2--,c0++;
else if(c1 >= c2 && c1 >= c0) c1--,c2++;
else c0--,c1++;
res++;
}
cout<<res<<endl;
}
return 0;
}
C. Sum of Cubes
链接
题意:给您一个正整数 x ，问这个正整数能否拆分成两个立方数之和。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
map<long long , long long >p;
for(long long i = 1 ; i <= 10000 ; i ++)
{
p[i * i * i ] = 1 ;
}
long long T , n ;
cin>>T ;
while(T-- )
{
cin>>n ;
int ok = 0 ;
for(long long i = 1 ; i <= 10000 ; i ++)
{
if(p[n - i * i * i ] == 1 )
{
ok = 1 ;
break;
}
}
if(ok == 1 ) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0 ;
}
D. Permutation Transformation
链接
题意：
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int all[N] , p[N];
int T , n ;
void find(int l , int r , int v)
{
if(l > r) return;
int maxx = - 1, w;
for(int i = l ; i <= r ; i ++ )
{
if(all[i] > maxx)
{
maxx = all[i] ;
w = i ;
}
}
p[w] = v;
find(l , w - 1 , v+ 1 ) ;
find(w + 1 , r , v + 1 );
}
int main()
{
cin>>T;
while(T -- )
{
cin>>n;
for(int i = 0 ; i < n ; i ++) cin>>all[i] ;
int maxx = -1, w ;
for(int i = 0 ; i < n ; i ++)
{
if(maxx < all[i])
{
maxx = all[i] ; w = i ;
}
}
memset(p , -1, 0 ) ;
p[w] = 0 ;
find(0 , w - 1 , 1) , find(w + 1 , n - 1 , 1) ;
for(int i = 0 ; i < n ; i ++) cout<<p[i] <<" " ;
cout<<endl;
}
return 0 ;
}
E. Accidental Victory
链接
题意：
有 n 支队伍参加比赛，每个队伍初始时有一些代币。
比赛每一轮随机挑两个代币数不为0的队伍，然后代币多的队伍获胜，代币少的队伍把代币全部给代币多的（代币数量相同则随机），直到最后只有一个队伍有代币， 这个队伍获胜。
求哪些队伍是有可能获胜的。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
long long all[N] , a[N] , b[N];
long long ok[N] ;
long long T;
long long n;
int check()
{
for(long long i = n - 1 ; i >=1 ; i -- )
{
// cout<<a[i + 1 ] <<b[i ]<<endl;
if(a[i + 1 ] > b[i]) return i;
}
return -1 ;
}
int main()
{
scanf("%lld" , &T) ;
while(T -- )
{
memset(a , 0 , sizeof a );
memset(b , 0 , sizeof b );
memset(ok , 0 , sizeof ok );
scanf("%lld" , &n );
for(long long i = 1 ; i <= n ; i ++ )
{
scanf("%lld" , &all[i]);
a[i] = all[i];
}
sort(a+ 1 , a + n+ 1 ) ;
map<long long , long long > p;
for(int i = 1 ; i <= n ; i ++)
{
p[a[i]] = i ;
}
for(long long i = 1 ; i <= n ; i ++) b[i] = b[i - 1 ] + a[ i];
long long k =check();
//cout<<"k:"<<k<<endl;
if(k == -1)
{
cout<<n <<endl;
for(int i = 1 ; i <= n ; i ++) cout<<i<<" " ;
cout<<endl;
}
else {
long long kk = a[k];
cout << n - k <<endl;
for(int i = 1 ; i <= n ; i ++)
{
if(all[i] >kk) cout<<i<<" " ;
}
cout<<endl;
}
}
return 0 ;
}
F. Equalize the Array
链接
题意：
本题有 t组数据。
每组数据给出一个长度为 n 的序列，问最少需要删除多少个元素，才可以使得剩余的序列中，所有不同数字出现的次数均相等。
代码
#include <bits/stdc++.h>
using namespace std;
int T , n ;
int main()
{
cin>>T;
int k ;
while(T -- )
{
map<int , int>p;
cin>>n;
int f = 0;
for(int i = 0 ; i < n ;i ++ )
{
cin>>k;
if(!p[k]) p[k] = 1 ;
else p[k] ++ ;
}
map<int ,int > pp;
for(auto t :p)
{
if(!pp[t.second]) pp[t.second]= 1 ,f++;
else pp[t.second] ++ ;
}
int res = 0 ,sum = -1 ;
int i = 1 ;
for(auto t :pp)
{
//cout<<t.second << " "<<t.first <<" "<<f - i <<endl;
int summ = t.second*t.first ;
for(auto tt :pp)
{
if(tt.first > t.first )
{
summ += t.first*tt.second;
}
}
sum = max(sum , summ );
}
cout<<n - sum <<endl;
}
return 0;
}