Preface
打的就是依托答辩居然也能上分，看来手稳还是重要的说
D题半场开香槟以为随便写，然后没想到怎么处理这个局部没有三分性的函数，直接GG
后面听学长一说其实分成四种函数分别求最值即可直接恍然大悟，只能说还是太菜太菜
而且F好像是个蓝桥杯的某个题的弱化版，我说比赛的时候怎么那么多人艹过去
A. Vika and Her Friends
这场的题面简直就是灾难级别的，A题搞懂题意都快5min了
不难发现可以对格子进行黑白染色，如果有一个朋友和Vika在同色格子内最后就一定能捉到
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=105;
int t,n,m,k,X0,Y0,x,y,s[2];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d%d%d%d",&n,&m,&k,&X0,&Y0),s[0]=s[1]=0,i=1;i<=k;++i) scanf("%d%d",&x,&y),++s[(x+y)&1];
puts(s[(X0+Y0)&1]?"NO":"YES");
}
return 0;
}
B. Vika and the Bridge
又是题面杀，做法其实很简单
刚开始最大值最小一眼二分，后面发现不需要
直接枚举最后走的是哪种颜色，然后扫一遍求一下相邻元素的最大值与次大值
考虑修改的话就是把最大值的贡献减半，再和之前的次大值取较大的一个更新答案即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005,INF=1e9;
int t,n,k,c; vector <int> pos[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&c),pos[c].push_back(i);
int ans=INF; for (i=1;i<=k;++i) if (pos[i].size())
{
int mx=0,smx=0,lst=0; for (int x:pos[i])
{
if (x-lst-1>mx) smx=mx,mx=x-lst-1;
else if (x-lst>smx) smx=x-lst-1; lst=x;
}
if (n-lst>mx) smx=mx,mx=n-lst;
else if (n-lst>smx) smx=n-lst;
ans=min(ans,max(smx,mx/2)); pos[i].clear();
}
printf("%d\n",ans);
}
return 0;
}
C. Vika and Price Tags
刚开始搞错了最后\((0,x)\)后的循环节，以为是以\(2\)为循环然后一直跑不过样例，后面发现后真想抽自己大耳光子
首先不难发现我们只要求出每组位置\((a_i,b_i)\)第一次变成\((0,x)\)这种形式所需要的步数，最后如果要让所有数都为\(0\)就需要所有的步数对\(3\)取模的值相同
而怎么求这个东西，直接暴力辗转相减显然不可取，但我们可以找一手规律
不妨设\(n>m\)，则在\(3\)次操作后\((n,m)\)会变成\((n,n-2\times m)\)，利用这个可以快速缩减数据规模
最后单组的次数求解大概是\(O(\log a_i)\)级别的，总之可以跑过
注意特判两个数都是\(0\)的情况
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int t,n,a[N],b[N];
inline int calc(int n,int m)
{
//printf("%d %d\n",n,m);
if (!n) return 0; if (!m) return 1;
if (n<m) return calc(m,m-n)+1;
int t=(n/m)/2,step=t*3; n-=t*2*m;
if (!n) return step;
if (n<m) return step+calc(n,m);
return step+calc(m,n-m)+1;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
for (i=1;i<=n;++i) scanf("%lld",&b[i]); int s[3]={0,0,0};
for (i=1;i<=n;++i)
{
if (!a[i]&&!b[i]) continue;
++s[calc(a[i],b[i])%3LL];
}
if (!s[0]&&!s[1]&&!s[2]) { puts("YES"); continue; }
if (s[0]&&!s[1]&&!s[2]) { puts("YES"); continue; }
if (s[1]&&!s[0]&&!s[2]) { puts("YES"); continue; }
if (s[2]&&!s[0]&&!s[1]) { puts("YES"); continue; }
puts("NO");
}
return 0;
}
D. Vika and Bonuses
这个题一眼看上去实在是太板了，考虑对于做了\(x\)次加数操作的情况，一定是先把\(x\)次加数都加了然后再乘上\(k-x\)
然后这个东西一眼看上去实在太像个单峰函数了，所以感觉直接三分\(x\)，而加数的过程很容易发现除了\(0,5\)外都有长度为\(4\)的循环节，随便搞一下就好了
但是飞速写完发现怎么连样例都过不了，后面一想其实是因为这是个多个单峰函数复合的函数，只有整体的单峰性，但局部可能会有偏差
处理方法大致有两种，一种是三分的时候每次取分点的左右各\(10\)各点左右，取最大值来作为比较的依据
不过注意这样最后区间长度要保证是一个较大的数，最后再暴力扫一遍区间即可，感觉是个很好用的trick以后有机会可以试试
另一种比较科学的方法就是做四次三分，每次三分规定后面加数操作一定是\(4\)的倍数，这样得到的一定是一个二次函数的形式，显然是可以三分的
这里的代码写的是后面的做法
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
int t,s,k,num[10],d[10],cnt;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i,j; scanf("%lld%lld",&s,&k); memset(num,-1,sizeof(num));
int len,st; for (num[s%10]=0,d[cnt=0]=s;;)
{
s+=s%10; if (~num[s%10])
{
len=cnt+1-num[s%10]; st=num[s%10];
d[++cnt]=s; break;
} else num[s%10]=cnt+1,d[++cnt]=s;
}
int ans=0; for (i=0;i<=min(st,k);++i) ans=max(ans,d[i]*(k-i));
int dlt=d[cnt]-d[st];
if (k>=st)
{
auto calc=[&](int x)
{
x-=st; int c=d[st]+x/len*dlt;
c+=d[st+x%len]-d[st]; return (k-x-st)*c;
};
for (i=st;i<=min(st+len-1,k);++i)
{
int l=0,r=(k-i)/len;
while (r-l>2)
{
int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
if (calc(lmid*len+i)<=calc(rmid*len+i)) l=lmid; else r=rmid;
}
for (j=l;j<=r;++j) ans=max(ans,calc(j*len+i));
}
}
printf("%lld\n",ans);
}
}
E. Vika and Stone Skipping
搞不懂出题人为什么喜欢搞不定模数，就是给题徒增难度是吧
对于等差数列求和，不妨设求和的区间为\([l,r]\)，最后得到的数为\(t\)，则\(\sum_{i=l}^ r i=\frac{(l+r)\times (r-l+1)}{2}=t\)，等价于\((l+r)\times (r-l+1)=2t\)
稍加讨论一下会发现左边的两个式子的奇偶性一定不同，因此我们可以想到把\(2t\)分成奇偶性不同的两个因子，同时我们惊喜地发现这种划分方案和\([l,r]\)的取法一一对应
那么现在问题就很简单了，我们对于\(2t\)做一遍质因数分解，所有的\(2\)必须放在某一边，而其它的质因子都可以随便放
方案数其实就是一个数的约数个数的式子的变形，即\(\prod_{p_i\ne 2} (c_i+1)\)
然后实现的时候要注意一个坑点，由于\((c_i+1)\)可能是模数的倍数，因此直接搞会出现某些数没有逆元的情况
这种问题的处理方法也比较经典了，考虑记录一下此时整个式子乘上\(0\)的个数，输出的时候判断下即可，具体看代码吧
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=1e6+5;
int x,q,mod,cnt[N],ans=1,cnt0;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void calc(int x)
{
for (RI i=2;i*i<=x;++i) if (x%i==0)
{
if (i!=2)
{
if ((cnt[i]+1)%mod) ans=1LL*ans*quick_pow(cnt[i]+1)%mod; else --cnt0;
}
while (x%i==0) x/=i,++cnt[i];
if (i!=2)
{
if ((cnt[i]+1)%mod) ans=1LL*ans*(cnt[i]+1)%mod; else ++cnt0;
}
}
if (x>1)
{
if (x>1000000) return (void)(ans=2LL*ans%mod);
if (x!=2)
{
if ((cnt[x]+1)%mod) ans=1LL*ans*quick_pow(cnt[x]+1)%mod; else --cnt0;
}
++cnt[x];
if (x!=2)
{
if ((cnt[x]+1)%mod) ans=1LL*ans*(cnt[x]+1)%mod; else ++cnt0;
}
}
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d",&x,&q,&mod),calc(x),i=1;i<=q;++i)
scanf("%d",&x),calc(x),printf("%d\n",cnt0?0:ans);
return 0;
}
F. Vika and Wiki
额蓝桥杯某题究极弱化版来了，当时那题我记得\(n\)还不是\(2\)的幂次，所以写起来还有些细节
这题其实就是利用一个关键性质，在操作\(2^t\)次后\(a'_i=a_i\oplus a_{(i+2^t)\bmod 2^k}\)，我记得当时我做蓝桥杯那题的时候是找规律发现的，其实归纳一下很好证明
有了这个我们会发现在操作\(2^k\)序列一定会变成全\(0\)，那么有没有更少的次数可能呢
考虑分治，对于当前长度为\(n\)的序列，不妨分成前面\(\frac{n}{2}\)和后面\(\frac{n}{2}\)来考虑
如果对于\(\forall i\in[0,\frac{n}{2}),a_i=a_{i+\frac{n}{2}}\)，则操作\(\frac{n}{2}\)就是完全没有必要的，否则我们必须进行这次操作
很容易发现可以把上面的东西写成一个分治的形式，具体实现看代码
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=20;
int n,a[1<<N];
inline int solve(CI n)
{
if (n==1) return a[0]!=0;
RI i; bool flag=1; for (i=0;i<n/2&&flag;++i)
if (a[i]!=a[i+n/2]) flag=0;
if (flag) return solve(n/2);
for (i=0;i<n/2;++i) a[i]^=a[i+n/2];
return n/2+solve(n/2);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=0;i<n;++i) scanf("%d",&a[i]);
return printf("%d",solve(n)),0;
}
Postscript
好好好不掉分就算成功
标签：cnt,const,885,int,Codeforces,pair,Div,include,define From： https://www.cnblogs.com/cjjsb/p/17566746.html