Preface
感觉现在水平有点迷了,D秒出的正解然后被一个细节搞了一直过不去,打完对着代码看一眼就发现了
场场掉分这谁顶得住啊
A. Two Groups
SB题,把所有正数和负数分开放即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,x; long long t1,t2;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),t1=t2=0,i=1;i<=n;++i)
if (scanf("%d",&x),x>0) t1+=x; else t2+=x;
printf("%lld\n",max(t1,-t2)-min(t1,-t2));
}
return 0;
}
B. BAN BAN
就这SB题我还WA了一发
考虑对于每个长度为3的块,我们把它和关于中心对称位置上的数交换就可以做到\(\lceil \frac{n}{2}\rceil\)的复杂度了
举个例子,对于\(n=5\)的情形,有
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=305;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),printf("%d\n",n+1>>1),i=1;i<=n+1>>1;++i)
printf("%d %d\n",3*(i-1)+1,3*n-(3*(i-1)+1)+1);
}
return 0;
}
C. Swap Game
现在拿到这种博弈我都是先码个暴力然后开始找性质,然后猜个结论直接过
先给出结论:若\(a_1\)是整个序列中的最小值,那么先手必败,否则先手必胜
证明的话考虑用归纳法,设\(m=\min_{i=1}^n a_i\),当\(m=1\)时:
- 若\(a_1=1\),显然此时先手必败
- 若\(a_1\ne 1\),此时先手可以把后面的\(1\)换到前面来,就转化成了必败态,因此此时先手必胜
设当\(m=t\)时结论成立,当\(m=t+1\)时:
- 若\(a_1=t+1\),无论先手把这个数换到哪里,后手只要把它换回来就转化成了\(a_1=t\)的先手必败态,因此此时先手必败
- 若\(a_1\ne t+1\),先手只要把后面的\(t+1\)换到前面来即可,此时先手必胜
因此结论成立,直接做即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
bool flag=0; for (i=2;i<=n&&!flag;++i) if (a[1]>a[i]) flag=1;
puts(flag?"Alice":"Bob");
}
return 0;
}
D. Yet Another Problem
妈的写错一个巨ZZ的地方害得我一直以为思路有问题,最后心态爆炸
大致问题就是我开了一个map <int,vector <int>> s[2];
然后想在每一个存在的元素后面加一个\(n+1\),结果这样写
for (auto v:s[0]) v.second.push_back(n+1); for (auto v:s[1]) v.second.push_back(n+1);
直接寄了,因为这只是修改迭代器对应的值,并没有真正修改要改的地方,后面写成这样就可以了
for (auto v:s[0]) s[0][v.first].push_back(n+1); for (auto v:s[1]) s[1][v.first].push_back(n+1);
好了下面开始讲正题
首先我们分别考虑二进制下每一位,不难发现我们的操作不会改变这一位上\(1\)的数目的奇偶性
因此每一位上\(1\)的个数必须是偶数,因此一个有解的充要条件是区间的异或和为\(0\)
接下来考虑算答案,首先先特判掉区间内全为\(0\)的情况,然后如果区间长度是奇数答案也显然是\(1\)
考虑区间长度为偶数的情况,先排除掉两个端点存在\(0\)的情形,此时答案仍然为\(1\)
否则我们可以把一个长度为偶数的区间划分成两个长度为奇数的区间,只要保证两个子区间的异或和都为\(0\)即可
由异或的性质知找到一个子区间\([l,k],k<r]\and 2 \nmid k-l+1\)即可,即找到\(pfx_k=pfx_{l-1}\),其中\(pfx\)为异或前缀和
我们可以把下标奇偶分开讨论,考虑用map
记录下满足\(pfx_i=x\)对应的\(i\)下标集合
然后询问的时候在上面二分找到第一个出现在\(l\)后面的下标,判断是不是在\(r\)之前即可
(其实只要从前往后扫一遍记录下每个数能和它凑出的长度最短的异或和为\(0\)的奇数区间的下标即可,但是比赛的时候太执着于算法本身的正确性而没去想实现的细节错误)
#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,q,a[N],pfx[N],l,r; map <int,vector <int>> s[2]; long long sum[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d",&n,&q),s[0][0].push_back(0),i=1;i<=n;++i)
scanf("%d",&a[i]),pfx[i]=pfx[i-1]^a[i],sum[i]=sum[i-1]+a[i],s[i&1][pfx[i]].push_back(i);
for (auto v:s[0]) s[0][v.first].push_back(n+1); for (auto v:s[1]) s[1][v.first].push_back(n+1);
for (i=1;i<=q;++i)
{
scanf("%d%d",&l,&r); int cur=pfx[r]^pfx[l-1];
if (sum[r]-sum[l-1]==0) { puts("0"); continue; }
if (cur) { puts("-1"); continue; }
if ((r-l+1)&1) { puts("1"); continue; }
if (a[l]==0||a[r]==0) { puts("1"); continue; }
if (!s[l&1].count(pfx[l-1])) { puts("-1"); continue; }
int pos=*lower_bound(s[l&1][pfx[l-1]].begin(),s[l&1][pfx[l-1]].end(),l);
puts(pos<=r?"2":"-1");
}
return 0;
}
原文地址:http://www.cnblogs.com/cjjsb/p/16864918.html