牛客周赛 Round 39

img

小红不想做炸鸡块粉丝粉丝题

直接开模拟，判断

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;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
const int N=1e6+100;
#define LF(x)   fixed<<setprecision(x)
void Totoro()
{

}
signed main()
{
    ios;
    int ans;
    int sum=0;
rep(i,1,6)
{
    int x;
        cin>>x;
    if(i==1)
    {
        ans=x;
    }
    sum+=x;
}
if(ans>=sum/30)
{
    cout<<"No";
}
else
{
    cout<<"Yes";
}
    return 0;
}

小红不想做鸽巢原理

本题有一个贪心点，想的很快的，但是实现却老是碰壁。

其实直接每次加最小的即可，然后大于的时候就取余，然后记录上一个

然后如果取余等于0，就记录这一个，最后记得判断最后那里，是不是满足sum==0，最后输出n-cnt.

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
const int N=1e6+100;
#define LF(x)   fixed<<setprecision(x)
int a[N];
signed main()
{
    ios;
int n,m;
cin>>n>>m;
int sum=0;
rep(i,1,n)
{
cin>>a[i];
}
int ans=n;
sort(a+1,a+1+n);
int cnt=0;
rep(i,1,n)
{
sum+=a[i];
if(sum>=m)
{
    sum%=m;
    if(sum==0)
    {
        cnt=i;
    }
    else
    cnt=i-1;
}
}
if(sum==0)
{
    cnt=n;
}
cout<<n-cnt;
    return 0;
}

小红不想做完全背包（easy）

用map存储1，2，0然后考虑3的性质

0直接输出1

1和2直接输出2

剩下都是直接输出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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
const int N=1e6+100;
#define LF(x)   fixed<<setprecision(x)
int a[N];
map<int,int>mp;
signed main()
{
    ios;
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
    a[i]%=3;
    mp[a[i]]++;

}
if(mp[0])
{
cout<<1<<'\n';
}
else if(mp[1]&&mp[2])
{
    cout<<2;
}
else if(mp[1])
{
cout<<3;
}
else
{
    cout<<3;
}
    return 0;
}

小红不想做完全背包 （hard）

我肯定做过这种题（）但哎，还是没做出来。

取模余数dp问题，需要记录一下了。

此为核心，通过dp[j]转移过来

如果取模等于0顺便记录一下答案。

1
2
3
4
5
dp[(j+a[i])%p]=min(dp[(j+a[i])%p],dp[j]+1);
if((j+a[i])%p==0)
{
    ans=min(dp[j]+1,ans);
}
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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
const int N=1e6+100;
#define LF(x)   fixed<<setprecision(x)
int a[N];
int dp[N];
void Totoro()
{

}
signed main()
{
int n,p;
cin>>n>>p;
int sum=0;
rep(i,1,n)
{
    cin>>a[i];
    a[i]%=p;
    if(a[i]==0)
    {
    sum=1;
    }
}
if(sum)
{
    cout<<1;
    return 0;
}
memset(dp,0x7f7f7f,sizeof dp);
int ans=1e18;
dp[0]=0;
rep(i,1,n)
{
    rep(j,0,p-1)
    {
dp[(j+a[i])%p]=min(dp[(j+a[i])%p],dp[j]+1);
if((j+a[i])%p==0)
{
    ans=min(dp[j]+1,ans);
}
    }
}
cout<<ans;
    return 0;
}

小红不想做莫比乌斯反演杜教筛求因子和的前缀和

这题肯定不能三重暴力，只能得到40分。

我们要思考优化

直接两层加判断是可以行的通的。

我们考虑枚举最下面那个矩形，如果加上x可以整除2,并且/2减去i*j还可以整除（i+j),并且整除的范围在1-p之间，我们就可以累加答案

这道题自觉地应该是比D简单的。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
const int N=1e6+100;
#define LF(x)   fixed<<setprecision(x)
void Totoro()
{

}
signed main()
{
 //(n*m+n*p+p*m)/2-n*m凑出来
int n,m,p,x;
cin>>n>>m>>p>>x;
int ans=0;
rep(i,1,n)
{
    rep(j,1,m)
    {  
        int t=(i*j+x);
        if(t&1)
        {
            continue;
        }
        if(t/2==i*j)
        {
            break;
        }
        if((t/2-i*j)%(i+j)==0&&(t/2-i*j)/(i+j)>=1&&(t/2-i*j)/(i+j)<=p)
{
    ans++;
}
    }
}
cout<<ans;
    return 0;
}

小红不想做模拟题

我也不知道我在写什么暴力，总之过了（）

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
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
const int N=1e6+100;
#define LF(x)   fixed<<setprecision(x)
int a[N];
int b[N];
int c[N];
int sum1[N];
int sum2[N];
int sum3[N];
int sum4[N];
signed main()
{
int n;
cin>>n;
string s1,s2;
cin>>s1>>s2;
s1=" "+s1;
s2=" "+s2;
int m;
cin>>m;
int cnt=0;
rep(i,1,n)
{
    if(s1[i]==s2[i]&&s1[i]=='1')
    {
        cnt++;
    }
}
rep(i,1,m)
{
    char c;
    cin>>c;
    int l,r;
    cin>>l>>r;
    if(c=='A')
    {
        rep(j,l,r)
        {
        if(s1[j]=='0'&&s2[j]=='1') 
        {
            s1[j]='1';
            cnt++;
            continue;
        }
        else
        {
            s1[j]='1';
            continue;
        }
        }
    }
    else
    {
              rep(j,l,r)
        {
        if(s2[j]=='0'&&s1[j]=='1') 
        {
            s2[j]='1';
            cnt++;
            continue;
        }
        else
        {
            s2[j]='1';
            continue;
        }
        }  
    }
cout<<cnt<<'\n';
}

    return 0;
}

正解应该是需要预处理加数据结构维护的

用set维护两个字符串0的位置

然后直接进行查询

改a查b删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
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
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long
using ll = long long;
const int inf=998244353;
const int N=1e5+6;
const int mod=1e9+7;
const double PI=acos(-1);
typedef pair<int,int>P;

void solve(){
    int n;cin>>n;
    string s1,s2;cin>>s1>>s2;
    s1=" "+s1,s2=" "+s2;
    set<int>a={n+1},b={n+1};
    int ans=0;
    for(int i=1;i<=n;i++){
        if(s1[i]=='0') a.insert(i);
        if(s2[i]=='0') b.insert(i);
        if(s1[i]=='1'&&s2[i]=='1') ++ans;
    }
    int q;cin>>q;
    while(q--){
        char op;int l,r;
        cin>>op>>l>>r;
        if(op=='A')
        {
            auto it=a.lower_bound(l);
            while(*it<=r)
            {
                if(!b.count(*it)) ++ans;
                it=a.erase(it);
            }
        }
        else{
            auto it=b.lower_bound(l);
            while(*it<=r)
            {
                if(!a.count(*it)) ++ans;
                it=b.erase(it);
            }
        }
        cout<<ans<<endl;
    }
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

小红不想做平衡树

待补

img