找回密码
 立即注册
首页 业界区 科技 Codeforces Round 1007 (Div. 2) A~D1个人题解

Codeforces Round 1007 (Div. 2) A~D1个人题解

薯羞 4 天前
上青纪念(这图真糊啊)
1.png

Problem - A - Codeforces
每人的最大连续比赛场数不超过二,那么显然,第一场比赛的旁观者将经历“旁观->比赛->比赛”的循环,故判断k模3是否等于1即可
2.png

交完A排第九,这辈子没这么靠前过(这图也真糊啊)
Problem - B - Codeforces
首先明确一点:如果n*(n+1)/2是完全平方数,那么符合要求的排列必然不存在(所有项求和是完全平方),故在一开始特判一下
之后用set降序存储1到n的所有数,遍历,若加上i后的前缀和不是完全平方,即将i压入ans中,最后遍历输出ans即可
至于set为什么降序呢?是因为考虑到完全平方在数轴上的排列是由稠密到稀疏,前缀和较小时,加入大数,能尽可能地跳过更多的完全平方,较大时加入小数,能尽可能地在保证前缀和在两个完全平方之间的前提下向ans数组中压入更多的数,不降序排列大约的确也是可以的
AC代码:
点击查看代码[code]#includeusing namespace std;#define ll long long#define llu long long unsigned int#define db double#define endl '\n'#define PII pairconst ll inf=0x3f3f3f3f;const ll mod=1e9+7;const ll nn=5e5+5;const ll mm=3005;const ll INF=1e18;ll n;void solve() {        cin>>n;        ll sum=(1ll*n*(n+1))/2ll;        ll x=sqrt(sum);        if (x*x==sum)         {            coutn)</p>故对于任意的m>n(m为偶数),都有am xor am+1 = 0
设a1到an的前缀异或和为x
则易得:
(1)m为奇数时,a2m = a2m+1 = x
(2)m为偶数时,a2m = a2m+1 = x xor am
故可不断缩小给出的查询值,直至其小于2n,再根据题中描述求am即可
注意一个小坑:为保证对于所有大于n的查询值都能实现奇数项和偶数项的异或相消,必须保证n为奇数,若给出的n为偶数,须自行计算an+1的值,再将n增1
AC代码:
点击查看代码[code]#includeusing namespace std;#define ll long long#define llu long long unsigned int#define db double#define endl '\n'#define PII pairconst ll inf=0x3f3f3f3f;const ll mod=1e9+7;const ll nn=1e5+5;const ll mm=3005;const ll INF=1e18;ll n,l,r;void solve() {    cin>>n>>l>>r;    vectorv(n+1);    for(ll i=1;i>v;    if(l
您需要登录后才可以回帖 登录 | 立即注册