Preface
补题
其实这场题目昨天基本就写好了，但因为昨天晚上有CF所以博客就先没写，鸽到今天才补
这场的难度只能说有点过于简单了，D之前都是一眼题，E最近学校那边做过类似的题目，F读懂题意后想到关键后也是个丁真题
A. Unit Array
为了偷懒我就直接枚举最后有多少个\(-1\)了
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,a[N],num;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),num=0,i=1;i<=n;++i) scanf("%d",&a[i]),num+=a[i]==-1;
int ans=n; for (i=0;i<=n;++i) if (i<=n-i&&i%2==0) ans=min(ans,abs(i-num));
printf("%d\n",ans);
}
return 0;
}
B. Maximum Strength
设\(L,R\)第一个不相同的位为\(i\)，后面还剩\(j\)位，则答案为\(R_i-L_i+9\times j\)
不难发现这是答案的上界且这个上界一定能取到，我们设\(L\)的后面\(j\)位都取\(9\)，\(R\)的后面\(j\)位都取\(0\)即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,m; char A[N],B[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; scanf("%s%s",A+1,B+1); n=strlen(A+1); m=strlen(B+1);
reverse(A+1,A+n+1); reverse(B+1,B+m+1); int len=max(n,m);
for (i=n+1;i<=len;++i) A[i]='0';
bool flag=0; for (i=len;i>=1&&!flag;--i) if (A[i]!=B[i])
printf("%d\n",B[i]-A[i]+9*(i-1)),flag=1;
if (!flag) puts("0");
}
return 0;
}
C. Game with Reversing
不妨枚举最后第二个人操作的次数\(x\)，则此时第一个人操作的次数为\(x+1\)或\(x\)
不难发现第二个人每次翻转哪个串对答案没有影响，因此我们都让它翻转\(T\)，同理规定第一个人只修改\(S\)
此时发现当\(2|x\)时，只要检验利用\(x/x+1\)次操作能否将\(S\)变成\(T\)，否则当\(2\nmid x\)时，就是把\(S\)变成\(\operatorname{Rev}(T)\)
枚举一下取总操作次数最小的即可，复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n; char A[N],B[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; scanf("%d%s%s",&n,A+1,B+1);
int d[2]={0,0}; for (i=1;i<=n;++i) d[0]+=A[i]!=B[i];
reverse(B+1,B+n+1); for (i=1;i<=n;++i) d[1]+=A[i]!=B[i];
int ans=2*n+1; for (i=0;i<=n;++i)
{
if (i+1>=d[i&1]) ans=min(ans,2*i+1);
if (i>=d[i&1]) ans=min(ans,2*i);
}
printf("%d\n",ans);
}
return 0;
}
D. Survey in Class
假设最后最高的最低的两个人对应的区间分别为\([l_1,r_1],[l_2,r_2]\)，考虑答案怎么计算
当这两个区间不交时，贡献就是\(2\times \max(r_1-l_1+1,r_2-l_2+1)\)，即我们全部问较长的那个区间对应的问题
否则当这两个区间有交时，先考虑部分相交的情况，此时\(l_1\le l_2\le r_1\le r_2\)，贡献为\(2\times \max(l_2-l_1,r_2-r_1)\)
而完全包含的情况设为\(l_1\le l_2\le r_2\le r_1\)，此时贡献为\(2\times (l_2-l_1+r_1-r_2)\)
将所有区间按照右端点排序后，考虑在选择当前这个区间的时候，挑选前面哪个区间匹配可以得到最大的贡献
上面的式子其实都很好维护，写一些数据结构维护下即可（这里写的是树状数组维护第一种情况，线段树维护后三种情况）
复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,INF=1e9;
int t,n,m,l[N],r[N],rst[N],cnt,ans; vector <int> pos[N];
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline void init(void)
{
for (RI i=1;i<=cnt;++i) bit[i]=0;
}
inline int get(RI x,int ret=0)
{
for (;x;x-=lowbit(x)) ret=max(ret,bit[x]); return ret;
}
inline void add(RI x,CI y)
{
for (;x<=cnt;x+=lowbit(x)) bit[x]=max(bit[x],y);
}
#undef lowbit
}BIT;
class Segment_Tree
{
private:
int mi[N<<2];
inline void pushup(CI now)
{
mi[now]=min(mi[now<<1],mi[now<<1|1]);
}
public:
#define TN CI now=1,CI l=1,CI r=cnt
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void build(TN)
{
mi[now]=INF; if (l==r) return; int mid=l+r>>1; build(LS); build(RS);
}
inline void updata(CI pos,CI mv,TN)
{
if (l==r) return (void)(mi[now]=min(mi[now],mv)); int mid=l+r>>1;
if (pos<=mid) updata(pos,mv,LS); else updata(pos,mv,RS); pushup(now);
}
inline int query(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return mi[now]; int mid=l+r>>1,ret=INF;
if (beg<=mid) ret=min(ret,query(beg,end,LS)); if (end>mid) ret=min(ret,query(beg,end,RS)); return ret;
}
#undef TN
#undef LS
#undef RS
}SEG_L,SEG_R,SEG_C;
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,&m),cnt=ans=0,i=1;i<=n;++i)
scanf("%d%d",&l[i],&r[i]),rst[++cnt]=l[i],rst[++cnt]=r[i];
sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
auto find=[&](CI x)
{
return lower_bound(rst+1,rst+cnt+1,x)-rst;
};
for (BIT.init(),SEG_L.build(),SEG_R.build(),SEG_C.build(),i=1;i<=cnt;++i) pos[i].clear();
for (i=1;i<=n;++i) pos[find(r[i])].push_back(find(l[i]));
for (i=1;i<=cnt;++i) for (int l:pos[i])
{
int cur=BIT.get(l-1); if (cur) ans=max(ans,2*max(cur,rst[i]-rst[l]+1));
ans=max(ans,2*(rst[l]-SEG_L.query(l,i)));
ans=max(ans,2*(rst[i]-SEG_R.query(l,i)));
ans=max(ans,2*(rst[i]-rst[l]-SEG_C.query(l,i)));
BIT.add(i,rst[i]-rst[l]+1); SEG_C.updata(l,rst[i]-rst[l]);
SEG_L.updata(i,rst[l]); SEG_R.updata(i,rst[i]);
}
printf("%d\n",ans);
}
return 0;
}
E. MEX of LCM
首先最后答案的范围一定不会很大，不妨设\(LIM=10^9\)来表示答案的上界
考虑求出以\(i\)为右端点向前的不同种的\(\operatorname{lcm}\)，类似于我们求区间\(\gcd\)那样
由于向前的\(\gcd\)只用\(\log a_i\)种，因此不同的且不超过\(LIM\)的\(\operatorname{lcm}\)也应该只有\(\log a_i\)种
用set存上面的东西，复杂度就是\(O(n\log^2 a_i)\)，实际上跑起来很快
#include<cstdio>
#include<iostream>
#include<set>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=300005,INF=1e9;
int t,n,a[N]; set <int> vis;
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
inline int lcm(CI n,CI m)
{
return n/gcd(n,m)*m;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i; for (scanf("%lld",&n),vis.clear(),i=1;i<=n;++i) scanf("%lld",&a[i]);
set <int> s; for (vis.insert(a[1]),s.insert(a[1]),i=2;i<=n;++i)
{
set <int> tmp; for (int x:s) tmp.insert(lcm(x,a[i]));
int x; while (!tmp.empty()&&(x=*(--tmp.end()))>INF) tmp.erase(x);
s=tmp; s.insert(a[i]); for (int x:s) vis.insert(x);
}
int x=1; while (vis.count(x)) ++x; printf("%lld\n",x);
}
return 0;
}
F. Typewriter
整道题的最大难点在于理解题意，后面的都很自然了
由于最后我们要把数组变成\(1,2,\cdots,n\)，然后给出的是一个排列，这就很难不让人联想到置换
考虑如果我们连出所有的\(i\to p_i\)的边，则最后图形成了若干个置换环
而需要重置的操作次数是多少呢，很显然如果\(p_i\ge i\)那么直接在某次向右的过程中顺带带过去一下即可，否则就只能等着被重置带回开头了
由于一次只能带回一个元素，因此最后的答案其实就是序列中\(i<p_i\)的位置个数
知道了这点后其实就很简单了，我们分别考虑每个位置，令右循环移位为正，则可以很容易地求出当\(shift\in[i\bmod n,(i-p_i-1+n)\bmod n]\)时会产生\(1\)的贡献
因此我们只要维护一个区间加，最后能得到每个元素的值的东西，直接差分即可
最后还有一个翻转操作，那我们直接预处理的时候把整个串反过来的答案也算出来，然后翻转也很好处理了
具体实现细节可以看代码，总复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=400005;
int n,q,p[N],opt,x,shift,tp,ans[2][N];
inline void solve(int *ans,int *p)
{
RI i; for (i=1;i<=n;++i)
{
if (p[i]==n) continue;
int l=i%n,r=(i-p[i]-1+n)%n;
if (l<=r) ++ans[l],--ans[r+1];
else ++ans[0],--ans[r+1],++ans[l];
}
for (i=1;i<n;++i) ans[i]+=ans[i-1];
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&p[i]);
solve(ans[0],p); reverse(p+1,p+n+1); solve(ans[1],p);
for (printf("%d\n",ans[tp][shift]),scanf("%d",&q);q;--q)
{
scanf("%d",&opt); switch (opt)
{
case 1:
scanf("%d",&x); (shift+=x)%=n; break;
case 2:
scanf("%d",&x); shift=(shift-x+n)%n; break;
case 3:
tp^=1; shift=(n-shift)%n; break;
}
printf("%d\n",ans[tp][shift]);
}
return 0;
}
Postscript
训，训，训！