文章目錄

• Codeforces Round #702 (Div. 3)
• • A. Dense Array
  • B. Balanced Remainders
  • C. Sum of Cubes
  • D. Permutation Transformation
  • E. Accidental Victory
  • F. Equalize the Array

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;
}