Preface
这场现场打的，顶着第二天一早起来军训硬打到一点
这场题目都是JOJO确实好评，但刚开始的评测姬爆让人很难顶啊，因为这个B题挂了一发没法第一时间改导致这场罚时裂开了
这场写完D还有快50min，然后看一眼榜E出的人很少但是F好多人过
然后就去想F，由于军训生物钟的缘故当时好困好困，终于在还有15min结束的时候想出来大概怎么写了，结果没时间了就转头睡觉去了
最后也是给小号小上了一波分，分数已经超过大号了233
A. The Man who became a God
就是一个很裸的DP，设\(f_{i,j}\)表示前\(i\)个人分成\(j\)组，然后强制上一组以\(i\)结尾的最优方案
数据范围很小可以暴力转移，复杂度\(O(n^3)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=105,INF=1e9;
int t,n,m,a[N],f[N][N],g[N][N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) for (g[i][i]=0,j=i+1;j<=n;++j) g[i][j]=g[i][j-1]+abs(a[j]-a[j-1]);
for (i=0;i<=n;++i) for (j=0;j<=m;++j) f[i][j]=INF;
for (f[0][0]=0,i=1;i<=n;++i) for (j=1;j<=min(m,i);++j)
for (k=1;k<=i;++k) f[i][j]=min(f[i][j],f[k-1][j-1]+g[k][i]);
printf("%d\n",f[n][m]);
}
return 0;
}
B. Hamon Odyssey
刚开始一个地方没想清WA了一发，可怜滴捏
首先设\(sum=\And_{i=1}^ na_i\)，若\(sum>1\)则答案一定为\(1\)，即此时只有把所有数分成一个组才能保证答案最小
否则当\(sum=0\)时，我们就贪心地从前往后分，如果在某个时刻得到\(0\)了就直接断开，顺便统计下总个数即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],sum;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),sum=(1<<31)-1,i=1;i<=n;++i) scanf("%d",&a[i]),sum&=a[i];
if (sum!=0) { puts("1"); continue; }
int lst=(1<<31)-1,ans=0; for (i=1;i<=n;++i)
if (lst&=a[i],lst==0) ++ans,lst=(1<<31)-1;
printf("%d\n",ans);
}
return 0;
}
C. Vampiric Powers, anyone?
手玩一下不难发现答案一定是以下三种情况之一：
- 原来序列中就有的数\(a_i\)
- 原来序列的某个后缀异或和\(suf_i\)
- 原来序列的某两个位置的后缀异或和的异或值\(suf_i\oplus suf_j\)
前面两种情况很好处理，后面那个可以倒着枚举\(i\)然后查询之前出现的\(suf_j\)中与其异或值最大的那个
本来是要写0/1Trie的但由于这里的数值域很小，因此可以用桶存一下所有已经出现过的数然后枚举即可
复杂度\(O(n\times a_i)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],suf[N],bkt[1<<8],ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d",&n),ans=0,i=1;i<=n;++i)
scanf("%d",&a[i]),ans=max(ans,a[i]);
for (suf[n]=a[n],i=n-1;i>=1;--i) suf[i]=suf[i+1]^a[i],ans=max(ans,suf[i]);
for (i=0;i<(1<<8);++i) bkt[i]=0;
for (i=n;i>=1;--i)
{
for (j=0;j<(1<<8);++j)
if (bkt[j]) ans=max(ans,suf[i]^j);
bkt[suf[i]]=1;
}
printf("%d\n",ans);
}
return 0;
}
D. Professor Higashikata
分析题目要求的这个东西字典序最小，显然就是按照它给出的区间的顺序，然后保证\(1\)从左边开始填
如果第一个区间填满了就换下一个，重复的位置就忽略掉，直到所有位置都被填了或者\(1\)的数量不够了为止
举个例子比如样例二我们可以得出一个填数的位置数组\(pos=\{5,6,2,3,7,8\}\)，记其长度为\(cnt\)
有了这个其实统计答案就很简单了，我们记录下当前数组中\(1\)的个数\(num\)，然后要求的就是\(pos\)数组的前\(\min(num,cnt)\)个元素中对应的位置上为\(0\)的个数
修改的话由于只有单点修改，因此只要模拟讨论一下就行，不过里面还是有点顺序的问题啥的，写的时候样例挂了好久才调过
现在的问题就是怎么快速求\(pos\)数组，由于每个数被删除之后就不会对后面产生贡献了，因此可以用并查集来维护
用\(nxt_i\)表示\(i\)向右跳过连续一段已经删掉的数后到达的位置，每次对一个区间\([l,r]\)操作完后就直接把\([l,r]\)的\(nxt\)u全部改成\(nxt_r\)即可
总复杂度\(O(n\times \alpha (n)+q)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,m,q,l,r,x,a[N],nxt[N],num,vis[N],cnt,pos[N],ext[N],ans; char s[N];
inline int get_nxt(CI x)
{
return nxt[x]!=x?nxt[x]=get_nxt(nxt[x]):x;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d%s",&n,&m,&q,s+1),i=1;i<=n;++i)
a[i]=s[i]=='1',num+=a[i],nxt[i]=i,vis[i]=ext[i],0;
for (cnt=0,i=1;i<=m;++i)
{
scanf("%d%d",&l,&r); while (l<=r)
{
if (!vis[l]) vis[l]=1,pos[++cnt]=l;
int tmp=l; l=get_nxt(l)+1; nxt[tmp]=get_nxt(r);
}
}
//for (printf("cnt=%d\n",cnt),i=1;i<=cnt;++i) printf("%d%c",pos[i]," \n"[i==cnt]);
for (ans=0,i=1;i<=min(cnt,num);++i) if (ext[pos[i]]=1,!a[pos[i]]) ++ans;
for (i=1;i<=q;++i)
{
if (scanf("%d",&x),!a[x])
{
if (ext[x]) --ans; a[x]^=1;
if (num<cnt)
{
if (ext[pos[num+1]]=1,!a[pos[num+1]]) ++ans;
}
++num;
} else
{
if (num<=cnt)
{
if (ext[pos[num]]=0,!a[pos[num]]) --ans;
}
--num;
if (ext[x]) ++ans; a[x]^=1;
}
printf("%d\n",ans);
}
return 0;
}
E. Triangle Platinum?
很有意思的一个题，不过好像因为比赛的时候样例出锅了导致好多人被误导了的说，只能说这场真是多灾多难了
首先考虑我们什么时候能确定三个位置\(i,j,k\)上的数，显然是它们等边三角形的时候
而一旦我们确定了某两个位置\(a_i=a_j=len\)，则我们只要枚举其它的位置\(k\)并询问\(i,j,k\)，通过已知的\(len\)的信息就能判断\(a_k\)的值了
大致的想法就是这样，但实际实现的时候就会有一些问题，比如我们要怎么找到三个数构成等边三角形呢
这个其实很好解决，因为根据抽屉原理，任意\(9\)个数里一定存在三个数相同，因此可以暴力枚举先找一个等边三角形出来
而对于\(n<9\)的情况，我们大可直接暴力枚举\(a\)的取值然后检验，复杂度为\(O(4^n\times n^3)\)可以通过\(n\le 8\)的数据
但是接下来还有个问题，如果找到的等边三角形的边长\(len\ge 2\)那还好办，此时对于\(t\in[1,4]\)，三角形\((len,len,t)\)的面积都可以被相互区分
但当\(len=1\)时就会出现当\(t\in[2,4]\)时，\((len,len,t)\)的面积都是\(0\)（因为构不成三角形），就没法把它们相互区分了
处理方法也很容易，我们直接在枚举\(k\)的过程中把区分不了的（即确定值是\(\ge 2\)）的位置都记录下来
如果出现了\(4\)个及以上的位置，那么根据抽屉原理此时一定有某个值出现了两次及以上，我们可以很容易地找出这个数，然后把\(len\)换成找到的\(>1\)的边长再做上面的过程即可
总询问次数大概是\(C_9^3+C_4^2+n\)级别的，可以稳稳地通过题目限制
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#include<array>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005;
typedef array <int,3> tri;
int n,ans[N]; map <tri,int> rst;
inline int ask(CI x,CI y,CI z)
{
vector <int> v; v.push_back(x); v.push_back(y); v.push_back(z);
sort(v.begin(),v.end()); if (rst.count({v[0],v[1],v[2]})) return rst[{v[0],v[1],v[2]}];
printf("? %d %d %d\n",v[0],v[1],v[2]); fflush(stdout);
int tmp; scanf("%d",&tmp); return rst[{v[0],v[1],v[2]}]=tmp;
}
inline int calc(CI a,CI b,CI c)
{
vector <int> v; v.push_back(a); v.push_back(b); v.push_back(c);
sort(v.begin(),v.end()); if (v[0]+v[1]<=v[2]) return 0;
int p=a+b+c; return p*(p-2*a)*(p-2*b)*(p-2*c);
}
namespace BF
{
const int NN=10;
int res[NN][NN][NN],num,a[N],ans[NN];
inline void check(void)
{
RI i,j,k; for (i=1;i<=n;++i)
for (j=i+1;j<=n;++j) for (k=j+1;k<=n;++k)
if (calc(a[i],a[j],a[k])!=res[i][j][k]) return;
for (++num,i=1;i<=n;++i) ans[i]=a[i];
}
inline void DFS(CI now=1)
{
if (now>n) return check();
for (RI i=1;i<=4;++i) a[now]=i,DFS(now+1);
}
inline void solve(void)
{
RI i,j,k; for (i=1;i<=n;++i)
for (j=i+1;j<=n;++j) for (k=j+1;k<=n;++k)
res[i][j][k]=ask(i,j,k);
DFS(); if (num>1) return (void)(puts("! -1"));
for (printf("! "),i=1;i<=n;++i) printf("%d ",ans[i]); fflush(stdout);
}
};
int main()
{
RI i,j,k; scanf("%d",&n); if (n<=8) return BF::solve(),0;
map <int,int> pft; for (i=1;i<=4;++i) pft[calc(i,i,i)]=i;
bool flag=0; int a,b,len;
for (i=1;i<=9&&!flag;++i)
for (j=i+1;j<=9&&!flag;++j)
for (k=j+1;k<=9&&!flag;++k)
if (pft[ask(i,j,k)]) flag=1,a=i,b=j,len=pft[ask(i,j,k)];
if (len>1)
{
map <int,int> mp;
for (i=1;i<=4;++i) mp[calc(i,len,len)]=i;
for (i=1;i<=n;++i) if (i==a||i==b) ans[i]=len; else ans[i]=mp[ask(a,b,i)];
for (printf("! "),i=1;i<=n;++i) printf("%d ",ans[i]); fflush(stdout);
return 0;
}
vector <int> pos; for (i=1;i<=n;++i)
{
if (i==a||i==b||ask(i,a,b)!=0) ans[i]=1;
else pos.push_back(i); if (pos.size()==4) break;
}
if (pos.size()==0)
{
for (printf("! "),i=1;i<=n;++i) printf("%d ",ans[i]); fflush(stdout);
return 0;
}
map <int,int> mp; for (i=2;i<=4;++i) mp[calc(1,i,i)]=i;
flag=0; int A,B,Len;
for (i=0;i<pos.size()&&!flag;++i) for (j=i+1;j<pos.size()&&!flag;++j)
if (mp[ask(a,pos[i],pos[j])]) flag=1,A=pos[i],B=pos[j],Len=mp[ask(a,pos[i],pos[j])];
if (!flag) return puts("! -1"),0;
mp.clear(); for (i=1;i<=4;++i) mp[calc(Len,Len,i)]=i;
for (ans[A]=ans[B]=Len,i=1;i<=n;++i) if (!ans[i]) ans[i]=mp[ask(A,B,i)];
for (printf("! "),i=1;i<=n;++i) printf("%d ",ans[i]); fflush(stdout);
return 0;
}
F. The Boss's Identity
说实话称这题一个最easy的F不过分吧，做法很trivial而且还不卡两个\(\log\)
首先我们通过观察可以发现数组后面部分的元素构成大概是这样的（以\(n=5\)为例）：
不难发现去除掉开头的\(a_1\)后，每一行都有\(n-1\)个数，且每向下一行就是把每一项的第一个元素的前一个数加入
根据这个我们可以很容易的算出贡献，具体地，枚举二进制下每一位置\(j\)
根据初始时每一个数这一位上是否为\(1\)，我们可以求出每一列在第几行出现\(1\)，很显然在这之后后面这一列上就都是\(1\)了
因为我们要统计的位置要尽量往前，因此对于每一列来说只有这个位置可能是最终的答案
这样我们就得到了\(O(n\log a_i)\)个位置，直接把它们按照出现时间排序后，求一个前缀最大值，然后就可以二分查询答案了
总复杂度\(O(n\log a_i\log n)\)，可以把加入元素的地方用BFS实现来使得直接按出现时间排序，这样可以省掉一个排序的\(\log\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int t,n,q,a[N],b[N],x; vector <pi> pos[N],num;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i,j; for (scanf("%lld%lld",&n,&q),i=1;i<=n;++i) scanf("%lld",&a[i]),pos[i].clear();
for (j=0;j<30;++j)
{
for (i=1;i<=n;++i) b[i]=((a[i]>>j)&1);
int lst=0; for (i=n;i>=1;--i) if (b[i]) { lst=i; break; }
if (!lst) continue; int pre=b[1]?1:0;
if (b[1]) pos[1].push_back(pi(0,1<<j));
for (i=2;i<=n;++i)
{
if (b[i]) pre=i; int dlt=pre?i-pre:n-lst+i;
pos[i].push_back(pi(dlt,1<<j));
}
}
for (num.clear(),i=1;i<=n;++i)
{
sort(pos[i].begin(),pos[i].end());
int cur=0; for (auto [t,v]:pos[i])
cur|=v,num.push_back(pi(t*(n-1)+i,cur));
}
sort(num.begin(),num.end());
for (i=1;i<num.size();++i) num[i].se=max(num[i].se,num[i-1].se);
//for (auto [p,v]:num) printf("%lld %lld\n",p,v);
for (i=1;i<=q;++i)
{
auto cmp=[&](const pi& A,const pi& B)
{
return A.se<B.se;
};
scanf("%lld",&x); int pos=upper_bound(num.begin(),num.end(),pi(0,x),cmp)-num.begin();
if (pos<num.size()) printf("%lld\n",num[pos].fi); else puts("-1");
}
}
return 0;
}
Postscript
接下来按照学校的要求CF以后可能都要打Div1了，没法逃避总是写不出的Div2 E/F了
不过坚持练下去总能有所进步的说，记得刚开始打的时候Div2 D都经常写不出来了，现在基本可以一眼稳出了