首页 > 其他分享 >牛客小白月赛65ABCD(E)

牛客小白月赛65ABCD(E)

时间:2023-01-07 18:22:05浏览次数:66  
标签:数字 必胜 牛牛 石子 cin 牛客 int 小白月赛 65ABCD

                     

比赛链接:牛客小白月赛65_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A:牛牛去购物

题意:

给n元钱,有两种商品,价格为a和b,问最少能花到剩多少钱?

思路:

一开始就猜了发结论:min({n % a,n % b,n % a % b,n % b % a})

感觉自己对麻了

然后喜提WA

但是实际上要花到最少并不一定是先把其中一个花到不能再花才考虑另外一个

比如一个反例就是n = 33,a = 4,b = 7

先买a,买到剩1元,就啥都买不了了

先买b,买到剩5元,再买a,买到剩1元

实际上最优解是先买三个a,剩21元,再买3个b,剩0元

看看数据范围都是<=1000的,直接暴力就完事了

第一重循环枚举买a的数量[0,n / a]

第二重循环枚举买b的数量[0,n / a]

判断条件是i * a + j * b <= n

然后一直取min就完事了

代码:

void solve()
{
	int ans = 1e18;
	int a,b;
	cin >> n >> a >> b;
	for(int i = 0;i <= n / a;i++)
	{
		for(int j = 0;j <= n / b;j++)
		{
			if(i * a + j * b <= n)
			{
				ans = min(ans,n - i * a - j * b);
			}
		}
	}
	cout << ans << endl;
}

总结:

看看数据范围再决定猜结论还是打暴力(

如果能打暴力坚决不猜结论!

B:牛牛写情书

题意:

给一个长度为n的初始字符串和一个长度为m的目标字符串

问初始字符串去掉除开小写字母以外的字符后是否含有目标字符串

思路:

思路很显然,模拟即可

就先用个字符串收集初始字符串中的小写字母

然后再用一下find()函数来判断即可

代码:

void solve()
{
	string s1,s2,s3;
	cin >> n >> m;
	cin >> s1 >> s2;
	for(int i = 0;i < n;i++)
	{
		if(s1[i] >= 'a'&&s1[i] <= 'z') s3 += s1[i];
	}
	if(s3.find(s2) != -1) YES;
	else NO;
}

总结:

A题卡了可以先看看后面的,感觉B比A简单一些(

C:牛牛排队伍

题意:

有一个1到n的排列

有m次操作和询问

操作是去掉排列的某个数字

询问是输出某个数字的前面一个数字,如果这个数字是第一个数字就输出0

思路:

按要求模拟即可

因为涉及到去除数字和查找数字

我选择用set来模拟

查找数字用find()即可

去除数字用erase()即可

代码:

void solve()
{
	cin >> n >> m;
	set<int> s;
	for(int i = 1;i <= n;i++) s.insert(i);
	int x,y;
	while(m--)
	{
		cin >> x >> y;
		if(x == 1) s.erase(y);
		else
		{
			auto it = s.find(y);
			if(it == s.begin()) cout << 0 << endl;
			else cout << *prev(it) << endl;
		}
	}
}

C题总结:

STL容器和函数还是很有用的!

D题:牛牛取石子

题意:

给两堆石子为n和m,石子数为a和b

牛牛先手,牛妹后手

操作有两种

一种为在n堆取1个,m堆取2个

一种为在n堆取2个,m堆取1个

谁先无法取石子谁就输

思路:

最开始考虑先手必胜,咋个都想不出来

后来考虑后手必胜:

如果数量少的那一堆石子%3 == 0的话

不管牛牛咋个取石子

牛妹跟他弄相反的操作即可

这样牛妹是必胜的

反之,如果石子数 % 3 != 0

牛牛只要操作一次使得小的那一堆 % 3 == 0即可

显然这个结论是成立的

然后就喜提WA

如果两个数字是一样的捏

比如 4 4

这种牛牛就做不到必胜了

因为不管咋个操作都会变成 2 3

也就是说如果(两个数字一样的&&小的一堆 % 3 != 0) != 牛牛必胜

原因就是之前的证明都默认了第一次操作不会改变a,b的相对大小

所以这里再判断一下

如果两个数相等且石子数 % 3 == 2 -> 牛牛必胜

如果两个数相等且石子数 % 3 == 1 -> 牛妹必胜

代码:

void solve()
{
	cin >> n >> m;
	if(n > m) swap(n,m);
	if(n % 3 == 0) cout << "niumei" << endl;
	else if(n == m)
	{
		if(n % 3 == 1) cout << "niumei" << endl;
		else cout << "niuniu" << endl;
	}
	else cout << "niuniu" << endl;
}

总结:

后来才知道这种叫做"对称博弈"

就是两种操作是对称的

一般对称博弈都是考虑后手必赢状态

因为后手只要对称着操作

两次操作就会某种形式上的抵消

决定是否抵消的是后手

当然先手也可以通过操作来使得下一次操作变成必输态

这就要根据题来讨论了

E:牛牛的构造

题意:

        要你构造一个长度为n的排列,并且满足 这个排列恰好有k个二元组 二元组条件为:1 <= i < j <= n&&ai - aj = 2x

思路:

赛事没弄出来(实际根本没去想)

典型的构造题

典型的没思路

先想想极端情况

如果一个排列是从小到大的->0个二元组

如果排列是从大到小的捏

如果数字从n开始,那么后面满足的数字有这些:

n - 1,n - 2,n - 4,n - 8,n - 16.......

因为n - (n - x) = x

由于是个排列,换种方式考虑

n=6时:6 5 4 3 2 1

6 - 5 = 1,6 - 4 = 2,6 - 3 = 3,6 - 2 = 4,6 - 1 = 5

5 - 4 = 1,5 - 3 = 2,5 - 2 = 3,5 - 1 = 4;

......

发现就是对于一个逆序的排列

每个数算贡献的时候考虑的都是[1,p[i] - 1]

那么在[1,p[i] - 1]中的贡献为log2(p[i] - 1) + 1

公式就出来了

打个表:

2    3    4    5    6    7    8    9

1    2    2    3    3    3    3    4

所以如果要构造的n算出来的值如果小于了k

可以直接退出然后输出-1了(因为这已经是最大的情况了)

如果刚好等于k当然可以直接输出逆序的排列

然后就是关于这个值<k了

这题的结论就是如果这个值<k,不管是啥都可以构造出来

不会证明

然后最关键的地方来了((

要做这题就要想个构造方式

这题的构造方式就是:先降后升

比如要构造贡献为11的,n为9的

根据上面打的表

4 + 3 + 3 + 1即可

对应的就是9 8 7 2

然后加上剩余的数

就是9 8 7 2 1 3 4 5 6

可以发现:

对于前面降序的数有这个性质:比这个数小的都在这个数后面

那么可以直接通过上面那个表求出相应的值

而对于后面升序的数来说,已经和前面的数算过贡献,但是后面的数又都比当前位置的数大

所以后面的数贡献都是0

所以结论就是:

只要在算出的那个表中选出几个数字且这几个数之和为k作为前面降序的数就好了

我以为这里要用背包来着

结果从大到小贪心即可

不会证明

代码:

void solve()
{
	cin >> n >> m;
	if(n == 1)
	{
		if(m == 0) cout << 1 << endl;
		else cout << -1 << endl;
		return;
	}
	int sum = 0;
	vector<int> a(n + 10),b(n + 10),st(n + 10);
	for(int i = 1;i <= n;i++) a[i] = i;
	for(int i = 2;i <= n;i++) b[i] = (int)log2(a[i] - 1) + 1,sum += b[i];
	// cout << b[3] << endl;
	reverse(all(a));
	reverse(all(b));
	// for(int i = 1;i <= n;i++) cout << a[i] << " ";
	// cout << endl;
	// for(int i = 1;i <= n;i++) cout << b[i] << " ";
	// cout << endl;
	if(sum < m) cout << -1 << endl;
	else if(sum == m)
	{
		for(int i = 1;i <= n;i++) cout << a[i] << " ";
		cout << endl;
	}
	else
	{
		int res = 0;
		for(int i = 1;i <= n;i++)
		{
			if(res + b[i] <= m)
			{
				res += b[i];
				st[i] = 1;
				cout << a[i] << " ";
			}
		}
		for(int i = n;i >= 1;i--)
		{
			if(!st[i]) cout << a[i] << " ";
		}
	}
}

总结:

这题感觉非常巧妙((

即使听了思路也是如此

对于这类构造题,先要去考虑一下极端情况,比如最多多少,最少多少

然后再根据极端情况来进行调整

然后再根据性质推出一些结论

但是这题的先降序后升序这里

感觉确实比较人类智慧((

                                       

标签:数字,必胜,牛牛,石子,cin,牛客,int,小白月赛,65ABCD
From: https://www.cnblogs.com/rickly233/p/17032755.html

相关文章

  • 牛客小白月赛65(C,D,E,F)
    牛客小白月赛65(C,D,E,F)果然人是不能太得意,上一次打的还没有那么惨,沾沾自喜,结果这一次就翻车了,o(╥﹏╥)oCC这个题我先前好像看过类似的,不过具体的忘记了这个题我有两种写法......
  • 牛客小白月赛65 D题 题解
    原题链接题意描述一共有两堆石子,第一堆有\(a\)个,第二堆有\(b\)个,牛牛和牛妹轮流取石子,牛牛先手,每次取石子的时候只能从以下\(2\)种方案种挑一种来取(对于选择的方案......
  • 牛客小白月赛补题65
    A.牛牛去购物这道题目纯纯数学题,一遍一遍更新最小值,我们每一次都用a*i+b*j,计算出最小的答案ACcode#include<bits/stdc++.h>#defineintlonglongconstint......
  • 牛客题目进阶7:数据累加输出
    代码头ready_a声明为了wire型,所以是暗示用组合逻辑。对于三个输出信号,分别来看ready_a:用来和valid_a握手,表示当前模块可以从上游模块接收数据进行累加。所以就要判断在什......
  • 牛客进阶题目6:数据串并转换电路
    接收6个bit之后下一拍输出一个6bit宽的data,注意此时如果valid_a拉高,也要接收新进来的数据这里用移位寄存器计数不太行,不太好让data_b在新数据出来前保持不变,虽然功能一样,......
  • 牛客进阶题目5:信号发生器
    这个题目有点离谱,题里什么也没给,需要去题解中才知道方波、锯齿波和三角波最大值都为20,方波周期20,锯齿波周期21,三角波周期40对三种波形具体分析方波:周期为20且最大值也为2......
  • 牛客小白月赛 64 D题
    https://ac.nowcoder.com/acm/problem/247496 1#include<bits/stdc++.h>2usingnamespacestd;34constintN=3e5+10;56typedeflonglongLL;......
  • 牛客进阶题目4:输入序列不连续的序列检测
    跟上一题基本类似,多了个valid判定当前输入数据是否有效`timescale1ns/1nsmodulesequence_detect( inputclk, inputrst_n, inputdata, inputdata_valid, outpu......
  • 牛客小白月赛 64 C题
    https://ac.nowcoder.com/acm/contest/50044/C 1#include<bits/stdc++.h>2usingnamespacestd;3//贪心构造我认为思路是其一,然后模拟这个过程还是比较重......
  • 牛客进阶题目3:不重叠序列检测
    还是移位寄存器,加一个计数器来限制周期题目要求状态机,懒得画了,移位寄存器可根据时序图直接写`timescale1ns/1nsmodulesequence_detect( inputclk, inputrst_n, i......