牛客小白月赛65

牛客小白月赛65

A 牛牛去购物

思路：完全背包
可以看成背包容量为n，有两种产品若干个，然后dp[i][j]=max(dp[i-1][j],dp[i][j-a[i]]+a[i])

#include
using namespace std;
#define int long long
const int N=1100;
int dp[N][N];
signed main(){
    int n,a[3],b;
    cin>>n;
    int res=0;
    for(int i=1;i<=2;i++){
        cin>>a[i];
        for(int j=0;j<=n;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=a[i])dp[i][j]=max(dp[i][j],dp[i][j-a[i]]+a[i]);
            res=max(res,dp[i][j]);
        }
        
    }
    
    cout<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

B 牛牛写情书

思路：暴力
取出所有小写字母，然后和第二个字符串进行匹配即可

#include
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    string s;
    string v;
    cin>>s>>v;
    string v2="";
    for(int i=0;i='a'&&s[i]<='z'){
            v2+=s[i];
        }    
    }
    for(int i=0;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

C 牛牛排队伍

思路：二分
这里我们可以用一个set讲所以数字包括0都存入set中，然后如果是1将对应下标找到并删除，如果是2的话，用lower_bound()找到大于等于该值的下标然后减1后即是答案下标，然后输出即可

#include
using namespace std;
const int N=2e6+7;
int a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    setst;
    for(int i=0;i<=n;i++)st.insert(i);
    while(m--){
        int q,x;
        cin>>q>>x;
        if(q==1){
           st.erase(st.find(x));
        }else{
            auto t=st.lower_bound(x);
            t--;
            cout<<*t<<"\n";
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

D 牛牛取石子

思路：博弈论
一般来说，如果题目中有类似游戏双方都很聪明这种字眼，
那一定是一道博弈论题，而不是模拟题
那就一定要往先手必胜or后手必胜的角度考虑
那我们再来看看这个游戏过程：
不难发现，每过一个回合相当于:A-3 B-3
然后，两名玩家是不是好像又回到了游戏最开始的状态
此时的状态就等价于开始了一场初始石子数为A-3和B-3的游戏
换句话说，对于一组数据(a,b)，它的结果和(a-3,b-3)是一样的
这样一想，思维就流淌出来了：这道题肯定和3有关！
接下去我们要考虑，在什么状态下，游戏会结束？
既然要取到不能取为止，玩家就应该把策略聚焦到更少的那一堆上，就会跟容易kill对手
那么取完之后，如果能让更少的一堆数量变为0，就获胜了
（不需要考虑1、1这种终止情况。为什么呢？因为倘若结束时的状态是1、1，那么上一状态换一种取法的结果一定是2、0）
再考虑到：每过一个回合相当于:A-3 B-3
后手必胜的策略就很清晰了，只要较小的数是三的倍数，那么后手必胜
这种情况下，只要先手选①后手选②，先手选②后手选①，那么就能坐等先手完蛋
而当较小数不是3的倍数
先手想要获胜也很简单，如果较小数%3==1，那我先就在这堆取1，
如果%3等于2，那么我就在这堆取2
接下来，此前的先手就变为了较小的数是三的倍数情况下的后手，就坐等。。。
很简单对吧？😉
比赛的时候我也是这么想的，想到这儿，就打代码提交了
结果WA了一发😅😅😅
问题不大
再仔细想想，当A=B的时候，先手似乎还要多一个心眼
当A=B且A÷3余1时，先手怎么不管怎么取都不能让较小数变成3的倍数
而当先手rand(①/②)来取一次，后手只需要采取一样的取法，就可以让-4的那个更小的数变成3的倍数
这是后手必胜的一种特殊情况

#include
using namespace std;
typedef long long ll;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll a,b,minn;
		cin>>a>>b;
		if(a