Noip模拟100 2021.11.17
直接给我整了个原题大战，出题人四处嫖题就非常离谱。。。
我是小马 桶 ，今天终于一百场了我真开心
T1 饥饿的狐狸
比较水的贪心，不知道为啥洛谷上面评级是紫的。。。。
题意可以转化为规定每次走的位置和一个可以随时到达的原点，要求最大化和最小化行走的距离
显然可以先把\(T\)升序排序
先看当\(W=0\)的情况，比较好想出最小值直接就是\(T_n\)，最大值可以通过观察你的全排列的暴力得出结论
最大值的时候直接反复横跳就是答案，其实性感理解的话比较好想出，但是我考场上打了暴力我为什么还要想呢？？
这样我们继续考虑原点不是\(0\)的情况，发现还是可以用反复横跳来解决，只不过起点需要找到距离原点最远的点
但是我为了保证贪心正确打了好几个不同的贪心取了最大值，里面还有一个随即贪心。。。。1
最小值的话需要找到离原点最近的两个点，然后分别向最小值和最大值的方向移动即可
注意在累计答案的时候都需要和到原点的距离进行比较，因为如果这时候去原点更优肯定会选择先去一下原点（也就是先喝一口水再吃）
a
#include
#define int long long
using namespace std;
namespace AE86{
FILE *wsn;
#define gc() p1==p2 and (p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++
char buf[1<<20],*p1=buf,*p2=buf;
auto read=[](){
int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
};
#define mzs
}using namespace AE86;
const int NN=1e6+5;
int n,w,t[NN];
auto task=[](int sm=0){
sort(t+1,t+n+1);int it1=1,it2=n,pre=0;
for(int i=1;i<=n;i++){
if(i&1){
sm+=max(abs(t[it2]-pre),abs(t[it2]-w));
pre=t[it2--];
}else{
sm+=max(abs(t[it1]-pre),abs(t[it1]-w));
pre=t[it1++];
}
}
printf("%lld %lld\n",t[n],sm);
};
int mx,mn;
bool vis[NN];
auto getnum=[](){
int x=rand()%n+1;
while(vis[x]) x=rand()%n+1;
vis[x]=1; return x;
};
auto greedymax=[](){
int itl=1,itr=n,pre=w;
int tmp=0;
for(int i=1;i<=n;i++){
if(i&1){
tmp+=max(abs(t[itl]-pre),abs(t[itl]-w));
pre=t[itl++];
}else{
tmp+=max(abs(t[itr]-pre),abs(t[itr]-w));
pre=t[itr--];
}
}
mx=tmp; itl=1; itr=n; pre=w; tmp=0;
for(int i=1;i<=n;i++){
if(!(i&1)){
tmp+=max(abs(t[itl]-pre),abs(t[itl]-w));
pre=t[itl++];
}else{
tmp+=max(abs(t[itr]-pre),abs(t[itr]-w));
pre=t[itr--];
}
}
mx=max(mx,tmp);
write(mx);
};
auto greedymin=[](){
int pre=w,pos=1;
while(t[pos] T2 保险箱
感觉提议描述很不清楚，考试的时候根本不知道他要我求什么。。。
显然考试之后还有很多人跟我是一样的，都理解错题意了。。。
所以这题直接去洛谷上面瞅题解吧，没啥好说的了，我反正是伞兵做法。。。。（逃）
洛谷题解
b
#include
#define int long long
using namespace std;
namespace AE86{
FILE *wsn;
#define gc getchar
auto read=[](){
int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
};
}using namespace AE86;
const int NN=250005;
int n,k,m[NN],tot;
auto check=[](int x){
for(int i=tot;i;i--){
if(!(m[i]%x)) return false;
if(m[i] T3 追逐
原题大作战系列
洛谷原题链接
c
#include
#define int long long
using namespace std;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
}
const int NN=1e5+2;
int n,v,p[NN],sum[NN];
int up[NN][101],dw[NN][101],ans;
vector g[NN];
inline void dfs(int f,int x){
sum[x]+=p[f];
for(int i=0;i T4 字符串
我看不懂题解，于是去看了洛谷上的题解
d
#include
#define int long long
using namespace std;
namespace AE86{
FILE *wsn;
#define gc getchar
auto read=[](){
int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
};
#define mzs
}using namespace AE86;
const int NN=5e5+5;
int n,q,a[NN],l,r;
char s[NN];
namespace segment_tree{
#define lid (id<<1)
#define rid (id<<1|1)
#define mid ((l+r)>>1)
struct node{
int ls,rs,ms,sm;
node(){ls=rs=ms=sm=0;}
node(int ls,int rs,int ms,int sm):ls(ls),rs(rs),ms(ms),sm(sm){}
node operator+(const node&x)const{
node ret;
ret.ls=max(ls,sm+x.ls);
ret.rs=max(x.rs,x.sm+rs);
ret.ms=max(max(ret.ls,ret.rs),max(x.ls+rs,max(ms,x.ms)));
ret.sm=sm+x.sm;
return ret;
}
}w[NN<<2];
inline void pushup(int id){w[id]=w[lid]+w[rid];}
inline void build(int id,int l,int r){
if(l==r)return w[id]=node(a[l],a[l],a[l],a[l]),void();
build(lid,l,mid);build(rid,mid+1,r);pushup(id);
}
inline node query(int id,int l,int r,int L,int R){
if(L<=l&&r<=R) return w[id]; node ret;
if(L<=mid) ret=query(lid,l,mid,L,R)+ret;
if(R>mid) ret=ret+query(rid,mid+1,r,L,R);
return ret;
}
}
segment_tree::node ans;
auto solve=[](){
l=read(); r=read();ans=segment_tree::query(1,1,n,l,r);
write(ans.ms-ans.sm);
};
namespace WSN{
inline short main(){
wsn=freopen("d.in","r",stdin);
wsn=freopen("d.out","w",stdout);
n=read();scanf("%s",s+1);
for(int i=1;i<=n;i++)if(s[i]=='C') a[i]=1;else a[i]=-1;
segment_tree::build(1,1,n);q=read(); while(q--) solve();
return 0;
}
}
signed main(){return WSN::main();}