当前位置:网站首页>Code works round 697 (Div. 3) (Unrated for Div. 3)

Code works round 697 (Div. 3) (Unrated for Div. 3)

2021-01-28 12:30:07 osc_ f9krav3q

Topic link :https://codeforces.com/contest/1475

A.Odd Divisor

number theory
The topic is to judge n Is there an odd factor .
Consider the unique decomposition theorem ,n Of all the qualitative factors, only 2 For the even , remove n The prime factor of contains only 2, namely n by 2 In this case , rest n All meet the criteria .

#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
ll _,n;
int main(){
   
   
	scanf("%lld",&_);
	while(_--){
   
   
		scanf("%lld",&n);
		if(n&1) printf("YES\n");
		else{
   
   
			while(n>1&&n%2==0) n>>=1;
			if(n>1) printf("YES\n");
			else printf("NO\n");
		}
	}
	return 0;
}

B.New Year’s Number

mathematics
The solution requires judgment n Can it be broken down into several 2020 And 2021 And .
2021 by 2020+1, To calculate the n/2020 And n%2020 Result ,n/2020 That is to say n It can be broken down into 2020 The number of ,n%2020 by n The number left after decomposition , if n%2020 Less than or equal to n/2020, You can put the extra n%2020 Evenly distributed to 2020 On , constitute 2021, Meet the conditions , if n%2020 Greater than n/2020, It doesn't meet the conditions .

#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
ll _,n,a,b;
int main(){
   
   
	scanf("%lld",&_);
	while(_--){
   
   
		scanf("%lld",&n);
		a=n/2020;
		b=n%2020;
		if(b<=a) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

C.Ball in Berland

mathematics
Choose two pairs of combinations , No one can be in two groups at the same time , Find the number of feasible solutions .
Use two arrays to record the number of times men and women appear in the combination , Go through all the combinations again , Subtract the total number of people in the current group from the total number of people , The number of conflicting groups , Finally, add yourself . It turns out that long long Storage .

#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
ll _,a,b,k,x[200010],y[200010],num1[200010],num2[200010],ans;
struct p{
   
   
	ll a;
	ll b;
}c[200010];
bool cmp(p x,p y){
   
   
	return x.a<y.a;
}
int main(){
   
   
	scanf("%lld",&_);
	while(_--){
   
   
		ans=0;
		scanf("%lld%lld%lld",&a,&b,&k);
		for(ll i=1;i<=a;i++) num1[i]=0;
		for(ll i=1;i<=b;i++) num2[i]=0;
		for(ll i=1;i<=k;i++){
   
   
			scanf("%lld",&c[i].a);
			num1[c[i].a]++;
		}
		for(ll i=1;i<=k;i++){
   
   
			scanf("%lld",&c[i].b);
			num2[c[i].b]++;
		}
		for(ll i=1;i<=k;i++)
			ans+=k-num1[c[i].a]-num2[c[i].b]+1;
		printf("%lld\n",ans/2);
	}
	return 0;
}

D.Cleaning the Phone

greedy , Sort
Choose the right application , So that at least m The convenience value of simultaneous removal is the smallest .
It's like a backpack , But the time and space complexity of using knapsack to solve the problem can not meet the demand .
The positive solution is as follows :
First of all, if the total memory occupied by all applications is less than m There is no solution. .
According to the convenience value, the application is 1 or 2 Sort in descending order , The priority value is 1 Application , If the free memory is greater than or equal to m, Then output the current result directly . If the convenience value is 1 The selected application still does not meet the requirements , And then select in the sorted order 2, And in the selection process will continue to be more than 1 The app kicks out the app that will be removed , Record the minimum value continuously during the process , Finally, output .




#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
ll _,n,m,suma,sumb,pos1,pos2,tot,ans,sum; 
struct p{
   
   
	ll a;
	ll b;
}a[200010];
bool cmp(p x,p y){
   
   
	if(x.b!=y.b) return x.b<y.b;
	return x.a>y.a;
}
int main(){
   
   
	scanf("%lld",&_);
	while(_--){
   
   
		suma=sumb=tot=ans=sum=0;
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++){
   
   
			scanf("%lld",&a[i].a);
			suma+=a[i].a;
		}
		for(ll i=1;i<=n;i++){
   
   
			scanf("%lld",&a[i].b);
			sumb+=a[i].b;
		}
		if(suma<m) printf("-1\n");
		else{
   
   
			sort(a+1,a+1+n,cmp);
			pos1=1;pos2=n+1;
			for(ll i=1;i<=n;i++){
   
   
				if(a[i].b==2){
   
   
					pos2=i;
					break;
				}
			}
			ll i;
			for(i=1;i<pos2;i++){
   
   
				tot+=a[i].a;
				ans+=a[i].b;
				if(tot>=m) break;
			}
			if(i==pos2) i--;
			sum=ans;
			if(tot<m) ans=1e15;
			for(ll j=pos2;j<=n;j++){
   
   
				tot+=a[j].a;
				sum+=a[j].b;
				while(tot-a[i].a>=m&&i>=1){
   
   
					tot-=a[i].a;
					sum-=a[i].b;
					i--;
				}
				if(tot>=m) ans=min(ans,sum);
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

E.Advertising Agency

Combinatorial mathematics , Sort
The title means from n Choose from the number of k individual , I'm looking for k The maximum number of schemes is the sum of the number of schemes .
First record the number of times all numbers appear , Second, sort the input data , Choose the largest k Number , And record this k The number of times each number is selected , After from 1-n Traverse all numbers , Using the formula of combination number, we can get the sum .

#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
ll _,n,k,a[1010],b[1010],c[1010],ans,sum,fac[1010],inv[1010];
const ll mod=1e9+7;
ll pow(ll a,ll b){
   
   
	ll sum=1;
	while(b){
   
   
		if(b&1) sum=sum*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return sum;
}
void init(){
   
   
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(ll i=2;i<=1000;i++){
   
   
		fac[i]=i*fac[i-1]%mod;
		inv[i]=pow(fac[i],mod-2);
	}
}
int main(){
   
   
	init();
	scanf("%lld",&_);
	while(_--){
   
   
		ans=1;
		scanf("%lld%lld",&n,&k);
		for(ll i=1;i<=n;i++) b[i]=c[i]=0;
		for(ll i=1;i<=n;i++){
   
   
			scanf("%lld",&a[i]);
			b[a[i]]++;
		}
		sort(a+1,a+1+n);
		for(ll i=n;i>=n-k+1;i--) c[a[i]]++;
		for(ll i=1;i<=n;i++){
   
   
			sum=((fac[b[i]]*inv[c[i]])%mod*inv[b[i]-c[i]]%mod)%mod;
			ans=ans*sum%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

F.Unusual Matrix

greedy
The idea is to let you judge the matrix A Whether the matrix can be obtained by XOR operation of row and column B.
First traverse the number in the leftmost column , if A And B Different in , Then XOR the whole line of elements , There should be no more XOR operations after traversal , therefore , Start with the second column , Now the matrix A And matrix B Elements in the same column should be all equal or all opposite , If there is a conflict , Then the matrix A You can't get to the matrix by transformation B.

#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
int _,n,a[1010][1010],b[1010][1010];
bool ok;
int main(){
   
   
	scanf("%d",&_);
	while(_--){
   
   
		ok=true;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) scanf("%1d",&a[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) scanf("%1d",&b[i][j]);
		for(int i=1;i<=n;i++){
   
   
			if(a[i][1]!=b[i][1]) for(int j=1;j<=n;j++) a[i][j]^=1;
		}
		for(int j=2;j<=n;j++){
   
   
			if(a[1][j]==b[1][j]){
   
   
				for(int i=1;i<=n;i++) if(a[i][j]!=b[i][j]){
   
   
					ok=false;
					break;
				}
			}
			else{
   
   
				for(int i=1;i<=n;i++) if(a[i][j]==b[i][j]){
   
   
					ok=false;
					break;
				}
			}
		}
		if(ok) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

G.Strange Beauty

DP, number theory
To find out at least a few numbers can be deleted so that all the numbers in the sequence can be divided by one side .
At first I imitated DP The method of not descending subsequence , But the time complexity of doing that is O(n2), Obviously it's going to be overtime .
When we input data, we first count the number of times each number appears num[i], Using arrays f[i] Denote by number i Is the number of digits in the sequence of the maximum value , Then the corresponding transfer equation is :f[i]=num[i]+max(f[a1],f[a2],f[a3],…,f[ak]), among i%aj==0(1<=j<=k).
From numbers 1 Start enumerating to 200000, On the way i All multiples of j Of f[j] All values are consistent with f[i] Taking the maximum .



#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
int _,n,a[200010],f[200010],num[200010],ans;
int main(){
   
   
	scanf("%d",&_);
	while(_--){
   
   
		ans=0;
		scanf("%d",&n);
		memset(num,0,sizeof(num));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
   
   
			scanf("%d",&a[i]);
			num[a[i]]++;
		}
		for(int i=1;i<=200000;i++){
   
   
			f[i]+=num[i];
			for(int j=2*i;j<=200000;j+=i) f[j]=max(f[j],f[i]);
		}
		for(int i=1;i<=200000;i++) ans=max(ans,f[i]);
		printf("%d\n",n-ans);
	}
	return 0;
}

版权声明
本文为[osc_ f9krav3q]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210128121154517I.html