比赛链接:牛客小白月赛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] << " ";
}
}
}总结:
这题感觉非常巧妙((
即使听了思路也是如此
对于这类构造题,先要去考虑一下极端情况,比如最多多少,最少多少
然后再根据极端情况来进行调整
然后再根据性质推出一些结论
但是这题的先降序后升序这里
感觉确实比较人类智慧((