題目鏈接：https://codeforces.com/contest/1475
文章目錄
- A.Odd Divisor
- B.New Year's Number
- C.Ball in Berland
- D.Cleaning the Phone
- E.Advertising Agency
- F.Unusual Matrix
- G.Strange Beauty
A.Odd Divisor
數論
題目大意為判斷n是否有奇數因子，
考慮唯一分解定理，n的所有質因子中只有2為偶數，除去n的質因子只包含2，即n為2的正整數次冪這一情況，其余n都符合判定條件，
#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
數學
題解要求判斷n能否分解為若干個2020與2021的和，
2021為2020+1，計算出n/2020與n%2020的結果，n/2020即為n可以分解出的2020的個數，n%2020為n分解后余下的數，若n%2020小于等于n/2020，則可以將多出來的n%2020平均分配到2020上，構成2021，滿足條件，若n%2020大于n/2020，則不符合條件，
#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
數學
題意要求選出兩對組合，要求不能有一個人同時在兩組，求可行的方案數，
利用兩個陣列記錄男女在組合中出現的次數，再遍歷一遍所有組合，用總人數減去當前組的人物編號總共出現的次數，即沖突的組數，最后要加上自己，結果要開long long存盤，
#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
貪心，排序
題意為選出符合條件的應用，使得最少釋放m的空間的同時去除的便利值最小，
這道題很像背包，但利用背包求解的時間與空間復雜度都滿足不了，
正解如下：
首先若所有應用所占記憶體總和小于m則無解，
將應用根據便利值為1或2分別降序排序，優先去除便利值為1的應用，若在去除程序中出現釋放記憶體大于等于m，則直接輸出當前結果，若便利值為1的應用選取完仍然不滿足要求，再按排序后的順序選取2，并在選取程序中不斷將多于的1應用踢出將要去除的應用中，程序中不斷記錄最小值，最后輸出即可，
#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
組合數學，排序
題意為從n個數中選取k個，求取出的k個數之和最大的方案數，
首先記錄所有數出現的次數，其次對輸入資料進行排序，選取最大的k個數，并記錄這k個數中每個數被選取的次數，之后從1-n遍歷所有數，利用組合數公式求和即可，
#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
貪心
題意是讓你判斷矩陣A通過行列的異或運算能否得到矩陣B，
首先遍歷最左一列的數字，若A與B中的不同，則對一整行元素進行異或運算，遍歷完之后應該不會有更多行異或的操作，因此，從第二列開始遍歷，此時矩陣A與矩陣B在同一列中的元素應該全部相等或者全部相反，若出現矛盾，則矩陣A不能通過變換到達矩陣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，數論
題意為求出至少刪去幾個數能使得數列中的所有數兩兩之間能被一方整除，
一開始我是仿照DP求不下降子列的方法做的，但那樣做的時間復雜度為O(n2)，顯然會超時，
我們在輸入資料時先統計出每個數字出現的次數num[i]，用陣列f[i]表示以數字i為最大值的數列中的數字個數，則對應轉移方程為：f[i]=num[i]+max(f[a1],f[a2],f[a3],…,f[ak])，其中i%aj==0(1<=j<=k)，
從數字1開始列舉到200000，中途將i的所有倍數j的f[j]值都與f[i]取最大值，
#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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/253141.html
標籤：其他
上一篇：學習Software Testing的筆記（二）_測驗計劃
下一篇：談談我對協程的理解