【2020CCPC网络赛】1005 Lunch(HDU6892)

题目链接

大致题意

n

n

n 堆石头,每堆有

m

i

m_i

mi​ 个石头,两个人轮流进行操作,如果有谁不能操作了,则游戏结束
而操作为:选择其中一个堆,将这个堆的分为

t

t

1

t(t \neq 1)

t(t​=1) 堆,且每堆的石头数量相同

思路

交换胜负手的关键

考虑石头个数为 8 的情况

石头个数为

8

8

8 的时候,可以做如下拆分

个数 值 直接转为 1 还需要几次操作

242424810

可以注意到,

8

8

8 只能拆出偶数个值,当然这与它的质因数只有

2

2

2 有关
注意到,无论哪种拆分,增加的操作次数都是偶数次,也就是没有交换胜负手

考虑石头个数为 81 的情况

石头个数为

81

81

81 的时候,可以做如下拆分

个数 值 直接转为 1 还需要几次操作

3273999273278110

可以注意到,

81

81

81 只能拆出奇数个值,而对于前三种拆分,增加的操作次数都是奇数,也就是会交换胜负手

交换胜负手结论

当将一堆石头分为奇数个时,会出现交换胜负手,否则不会交换胜负手
而可以分解成的奇数个数,则与这个值的质因数中非

2

2

2 的值的数量直接相关
而每次都可以取走任意个数的奇质因子个数或者取走这个值的所有

2

2

2 的因子
也就变成了简单的 nim 博弈

结论

将每个值转化为这个值的所有奇质因数的幂次和加上这个值是否为2的倍数,然后进行nim博弈即可

AC code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 100;
bool notprime[MAXN]; // 值为 false 表示素数,值为 true 表示非素数
vector<int> prime;

void init() {
memset(notprime, false, sizeof(notprime));
notprime[0] = notprime[1] = true;
for (int i = 2; i < MAXN; i++)
if (!notprime[i]) {
prime.push_back(i);
if (i > MAXN / i)
continue; // 防止后面 i*i 溢出 (或者 i,j 用 long long)
// 直接从 i*i 开始就可以,小于 i 倍的已经筛选过了, 注意是 j += i
for (int j = i * i; j < MAXN; j += i)
notprime[j] = true;
}
}

int frac(int n) {
int sum = 0, flag = 0;
for (auto item : prime) {
if (n < item) break;
while (n % item == 0) {
if (item != 2) sum++;
else flag = 1;
n /= item;
}
}
if (n > 1) sum++;
return sum + flag;
}

void solve() {
init();
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n;
cin >> n;
int res = 0;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
res ^= frac(tmp);
}
cout << (res ? "W" : "L") << endl;
}
}

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed localTestCount = 1, localReadPos = cin.tellg();
char localTryReadChar;
do {
if (localTestCount > 20)
throw runtime_error("Check the stdin!!!");
auto startClockForDebug = clock();
solve();
auto endClockForDebug = clock();
cout << "Test " << localTestCount << " successful" << endl;
cerr << "Test " << localTestCount++ << " Run Time: "
<< double(endClockForDebug - startClockForDebug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (localReadPos != cin.tellg() && cin >> localTryReadChar && localTryReadChar != '$' &&
cin.putback(localTryReadChar));
#else
solve();
#endif
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【2020CCPC网络赛】1005 Lunch(HDU6892)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【2020CCPC网络赛】1005 Lunch(HDU6892)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏