JZTXT

Codeforces Round 697 (Div. 3)

发布时间 2023-11-22 21:47:18作者: PHarr

A. Odd Divisor

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n;cin>>n;
    while(n%2==0)n/=2;
    if(n==1)cout<<"NO\n";
    else cout<<"YES\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

B. New Year's Number

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n;cin>>n;
    int cnt=n/2020;
    n%=2020;
    if(n>cnt)cout<<"NO\n";
    else cout<<"YES\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

C. Ball in Berland

简单的的容斥一下，先统计每个点连接的边的数量，然后枚举每一条边，容斥掉所有与他相邻的边即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int a,b,k;cin>>a>>b>>k;
    vector<int>cnt(a+b+5,0);
    vector<PII>ve(k);
    for(int i=0,x;i<k;++i){
        cin>>x;
        ve[i].first=x;
        cnt[x]++;
    }
    for(int i=0,x;i<k;++i){
        cin>>x;
        ve[i].second=x+a;
        cnt[x+a]++;
    }
    int ans=0;
    for(int i=0;i<k;++i){
        ans+=k-cnt[ve[i].first]-cnt[ve[i].second]+1;
    }
    cout<<ans/2<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

D. Cleaning the Phone

这道题因为\(b\)的取值只有两种，首先把所有的手机按照\(b\)分类，对于每一种我们其实都可以谈心的选择\(a\)更大的，所有直接排序，然后求前缀和，这样枚举其中\(b=1\)的选多少个，可以直接二分出\(b=2\)的应该选多少个，这样就可以计算出最优解。

#include<bits/stdc++.h>

using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;
const int N = 1e5 + 5, INF = 0x3f3f3f3f, Mod = 1e9 + 7, mod = 998244353;
const double eps = 1e-6;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)cin >> a[i];
    vector<int> f2, f1;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        if (x == 1)f1.push_back(a[i]);
        else f2.push_back(a[i]);
    }

    if (accumulate(a.begin(), a.end(), 0ll) < m) {
        cout << "-1\n";
        return;
    }
    int ans = 1e9;
    sort(f1.begin(), f1.end(), greater<int>());
    sort(f2.begin(), f2.end(), greater<int>());
    for (int i = 1; i < f1.size(); ++i)f1[i] += f1[i - 1];
    for (int i = 1; i < f2.size(); ++i)f2[i] += f2[i - 1];
    for (int i = 0; i < f1.size(); ++i) {
        int c = m - f1[i];
        if (c <= 0) {
            ans = min(ans, i + 1);
            break;
        }
        if (f2.empty() or f2.back() < c) continue;
        int t = lower_bound(f2.begin(), f2.end(), c) - f2.begin();
        ans = min(ans, i + 2 * t + 3);
    }
    if (!f2.empty() and f2.back() >= m) {
        int t = lower_bound(f2.begin(), f2.end(), m) - f2.begin();
        ans = min(ans, t * 2 + 2);
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
//    init();
    while (T--) {
        solve();
    }
    return 0;
}

E. Advertising Agency

先不考虑方案数，我们其实可以贪心的直接选粉丝最多的。

然后对于多个粉丝一样多的有三种情况

  1. 全部都选
  2. 全部都不选
  3. 选一部分

可以发现，多种方案数发生的情况只有 3 一种，且最多只会有一种粉丝数量的博主。所以贪心找到然后组合数算一下就好了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
int pow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%Mod;
        x=x*x%Mod;
        y>>=1;
    }
    return res;
}
int inv(int x){return pow(x,Mod-2);}
int C(int x,int y){
    y=min(y,x-y);
    int res=1;
    for(int i=x,j=1;j<=y;--i,++j)res=res*i%Mod*inv(j)%Mod;
    return res;
}
void solve() {
    int n,k;cin>>n>>k;
    map<int,int>mp;
    for(int i=0,x;i<n;++i){
        cin>>x;
        mp[-x]++;
    }
    for(auto [x,y]:mp){

        if(y<k)k-=y;
        else{
            cout<<C(y,k)<<'\n';
            return ;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

F. Unusual Matrix

首先把其实状态和最终状态做异或，然后把新得到的矩阵变成全 0 即可

首先可以通过翻转列的形式暴力把第一行翻转为全 0 的，然后只需判断剩下的行是否是全 0 或全 1就好

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int NN=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n;cin>>n;
    vector<string>ve(n);
    for(int i=0;i<n;++i)cin>>ve[i];
    string s;
    for(int i=0;i<n;++i){
        cin>>s;
        for(int j=0;j<n;++j)ve[i][j]='0'+(int)(s[j]!=ve[i][j]);
    }
    for(int i=0;i<n;++i){
        if(ve[0][i]!='1'){
            for(int j=0;j<n;++j){
                if(ve[j][i]=='0')ve[j][i]='1';
                else ve[j][i]='0';
            }
        }
    }
    bool ok=true;
    for(int i=1;i<n;++i){
        for(int j=1;j<n;++j){
            if(ve[i][j]!=ve[i][j-1]){
                ok=false;break;
            }
        }
        if(!ok)break;
    }
    if(ok)cout<<"YES\n";
    else cout<<"NO\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

G. Strange Beauty

\(f[x]\)是选择一个满足条件的集合，且最大的数是\(x\)最多可以放多少个数，那么集合中的数字一定都是\(x\)的因子，如果在继续加数字，只要满足是\(x\)的倍数就是集合中所有数字的倍数。

显然对于每个数字如果选择肯定是全部都选最优，所以可以统计\(cnt[x]\)表示\(x\)出现的次数

那么转移方程就是\(f[x]= cnt[x] + max( f[y])\)其中\(y\)是\(x\)的因子，这样的话全局\(max(f[x])\)就是能够选择最多的数字，在这种情况下\(n-max(f[x])\)就是删除的最少的数字

但是现在这种转移方程我们需要枚举因子因此复杂度是\(O(n\sqrt n)\)，无法通过

其实优化方式非常简单，只要变成枚举倍数复杂度是就变成了\(O(n\ln n)\)，再随便加一点优化就好了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n;cin>>n;
    vector<int>cnt(N),f(N);
    for(int i=0,x;i<n;++i)cin>>x,cnt[x]++;
    for( int i = 1 ; i < N ; i ++ ){
        f[i] += cnt[i];
        for( int j = i + i ; j < N ; j += i ) f[j] = max( f[j] , f[i] );
    }
    cout << n - *max_element(f.begin(), f.end()) << "\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}