引言
几天没比赛，手痒了，决定尝试 VP 一场 ABC，作为第一次 VP AT（
下次可能就不挑这么简单的场了（
VP 登顶留念。
比赛从 19:30 开始。我一路正开，也没啥罚时。
比赛题解
A
憨憨题。直接 sort + unique 即可。
std::vector<uint>A(5);
for(auto&v:A)scanf("%u",&v);
std::sort(A.begin(),A.end());
printf("%d\n",(int)(std::unique(A.begin(),A.end())-A.begin()));
B
憨憨题。直接做即可。
chr C1[205],C2[205];
scanf("%s%s",C1,C2);
uint n=0;
while(C1[n]){
if(C1[n]!=C2[n])return puts("No"),0;
n++;
}
puts("Yes");
C
憨憨题。随便计算一下差量即可。
uint A[200005];
uint n;scanf("%u",&n);
for(uint i=0,v;i<n;i++)scanf("%u",&v) ,A[(i+n-v)%n]++;
uint ans=0;
for(uint i=0;i<n;i++)_max(ans,A[i]+A[(i+1)%n]+A[(i+2)%n]);
printf("%u\n",ans);
D
暴力 dfs 即可。
状态数可以预见不会很多。
细节有亿点多。
typedef std::vector<chr>str;
std::set<str>S;str C[32],now;chr User[32];uint n;bol Used[32];
voi dfs(uint p){
if(now.size()>16)return;
if(p==n){
for(uint i=0;i<n;i++)if(!Used[i]){
now.insert(now.end(),C[i].begin(),C[i].end());
if(now.size()>=3&&now.size()<=16&&!S.count(now)){
for(auto s:now)putchar(s);
exit(0);
}
now.erase(now.end()-C[i].size(),now.end());
}
return;
}
uint lim=18-now.size();
for(uint i=0;i<n;i++)if(!Used[i])lim-=C[i].size()+1;
for(uint i=0;i<n;i++)if(!Used[i]){
Used[i]=1,now.insert(now.end(),C[i].begin(),C[i].end());
for(uint k=1;k<=lim;k++)
{
for(uint t=1;t<=k;t++)now.push_back('_');
dfs(p+1);
now.erase(now.end()-k,now.end());
}
now.erase(now.end()-C[i].size(),now.end()),Used[i]=0;
}
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint m;scanf("%u%u",&n,&m);
for(uint i=0;i<n;i++){
scanf("%s",User);
for(chr c:User)if(c)C[i].push_back(c);else break;
}
while(m--){
scanf("%s",User);
for(chr c:User)if(c)now.push_back(c);else break;
S.insert(now),now.clear();
}
dfs(1);
puts("-1");
return 0;
}
E
还是考虑计算差量。
反向考虑对每种旋转方案的贡献，然后就是区间加一次函数。
直接用差分维护一下即可。
细节有亿点多。
ullt A[200005],B[200005];uint n;
voi add_base(ullt*A,uint l,uint r,ullt v){A[r]-=v,A[l]+=v;}
voi add(uint l,uint r,ullt k,ullt b){add_base(A,l,r,k),add_base(B,l,r,b);}
voi add_all(int l,int r,ullt k,ullt b){
if(l<0)
{
add(l+n,n,k,b-n*k),add(0,r,k,b);
return;
}
if(r>(int)n){
add(l,n,k,b),add(0,r-n,k,b+k*n);
return;
}
add(l,r,k,b);
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
scanf("%u",&n);
for(uint i=0,v;i<n;i++){
scanf("%u",&v),v=(v+n-i)%n;
add_all(v-n/2,v,-1llu,v);
add_all(v,v+n-n/2,1llu,-(ullt)v);
}
for(uint i=0;i<n;i++)A[i+1]+=A[i],B[i+1]+=B[i];
ullt ans=-1;
for(uint i=0;i<n;i++)_min(ans,A[i]*i+B[i]);
printf("%llu\n",ans);
return 0;
}
F
国王游戏的经典调整法贪心。
typedef std::pair<ullt,ullt>Pair;
chr C[200005];Pair P[200005];
uint n;ullt ans=0;scanf("%u",&n);
for(uint i=0;i<n;i++){
scanf("%s",C);
for(chr c:C)if(c){
if(c<='9')ans+=P[i].first*(c-'0'),P[i].second+=c-'0';
else P[i].first++;
}else break;
}
std::sort(P,P+n,[&](Pair a,Pair b){
return a.first*b.second>a.second*b.first;
});
ullt s=0;
for(uint i=0;i<n;i++)ans+=s*P[i].second,s+=P[i].first;
printf("%llu\n",ans);
G
考虑对排名反向计算贡献。
对 \(i\) 在 \(j\) 前的概率，有以下几种状态：
- \(s_i\) 为 \(s_j\) 前缀，则 \(i\) 必然在 \(j\) 前。
- \(s_j\) 为 \(s_i\) 前缀，则 \(i\) 必然在 \(j\) 后。
- 其余情况，前后顺序等可能出现。
直接拿棵 Trie 计算一下每个串有几个前缀出现在全集中，及作为全集中多少串的前缀。
然后随便统计一下信息就完了。
const ullt Mod=998244353;
typedef ConstMod::mod_ullt<Mod>modint;
struct node{node*son[26];uint v1,v2;}N[2000005],*rot=N,*cnt=N+1;
node*NewNode(){return cnt++;}
#define Id(p) ((uint)((p)-N))
#define Turn(c) ((c)-'a')
node*insert(chr*C){
node*p=N;
while(*C){
p->v1++;auto&s=p->son[Turn(*(C++))];
if(!s)s=NewNode();
p=s;
}
p->v2++;
return p;
}
chr C[500005];
node*At[500005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n;scanf("%u",&n);
for(uint i=0;i<n;i++)scanf("%s",C),At[i]=insert(C);
for(node*p=rot;p!=cnt;p++)for(auto s:p->son)if(s)s->v2+=p->v2;
for(uint i=0;i<n;i++){
(modint(n-At[i]->v1+At[i]->v2)/2).println();
}
return 0;
}
H
考虑对文本串每个前缀，计算出其最短的存在于模板串中的后缀。
这个拿个 ACAM 即可搞定。
然后就是每个这样的区间都得删掉一个点，直接贪心 / 差分约束即可。
const uint sigma=26;
struct node{node*son[sigma],*fail;uint kill;node():kill(-1u){}}N[2000005],*rot=N,*cnt=N+1;
node*NewNode(){return cnt++;}
#define Id(p) ((uint)((p)-N))
#define Turn(c) ((c)-'a')
voi insert(chr*C){
node*p=N;uint len=0;
while(*C){
auto&s=p->son[Turn(*(C++))];
if(!s)s=NewNode();
p=s,len++;
}
_min(p->kill,len);
}
voi build(){
std::queue<node*>Q;rot->fail=rot;
for(uint i=0;i<sigma;i++)(rot->son[i]?(Q.push(rot->son[i]),rot->son[i]->fail):rot->son[i])=rot;
while(!Q.empty()){
node*p=Q.front();Q.pop(),_min(p->kill,p->fail->kill);
for(uint i=0;i<sigma;i++)
(p->son[i]?(Q.push(p->son[i]),p->son[i]->fail):p->son[i])=p->fail->son[i];
}
}
chr S[500005],C[500005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
scanf("%s",S);
uint n;scanf("%u",&n);
while(n--){
scanf("%s",C);
insert(C);
}
build();
uint ans=0,last=1e9;
node*p=rot;
for(auto c:S)if(c){
last++,p=p->son[Turn(c)];
if(last>=p->kill)
last=0,ans++;
}else break;
printf("%u\n",ans);
return 0;
}