【解题报告】活跃思想训练3（上） | CF 博弈2000+

【解题报告】活跃思想训练3（上） | CF 博弈2000+

• E:Thanos Nim | CF1147C | 2000
• • 题意
  • 题意
  • 代码
• F：Game of Stones | CF 768E | 2100
• • 题意
  • 题意
  • 代码
• G：Industrial Nim | CF15C | 2000
• • 题意
  • 思路
  • 代码
• H：The Game Of Parity | CF 549C | 2200
• • 题意
  • 思路
  • 代码
• I：Game with Powers | CF 317D | 2300
• • 题意
  • 思路
  • 代码

• 活跃思想训练3（上） | CF 博弈2000+

E:Thanos Nim | CF1147C | 2000

题意

• Thanos Nim
  $n$ 堆石头，是个偶数，第 $i$ 堆有 a i a_i ai​ 个石头。
  两人轮流取，每次必须选择 $n/2$ 堆，每堆自行选择拿走任意正整数个石头。谁不能操作谁就输。
  问谁必胜。
• $2\le n\le 50$
  1 ≤ a i ≤ 50 1\le a_i\le 50 1≤ai​≤50

题意

• 我感觉这 $2000$ 的题比 $2300$ 的还难想…
  首先手搓一下 $n=2$，容易得到如果 a 1 = a 2 a_1=a_2 a1​=a2​ 先手输，否则先手胜。难道是对称性构造？还是和 $Nim$ 有关系？
• 但是手搓一下 $n=4$，发现和 $Nim$ 没有什么关系。某一堆石头如果是数量最大的，那么它多加再多的石头，也不会影响先手的胜负。在 $n>=4$ 时对称性构造也很难证明到底是否先手必胜。
• 我们举一些特例来慢慢渐入。首先，先手必须要选 $n/2$ 堆。容易想到，如果先手拿完了一堆或者更多堆，后手直接拿光另外 $n/2$ 堆，先手就输了。所以先手不能拿完任何一堆。
  也就是说，至少有 $n/2$ 堆，满足 a i > 1 a_i>1 ai​>1。
  在上面的基础上，如果小于 $n$ 堆满足 a i > 1 a_i>1 ai​>1，那么后手肯定会至少拿完一堆，后手也就输了。
• 于是我们发现，设 $t$ 表示有多少个 $i$ 满足 a i = 1 a_i=1 ai​=1
  $t\in [n/2+1,n]$，先手输。
  $t\in (0,n/2]$，后手输。
  $t=0$，我们还不大清楚。
• 接下来就比较难想了。我们要让结论有一般性，满足我们的做题需求。
  设 $t$ 表示有多少个 $i$ 满足 a i = min ⁡ j ∈ [ 1 , n ] { a j } a_i=\min_{j\in [1,n]}\{a_j\} ai​=minj∈[1,n]​{aj​}
  简单来说，就是有多少堆，满足这堆石头的数量是最少的。
  如果 $t>n/2$，那肯定玩家会选到最少石头的堆，于是最少石头的堆的数量更新了，很容易得到为 $1\le t\le n/2$
  如果 $t\le n/2$，玩家可以通过选择，选不是最少石头的堆，来让 $t>n/2$。
  于是我们发现，经过一轮，$t>n/2$ 与 $t\le n/2$ 来回互换。
• 我们查看一下边界条件。无法操作，肯定是 $0$ 的数量 $>n/2$ 了。
  所以我们只要查看，一开始的 $t$ 是 哪个状态，最终就是 $Alice$ 的状态。

代码

• 时间复杂度：$O(n)$

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}const int MAX = 505;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-7;int main()
{int n;cin >> n;int mn = INF;int cnt = 0;for(int i = 1;i <= n;++i){int t;cin >> t;if(t == mn)cnt++;else if(t < mn){mn = t;cnt = 1;}}if(cnt <= n / 2)puts("Alice");else puts("Bob");return 0;
}

F：Game of Stones | CF 768E | 2100

题意

• Game of Stones
  有 $n$ 堆，第 $i$ 堆有 a i a_i ai​ 个石头。两人轮流操作。
  一次操作，玩家选择一堆，从中拿 $x$ 个石头。这之后，这堆石头就不能一次性拿 $x$ 个石头了。
  谁不能操作就输，求必胜情况。
• 1 ≤ n ≤ 1 0 6 1\le n\le 10^6 1≤n≤106
  1 ≤ a i ≤ 60 1\le a_i\le 60 1≤ai​≤60

题意

• 注意到， a i a_i ai​ 很小。$Nim$ 石头堆直接异或一下他们的 $sg$ 值就行了。$sg$ 值直接暴力打表就行了。
  怎么打表呢？我们记 $sg[i][j]$ 表示现在这堆里有 $i$ 个石头，下一次拿石头必须数量要 $>j$ 个。
  因为拿石头数量不能重复，我们最后相当于是升序拿石头。所以可以这样做。

代码

• 时间复杂度： O ( n + 6 0 2 ) O(n+60^2) O(n+602)

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}const int MAX = 105;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-7;int sg[MAX][MAX];int SG(int x,int l){if(sg[x][l] != -1)return sg[x][l];if(x <= l)return 0;map<int,int>M;for(int i = l+1;i <= x;++i){M[SG(x-i,i)] = 1;}for(int i = 0;;++i){if(!M[i]){return sg[x][l] = i;}}
}int main()
{for(int i = 0;i <= 60;++i)for(int j = 0;j <= 60;++j)sg[i][j] = -1;int n;scanf("%d",&n);int ans = 0;for(int i = 1;i <= n;++i){int t;scanf("%d",&t);ans ^= SG(t,0);}puts(!ans?"YES":"NO");return 0;
}

G：Industrial Nim | CF15C | 2000

题意

• Industrial Nim
  有 $n$ 个采石场，第 $i$ 个采石场有 m i m_i mi​ 堆石头 ，其中的第 $i$ 个采石场的第 $j$ 堆石头的个数为 a i + j − 1 a_i+j-1 ai​+j−1
  玩 $Nim$ ，求问胜负情况。
• 1 ≤ n ≤ 1 0 5 1\le n\le 10^5 1≤n≤105
  1 ≤ a i , m i ≤ 1 0 16 1\le a_i,m_i\le 10^{16} 1≤ai​,mi​≤1016

思路

• 正常的 $Nim$ 游戏，每一个采石场相当于 m i m_i mi​ 堆石头堆，它的 $sg$ 值就是这 m i m_i mi​ 堆石头的异或值
  所以容易得到，第 $i$ 个采石场的 $sg$ 值就是 a i ⊕ ( a i + 1 ) ⊕ ⋯ ⊕ ( a i + m i − 1 ) a_i\oplus(a_i+1)\oplus\cdots\oplus(a_i+m_i-1) ai​⊕(ai​+1)⊕⋯⊕(ai​+mi​−1)
  由异或值的性质，我们定义 $f(i)=1\oplus 2\oplus \cdots \oplus i$
  答案就是 f ( a i + m i − 1 ) ⊕ f ( a i − 1 ) f(a_i+m_i-1)\oplus f(a_i-1) f(ai​+mi​−1)⊕f(ai​−1)
• 接下来，我们需要知道异或前缀和 $f(x)$ 怎么快速求。
  容易想到，我们需要写出 $x$ 的二进制表示，把它表示成多段的异或值。比如：
  1111 ⊕ − − 0001 ⋮ 1000 − − 1001 ⋮ 1100 − − 1101 1110 − − 1111 \begin{matrix} 1111\\ \oplus--\\ 0001\\ \vdots\\ 1000\\ --\\ 1001\\ \vdots\\ 1100\\ --\\ 1101\\ 1110\\ --\\ 1111 \end{matrix} 1111⊕−−0001⋮1000−−1001⋮1100−−11011110−−1111​
  容易发现， f ( 2 i ) = 2 i f(2^i)=2^i f(2i)=2i，其中 $i\ge 2$
  f ( 2 1 ) = 3 f(2^1)=3 f(21)=3
• 容易想到，第一段的答案就是 f ( 2 i ) f(2^i) f(2i)
  第二段，行数是 2 i 2^i 2i，如果 $i>1$，行数是偶数，那么前面的那些 $1$ 异或完后就是 $0$ 了。
  如果 $i=0$，行数为 $1$，那么答案最终多异或一个 $x$

代码

• 时间复杂度： O ( n log ⁡ ( a i + m i ) ) O(n\log (a_i+m_i)) O(nlog(ai​+mi​))，我经过优化之后变成了 $O(n)$

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}const int MAX = 505;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-7;ll getXor(ll x){		// 推导了一些，变得更加简洁了。ll ans = x;if(x & 2)ans ^= 1;if(x & 1)ans ^= x ^ 1;return ans;
}int main()
{int n;scanf("%d",&n);ll ans = 0;for(int i = 1;i <= n;++i){ll x,m;scanf("%lld%lld",&x,&m);ans ^= getXor(x-1);ans ^= getXor(x+m-1);}puts(ans?"tolik":"bolik");return 0;
}

H：The Game Of Parity | CF 549C | 2200

题意

• The Game Of Parity | CF 549C | 2200
  有 $n$ 个盒子，第 $i$ 个盒子有 a i a_i ai​ 个球。
  两人轮流操作。玩家选择一个盒子，然后把这个盒子与里面的球都丢掉。
  最后只剩下 $k$ 个盒子之后，看球的数量的奇偶性。奇则先手赢，否则先手输。
  问胜负情况。
• 1 ≤ k ≤ n ≤ 2 ⋅ 1 0 5 1\le k\le n\le 2\cdot10^5 1≤k≤n≤2⋅105

思路

• 容易想到，盒子里到底几个球无所谓，只关注里面的奇偶性即可。
  然后感觉就是一个非常复杂的分类讨论题，事实也确实如此，但是自己推导一遍还是能一遍过的。
• 设 $S$ 表示先手玩家的操作次数， $D$ 表示后手玩家的操作次数， S J S_J SJ​ 表示奇数球的盒子数， S O S_O SO​ 表示偶数球的盒子数。
  设 $STEP$ 表示玩家操作次数
• 第一种情况：$STEP=0$，我们不能操作了
  直接判断是否先手必胜即可。
• 第二种情况：$STEP\%2=1$，最后一定是先手玩家操作后结束。
  拿偶数球的盒子不影响球数的奇偶性。
  我们按最终的盒子状态进行合理判断。
  • （1）只剩下偶数球的盒子，先手输： D ≥ S J D\ge S_J D≥SJ​，后手把奇数球盒子都拿光。
  • （2）奇数球偶数球盒子都有，先手赢： D < S J DD<SJ​ 且 D < S O DD<SO​。因为先手最后操作，不管目前奇偶性如何，有奇数和偶数球盒子，先手一定有必胜操作。一定是后手无法把任意一种奇偶性的盒子拿光导致的。
  • （3）只剩下奇数球的盒子
    • 如果 $k$ 是奇数，先手胜：如果先手拿的完偶数盒子，那么最后剩下奇数个 $1$，赢；如果先手拿不完偶数盒子，则到（2），仍然先手胜。
    • 如果 $k$ 是偶数
      • 如果 D ≥ S O D\ge S_O D≥SO​，先手输：后手把偶数球盒子拿光，只剩下偶数个 $1$，先手输了。
      • 否则，先手胜：后手拿不光偶数，先手只要让奇数有所剩下，就能转化到（2）。注意因为 $k\ge 1$，所以是一定有奇数存在的。
• 第三种情况： $STEP\%2=0$，最后一定是后手玩家操作后结束。
  • （1）只剩下偶数球的盒子，先手输： D ≥ S J D\ge S_J D≥SJ​，后手把奇数拿光即可。
  • （2）奇偶都有剩下，先手输： S < S J SS<SJ​ 且 S < S O SS<SO​，先手拿不光一种，后手两种都有的选。
  • （3）只剩下奇数球盒子
    • 如果 $k$ 是奇数，先手胜： S ≥ S 0 S \ge S_0 S≥S0​，先手把偶数拿光就赢了。
    • 否则，先手输：先手把偶数拿光，偶数个奇数输了；先手不把偶数拿光，到（2）也输了；先手把奇数拿光，只剩下偶数也输了。
• 注意：上述判断要按照从上往下的判断进行，因为有些判断是有先后关系的。

代码

• 时间复杂度：$O(n)$

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}const int MAX = 105;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-7;void out(int mex){puts(mex?"Stannis":"Daenerys");
}int main()
{int n,k;scanf("%d%d",&n,&k);int shu[2]={};for(int i = 1;i <= n;++i){int t;scanf("%d",&t);shu[t%2]++;}int S = (n - k + 1) / 2;int D = (n - k) / 2;int STEP = (n - k);if(STEP == 0){out(shu[1]%2);return 0;}if(STEP & 1){if(D >= shu[1]){out(0);return 0;}if(D < shu[1] && D < shu[0]){out(1);return 0;}if(k & 1){out(1);return 0;}else if(D >= shu[0]){out(0);return 0;}else {out(1);return 0;}}else{if(D >= shu[1]){out(0);return 0;}if(S < shu[0] && S < shu[1]){out(0);return 0;}if(k & 1){out(1);return 0;}else {out(0);return 0;}}return 0;
}

I：Game with Powers | CF 317D | 2300

题意

• Game with Powers
  有 $n$ 个数字，为从 $1,2,3,\cdots ,n$
  两个人轮流选数字。如果他选了数字 $i$，那么也要同时拿走数字 i 2 , i 3 , i 4 , ⋯ i^2,i^3,i^4,\cdots i2,i3,i4,⋯
  谁拿不了了谁就输了。
  问胜负情况
• 1 ≤ n ≤ 1 0 9 1\le n\le 10^9 1≤n≤109

思路

• 首先容易想到，我们按照每个类 C，里面包含 c , c 2 , c 3 , ⋯ c,c^2,c^3,\cdots c,c2,c3,⋯
  容易想到，任何两个类之间的交集都为空。
  所以我们可以看做是这几个类的简单游戏的 $sg$ 值的异或值就是整个游戏的 $sg$ 值。
  一个类最多有 $30$ 个元素。由于 $c$ 并不影响这个类的 $sg$ 值，只有这个集合的大小才影响。
  所以我们就是问：$sg(x)$ ，其中 $x=|C|$ 的值是多少？
• 按照下标来拿，如果拿了下标 $i$，那么要同时拿走下标 $2i,3i,4i,\cdots$
  但是每个集合都可以拿走下标 $1$ 来把所有的东西给拿走。看起来是一定先手必胜的，但是只能知道它的 $sg>1$，并不知道具体的 $sg$，我们怎么算呢？
• 容易想到，这是一个状压 $dp$，设我们目前拿走的下标位置集合为 $S$，我们枚举所有下一次的转移位置 $i$，然后获取一个 $mex$ 即可。
  但是复杂度 O ( 2 30 × 30 ) O(2^{30}\times 30) O(230×30)，这不是铁炸？？那就打个表，反正就 $30$ 个值呗。
• 但是 $n$ 很大。我们想到，如果 $x>sqrt(n)$，那么 $|S|=1$，就直接获取有多少个这样的 $x$ 就好了。
  但是要保证这个 $x$ 并不是某一个数的几次方。

代码

• 时间复杂度： O ( n log ⁡ n ) O(\sqrt n\log n) O(n ​logn)

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}const int MAX = 1e5+50;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-7;void out(int mex){puts(mex?"Vasya":"Petya");
}bool vis[MAX];map<int,int>M;int sg[50]={0,1 ,2 ,1 ,4 ,3 ,2 ,1 ,5 ,6 ,2 ,1 ,8 ,7 ,5 ,9 ,8 ,7 ,3 ,4 ,7 ,4 ,2 ,1 ,10 ,9 ,3 ,6 ,11 ,12 ,14};
int all;
int SG(int x){if(x == 0)return 0;if(M[x])return M[x];int ed = (1LL << x) - 1;map<int,int>mex;for(int i = 0;i < all;++i){if((x & (1LL << i))){int tmp = x;for(int j = 1;j * (i + 1) <= all;++j){int duo = (1LL << (((i + 1) * j) - 1));if(tmp & duo)tmp -= duo;}
//            show(x,tmp);mex[SG(tmp)] = 1;}}for(int i = 0;;++i){if(!mex[i]){return M[x] = i;}}
}int main()
{
//    for(int i = 1;i <= 40;++i)sg[i] = -1;
//    for(all = 1;all <= 30;++all){
//        cout << SG((1<
//    }ll n;cin >> n;int ans = 1;int you = 1;for(ll i = 2;i * i <= n;++i){if(vis[i])continue;int cnt = 1;ll tmp = i;while(tmp * i <= n){tmp *= i;if(tmp <= 100000)vis[tmp] = 1;cnt++;}you += cnt;ans ^= sg[cnt];
//        show(i,cnt,SG(cnt));}if((n - you) & 1)ans ^= 1;out(ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！