前言
- 比赛链接。
从来没见过交互题，T1 狂 CE 不止心态炸了，后面的题也没打好，T2、T3 简单题都不会了，所以为啥 T4 又放黑题。
T1 大众点评
- 原题：AT_joisc2014_d。
难点主要在交互，赛时琢磨了半场比赛终于搞明白是啥玩意儿了，可以将给定库当成压缩的一部分代码，可以调用里面的函数，输入输出已在里面，因为里面有主函数了，本地不能再打主函数了。
两两配对，大的加入 \(\max\) 集合，小的加入 \(\min\) 集合，再分别扫，共需要 \(n+\dfrac{n}{2}\) 次。
点击查看代码
#include "ramen.h"
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
void Ramen(int N)
{
if(N==1) {Answer(0,0); return ;}
vector<int>mx,mi;
int maxx=0,minn=0;
for(int i=1;i<=N-1;i+=2)
{
if(Compare(i-1,i)==1)
{
mx.push_back(i-1);
mi.push_back(i);
maxx=i-1,minn=i;
}
else
{
mx.push_back(i);
mi.push_back(i-1);
maxx=i,minn=i-1;
}
}
for(int i:mx) if(i!=maxx) if(Compare(i,maxx)==1) maxx=i;
for(int i:mi) if(i!=minn) if(Compare(i,minn)==-1) minn=i;
if(!((N-1)&1))
{
if(Compare(N-1,maxx)==1) maxx=N-1;
else if(Compare(N-1,minn)==-1) minn=N-1;
}
Answer(minn,maxx);
}
T2 录取查询
赛时心态崩了这么简单的题都没想出来。
结论就是需满足区间单调不下降且 \(s_l+1\sim s_r-1\) 之间的字符集在这个区间出现次数等于全局出现次数，线段树维护即可，复杂度 \(O(26n\log_n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define f t[p]
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,cnt[N];
char s[N],tt;
struct aa
{
int l,r,val[30],pre,suf;
bool flag;
}t[N<<2];
void pushup(int p)
{
for(int i=0;i<=25;i++)
f.val[i]=t[ls].val[i]+t[rs].val[i];
f.flag=(t[ls].flag&&t[rs].flag&&t[rs].pre>=t[ls].suf);
f.pre=t[ls].pre;
f.suf=t[rs].suf;
}
void build(int p,int l,int r)
{
f.l=l,f.r=r;
if(l==r)
{
f.val[s[l]-'a']++;
f.pre=f.suf=s[l]-'a';
f.flag=1;
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(p);
}
void change(int p,int x,int d)
{
if(f.l==f.r)
{
f.val[s[x]-'a']+=d;
f.pre=f.suf=s[x]-'a';
f.flag=1;
return ;
}
int mid=(f.l+f.r)>>1;
if(x<=mid) change(ls,x,d);
else change(rs,x,d);
pushup(p);
}
aa ask(int p,int l,int r)
{
if(l<=f.l&&r>=f.r) return f;
int mid=(f.l+f.r)>>1;
aa ans;
if(r<=mid) ans=ask(ls,l,r);
else if(l>mid) ans=ask(rs,l,r);
else if(l<=mid&&r>mid)
{
aa x=ask(ls,l,r),y=ask(rs,l,r);
for(int i=0;i<=25;i++)
ans.val[i]=x.val[i]+y.val[i];
ans.flag=(x.flag&&y.flag&&y.pre>=x.suf);
ans.pre=x.pre,ans.suf=y.suf;
}
return ans;
}
signed main()
{
read(n); cin>>(s+1);
for(int i=1;i<=n;i++) cnt[s[i]-'a']++;
build(1,1,n);
read(m);
for(int i=1,op,x,y;i<=m;i++)
{
read(op),read(x);
if(op==1)
{
cin>>tt;
cnt[s[x]-'a']--; change(1,x,-1);
s[x]=tt;
cnt[s[x]-'a']++; change(1,x,1);
}
else
{
read(y);
aa ans=ask(1,x,y);
bool flag=ans.flag;
if(flag) for(int i=s[x]-'a'+1;i<=s[y]-'a'-1;i++)
if(ans.val[i]!=cnt[i])
{
flag=0;
break;
}
puts(flag?"Yes":"No");
}
}
}
T3 精准打击
是道紫但实际没那么难，比较平凡的贪心，因为 \(d\) 很小可以暴力枚举，赛时根本没时间想。
枚举深度 \(d\)，即一棵深度为 \(d\) 的子树，贪心的角度一定是从大往小拿，将 \(d-1\) 层能拿的都拿了接着向下递归即可，最后取最小值。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define f t[p]
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
ll T,d,k,x,a[N];
signed main()
{
read(T);
while(T--)
{
read(d),read(k),read(x);
a[0]=1;
for(int i=1;i<=d;i++) a[i]=a[i-1]*k+1;
ll ans=1e18;
for(int i=d;i>=0;i--)
{
if(a[i]>=x)
{
ll sum=!(i==d);
for(ll y=a[i]-x,j=i-1;y>0&&j>=0;j--)
{
sum+=y/a[j];
y%=a[j];
}
ans=min(ans,sum);
}
else break;
}
write(ans),puts("");
}
}
T4 你画我猜
总结
有点难受心态炸了，就纯心态问题了，这次和身体没关系，硬磕交互了，但是不去磕除了能把 T2 切掉 T3 好好想想还能干什么呢，交互早晚要学，挂一次印象更深刻嘛，命中注定吧。
心态需要磨炼但还是有点难受，至少最近几次没挂这么狠过，但后面的甚至赛场上要是还这样怎么办呢。
标签：13,int,void,Tp,2024,ans,inline,集训,define From： https://www.cnblogs.com/Charlieljk/p/18327165