传送门
简要题解？因为最后一题太毒不想写了所以其实是部分题解。。。
A题
传送门
题意简述：给你一个数，问你能不能通过加前导000使其成为一个回文数。
思路：直接模拟。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
int cnt[10];
char s[20];
int main(){
scanf("%s",s+1);
int l=1,r=strlen(s+1);
while(s[l]=='0'&&l!=r)++l;
if(l==r)return puts("YES"),0;
while(s[r]=='0')--r;
while(l<r){
if(s[l]!=s[r])return puts("NO"),0;
++l,--r;
}
puts("YES");
return 0;
}
B题
传送门
题意：有2n2n2n个人坐船，每个人有重量，n−1n-1n−1艘双人船和222艘单人船，双人船的代价是乘坐的两个人重量差的绝对值，问所有人坐上船的最小代价。
思路：枚举哪两个坐单人船暴力更新答案。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=1055;
int n,w[N],a[N],ans=0x3f3f3f3f;
inline void solve(){
int sum=0;
for(ri i=1;i<=n*2-2;i+=2)sum+=a[i+1]-a[i];
ans=min(ans,sum);
}
int main(){
n=read();
for(ri i=1;i<=n*2;++i)w[i]=read();
sort(w+1,w+n*2+1);
for(ri i=1;i<=n*2;++i){
for(ri j=i+1;j<=n*2;++j){
int tot=0;
for(ri k=1;k<=n*2;++k)if(k!=i&&k!=j)a[++tot]=w[k];
solve();
}
}
cout<<ans;
return 0;
}
C题
传送门
题意：两个机器人猜拳，出拳可能为1,2,31,2,31,2,3中的一个，当局面为(i,j)(i,j)(i,j)时AAA下一轮会出Ai,jA_{i,j}Ai,j，BBB下一轮会出Bi,jB_{i,j}Bi,j，问最后两个机器人的积分。
思路：显然出拳序列是一个ρ\rhoρ型的，把环找出来即可。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef pair<int,int> pii;
typedef long long ll;
const int N=1055;
vector<pii>turn;
vector<pii>sum;
ll k;
int a,b;
pii trans[4][4];
map<pii,int>vis;
inline int check(int a,int b){
if(a==2&&b==1)return 1;
if(a==3&&b==2)return 1;
if(a==1&&b==3)return 1;
return 0;
}
int main(){
scanf("%lld",&k),a=read(),b=read();
for(ri i=1;i<=3;++i)for(ri j=1;j<=3;++j)trans[i][j].fi=read();
for(ri i=1;i<=3;++i)for(ri j=1;j<=3;++j)trans[i][j].se=read();
turn.push_back(pii(0,0)),sum.push_back(pii(0,0));
turn.push_back(pii(a,b)),sum.push_back(pii(check(a,b),check(b,a)));
for(ri i=1;i<k;++i){
pii tmp=turn[i],nxt=trans[tmp.fi][tmp.se],pts=sum[i];
vis[tmp]=i;
if(vis[nxt]){
int tim=vis[nxt],len=i-tim+1,ttmp=(k-tim+1)%len;
pii ans=sum[tim-1+ttmp];
ll a1=ans.fi,a2=ans.se;
a1+=(k-tim+1)/len*(pts.fi-sum[tim-1].fi),a2+=(k-tim+1)/len*(pts.se-sum[tim-1].se);
cout<<a1<<' '<<a2;
return 0;
}
turn.push_back(nxt),sum.push_back(pii(pts.fi+check(nxt.fi,nxt.se),pts.se+check(nxt.se,nxt.fi)));
}
cout<<sum[k].fi<<' '<<sum[k].se<<'\n';
return 0;
}
D题
传送门
题意：给一个序列，支持区间右移，区间翻转，问最后的序列。
思路：加强版文艺平衡树。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=4e5+5;
typedef pair<int,int> pii;
int n,m,q;
namespace bst{
#define lc (son[p][0])
#define rc (son[p][1])
int val[N],rd[N],siz[N],rev[N],rt=0,tot=0,son[N][2];
inline int build(int v){return val[++tot]=v,rd[tot]=rand(),siz[tot]=1,son[tot][0]=son[tot][1]=0,tot;}
inline void pushup(int p){siz[p]=siz[lc]+1+siz[rc];}
inline void pushnow(int p){rev[p]^=1,swap(son[p][0],son[p][1]);}
inline void pushdown(int p){
if(!rev[p])return;
if(lc)pushnow(lc);
if(rc)pushnow(rc);
rev[p]=0;
}
inline int merge(int a,int b){
if(!a||!b)return a+b;
pushdown(a),pushdown(b);
if(rd[a]>rd[b])return son[a][1]=merge(son[a][1],b),pushup(a),a;
return son[b][0]=merge(a,son[b][0]),pushup(b),b;
}
inline pii split(int p,int k){
if(!p)return pii(0,0);
pii tmp;
pushdown(p);
if(siz[lc]>=k)return tmp=split(lc,k),lc=tmp.se,pushup(p),pii(tmp.fi,p);
return tmp=split(rc,k-siz[lc]-1),rc=tmp.fi,pushup(p),pii(p,tmp.se);
}
inline void insert(int id,int v){
pii x=split(rt,id-1);
rt=merge(merge(x.fi,build(v)),x.se);
}
inline void delet(int id){
pii x=split(rt,id-1),y=split(x.se,1);
rt=merge(x.fi,y.se);
}
inline int query(int id){
pii x=split(rt,id-1),y=split(x.se,1);
int ret=val[y.fi];
return rt=merge(x.fi,merge(y.fi,y.se)),ret;
}
inline void update(int l,int r){
pii x=split(rt,l-1),y=split(x.se,r-l+1);
pushnow(y.fi),rt=merge(x.fi,merge(y.fi,y.se));
}
#undef lc
#undef rc
}
int main(){
srand(time(NULL));
n=read(),q=read(),m=read();
for(ri i=1;i<=n;++i)bst::insert(i,read());
while(q--){
int op=read(),l=read(),r=read();
if(op==1){
int tmp=bst::query(r);
bst::delet(r);
bst::insert(l,tmp);
}
else bst::update(l,r);
}
for(ri i=1;i<=n;++i)cerr<<bst::query(i)<<' ';
puts("");
for(ri i=1;i<=m;++i)cout<<bst::query(read())<<' ';
return 0;
}
E题
传送门
题意：给一些线段，输出任意一条满足以下条件的线段：
去掉它之后覆盖的总长度不变。
思路：离散化之后差分/线段树。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=6e5+5;
int n,m=0,val[N];
struct node{int l,r;}a[N];
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
int mn[N<<2],add[N<<2];
inline void pushup(int p){mn[p]=min(mn[lc],mn[rc]);}
inline void pushnow(int p,int v){mn[p]+=v,add[p]+=v;}
inline void pushdown(int p){if(add[p])pushnow(lc,add[p]),pushnow(rc,add[p]),add[p]=0;}
inline void update(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return pushnow(p,1);
pushdown(p);
if(qr<=mid)update(lc,l,mid,ql,qr);
else if(ql>mid)update(rc,mid+1,r,ql,qr);
else update(lc,l,mid,ql,mid),update(rc,mid+1,r,mid+1,qr);
pushup(p);
}
inline int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return mn[p];
pushdown(p);
if(qr<=mid)return query(lc,l,mid,ql,qr);
if(ql>mid)return query(rc,mid+1,r,ql,qr);
return min(query(lc,l,mid,ql,mid),query(rc,mid+1,r,mid+1,qr));
}
}
int main(){
n=read();
for(ri i=1;i<=n;++i)val[++m]=a[i].l=read(),val[++m]=a[i].r=read(),val[++m]=a[i].l-1;
sort(val+1,val+m+1),m=unique(val+1,val+m+1)-val-1;
for(ri i=1;i<=n;++i){
a[i].l=lower_bound(val+1,val+m+1,a[i].l)-val;
a[i].r=lower_bound(val+1,val+m+1,a[i].r)-val;
SGT::update(1,1,m,a[i].l,a[i].r);
}
for(ri i=1;i<=n;++i)if(SGT::query(1,1,m,a[i].l,a[i].r)>1)return cout<<i,0;
puts("-1");
return 0;
}
F题
传送门
题意：
现在有nnn个数，mmm个限制。每个数只能为111到nnn，限制表示为一个区间中所有数不小于/不大于某个数，最后的代价是∑i=1ncnti2\sum_{i=1}^ncnt_i^2∑i=1ncnti2，问最小代价。
思路：直接按照题意模拟跑费用流。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=205,M=100005;
int n,m,up[N],down[N];
namespace mcmf{
int d[N],first[N],pred[N],pos[N],F,s,t,cnt;
bool in[N];
struct edge{int v,next,c,w;}e[M];
inline void addedge(int u,int v,int c,int w){e[++cnt]=(edge){v,first[u],c,w},first[u]=cnt;}
inline void add(int u,int v,int c,int w){cerr<<u<<' '<<v<<' '<<c<<' '<<w<<'\n',addedge(u,v,c,w),addedge(v,u,0,-w);}
inline void init(){cnt=-1,memset(first,-1,sizeof(first)),F=0,s=0,t=2*n+1;}
inline bool bfs(){
static int q[N],hd,tl;
for(ri i=s;i<=t;++i)d[i]=0x3f3f3f3f;
d[q[hd=tl=1]=s]=0;
while(hd<=tl){
int x=q[hd++];
in[x]=0;
for(ri i=first[x],v;~i;i=e[i].next){
if(e[i].c&&d[v=e[i].v]>d[x]+e[i].w){
d[v]=d[x]+e[i].w,pred[v]=x,pos[v]=i;
if(!in[v])in[q[++tl]=v]=1;
}
}
}
if(d[t]==0x3f3f3f3f)return 0;
int p=t;
F+=d[t];
while(p^s)--e[pos[p]].c,++e[pos[p]^1].c,p=pred[p];
return 1;
}
}
int main(){
n=read(),m=read();
mcmf::init();
for(ri i=1;i<=n;++i){
up[i]=n,down[i]=1;
for(ri j=1;j<=n;++j)mcmf::add(mcmf::s,i,1,j*j-(j-1)*(j-1));
mcmf::add(i+n,mcmf::t,1,0);
}
for(ri t,l,r,v,tt=1;tt<=m;++tt){
t=read(),l=read(),r=read(),v=read();
if(t==1)for(ri i=l;i<=r;++i)down[i]=max(down[i],v);
else for(ri i=l;i<=r;++i)up[i]=min(up[i],v);
}
for(ri i=1;i<=n;++i){
if(up[i]<down[i])return puts("-1"),0;
for(ri j=down[i];j<=up[i];++j)mcmf::add(j,i+n,1,0);
}
while(mcmf::bfs());
cout<<mcmf::F;
return 0;
}
G题
传送门
咕咕咕