当前位置：首页 > article >正文

牛客小白月赛109 A-C

article 2025/3/1 16:55:04

A-Onewan的疑惑

题目描述

Onewan 有一天知道了 19 260 817 和 114 514这两个奇妙的数字。他想知道在小于等于 n 的正整数中有多少个数 x ，使得下式成立：
x+(19 260 817)≥n−(114 514)

他算不出来答案所以想请你帮帮他。

输入描述:

在一行上输入一个整数 n(1≤n≤1e9) 代表所给定的上限。

输出描述:

在一行上输出一个整数，代表满足题意的 x 的数量。

示例1

输入

输出

示例2

输入

19375332

输出

19375332

示例3

输入

输出

思路：直接看代码。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
int main()
{
	ll n; 
    cin >> n;
    if(n<19375331) {
    	cout<<n;
	}
	else if(n==19375331) {
		cout<<n;
	}
	else if(n>19375331){
		cout<<n-(n-19375331)+1;
	}
	return 0;	
}

B-菲菲姐的游戏

题目描述

你将要和菲菲姐玩游戏！现在有一个由 nnn 个正整数组成的数组 {a1,a2,…,an} 。游戏的规则如下：
你需要将数组切分成前后两半，前一半给你，后一半给菲菲姐（长度可以任意，但不能为空）；
你能在你的一半数组中至多选择 k1 个数，菲菲姐能在她的另一半数组中至多选择 k2个数，双方都不能不选；
若你选的数字的平均值大于菲菲姐选的数字的中位数，则你获胜；否则，则你输。
假设你和菲菲姐都会采用最优策略，使得平均数和中位数最大。你是否拥有必胜策略？

输入描述:

第一行输入三个整数 n,k1,k2(2≤n≤105; 1≤k1,k2≤105) 代表数组中的元素数量、你至多选择的数字数量、菲菲姐至多选择的数字数量。
第二行输入 n个整数 a1,a2,…,an(1≤ai≤105)代表数组中的元素。

输出描述:

如果存在必胜策略，在一行上输出 Yes ；否则，直接输出 No。

示例1

输入

5 5 5
5 1 4 2 4

输出

Yes

说明

对于这一组测试数据，你可以切分出 {5} 作为你的数组，随后从中选择橙色的数字，得到最大平均值为 5 ；菲菲姐将从切分出的后一半数组 {1,4,2,4}中选择橙色的数字，得到最大中位数 4 。
我们可以证明，这样的选择是最优的策略。所以你获胜。

示例2

输入

5 5 5
1 2 3 4 5

输出

No

思路：

如果 mindex==n（无法划分数组）或者cunm>k1（无法保证最大的数都在自己这）就可能输。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
int main()
{
	int n,k1,k2;
	cin>>n>>k1>>k2;
	int mmax=0,mindex,cunm=0;
	vector<int> v(n+5,0);
	for(int i=1;i<=n;i++) {
		cin>>v[i];
		if(v[i]>=mmax) {
			mmax=v[i]; mindex=i;cunm++;
		}
	}
	if(cunm>k1||mindex==n) {
		cout<<"No";return 0;
	}
	cout<<"Yes";
	return 0;	
}

C-猪猪养成计划1

题目描述

Tobo 养了 n 只猪猪，猪猪们的编号为 1∼n。我们规定两种操作：
1.对于给定的 l,r，表示 Tobo 要和编号为 l到 r 的猪猪按顺序玩耍，但因为 Tobo 喜新厌旧，所以已经玩耍过的猪猪不会再一起玩，会直接跳过它。
2.对于给定的 x ，表示编号为 x 的猪猪想知道自己是第几个和 Tobo 玩耍的，如果没有玩耍过则输出 0 。

你一共需要处理 q次操作。

输入描述:

第一行输入两个整数 n,q(1≤n,q≤105)代表 Tobo 养的猪猪数量、操作次数。 
此后 q 行，每行先输入一个整数 op(1≤op≤2)op 示操作类型，随后：
若 op=1，在同一行上输入两个整数 l,r(1≤l≤r≤n)代表 Tobo 将依次和编号为 l 到 r 的猪猪玩耍。 
若 op=2，在同一行上输入一个整数 x(1≤x≤n)代表一次询问。

输出描述:

对于每一次询问，在单独的一行上输出一个整数，表示询问的猪猪是第几个和 Tobo 玩耍的；若没有玩耍过，则直接输出 0 。

示例1

输入

输出

说明

对于第一次操作，Tobo 将依次和编号为 2,3的猪猪玩耍；
对于第二次操作，编号为 3 的猪猪想知道自己是第几个和 Tobo 玩的，输出 2 ；
对于第三次操作，Tobo 将依次和编号为 3,4,5的猪猪玩耍，这其中，由于编号为 3的猪猪已经和 Tobo 玩过，所以 Tobo 会跳过它，直接和编号为 4 的猪猪玩耍。

示例2

输入

输出

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, q;
    cin >> n >> q;
    int k = 1;
    vector<int> cnt(n + 1);
    set<int> s;
    for(int i = 1; i <= n; i++) s.insert(i);
    while(q--)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int l, r;
            cin >> l >> r;
            while(l <= r)
            {
                if(s.lower_bound(l) == s.end()) break;
                l = *s.lower_bound(l);
                if(l <= r)
                {
                    s.erase(l);
                    cnt[l] = k;
                    k++;
                }
            }
        }
        else
        {
            int x;
            cin >> x;
            cout << cnt[x] << "\n";
        }
 
    }
	return 0;	
}

查看全文

http://www.kler.cn/a/507498.html