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

2021-01-28 12:30:07

## 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,y,num1,num2,ans;
struct p{

ll a;
ll b;
}c;
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;
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;
}
``````

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,b,c,ans,sum,fac,inv;
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=fac=inv=inv=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,b;
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]!=b[i]) for(int j=1;j<=n;j++) a[i][j]^=1;
}
for(int j=2;j<=n;j++){

if(a[j]==b[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,f,num,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;
}
``````

https://chowdera.com/2021/01/20210128121154517I.html