Preface
AB很水，C一般难度，D1很简单但D2确实巧妙
没有现场打有点可惜，后面补的时候都是1A（结果每次比赛的时候都要莫名WA上好久）
A. Bestie
我刚开始没咋想，感觉操作步数不会很多，直接Rush了一个爆搜上去
其实只用看最后两个位置即可，因为\(\gcd(n,n-1)=1\)，因此答案最多是\(3\)
#include<cstdio>
#include<vector>
#include<queue>
#define RI register int
#define CI const int&
#define mp make_pair
using namespace std;
typedef vector <int> VI;
const int N=25;
int t,n,a[N]; priority_queue < pair<int,VI> > hp;
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
inline int calc(VI& v)
{
int ret=v[0]; for (RI i=1;i<n;++i) ret=gcd(ret,v[i]); return ret;
}
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]);
while (!hp.empty()) hp.pop(); VI cur; cur.clear();
for (i=1;i<=n;++i) cur.push_back(a[i]); hp.push(mp(0,cur));
while (!hp.empty())
{
cur=hp.top().second; int ret=-hp.top().first,G=calc(cur); hp.pop();
if (G==1) { printf("%d\n",ret); break; }
for (i=1;i<=n;++i)
{
VI apd=cur; apd[i-1]=gcd(apd[i-1],i);
int NG=calc(apd); if (NG<G) hp.push(mp(-(ret+n-i+1),apd));
}
}
}
return 0;
}
B. Ugu
首先简单观察我们发现，所有相邻的相同的数是可以合并的，我们每次操作都取这一颜色段的开头即可
那么现在问题就变成对于一个\(01\)间隔的串的问题了，直接从前往后贪心就能得到答案，稍作总结就能得到式子
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,sum; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%s",&n,s+1),sum=0,i=2;i<=n;++i)
if (s[i]!=s[i-1]) ++sum; printf("%d\n",max(0,sum-(s[1]=='0')));
}
return 0;
}
C1. Sheikh (Easy version)
大概讲一下C1的做法吧（虽然我没写代码）
首先由于异或是不进位的加法，因此区间变大\(f(l,r)\)肯定是不会变小的，因此我们就要找出最小的区间使得其值等于\(f(1,n)\)
容易想到当一个端点固定时，另一个端点的取值具有可二分性，因此可以二分或者双指针来做
C2. Sheikh (Hard Version)
我们考虑在什么情况下一个区间的值是等于\(f(L,R)\)的，放在二进制下来看就是每一个二进制位上1的个数不能超过一个
\(10^9\)范围内最多只有\(30\)个二进制位，如果我们不考虑\(0\)的话，显然最多只能在\([L,R]\)的基础上拿走\(31\)个数
因此把\(0\)剔除掉直接从两端向内暴力找即可，复杂度\(O(q\log a_i)\)
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=100005;
int t,n,q,a[N],L,R,pos[N],cnt,pxor[N]; LL psum[N];
inline LL calc(CI l,CI r)
{
return psum[r]-psum[l-1]-(pxor[r]^pxor[l-1]);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d",&n,&q),cnt=0,i=1;i<=n;++i)
{
if (scanf("%d",&a[i]),a[i]) pos[++cnt]=i;
psum[i]=psum[i-1]+a[i]; pxor[i]=pxor[i-1]^a[i];
}
while (q--)
{
scanf("%d%d",&L,&R); LL tar=calc(L,R);
int l=lower_bound(pos+1,pos+cnt+1,L)-pos;
int r=upper_bound(pos+1,pos+cnt+1,R)-pos-1;
int ansl=0,ansr=n+1; for (i=l;i<=r;++i)
{
if (calc(pos[i],pos[r])<tar) break;
for (j=r;j>=i;--j)
{
if (calc(pos[i],pos[j])<tar) break;
if (pos[j]-pos[i]+1<ansr-ansl+1) ansl=pos[i],ansr=pos[j];
}
}
if (ansl) printf("%d %d\n",ansl,ansr); else printf("%d %d\n",L,L);
}
}
return 0;
}
D1. Balance (Easy version)
还是讲个想法（因为也没写代码）
不难发现由于没有删除操作，因此对于同一个\(k\)，它询问的结果是单调不减的
因此可以直接用一个\(lst_k\)记录下\(k\)的答案，下次直接从这个\(lst_k\)开始往后跳即可
由于每个\(k\)最多向后跳\(\frac{n}{k}\)个点，因此总复杂度是\(O(n\log n)\)的，加上map是两只\(\log\)
D2. Balance (Hard version)
考虑换一种统计mex的方式，对于一个数\(k\)，我们令一个集合\(S_k=\{0,k,2k,3k,\cdots\}\)
然后每当一个数\(t\times k\)出现后，我们把这个数在\(S_k\)中删去，这样k-mex的值就是集合\(S_k\)中最小的元素了
那么这里我们一样，考虑统计出当一个数\(x\)被删去后，它会导致哪些\(k\)的k-mex发生改变，显然只要在跳\(lst_k\)的时候顺带维护下即可
对于每一个询问的\(k\)，若\(S_k\)为空答案就是\(lst_k\)，否则就是\(S_k\)中最小的元素
由于当一个数被丢进\(S_k\)时所有小于等于它的数都已经出现过了，因此我们不需要维护初始的满的\(S_k\)，等有删除时直接插入即可
复杂度的话考虑均摊分析，大概就是D1的基础上加一个\(\log n\)的复杂度（这个复杂度是set的，算法本身的复杂度没变）
#include<cstdio>
#include<map>
#include<set>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
map <int,int> vis,lst; map <int,set <int>> del; map <int,vector <int>> rmv;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
int q,x; for (scanf("%lld",&q);q;--q)
{
char ch; while (ch=getchar(),ch!='+'&&ch!='-'&&ch!='?');
scanf("%lld",&x); switch (ch)
{
case '+':
vis[x]=1; for (int y:rmv[x]) del[y].erase(x); break;
case '-':
vis[x]=0; for (int y:rmv[x]) del[y].insert(x); break;
case '?':
if (!lst.count(x)) lst[x]=x;
if (!del[x].empty()) printf("%lld\n",*del[x].begin()); else
{
while (vis[lst[x]]) rmv[lst[x]].push_back(x),lst[x]+=x;
printf("%lld\n",lst[x]);
}
break;
}
}
return 0;
}
原文地址：http://www.cnblogs.com/cjjsb/p/16837340.html
