首页 > 代码库 > 玲珑杯 #9 A 质数 B 博弈 C 不会
玲珑杯 #9 A 质数 B 博弈 C 不会
玲珑杯 #9
tangjz老师出的题，一伙大佬来抢钱，本菜鸡连签到题都做不了，只能补补题了==
官方题解
A.Check-in Problem
题意：判断n是否恰好有p个因子，p为质数，1<=n<=1e18，p>2。
tags： 1、因为p>2知n肯定是一个大于1的非素数，由算术基本定理N=(P1^a1)*(P2^a2)*(P3^a3)......(Pn^an)， n的因子个数就是(a1+1)×(a2+1)×(a3+1)×...×(an+1)。又因为p是质数，所以n的质因子只能有一个p1，且n=p1^(p-1)。 2、所以只要判断n开p-1次方是质数即可。对于p>3的情况，直接预处理出1e6内的质数就行；对于p==3的情况，用 Miller-Rabin 算法判定（需要 O(1) 的模乘法）。 但不知道哪里错了，挖了十几发都过不了，留坑待补。
B.Alice and Bob
题意：k层的完美二叉树，两人博弈，轮流任取一个点，必须从这个点选取出数，如果有儿子就转给儿子，如果是叶子结点就移除。最后不能操作的人败，问先手第一次操作有几种方案可保证胜。
tags：题解说用SG函数，还不太会SG，后面补一下吧。。但这个题类似于阶梯博弈，也可以做，只要看奇数层就行。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 2e6+10;int b[N], a[N], t, T, k, tt;ll s, m, sum;int main(){ scanf("%d", &T); while(T--) { t=tt=1, s=sum=0; mes(b, 0); scanf("%d", &k); FF(i,1,k) for(int j=1; j<=(1<<(i-1)); j++) { scanf("%d", &a[t]); if((k-i+1)&1) s^=a[t], b[tt++]=t ; t++; } if(s==0) printf("0\n"); else { FF(i,1,tt-1) { m=s^a[b[i]]; if(m<a[b[i]]) { if(b[i]>=(1<<(k-1))) sum++; else sum+=2; } else if(a[(b[i]>>1)]>=(m-a[b[i]])) sum++; } printf("%lld\n", sum); } } return 0;}
C. Red Packets
题意：n种商品，价格ai，开心值bi。有金钱k元，选取连续的多件商品，可以免费m件。问在花费k元钱内，可以获得最大开心值是多少。
tags：虽然这题目有点熟悉，但不会做。。
玲珑杯 #9 A 质数 B 博弈 C 不会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。