儿时仰星光,举手若能摘。 于今七尺身,天高不可及。

img

牛客周赛 Round 11

A

注意为0就是m

上场div4吃大亏

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

void solve()
{
    int q;
    cin >> q;
    while(q--)
    {
        LL m,x;
        cin >> m >> x;
        if(x%m == 0) cout << m << '\n';
        else cout << x%m << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    while(t--) solve();
    return 0;
}

B

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
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
 
void init()
{
    int n,k;
    cin>>n>>k;
    int a[105];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    while(k--)
    {
        int u,v;
        cin>>u>>v;
        a[u]++;a[v]--;
    }
    for(int i=1;i<n;i++)
        if(a[i]>a[i+1])
        {
            cout<<"No"<<endl;
            return ;
        }
    cout<<"Yes"<<endl;
}
 
signed main()
{
    int _=1;
    cin>>_;
    while(_--)
        init();
    return 0;
}

C

暴力枚举所有子串

修改后必为0101,1010

因此模拟这两种修改情况即可。

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e3 + 10;

char s[N];

void solve()
{
    cin >> s + 1;
    int n = strlen(s + 1);

    LL res = 0;
    for(int i = 1; i <= n; i++)
    {
        LL temp1 = 0,temp2 = 0;
        for(int j = i; j <= n; j++)
        {
            if(j%2)
            {
                if(s[j] == '0') temp1++;
                else temp2++;
            }
            else
            {
                if(s[j] == '0') temp2++;
                else temp1++;
            }
            res += min(temp1,temp2);
        }
    }
    cout << res << '\n';
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    while(t--) solve();
    return 0;
}

D

两两为倍数 & 元素互不相等，所以排序后，后一个元素都是前一个元素的倍数

最大数为1e9, 而最小倍数为2，所以序列的长度最多为31

删除k个不好考虑，考虑最后保留的，也就是选出n-k个

dp[i][k], 以i元素为末尾元素，且前排累计挑选k个的方案数，最后答案就是每个元素为末尾，都选出n-k个的方案数累加。

暴力枚举1-i，找出当前在集合里的元素j，对于所有元素j为末尾，依次选出1~(n-k)个时的方案都可以作为i为末尾时的贡献，累加上去即可。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2010, mod = 1e9+7;
int a[maxn], dp[maxn][maxn];
int main(){
    int n, k; cin>>n>>k;
    for(int i = 1; i <= n; i++) cin>>a[i];
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; i++) {
        dp[i][1] = 1;  //选1个方案数1
        for(int j = 1; j < i; j++){  //暴力枚举前1-i
            if(a[i]%a[j]==0)
            {  
                //a[j]可以作为以a[i]为末尾元素的集合中的元素（或者说a[i]可以加到a[j]后面）
                for(int kk = 2; kk <= n-k; kk++)
                {  
                    // 依次选出2~(n-k)个时的方案，先把a[i]选上去，所以从2开始
                    dp[i][kk] += dp[j][kk-1];  
                    // 贡献累加
                    dp[i][kk] %= mod;
                }
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++)
    {  
        //以每个元素为末尾，都选出n-k个的方案数累加
        res = (res + dp[i][n-k])%mod;
    }
    cout<<res<<"\n";
    return 0;
}
img