稳啊稳啊。对拍大法好。
不过最开始看题的时候要记住评估一下正解难度和暴力难度，T3明明可以搞60分的，可惜了。
还有就是，写程序之前一定要想清楚！处理好特殊情况，确保算法在实现过程中的正确性！对拍出错再来改代价太大！
T1:
题意：
对一个给定字符串进行多次复制黏贴操作，求最后得到字符串的前n位，若字符串过长，只保留前m位。
分析：
看了下m的大小，觉得非常酸爽。
因为如果正向处理的话，要么就要记下正处理的字符串，要么就，不对，必须存，因为存开头结尾的话可能会变。
所以考虑逆推，我们只需要用f[i]来存在当前情况的i这个位置在哪个位置。显然初始值为f[i]=i，然后只需要注意以下情况：
1.一串字母插入到前面：减去插入长度；
2.正好在这串字母插入后的区间内：变为该串字母中对应位置上字母的位置。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n,m) for(int i=n;i<m;i++)
#define eachrev(i,n,m) for(int i=n;i>m;i--)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "A"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=3e5+5;
const int modd=1e9+7;
int res[Maxn];
int n,kkk,m,a[Maxn],b[Maxn],c[Maxn];
char ini[Maxn];
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*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
kkk=read();m=read();
cin.getline(ini+1,Maxn);
n=read();
for(int i=1;i<=n;i++){
a[i]=read()+1;b[i]=read();c[i]=read()+1;
}
for(int i=1;i<=kkk;i++)
res[i]=i;
}
void work()
{
for(int i=n;i>=1;i--){
for(int j=1;j<=kkk;j++)
if(res[j]>=c[i]&&res[j]<=c[i]+b[i]-a[i])
res[j]=a[i]+res[j]-c[i];
else if(res[j]>c[i]+b[i]-a[i])res[j]-=b[i]-a[i]+1;
/*if(c[i]<=kkk){
b[i]=min(b[i],kkk-c[i]+1+a[i]);
for(int j=1;j<=b[i]-a[i];j++){
int tmp=res[c[i]+j-1];
for(int k=c[i]+j;k<=kkk;k++)
swap(res[k],tmp);
}
for(int j=c[i];j<=c[i]+b[i]-a[i];j++)
res[j]=j-c[i]+a[i];
}*/
}
for(int i=1;i<=kkk;i++)
printf("%c",ini[res[i]]);
//减到负数，未填完
}
void debug()
{
//
}
void work1()
{
char ovo[Maxn];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
ini[j]=res[j];
a[i]=read()+1;b[i]=read();c[i]=read()+1;
for(int j=b[i];j>=a[i];j--){
char tmp=ini[j];
for(int k=c[i];k<=m;k++)
swap(tmp,res[k]);
}
}
for(int i=1;i<=kkk;i++)
printf("%c",res[i]);
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
if(n<=2000&&m<=2000)
work1();
else
work();
//debug();
return 0;
}T2:
题意：
给定一个序列和一个标准序列（为一个递归序列，每次在前面加上同样长度的某字母），求最少改变几个，可以使这个序列从某个地方开始遍历一次恰好为标准序列。
分析：
根据该序列的定义可以知道，会有很长的一个区间字母相同，此时若用暴力一个枚举开始一个统计不同会重复做很多操作，所以只需要枚举某区间结尾的那个数:
若该字母之前匹配，后来不匹配，答案为之前答案加一。
若该字母之前不匹配，之后匹配，答案为之前答案减一。
然后这里就体现了准确的变量定义的重要性：
保存之前是否匹配用一个数组，这个数组只能对应读入序列，因为标准序列的对应一直在变，内部不更新。
然后因为最后一个无论怎样都满足，所以要考虑对used数组的传递。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n,m) for(int i=n;i<m;i++)
#define eachrev(i,n,m) for(int i=n;i>m;i--)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "B"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=(1<<21)+5;
const int modd=1e9+7;
int k,lim,cur,mini,cur2,ans[Maxn],used[Maxn];
char a[Maxn],stdd[Maxn];
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*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
k=read();lim=(1<<(2*k));
cin.getline(a+1,Maxn);
for(int i=k-1;i>=0;i--)
for(int j=1;j<=3;j++)
for(int z=1;z<=(1<<(2*i));z++){
cur++;
stdd[cur]=(j==1?'J':(j==2?'O':'I'));
}
}
void calc(int nowy)
{
cur=nowy-1;cur2=0;
for(int i=k-1;i>=0;i--)
for(int j=1;j<=3;j++){
cur+=(1<<(2*i));
cur2+=(1<<(2*i));
if(cur>lim)cur%=lim;
if(a[cur]!=stdd[cur2]&&(!used[cur])){
ans[nowy]++;used[cur]=1;
}
else if(a[cur]==stdd[cur2]&&used[cur]){
used[cur]=0;ans[nowy]--;}
}
cur++;
if(cur>lim)cur%=lim;
used[cur]=used[nowy];
ans[nowy]+=ans[nowy-1];
mini=min(mini,ans[nowy]);
}
void work()
{
for(int i=1;i<lim;i++)
if(a[i]!=stdd[i]){
ans[1]++;used[i]=1;}
mini=ans[1];used[lim]=used[1];
for(int i=2;i<=lim;i++)
calc(i);
printf("%d",mini);
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
//debug();
return 0;
}T3:
题意：
给你一个序列
你可以删除序列中的数，当然，有代价
删除之后统计，你此次删除的得分为序列得分减去删除数的代价
序列得分定义为：
被删除后，所有“左边或右边没有比它大的数”的数的得分和
然后让你删除，求最大得分
分析：
首先，n^2的算法很好想吧。
然后我们要考虑优化，因为这道题一看最后就要带log，优先考虑线段树。然后我们要把之前的DP式变得可以优化，也就是说，避开和正在枚举的数相关的量。
所以就可以把DP变成：
f[i]=max(f[j]+sigma cost[k])也就是从j推过来，拔掉j,k之间比它们大的。
此处f在i为从左向右最高时的收益。再从右向左来一次就可以了。
具体实现：
线段树维护最大值，f很简单，关键是sigma c。我们可以把所有比它小的数都直接加上代价c，因为如果有比它小又可能被取到的数被误减了，则这个数一定会比那个被误减的数更优！
这种思路比较有用，要记住，随时注意最优解的取得条件和排除条件。
需要注意：离散的时候，因为高度相等也可以选，离散后值要相等，且找最大也要包括自己。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n,m) for(int i=n;i<m;i++)
#define eachrev(i,n,m) for(int i=n;i>m;i--)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "C"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
const int modd=1e9+7;
ll ans;
struct node
{
ll h,b,c,lf,rf;
int num,pos;
}a[Maxn];
struct node2
{
int lef,rig;
ll maxn[2];
ll bj[2];
}tre[Maxn<<2];
int n;
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*10+ch-'0';ch=getchar();}
return x*f;
}
bool cmp(node x,node y)
{
return x.h<y.h;
}
bool cmp2(node x,node y)
{
return x.num<y.num;
}
void build(int u,int lef,int rig)
{
tre[u].lef=lef;
tre[u].rig=rig;
if(lef==rig)return;
int mid=(lef+rig)>>1;
build(2*u,lef,mid);
build(2*u+1,mid+1,rig);
}
void init()
{
n=read();
for(int i=1;i<=n;i++){
a[i].h=(ll)read();a[i].b=(ll)read();
a[i].c=(ll)read();a[i].num=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
a[i].pos=i;
sort(a+1,a+n+1,cmp2);
build(1,0,n+1);
}
void pushdown(int u,int pd)
{
if(tre[u].lef==tre[u].rig)return;
tre[2*u].maxn[pd]+=tre[u].bj[pd];
tre[2*u+1].maxn[pd]+=tre[u].bj[pd];
tre[2*u].bj[pd]+=tre[u].bj[pd];
tre[2*u+1].bj[pd]+=tre[u].bj[pd];
tre[u].bj[pd]=0;
}
ll query(int u,int lef,int rig,int pd)
{
if(tre[u].lef==lef&&tre[u].rig==rig)
return tre[u].maxn[pd];
if(tre[u].bj[pd])pushdown(u,pd);
tre[u].maxn[pd]=max(tre[2*u].maxn[pd],tre[2*u+1].maxn[pd]);
int mid=(tre[u].lef+tre[u].rig)>>1;
if(rig<=mid)return query(2*u,lef,rig,pd);
else if(lef>mid)return query(2*u+1,lef,rig,pd);
return max(query(2*u,lef,mid,pd),query(2*u+1,mid+1,rig,pd));
}
void update(int u,int lef,int rig,int val,int pd)
{
if(tre[u].lef==lef&&tre[u].rig==rig){
tre[u].maxn[pd]+=val;
tre[u].bj[pd]+=val;
return;}
if(tre[u].bj[pd])pushdown(u,pd);
int mid=(tre[u].lef+tre[u].rig)>>1;
if(rig<=mid)update(2*u,lef,rig,val,pd);
else if(lef>mid)update(2*u+1,lef,rig,val,pd);
else{
update(2*u,lef,mid,val,pd);
update(2*u+1,mid+1,rig,val,pd);
}
tre[u].maxn[pd]=max(tre[2*u].maxn[pd],tre[2*u+1].maxn[pd]);
}
void update1(int u,int lef,int rig,int val,int pd)
{
if(tre[u].bj[pd])pushdown(u,pd);
if(tre[u].lef==lef&&tre[u].rig==rig){
tre[u].maxn[pd]=val;
return;}
int mid=(tre[u].lef+tre[u].rig)>>1;
if(rig<=mid)update1(2*u,lef,rig,val,pd);
else if(lef>mid)update1(2*u+1,lef,rig,val,pd);
else{
update1(2*u,lef,mid,val,pd);
update1(2*u+1,mid+1,rig,val,pd);
}
tre[u].maxn[pd]=max(tre[2*u].maxn[pd],tre[2*u+1].maxn[pd]);
}
void work()
{
for(int i=1;i<=n;i++){
a[i].lf=a[i].b+query(1,0,a[i].pos-1,0);
update(1,0,a[i].pos-1,-a[i].c,0);
update1(1,a[i].pos,a[i].pos,a[i].lf,0);
}
for(int i=n;i>=1;i--){
a[i].rf=query(1,0,a[i].pos-1,1);
update(1,0,a[i].pos-1,-a[i].c,1);
update1(1,a[i].pos,a[i].pos,a[i].rf+a[i].b,1);
query(1,3,3,1);
}
for(int i=1;i<=n;i++)
ans=max(ans,a[i].lf+a[i].rf);
printf(lld,ans);
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
//debug();
return 0;
}