A题
传送门
题意简述：给你一个mmm个数的数列，现在规定把一个数列的1,2,...,k1,2,...,k1,2,...,k分成第一组，把k+1,k+2,...,2kk+1,k+2,...,2kk+1,k+2,...,2k分成第二组,…,这样把前n∗kn*kn∗k个数分成nnn组，现在给你sss个数，你可以删去至多m−n∗km-n*km−n∗k个数使得新数列按照上述方式分组可以分出来至少一个组满足sss个数都在里面出现（如果sss个数中aaa出现bbb次则分出来满足条件的组中aaa出现至少bbb次），求任意方案。
思路：
我们用双指针统计一下就行了，注意细节。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=5e5+5;
int cnt[N],tot[N],lim[N],a[N],okcnt=0,m,n,k,s,det=0;
bool in[N];
inline void check(int l,int r){
int blo=l==l/k*k?(l/k-1)*k+1:l/k*k+1;
if(r-blo+1-k>(n-m*k))return;
if(r-blo+1-k<=0)puts("0"),exit(0);
int ccnt=0;
for(ri i=blo;i<=r;++i)ccnt+=in[i];
cout<<r-blo+1-k<<'\n';
for(ri i=blo,j=1;i<=r&&j<=r-blo+1-k;++i){
if(lim[a[i]]&&tot[a[i]]<lim[a[i]]){
++tot[a[i]];
continue;
}
cout<<i<<' ',++j;
}
exit(0);
}
int main(){
n=read(),k=read(),m=read(),s=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1,v;i<=s;++i){
++lim[v=read()];
if(lim[v]>1)++det;
}
for(ri l=1,r=0;;){
while(r<n&&okcnt!=s-det){
++r,++cnt[a[r]];
if(cnt[a[r]]==lim[a[r]])++okcnt;
if(cnt[a[r]]<=lim[a[r]])in[r]=1;
}
if(okcnt!=s-det)break;
while(okcnt==s-det){
if(cnt[a[l]]==lim[a[l]])check(l,r),--okcnt;
if(cnt[a[l]]<=lim[a[l]])in[l]=0;
--cnt[a[l]];
++l;
}
}
puts("-1");
return 0;
}
B题
传送门
题意简述：给你两个等长的数字串a,ba,ba,b，你可以把aaa中的任意相邻两个数同时+1/−1+1/-1+1/−1，问能否把aaa变成bbb以及输出操作方案数和具体方案。
思路：
一道比较显然的贪心吧。
直接一位一位匹配就行了，如果aia_iai比bib_ibi小就给ai,ai+1a_i,a_{i+1}ai,ai+1同时加上bi−aib_i-a_ibi−ai；如果aia_iai比bib_ibi大就给aia_iai和ai+1a_{i+1}ai+1同时减去ai−bia_i-b_iai−bi；如果相等就跳过位置iii。
然后构造方案直接暴力构造，因为可以证明每个数的增量是很小的。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=1e5+5;
char s[N];
int n,a[N],b[N],det[N];
ll ans=0;
int main(){
n=read();
scanf("%s",s+1);
for(ri i=1;i<=n;++i)a[i]=s[i]^48;
scanf("%s",s+1);
for(ri i=1;i<=n;++i)b[i]=s[i]^48;
det[1]=b[1]-a[1];
for(ri i=2;i<=n;++i)det[i]=b[i]-det[i-1]-a[i];
if(det[n])return puts("-1"),0;
for(ri i=1;i<n;++i)ans+=det[i]>0?det[i]:-det[i];
cout<<ans<<'\n';
ans=min(ans,100000ll);
int p=1,cur=1,tmp;
while(ans--){
while(!det[p])++p,++cur;
while((det[cur]>0&&a[cur+1]==9)||(det[cur]<0&&a[cur+1]==0))++cur;
tmp=det[cur]>0?1:-1;
cout<<cur<<' '<<tmp<<'\n';
a[cur]+=tmp,a[cur+1]+=tmp,det[cur]-=tmp;
cur=max(cur-1,p);
}
return 0;
}
C题
传送门
题意简述：要求你压缩一个字符串，假设你将SSS压缩成了t1t2...tkt_1t_2...t_kt1t2...tk，那么对于一个串tit_iti。
若∣ti∣=1|t_i|=1∣ti∣=1可以花aaa压缩，如果tit_iti是t1t2..ti−1t_1t_2..t_{i-1}t1t2..ti−1的子集可以花bbb压缩，问压缩的最小代价。
思路：
直接用samsamsam加dpdpdp。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=5005;
int n,a,b,f[N];
char s[N];
namespace sam{
int son[N<<1][26],len[N<<1],link[N<<1],tot=1,last=1;
inline void insert(const int&x){
int p=last,np=++tot;
len[last=np]=len[p]+1;
while(p&&!son[p][x])son[p][x]=np,p=link[p];
if(!p){link[np]=1;return;}
int q=son[p][x],nq;
if(len[q]==len[p]+1){link[np]=q;return;}
len[nq=++tot]=len[p]+1,memcpy(son[nq],son[q],sizeof(son[q])),link[nq]=link[q];
link[q]=link[np]=nq;
while(p&&son[p][x]==q)son[p][x]=nq,p=link[p];
}
}
int main(){
n=read(),a=read(),b=read(),scanf("%s",s+1);
memset(f,0x3f,sizeof(f));
f[1]=a;
for(ri i=1;i<n;++i){
sam::insert(s[i]-'a');
f[i+1]=min(f[i+1],f[i]+a);
for(ri j=1,p=1;i+j<=n;++j){
if(p)p=sam::son[p][s[i+j]-'a'];
if(p)f[i+j]=min(f[i+j],f[i]+b);
}
}
cout<<f[n];
return 0;
}
D题
传送门
题意简述：
给一棵树，现在AAA可以从树上面选一些点出来,选iii的花费为aia_iai,然后BBB给所有叶子结点赋值，然后AAA可以对所有选出来的点进行一次操作：使得以它为根的子树中的所有叶子结点全部减去一个相同的值，问如果AAA想保证无论BBB怎么赋值自己操作之后每个叶子的权值都为000那么选出来点的最少代价是多少并要求列出所有可能被选出的点。
思路：
先考虑构造出任意一种方案然后再统计。
这个最优值可以非常简单的树形DPDPDP出来，然后对于一次儿子对父亲的转移我们把可行的方案都记下来，最后统计即可。
细节见代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef pair<int,int> pii;
typedef long long ll;
const int N=2e5+5;
int n,a[N],fa[N],nxt[N];
bool pass_on[N],vis[N];
vector<int>e[N],Ans;
ll ans=0;
pii dfs(int p){
pii ret=pii(a[p],p),mx;
vector<pii>tmp;
for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])^fa[p])fa[v]=p,tmp.push_back(dfs(v));
if(!tmp.size())return ret;
sort(tmp.begin(),tmp.end(),greater<pii>());
mx=tmp[0];
int cnt=0;
for(ri i=0;i<tmp.size();++i)if(tmp[i].fi^mx.fi)break;else ++cnt;
for(ri i=1;i<tmp.size();++i)pass_on[tmp[i].se]=1,ans+=tmp[i].fi;
if(cnt>1)pass_on[mx.se]=1;
if(ret.fi^mx.fi)return min(ret,mx);
return nxt[ret.se]=mx.se,ret;
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
pii tmp=dfs(1);
ans+=tmp.fi,pass_on[tmp.se]=1;
for(ri i=1;i<=n;++i){
if(vis[i])continue;
bool f=0;
for(ri j=i;j;j=nxt[j]){
vis[j]=1;
pass_on[j]=(f|=pass_on[j]);
}
}
for(ri i=1;i<=n;++i)if(pass_on[i])Ans.push_back(i);
cout<<ans<<' '<<Ans.size()<<'\n';
for(ri i=0;i<Ans.size();++i)cout<<Ans[i]<<' ';
return 0;
}
E题
传送门
题意简述：给出一个a,(a≤1000)a,(a\le1000)a,(a≤1000)，现在要求找出一个nnn满足：S(a∗n)=S(n)a,S(x)S(a*n)=\frac{S(n)}a,S(x)S(a∗n)=aS(n),S(x)表示xxx各位数字之和。
思路：
如果先要完全正确的思路请看官方题解的solution1solution1solution1，博主写的是solution2solution2solution2一种有点假的算法。
考虑构造一个balance(x)=S(a∗n)a−S(n)balance(x)=S(a*n)a-S(n)balance(x)=S(a∗n)a−S(n)，显然这个值为000的时候说明满足题意。
这样我们构造一个二元组来进行bfsbfsbfs直到搜出来一个环为止。
然后当∣balance∣>a|balance|>a∣balance∣>a的时候可以剪个枝。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
#define id(x) ((x)+1500)
using namespace std;
typedef pair<int,int> pii;
const int N=3005;
int hd,tl,sta[N][N],dig[N][N];
pii q[N*1500],pre[N][N],tt;
inline string solve(int A){
memset(sta,-1,sizeof(sta));
sta[0][id(0)]=0;
q[hd=tl=1]=pii(0,0);
while(hd<=tl){
int car=q[hd].fi,bal=q[hd].se;
for(ri tmp,ncar,nbal,num=hd>1?0:1;num<10;++num){
tmp=car*10+num;
ncar=tmp%A;
nbal=bal+A*num-tmp/A;
if(id(nbal)>3000||id(nbal)<0)continue;
if(!nbal&&!ncar){
string ret="",tret="";
tret+=(char)(num^48);
while(car||bal){
tret+=(char)(dig[car][id(bal)]^48);
tt=pre[car][id(bal)];
car=tt.fi,bal=tt.se;
}
reverse(tret.begin(),tret.end());
for(ri sum=0,i=0,up=tret.size();i^up;++i){
sum=sum*10+(tret[i]^48);
if(sum/A||ret.size())ret+=(char)((sum/A)^48);
sum%=A;
}
return ret;
}
if(sta[ncar][id(nbal)]==-1){
sta[ncar][id(nbal)]=sta[car][id(bal)]+1;
q[++tl]=pii(ncar,nbal);
pre[ncar][id(nbal)]=pii(car,bal);
dig[ncar][id(nbal)]=num;
}
}
++hd;
}
return "-1";
}
int main(){
int A;
scanf("%d",&A);
cout<<solve(A);
return 0;
}
F题
传送门
题意简述：
两个人W,PW,PW,P需要互相送信。
现在有nnn个时间点t1,t2,...,tnt_1,t_2,...,t_nt1,t2,...,tn，每个时间点W/PW/PW/P负责送信，以及一个结束时间点tn+1t_{n+1}tn+1。
有两种选择：
- 直接花ddd的代价送给对方
- 将信寄存在RRR那里，设从寄存到拿信花了TTT个单位时间，代价是c∗Tc*Tc∗T。
一个人可以在RRR那儿拿信当且仅当自己去RRR送信或者时间为tn+1t_{n+1}tn+1
思路：
考虑dpdpdp.
考虑现在WWW两次去RRR之间PPP的送信情况。
显然应该是最开始可能去一次RRR,最后连续一段可能去RRR，中间一段直接送。
然后这就是一个显然的O(n2)dpO(n^2)dpO(n2)dp，发现本质其实是一堆线段里取最值。
那么上李超树优化一波复杂度O(nlogn2)O(nlog_n^2)O(nlogn2)
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=1e5+5;
const ll inf=1e9;
inline ll calc(const pii&coe,const int&x0){return coe.fi*x0+coe.se;}
inline pii operator+(const pii&a,const pii&b){return pii(a.fi+b.fi,a.se+b.se);}
inline void operator+=(pii&a,const pii&b){a=a+b;}
int t[N],n;
ll c,d;
struct SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
pii val[N<<2],add[N<<2];
inline void pushnow(int p,pii v){val[p]+=v,add[p]+=v;}
inline void pushdown(int p){if(add[p]!=pii(0ll,0ll))pushnow(lc,add[p]),pushnow(rc,add[p]),add[p]=pii(0ll,0ll);}
inline void change(int p,int l,int r,pii v){
if(calc(v,t[l])<=calc(val[p],t[l]))swap(val[p],v);
if(calc(val[p],t[r])<=calc(v,t[r]))return;
pushdown(p);
if(calc(val[p],t[mid])<=calc(v,t[mid]))change(rc,mid+1,r,v);
else swap(v,val[p]),change(lc,l,mid,v);
}
inline void update(int p,int l,int r,int k){
ll v1=c*(t[l]-t[k])-d,v2=c*(t[r]-t[k])-d;
if(v2<=0)return pushnow(p,pii(c,-c*t[k]));
if(v1>=0)return pushnow(p,pii(0,d));
pushdown(p);
change(lc,l,mid,val[p]),change(rc,mid+1,r,val[p]);
val[p]=pii(inf,inf);
update(lc,l,mid,k),update(rc,mid+1,r,k);
}
inline ll query(int p,int l,int r,int k){
ll ret=calc(val[p],t[k]);
if(l==r)return ret;
pushdown(p);
return min(ret,k<=mid?query(lc,l,mid,k):query(rc,mid+1,r,k));
}
#undef lc
#undef rc
#undef mid
}f[2];
char S[2];
bool type[N];
int main(){
n=read(),c=read(),d=read();
for(ri i=1;i<=n;++i)t[i]=read(),scanf("%s",S),type[i]=(S[0]=='W');
t[n+1]=read();
for(ri i=1;i<=n;++i){
f[type[i]].update(1,1,n+1,i);
f[type[i]].change(1,1,n+1,pii(c,f[type[i]^1].query(1,1,n+1,i)-c*t[i]));
f[type[i]^1].pushnow(1,pii(0,d));
}
cout<<min(f[0].query(1,1,n+1,n+1),f[1].query(1,1,n+1,n+1));
return 0;
}