SDNU_ACM_ICPC_2021_Winter_Practice_3rd [个人赛]
E – Being a Good Boy in Spring Festival
题意：
桌子上有M堆扑克牌，两个人玩，每人每次可以取任意一堆中任意数量的扑克牌，直至扑克牌全被取完，取走最后一步的那个人获胜，为先手的人想赢，第一步有几种选择
思路：
我做的时候对题目理解不深，觉得这样例不止1种赢法啊，后来才发现我还是太蒻了
这是一道尼姆博弈的变形题
先从最简单的模型说起：有三堆若干个物品，每次至少拿一个，多者不限，最后取光者胜。
要想制造必胜局，我们得让对面陷入一种必败态，然后维护这种必败态即可，所以我们可以想一下必败态是什么样的，最特殊的必败态是（0,0,0），这样的情况下是对方已经取完最后的物品，获胜了。再仔细分析一下（0,n,n）也是一种必败态，为什么呢 ？因为无论我选择取哪一堆的多少物品，对方只需要在另一堆上取相同数目的物品，保持（0,n,n）的局势，取到最后一定会变成（0,1,1）的局势，这样我只能取一个物品，剩下的那个物品对方就可以取了获胜。再仔细想想，（1,2,3）其实也是一种必败态，因为无论我如何取，取多少，对方都可以将局势变成（0,n,n）的必败态。
我们将这种局势统称为奇异局势，那这种奇异局势有什么特点呢？
也不知道是谁这么牛逼，竟然能把这种局势和二进制连续在一起
对于奇异局势来说，a ^ b ^ c其实是等于0的。第一种必败态就不用说了全是0，异或完了也是0，对于第二种，n^n其实也是0，因为任何数异或她本身得到的绝对是0，对于第三种（a,b,c）类的异或和也是0
如果我们面对的是一个非必败态（a,b,c），要如何变成必败态呢？
我们假设a < b <c,我们只需要将c变成a ^ b即可，因为这样的话c ^ (a ^ b)就是0了，符合必败态的规律，所以对于三堆物品，我们第一步只需要取c – (a ^ b)个物品即可
不知道，你看懂没……如果还是没懂，就给个面子装懂好嘛……
现在将尼姆博弈模型推广一下，有n个物品堆，两人人轮流在任意的物品堆取任意多的物品，最后取光者获胜
同样的（a,b,c,……n）堆物品，我们需要先求出abc……n的值，然后对每一堆进行判断，看需要取几个能构成必败态，也就是判断一下是否满足如下条件即可
if(tr[i] > (sum ^ tr[i]))
sum^tr[i]得到的是除了第i堆以外其他堆的数的异或和，如果我们能让第i堆的值等于剩下的所有值的异或和，那么他们异或起来的值肯定是0，即符合奇异局势
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
inline int re()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
ll n, tr[10005], sum, ans;
int main()
{
while(cin>>n && n)
{
ans = 0;
sum = 0;
for(int i = 1; i <= n; i++)
{
cin>>tr[i];
ans ^= tr[i];
}
for(int i = 1; i <= n; i++)
{
if(tr[i] > (ans ^ tr[i]))
sum++;
}
cout<<sum<<endl;
}
return 0;
}
A – Cards for Friends
题意：
一个长为w，宽为h的纸片，边长为偶数则可以对半剪，问你这张纸片剪出来的数量能否大于n
思路：
对长和宽分别进行除二操作，看看总共能整除几次2，有几次就说明纸片的数量可以翻倍，最后用过pow（2，sum）即可求出最多的纸片数量
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, m,sum, ans, tr[100005], a,b;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
int main()
{
n = IntRead();
while(n--)
{
sum = 0;
a = IntRead();
b = IntRead();
m = IntRead();
while(a % 2 == 0)
{
sum++;
a /= 2;
}
while(b % 2 == 0)
{
sum++;
b /= 2;
}
if(pow(2, sum) >= m)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
// cout<<sum;
}
return 0;
}
B – Even-Odd Game
题意：
Alice和Bob一起玩一个关于数组tr的游戏，Alice先手，每轮可以取一个数x，如果是Alice取，且x为偶数，则Alice的权值加上x，若为奇数，则权值不变，用掉一个数就从数组里扔掉；如果是Bob取，且x为奇数，则Bob的权值加上x，若x是偶数，则权值不变，该数照样从数组中扔掉，问你最终谁的权值大
思路：
我们可以先对数组排个序，根据得分规则，他们可以选择拿走让自己加分的数字来提高自己，也可以通过拿走不能让自己加分的数字，让对手不能选这个分，所以我们只需要对排序完的数组的最大数开始往下遍历，分情况讨论，最终记录个自的权值，比较后输出输赢
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int re()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
ll sum1, sum2, n, m, tr[200005];
int main()
{
m = re();
while(m--)
{
sum1 = 0;//Alice的权值
sum2 = 0;//Bob的权值
n = re();
int k = 2;//用来调整抽数的人，我规定的是偶数的时候是Alice抽，奇数是Bob抽，和题干对应了起来
for(int i = 1; i <= n; i++)
tr[i] = re();
sort(tr + 1, tr + 1 + n);//排序
for(int i = n; i > 0; i--)//从大数开始遍历
{
if(tr[i] % 2 == 0)//先看这个数是奇数还是偶数
{
if(k % 2 == 0)//再看这轮是Alice还是Bob
{
sum1 += tr[i];//是Alice又是偶数，就让Alice的权值加上tr[i]
k++;//让k++，保证下一次是Bob抽数
}
else
{
k++;
}
}
else//道理同上，不赘述
{
if(k % 2 == 0)
{
k++;
}
else
{
sum2 += tr[i];
k++;
}
}
}
if(sum1 > sum2)
cout<<"Alice"<<endl;
else if(sum1 < sum2)
cout<<"Bob"<<endl;
else
cout<<"Tie"<<endl;
}
return 0;
}
J – 剪花布条
题意：
给你连个字符串s1,s2，让你找s1中有几个不重复的s2
思路：
1.KMP
2.用find函数加erase函数
#include<bits/stdc++.h>
using namespace std;
int next1[1000005];
string s, ss;
int n, m, ans ;
void getnext()//构建next1数组
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;
while(j < m)
{
if(k == -1 || ss[j] == ss[k])
next1[++j] = ++k;
else
k = next1[k];
}
}
int kmp()
{
ans = 0;//用来记录出现几次
int i = 0;//i是用来记录被搜字符串的位置
int j = 0;//j是用来记录要搜的字符串的位置
getnext();
while(i <= n && j <= m)
{
if(j == m)//当找到符合的子串就让ans++,j = 0重新开始找
{
ans ++;
j = 0;
continue;
}
if(j == -1 || s[i] == ss[j])//如果相等就继续匹配下一个字符，所以是让i++，j++
{
i++;
j++;
}
else
j = next1[j];//如果不匹配，就让j = 0;
}
return ans;
}
int main()
{
while(cin>>s)
{
if(s[0] == '#')
break;
else
{
cin>>ss;
n = s.size();
m = ss. size();
cout<<kmp()<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
string a, b;
int sum;
while(cin>>a)
{
if(a[0] == '#')
break;
else
{
cin>>b;
sum = 0;
while(a.find(b) != -1)
{
a.erase(a.begin(),a.begin() + a.find(b) + b.size());
sum++;
}
}
cout<<sum<<endl;
}
}
M – Fair Division
题意：
有若干个重量为1或2的糖果，问在糖果不能切开的前提下能否均分
思路：
刚开始我是考虑的计算一下所有糖果的总重量，以及糖果块数，然后判断一下如果二者都能除以2就可以均分，然后就wa了，因为只有是1,2，2,2，就能把我卡掉，所以我就想看看利用贪心使得循环一次，能不能让ans的值达到sum的一半，肯定不能排序然后取小的，因为1,2,1,2，就能卡死你，所以我就开始想边贪大的边贪小的。然后我就发现，想让值可以达到sum一半，肯定是1越多越好，这样可以随便凑数，而且1的数量必须是偶数。再分析一下你会发现，当1的数量不是0，且是偶数的时候，绝对成立！为什么呢？因为我们要让ans的值能等于sum的一半，所以我们先取2，这样凑的快，因为你如果想平分sum，那么sum必须是偶数，这个时候我们讨论一下2的数量，如果2的数量刚好满足2*num == sum / 2,那就是直接成立，如果2 * num大于 sum / 2,则也一定成立，为什么呢？因为我只需要让ans的值离sum / 2 差2 的时候，用1来补即可，（1的数量是偶数，可以分得开），如果2 * num 小于 sum / 2的时候就更棒了，因为你有大把大把的1可以随意支配。故当1的数量不为0且为偶数时，绝对能分出重量相等的糖果，剩下的就是讨论一下1的数量是不是0，如果是0，就看看m能不能除尽2，（m是糖果的数量，这里因为没有1，只有2，所以当数量是2 的倍数就可以成立）
我罗里吧嗦这么多还是不如直接看代码趴
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, m,sum, ans, tr[100005], a,b;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
int main()
{
n = IntRead();
while(n--)
{
ans = 0;//用来计算糖果总重量
sum = 0;//用来统计有几个1
m = IntRead();
while(m--)
{
cin>>k;
if(k == 1)//计算1的数量
sum++;
else
ans++;
}
if(sum == 0)
{
if(ans % 2 == 0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
else
{
if(sum % 2 == 0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}
是不是更简单一点哩
