• Codeforces Round #803 (Div. 2) A-D && 组合数学 day14

     A

    暴力没啥好说的

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 110;
    4. const int M = 1e4+10;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define inf 0x3f3f3f3f3f3f3f3f
    10. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    11.  
    12. signed main(){
    13.     fast
    14.     int t;cin>>t;
    15.     while(t--){
    16.         int a[N];
    17.         int n;cin>>n;
    18.         for(int i=0;i<n;i++)cin>>a[i];
    19.         for(int i=0;i<n;i++){
    20.             int sum=0;
    21.             for(int j=0;j<n;j++){
    22.                 if(j==i)continue;
    23.                 sum^=a[j];
    24.             }
    25.             if(sum==a[i]){
    26.                 cout<<a[i]<<endl;
    27.                 goto out;
    28.             }
    29.         }
    30.         out:1;
    31.     }
    32.     return 0^0;
    33. }

    B

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10;
    4. const int M = 1e4+10;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define inf 0x3f3f3f3f3f3f3f3f
    10. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    11. int a[N];
    12. signed main(){
    13.     fast
    14.     int t;cin>>t;
    15.     while(t--){
    16.         int n,m;cin>>n>>m;
    17.         for(int i=1;i<=n;i++){
    18.             cin>>a[i];
    19.         }
    20.         int cnt=0;
    21.         for(int i=2;i<=n;i++){
    22.             if(i!=n&&a[i-1]+a[i+1]<a[i])cnt++;
    23.         }
    24.         if(n<=2){
    25.             cout<<0<<endl;
    26.             continue;
    27.         }
    28.         if(m==1&&n%2){
    29.             cout<<n/2<<endl;
    30.             continue;
    31.         }else if(m==1&&n%2==0){
    32.             cout<<n/2-1<<endl;
    33.             continue;
    34.         }
    35.         cout<<cnt<<endl;
    36.     }
    37.     return 0^0;
    38. }

    C

    三和四的时候都要特判把 其他没啥好说的 m 分 1 和 多就是了

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10;
    4. const int M = 1e4+10;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define inf 0x3f3f3f3f3f3f3f3f
    10. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    11. int a[N];
    12. signed main(){
    13.     fast
    14.     int t;cin>>t;
    15.     while(t--){
    16.         int n;cin>>n;
    17.         vector<int>cnt;
    18.         for(int i=1;i<=n;i++){
    19.             cin>>a[i];
    20.             if(a[i])cnt.push_back(a[i]);
    21.         }
    22.         if(n==3&&cnt.size()==3){
    23.             int sum=a[1]+a[2]+a[3];
    24.             if(sum==a[3]||sum==a[1]||sum==a[2])cout<<"Yes"<<endl;
    25.             else cout<<"No"<<endl;
    26.             continue;
    27.         }
    28.         set<int>s;
    29.         if(n==4&&cnt.size()==4){
    30.             for(int i=1;i<=4;i++)s.insert(a[i]);
    31.             for(int i=1;i<=4;i++){
    32.                 for(int j=i+1;j<=4;j++){
    33.                     for(int k=j+1;k<=4;k++){
    34.                         if(s.count(a[i]+a[j]+a[k])==0){
    35.                             cout<<"No"<<endl;
    36.                             goto out;
    37.                         }
    38.                     }
    39.                 }
    40.             }
    41.             cout<<"Yes"<<endl;
    42.             out:1;
    43.             continue;
    44.         }
    45.         if(cnt.size()<=1)cout<<"Yes"<<endl;
    46.         else if(cnt.size()==2){
    47.             if(cnt[1]+cnt[0]==0)cout<<"Yes"<<endl;
    48.             else cout<<"No"<<endl;
    49.         }else cout<<"No"<<endl;
    50.     }
    51.     return 0^0;
    52. }

     D

    题意明显 只交换一次 那么我们只有一个数 会在正确的位置

    那我们就可以二分判断 要是有偶数个数他在他应该在的区间内 那么我们就 不应该会有ans在里面

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 2e5+10;
    4. const int M = 1e4+10;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define inf 0x3f3f3f3f3f3f3f3f
    10. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    11. signed main(){
    12.     int t;cin>>t;
    13.     while(t--){
    14.         int n;cin>>n;
    15.         int l=1,r=n;
    16.         while(l<=r){
    17.             if(l==r){
    18.                 printf("! %d\n",l);
    19.                 fflush(stdout);
    20.                 break;
    21.             }
    22.             int mid=(l+r)/2;
    23.             printf("? %d %d\n",l,mid);
    24.             fflush(stdout);
    25.             int cnt=0;
    26.             for(int i=l;i<=mid;i++){
    27.                 int s;cin>>s;
    28.                 if(s<l||s>mid)cnt++;
    29.             }
    30.             if((mid-l-cnt+1)%2==1)r=mid;
    31.             else l=mid+1;
    32.         }
    33.     }
    34.     return 0^0;
    35. }

     885. 求组合数 I

    预处理+dp

    #include<bits/stdc++.h>
    using namespace std;
    const int mod =1e9+7;
    const int N = 2010;
    int c[N][N];
    int main(){
        for(int i=0;i<=2000;i++){
            for(int j=0;j<=i;j++){
                if(!j)c[i][j]=1;
                else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
            }
        }
        int n;cin>>n;
        while(n--){
            int a,b;cin>>a>>b;
            cout<<c[a][b]<<endl;
        }
        return 0;
    }

    886. 求组合数 II

    还是预处理+乘法逆元

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5+10;
    const int M = 1e4+10;
    const int mod = 1e9+7;
    #define int long long
    #define endl '\n'
    #define Endl '\n'
    #define inf 0x3f3f3f3f3f3f3f3f
    #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    int a[N],b[N];
    int qmi(int a,int k,int p){
        int res=1;
        while(k){
            if(k&1)res=(res*a)%p;
            k>>=1;
            a=a*a%p;
        }
        return res;
    }
    signed main(){
        fast
        a[0]=b[0]=1;
        for(int i=1;i<=1e5;i++){
            a[i]=(a[i-1]*i)%mod;
            b[i]=b[i-1]*qmi(i,mod-2,mod)%mod;
        }
        int t;cin>>t;
        while(t--){
            int x,y;cin>>x>>y;
            cout<<a[x]*b[y]%mod*b[x-y]%mod<<endl;
        }
        return 0^0;
    }

     887. 求组合数 III

    lucas定理+乘法逆元

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5+10;
    const int M = 1e4+10;
    const int mod = 1e9+7;
    #define int long long
    #define endl '\n'
    #define Endl '\n'
    #define inf 0x3f3f3f3f3f3f3f3f
    #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    int p;
    int qmi(int a,int k){
        int res=1;
        while(k){
            if(k&1)res=res*a%p;
            a=a*a%p;
            k>>=1;
        }
        return res;
    }
    int C(int a,int b){
        int res=1;
        for(int i=a,j=b;j;i--,j--){res=res*i%p*qmi(j,p-2)%p;}
        return res;
    }
    int lucas(int a,int b){
        if(a<p&&b<p)return C(a,b);
        else return C(a%p,b%p)*lucas(a/p,b/p)%p;
    }
    signed main(){
        fast
        int t;cin>>t;
        while(t--){
            int a,b;cin>>a>>b>>p;
            cout<<lucas(a,b)<<endl;
        }
        return 0^0;
    }

     888. 求组合数 IV

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 5000+10;
    const int M = 1e4+10;
    const int mod = 1e9+7;
    #define int long long
    #define endl '\n'
    #define Endl '\n'
    #define inf 0x3f3f3f3f3f3f3f3f
    #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    int prime[N],cnt,sum[N];
    bool st[N];
    void get_prime(int n){
        for(int i=2;i<=n;i++){
            if(!st[i])prime[cnt++]=i;
            for(int j=0;prime[j]<=n/i;j++){
                st[prime[j]*i]=true;
                if(i%prime[j]==0)break;
            }
        }
    }
    vector<int> mul(vector<int>(A),int b){
        vector<int> C;
        int t=0;
        for(int i=0;i<A.size();i++){
            t+=A[i]*b;
            C.push_back(t%10);
            t/=10;
        }
        while (t)
        {
            C.push_back(t % 10);
            t /= 10;
        }
        return C;
    }
    int get(int n,int p){
        int res=0;
        while(n){
            res+=n/p;
            n/=p;
        }
        return res;
    }
    signed main(){
        fast
        int a,b;cin>>a>>b;
        get_prime(a);
        for(int i=0;i<cnt;i++){
            int p=prime[i];
            sum[i]=get(a,p)-get(b,p)-get(a-b,p);
        }
        vector<int>res;
        res.push_back(1);
        for(int i=0;i<cnt;i++){
            for(int j=0;j<sum[i];j++){
                res=mul(res,prime[i]);
            }
        }
        for(int i=res.size()-1;i>=0;i--)cout<<res[i];
        return 0^0;
    }

     889. 满足条件的01序列

    卡特兰数

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 5000+10;
    const int M = 1e4+10;
    const int mod = 1e9+7;
    #define int long long
    #define endl '\n'
    #define Endl '\n'
    #define inf 0x3f3f3f3f3f3f3f3f
    #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    int qmi(int a,int k,int p){
        int res=1;
        while(k){
            if(k&1)res=res*a%p;
            a=a*a%p;
            k>>=1;
        }
        return res;
    }
    signed main(){
        fast
        int n;cin>>n;
        int a=n<<1,b=n;
        int ans=1;
        for(int i=a,j=b;j;i--,j--){
            ans=ans*i%mod*qmi(j,mod-2,mod)%mod;
        }
        cout<<ans*qmi(b+1,mod-2,mod)%mod<<endl;
        return 0^0;
    } 

  • 相关阅读:
    Windows环境下的ELK——Logstash+Mysql（4）
    vue3中axios的使用方法
    阿里云服务器的介绍和使用
    会计制度设计名词解释大全
    leetcode1221. 分割平衡字符串
    谷歌版ChatGPT与旗下邮箱、视频、地图等，实现全面集成！
    字节码进阶之JSR269详解
    CEPH-1：ceph-deploy离线部署ceph集群及报错解决FAQ
    POJ 3279 Fliptile 反转 + 点灯游戏
    07 【数组及常用方法】
  • 原文地址：https://blog.csdn.net/qq_23852555/article/details/125512706