白色L号谢谢

题解

/ 注册

全部文章 / 题解（共22篇）

Cow Digit Game

当一个状态的后继状态有一个必败状态，我们可以通过移动到必败状态使得对手败。当一个状态的后继状态全部为必胜状态，无论怎么移动对手都会取胜。所以设d[x]表示先手拿到数字x的取胜情况，直接判断后继点的取胜情况即可。 #include <bits/stdc++.h> #include <...

2020-07-07

0 590

栗酱的异或和

原型nim游戏。当且仅当n堆石子异或和等于0时先手必败。这个时候我们考虑把必败的局面留给对手。所以先计算除了a[k]外的其他数字的异或和，如果a[k]大于这个sum，则我们取掉sum-a[k]即可。留给对手一个必败局面。 #pragma GCC optimize(2) #pragma GCC opt...

2020-07-06

3 673

AStringGame

用sam跑出DAG图，再求出sg值。SG定理：n个有向图游戏组成的组合游戏当且仅当SG值异或和等于0时先手必输，否则先手必胜。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typ...

2020-07-06

0 873

小牛vs小客

n>=3时后手必赢，因为先手无论什么操作，后手跟他进行对称操作即可。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef...

2020-07-06

6 623

牛客小白月赛24 J.建设道路

Cometoj出过这题。。考虑单个点的贡献(a[i] - a[x]) * (a[i] - a[x]) = a[i] * a[i] - 2 * a[i] * a[x] + a[x] * a[x]所以里面一共就有(n - 1)个a[i]的平方以及除了a[i]外其他所有数的平方，中间这部分减法就是2 * ...

2020-04-18

4 572

牛客小白月赛24 H.人人都是好朋友

考点:并查集，离散化。这题题意很明确，做法也很明确。先对友好的弄一个并查集，最后再查询敌人是否为友好关系。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long ...

2020-04-18

4 780

牛客小白月赛24 D.牛妹吃豆子

考点:二维差分，前缀和。这题题意很明确，做法也很明确，先对前k个操作差分，再进行二维前缀和，直接O(1)查询就行了。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef ...

2020-04-18

3 601

2019牛客暑期多校训练营（第五场)B:generator1

这题给出满足求第n项对做一次矩阵乘法，得到的即是与所以乘n次后，取m[1][0]即是答案但是这个数据范围太大了，直接快速幂会超。可以使用十进制快速幂有个优化，在...

2019-08-10

1 789

2019牛客暑期多校训练营（第七场）A : String

链接：https://ac.nowcoder.com/acm/contest/887/A 来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 A string is p...

2019-08-09

0 812

牛客假日团队赛5 F- 随机数（组合数学）

可以使用组合数学或者数位dp来写组合数的写法，就是通过枚举1 和 0的个数来计算总的方案数 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll pre[110]; ll C(ll n, ll m) ...

2019-07-19

0 570