首页 > 其他分享 >牛客多校2023 第三场

牛客多校2023 第三场

时间：2023-07-24 23:44:07浏览次数：31  
标签：cout int namespace 多校 long cin 牛客 include 第三场

A

签到，注意$0$的特判

#include <bits/stdc++.h>
using namespace std;
long long x,y;
int main(){
    string s1,s2;
    cin >> s1;
    cin >> s2;
    int Len1 = s1.length();
    int Len2 = s2.length();
    for (int i = 0 ; i < Len1 ; i ++)
        x = 2ll * x + s1[i]-'0';
    for (int i = 0 ; i < Len2 ; i ++)
        y = 2ll * y + s2[i]-'0';
    if (x == 0){
        if (y!=0) cout << "-1";
        else cout << "0";
        return 0;
    }
    cout << abs(x-y);
    return 0;
}

B

考虑问题的本质

实际上我们可以对于$>n$部分和$<n$部分分开讨论

$>n$部分来说，其实是需要构成一些下降段，对于$<n$部分来说，构成一堆上升段

假设划分了$k$段，则问题转化成把$n$个数的集合划分成$k$个组

显然是个第二类斯特林数

我们假设我们枚举了$i$段，其中有$x$段上升，$y$段下降

(x和y差值最大为1)

枚举共选了$a$个$b$个数

然后就可以用斯特林数算这部分方案了

然后再乘上$C(n,a)*C(n,b)$表示组合数

再乘上$x!y!$表示任意排列

$(2n-a-b)!$表示剩下的数随意排列

因为这题失败牌也算，所以要把失败牌的贡献加上，$(2n)!$

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int T;
int N,M;
int fac[706];
int S[505][505];
int C[505][505];
signed main(){
    cin >> T;
    while (T--){
        cin >> N >> M;
        for (int i = 0 ; i <= N+1 ; i ++){
            if ( i == 0 ) S[i][0] = 1; 
            for (int j = 1 ; j <= i ; j ++){
                S[i][j] = (S[i-1][j-1] + S[i-1][j] * j%M)%M;
            }
        }
        for (int i = 1 ; i <= N ; i ++){
            C[i][0] = 1;
            C[i][i] = 1;
            for (int j = 1 ; j < i ; j ++){
                C[i][j] = (C[i-1][j-1] + C[i-1][j])%M;
            }
        }
        fac[0] = 1;
        for (int i = 1 ; i <= 2*N ; i ++){
            fac[i] = fac[i-1] * i %M;
        }
        int ans = fac[2*N]%M;
        for (int i = 0 ; i <=N ; i ++){
            for (int j = 0 ; j <= 1 ; j ++){
                int x,y;
                if ( i == 0 && j == 0) continue; 
                if (j == 0) x = i,y = i;
                else x = i, y = i+1;
                for (int a = x ; a <= N ; a ++)
                    for (int b = y ; b <= N ; b ++){
                        if (a + b < 2*N){
                            ans = (ans + S[a][x] * S[b][y]%M*C[N][a]%M*C[N][b]%M*2ll%M*fac[2*N-a-b]%M*fac[x]%M*fac[y]%M)%M;
                        }
                    }
            }
        }
        cout << ans << endl; 
    }
    return 0;
}

D

发现第一列一定全是1或者第一行一定全是0

否则的话如果第一列和第一行都有0且有1的话，一定会有一些数第一列的1小于第一行的0

然后我们就得到了111111...1这样的列，行要都大于等于这个列

所以全1

全0同理

所以题目翻译一下就是把它转成全1/全0列

分类讨论模拟即可

#include <bits/stdc++.h>
using namespace std;
string ss[2005];
string ss1[2005];
int main(){
    int N;
    cin >> N;
    for (int i = 1 ; i <= N ; i ++){
        cin >> ss[i];
        ss1[i] = ss[i];
    }
    int cnt = 0;
    int cnt1 = 0;
    int cnt0 = 0;
    for (int i = 1 ; i <= N ; i ++){
        if (ss[i][0] == '1'){
            cnt++;
            for (int j = 0 ; j < N ;j ++){
                if (ss[i][j] == '1'){
                    ss[i][j] = '0';
                }else ss[i][j] = '1';
            }
        }
    }
    cnt0 = 1;
    cnt1 = 0;
    int ans = 1e9+7;
    for (int i = 1 ; i < N ; i ++){
        bool flag = false;
        for (int j = 1 ; j <= N ; j ++){
            if (j!=1 && ss[j][i] != ss[j-1][i]){
                flag = true;
            }
        }
        if (flag){
            cnt =1e9+7;
            break;
        }
        if (ss[1][i] == '1') cnt1 ++;
        else cnt0++;
    }
    if (cnt != 1e9+7){
        int ans1 = min(cnt0,cnt1) + cnt;
        ans = min(ans,ans1);
    }
    cnt = 0;
    for (int i = 1 ; i <= N ; i ++){
        if (ss1[i][0] == '0'){
            cnt ++;
            for (int j = 0 ; j < N ;j ++){
                if (ss1[i][j] == '1'){
                    ss1[i][j] = '0';
                }else ss1[i][j] = '1';
            }
        }
    } 
    cnt1 = 1;
    cnt0 = 0;
    for (int i = 1 ; i < N ; i ++){
        bool flag = false;
        for (int j = 1 ; j <= N ; j ++)
            if (j!=1 && ss1[j][i] != ss1[j-1][i]){
                flag = true;
        }
        if (flag){
            cnt =1e9+7;
            break;
        }
        if (ss1[1][i] == '0') cnt0 ++;
        else cnt1++;
    }
    if (cnt != 1e9+7){
        int ans1 = min(cnt0,cnt1) + cnt;
        ans = min(ans,ans1);
    }
    if (ans == 1e9+7) cout << "-1";
    else cout << ans;
    return 0;
}

 

H

根据哥德巴赫猜想，一个大于5的数一定能拆成三个素数和

大力讨论n=1,2,3和>3即可。

#include <bits/stdc++.h>
using namespace std;
int N;
long long Sum = 0;
bool IsPrime(long long x){
    if (x == 1) return false;
    for (int i = 2 ; i <= sqrt(x) ; i ++)
        if (x%i == 0) return false;
    return true;
}
int main(){
    cin >> N;
    for (int i = 1 ; i <= N ; i ++){
        long long x;
        cin >> x;
        Sum = Sum + x;
    }
    if (N == 1){
        if (IsPrime(Sum)){
            cout << "Yes";
        }else cout << "No";
        return 0;
    }
    if (N == 2){
        if (Sum < 2){
            cout << "No\n";
            return 0;
        }
        if (Sum%2 ==0){
            if (Sum > 2)
                cout << "Yes\n";
            else cout << "No\n";
            return 0;
        }else
        if (IsPrime(Sum-2)){
            cout << "Yes\n";
            return 0;
        }
        cout << "No\n";
        return 0;
    }
    if (N == 3){
        if (Sum> 5)
            cout << "Yes\n";
        else cout << "No\n";
        return 0; 
    }
    Sum = Sum - 2ll*(N-3);
    if (Sum > 5){
        cout << "Yes\n";
        return 0;
    }
    cout << "No\n";
}

J

队友写的，似乎是个toposort？

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1000010, M = 2000010;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N], q[N];
bool st[N];
int cnt;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort()
{
    int hh = 0, tt = -1;

    for(int i = 1; i <= n ; i ++)
        if(!d[i])
            q[++ tt] = i, st[i] = true;

    while(hh <= tt)
    {
        int t = q[hh ++];

        for(int i = h[t] ; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if(d[j] == 0) q[++ tt] = j, st[j] = true;        
        }
    }
    
    cnt = tt;
    return (tt == n - 1);
}

void solve(){
    cin >> n >> m;
    memset(h, -1, sizeof h);

    while(m --){
        int a, b;
        cin >> a >> b;
        add(a, b), d[b] ++;
    }

    bool flag = topsort();

    if(flag){
        cout << 1 << endl;
        for(int i = 0; i < n; i ++)
            cout << q[i] << ' ';
    }
    else{
        cout << 2 << endl;
        for(int i = 1; i <= n; i ++)
            if(!st[i])  
                q[++ cnt] = i;
        
        for(int i = 0; i < n; i ++)
            cout << q[i] << ' ';
        cout << endl;
        for(int i = n - 1; i >= 0; i --)
            cout << q[i] << ' ';
        cout << endl;
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;

    while(T --){
        solve();
    }

    return 0;
}

 

标签：cout,int,namespace,多校,long,cin,牛客,include,第三场
From： https://www.cnblogs.com/si--nian/p/17578658.html

相关文章

  • 牛客多校 Day3
    H哥德巴赫J诈骗A签到D要么全\(0\)，要么全\(1\)B不得不说我真的纯纯SB真的。考场做法是先转成概率，然后就是计算长度大于等于\(i\)概率之和。\(f(i,j,0/1)\)前\(i+j\)个位置填\(i\)个小于等于\(n\)的数，\(j\)个大于\(n\)的数，最后一段是上升/下降的......
  • 牛客小白月赛 47 题解
    牛客小白月赛47A.牛牛的装球游戏标签暴力思路显然，答案为\(\pir^2l-[\frac{l}{2r}]*\frac{4\pir^3}{3}\)。时间复杂度为\(\mathcalO(1)\)。代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;intT;doubleans,pi=3.141592653589;intt,h,r;int......
  • 牛客周赛Round4(java)
     Java组代码importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intn=scanner.nextInt();intm=scanner.nextInt();StringBuildersb=newStringB......
  • 牛客多校第二场-H
    H-0and1inBIT op1-->-x-1op2-->x+1由线性代数知识推每次操作要乘的矩阵，线段树维护一个矩阵信息 [op,d,1]就是代表一个f(x)=kx+b的方程，根据线性代数知识用矩阵表示该方程->f(x)=op*x+d,最后一个1只是凑矩阵用的，f代表该矩阵，因为刚开始就是x，所以op=1，d=0 #inclu......
  • 牛客多校1
    A.AlmostCorrect题意:给出一个长度为\(n\)的\(01\)串\(s\)，他一定是没有被排序的，构造不超过\(120\)对的操作序列，使得他不能对\(s\)排序，但可以对长度为\(n\)的其他\(01\)序列排序。思路：设\(s\)中最左边的位置为\(p\)，首先先让所有不在\(p\)位置的\(1\)与\(p\)操作，这样对原串没......
  • 牛客多校第二场补题
    牛客多校2I.LinkwithGomoku题意：两个人下五子棋，给出棋盘大小，构造一种方案，使得平局。思路：考虑这样构造xxxxooxxxxxxxxooooox以五一个为一个循环，多出来的部分也以这种方式构造，唯一的问题就是当有奇数行时会导致先手的棋子太多，因此当n为奇数时，让最后一行这样填充xoxoxox.......
  • 牛客第一场补题
    牛客多校1D.Chocolate题意：A、B轮流吃巧克力，当一个人选择一个点吃的时候，会把这个点及其左下的所有全部吃完，谁先吃完谁就输了，给出巧克力的大小，问谁会赢。思路：考虑当一个人吃完只剩一行或一列时，那么下一个吃的人就可以控制把最后一块留给这个人，因此当一个人吃完剩一行和一列的......
  • 杭电多校第一场补题
    杭电多校第一场1001Hide-And-SeekGame题意：给出一棵树，每次询问第一个人从Sa-Sb之间来回走，第二个人在Ta-Tb之间来回走，最早相遇的节点，如果无法相遇就输出-1做法：由于数据量是1e3级别，因此对于每一条路径都可以使用暴力找祖先的方法求出路径，然后对于路径上的每一个节点，其出现的时间......
  • 2023牛客暑期多校训练营2 补题
    D.TheGameofEating题意：有n个人和m道菜，每个人对每个菜的都有一个喜好度a[i][j]，所有人都知道其他人的喜好度，现在需要上k道菜，从1，2...，n，1，2.....的顺序来选，如果每个人都只考虑自己的喜好，问最后哪些菜会被端上来Solution我们考虑到所有人都知道其他人的喜好度，也就是说，假设当前要选......
  • 牛客多校2
    D.TheGameofEating题意:有\(n\)个人，\(m\)种菜，从\(1\)开始轮流点菜，一共点\(k\)道，\(n\)点完轮到\(1\)，直到点完，点过的菜其他人不能再点。第\(i\)个人对第\(j\)道菜有\(A_{i,j}\)的喜好度，每个人都想让自己对所有已选的菜的喜好度总和最大，他们能彼此看到对菜的喜好度，问最后点了的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99