牛客2024年七夕节比赛

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

赛后补题：

image-20240814170535900

A

有趣算术题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
void Totoro()
{
    int n, x;
    cin >> n;
    ll ans = 10;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        ans += (x + 4) * x;
    }
    cout << ans << '\n';
}
 
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
    return 0;
}

B

1
2
3
4
5
6
7
#include <bits/stdc++.h>
using namespace std;
  
int main() {
    cout << "いいよこいよ\n";
    return 0;
}

C

自己可以被自己整除啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
void Totoro()
{
    int n;
    cin >> n;
    cout << n << '\n';
    for (int i = 1; i <= n; i++)
    {
        cout << i << ' ';
    }
}
 
int main()
{
    int t = 1;
    //  cin >> t;
    while (t--)
    {
        Totoro();
    }
    return 0;
}

D

1
2
3
4
5
6
7
#include <bits/stdc++.h>
using namespace std;
  
int main() {
    cout << "一个长度为七的字符串。";
    return 0;
}

E

并查集求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N=1e6+100;
int a[N];
int fa[N];
int ans[N][2];
int find(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    fa[x]=y;
}
void Totoro()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    fa[i]=i;
}
while(m--)
{
    int x,y;
    cin>>x>>y;
    merge(x,y);
}
for(int i=1;i<=n;i++)
{
    ans[find(i)][a[i]]++;
}
for(int i=1;i<=n;i++)
{
    cout<<ans[find(i)][!a[i]]<<'\n';
}

}

int main()
{
    int t = 1;
    //  cin >> t;
    while (t--)
    {
        Totoro();
    }
    return 0;
}

F

1
2
3
4
5
6
#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<12;
}

G

对于n个位置 有且仅有两个位置相同,其余均不同 故一共有 n−1个数要被选择，即为C(m,n−1)，而对于选择 出来的n−1个数，由于有两个数相同 因此这两个数一定要放在两侧，即最大值左边放一个 最大值右边放一个，而易得这个数不能为选出来的数的最大值，故一共有n−2个数可以作为相同个数，而对于剩下的n−3个数 （去除了最大值和两个相同的数）

对于这些数把他们从小到大排序，从小开始选择，每个数既可以放最大值左边也可以放到最大值右边，故一共有\(2^{n−3}\)种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 2e6 + 100;
const int mod = 1e9 + 7;
const int MOD = 998244353;
ll inv[N];
ll fac[N];
ll qsm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = (ans * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans % mod;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = qsm(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
    {
        return 1;
    }
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void Totoro()
{
    init();
    ll n, m;
    cin >> n >> m;
    cout << (C(m, n - 1) * (n - 2) % mod * qsm(2, n - 3)) % mod << '\n';
}
 
int main()
{
    int t = 1;
    //  cin >> t;
    while (t--)
    {
        Totoro();
    }
    return 0;
}

H

1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;
  
int main(){
    cout<<"OMG"<<endl;
    return 0;
}

I

1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;
  
int main(){
cout<<"password";
    return 0;
}

J

某种数学推导（我不会）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 2e6 + 100;
const int mod = 1e9 + 7;
const int MOD = 998244353;
ll inv[N];
ll fac[N];
ll qsm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = (ans * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans % mod;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = qsm(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
    {
        return 1;
    }
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void Totoro()
{
    int n, k;
    cin >> n >> k;
 
    int all = (n + 1) * (n + 1) / 6;
    if (all >= k)
        cout << "yes";
    else
    {
        cout << "no" << '\n';
        cout << (ll)sqrt(6 * k - 1);
    }
}
    int main()
    {
        int t = 1;
        //  cin >> t;
        while (t--)
        {
            Totoro();
        }
        return 0;
    }

K

题目记得滑到最后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 2e6 + 10;
void solve()
{
    int x;
    cin >> x;
    int t = 0;
    int f = 1;
    for (int i = 1; i <= x; i++)
    {
        for (int j = 1; j <= t; j++)
            cout << " ";
        cout << "鸽\n";
        t += f;
        if (t == 27)
        {
            f = -1;
            t = 25;
        }
        else if (t == -1)
        {
            t = 1;
            f = 1;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    int T = 1;
    //  cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}