今天考的好一些。（244分，rk 2）
T1 [CF1279C] Stack of Presents
显而易见，每次排序的时候肯定是把先取出来的排在前面，所以只需要维护一个指针 \(z\)，表示目前最靠里的一个礼物，假如现在这个要取的礼物比它靠外，贡献为 1，否则它之前所有礼物都在它的外侧，计算出贡献后，将 \(z\) 改为这个礼物。
时间复杂度 \(O(t(n+m))\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int t,n,m,a[N],c[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;while(t--){
cin>>n>>m;
int z=0;ll ans=0;
for(int i=1;i<=n;i++)
cin>>a[i],c[a[i]]=i;
for(int i=1,b;i<=m;i++){
cin>>b;if(z>c[b]) ans++;
else ans+=(c[b]-i)*2+1,z=c[b];
}cout<<ans<<"\n";
}return 0;
}
T2 [luogu5522]棠梨煎雪
（堂梨煎雪是什么啊？）
明显可以想到拆开每一位分别维护。
发现维护的就是 \(n\) 个单点修改，区间查询的数列，里面可能是 \(0,1,?\)。
容易想到，假如一个区间内部全是 \(?\)，那么可能性翻倍；假如一个区间内同时存在 \(0,1\)，就没有符合条件的解。
存在性可以用两个树状数组维护，时间复杂度 \(O(nq\log m)\)，由于小常数所以能过。
我当时在考场上写的是线段树，时间复杂度一样，但是常数大，所以 \(TLE60\)。
//线段树代码(T)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2e7+5;
int n,m,q,id,rt[35];
int ls[M],rs[M],as[M];
int c[35][100010],ans;
int push_up(int l,int r){
if(l==4||r==4) return 4;
if(l==3) return r;
if(r==3) return l;
if(l!=r) return 4;
return l;
}void build(int a,int x,int l,int r){
if(l==r){
as[x]=c[a][l];
return;
}int mid=(l+r)/2;
ls[x]=++id;rs[x]=++id;
build(a,ls[x],l,mid);
build(a,rs[x],mid+1,r);
as[x]=push_up(as[ls[x]],as[rs[x]]);
}void change(int x,int l,int r,int w,int t){
if(l==r){
as[x]=t;
return;
}int mid=(l+r)/2;
if(w<=mid) change(ls[x],l,mid,w,t);
else change(rs[x],mid+1,r,w,t);
as[x]=push_up(as[ls[x]],as[rs[x]]);
}int que(int x,int l,int r,int s,int e){
if(s<=l&&r<=e) return as[x];
int mid=(l+r)/2;
if(s>mid) return que(rs[x],mid+1,r,s,e);
if(e<=mid) return que(ls[x],l,mid,s,e);
return push_up(que(ls[x],l,mid,s,e),que(rs[x],mid+1,r,s,e));
}int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
string s;
cin>>s;
for(int j=0;j<n;j++){
if(s[j]=='0') c[j+1][i]=1;
if(s[j]=='1') c[j+1][i]=2;
if(s[j]=='?') c[j+1][i]=3;
}
}for(int i=1;i<=n;i++){
rt[i]=++id;
build(i,rt[i],1,m);
}while(q--){
int o;cin>>o;
if(!o){
int l,r,sum=1;
cin>>l>>r;
for(int i=1;i<=n;i++){
int u=que(rt[i],1,m,l,r);
if(u==4){sum=0;break;}
if(u==3) sum*=2;
}ans^=sum;
continue;
}int p;cin>>p;
string s;
cin>>s;
for(int i=0;i<n;i++){
int chg;
if(s[i]=='0') chg=1;
if(s[i]=='1') chg=2;
if(s[i]=='?') chg=3;
change(rt[i+1],1,m,p,chg);
}
}cout<<ans;
return 0;
}
//树状数组做法(AC)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,q,id,ans;
int c[35][2][100010];
string s[100010];
void add(int x,int y,int a,int b){
for(;x<=m;x+=x&-x)
c[a][b][x]+=y;
}int que(int x,int a,int b){
int re=0;
for(;x;x-=x&-x)
re+=c[a][b][x];
return re;
}int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
cin>>s[i];
for(int j=0;j<n;j++){
if(s[i][j]=='0') add(i,1,j+1,0);
if(s[i][j]=='1') add(i,1,j+1,1);
}
}while(q--){
int o;cin>>o;
if(!o){
int l,r,sum=1;
cin>>l>>r;
for(int i=1;i<=n;i++){
int u=que(r,i,0)-que(l-1,i,0);
int v=que(r,i,1)-que(l-1,i,1);
if(u&&v){sum=0;break;}
if(!u&&!v) sum*=2;
}ans^=sum;
continue;
}int p;cin>>p;
string t;cin>>t;
for(int i=0;i<n;i++){
int x=-1,y=-1;
if(t[i]=='0') x=0;
if(t[i]=='1') x=1;
if(s[p][i]=='0') y=0;
if(s[p][i]=='1') y=1;
if(y>=0) add(p,-1,i+1,y);
if(x>=0) add(p,1,i+1,x);
}s[p]=t;
}cout<<ans;
return 0;
}
T3 [luogu1174] 打砖块
容易看出是 \(dp\)。
发现调整打砖块的顺序可能会得到更高分，所以考虑“借子弹”的方法。即打一半不打了，送一颗子弹给别的列，换另外一边打完所有的 \(Y\)，然后再把子弹还回来。
考虑设 \(dp_{i,j,0/1}\) 表示在第 \(i\) 列，前面一共用了 \(j\) 枚子弹，是否借子弹。则有：
\[\begin{cases} dp_{i,j,0}=\max(dp_{i-1,j,0},\max\limits_{l=1}^n(dp_{i-1,j-t_{i,l},1}+s1_{i,l},dp_{i-1,j-t_{i,l},0}+s2_{i,l}))\\ dp_{i,j,1}=\max(dp_{i-1,j,1},\max\limits_{l=1}^n(dp_{i-1,j-t_{i,l},1}+s2_{i,l})) \end{cases} \]\(t_{i,j}\) 表示第 \(i\) 列打到第 \(j\) 个点所用子弹数，\(s1_{i,j}\) 表示第 \(i\) 列打到第 \(j\) 个点的收益，\(s2_{i,j}\) 表示第 \(i\) 列打到第 \(j\) 个点和其后面紧跟的所有 \(Y\) 点的收益。这些都可以通过预处理得到。
时间复杂度 \(O(nmk)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,w[205],t[205][205];
int a[205][205],b[205][205];
int s1[205][205],s2[205][205];
int dp[205][205][2],ans,sum;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=n;i;i--)
for(int j=1;j<=m;j++){
char c;cin>>a[i][j]>>c;
if(c=='Y') b[i][j]=1;
sum+=a[i][j];
}
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++){
if(!b[i][j]){
w[j]=i;
break;
}ans+=a[i][j];
}
for(int j=1;j<=m;j++)
for(int i=w[j];i<=n;i++)
s2[j][i]=s1[j][i]=s1[j][i-1]+a[i][j];
for(int j=1;j<=m;j++){
t[j][w[j]]=1;
for(int i=w[j];i<=n;i++){
int id=i;while(b[id+1][j]) id++;
s2[j][i]+=s1[j][id]-s1[j][i];
t[j][id+1]=t[j][i]+1;i=id;
}
}for(int j=0;j<=m;j++)
dp[j][0][0]=-1e9;
for(int j=1;j<=m;j++)
for(int l=1;l<=k;l++){
dp[j][l][0]=dp[j-1][l][0];
dp[j][l][1]=dp[j-1][l][1];
for(int i=w[j];i<=n;i++){
if(b[i][j]||l<t[j][i]) continue;
dp[j][l][0]=max(dp[j][l][0],dp[j-1][l-t[j][i]][1]+s1[j][i]);
dp[j][l][0]=max(dp[j][l][0],dp[j-1][l-t[j][i]][0]+s2[j][i]);
dp[j][l][1]=max(dp[j][l][1],dp[j-1][l-t[j][i]][1]+s2[j][i]);
}
}
cout<<min(sum,dp[m][k][0]+ans);
return 0;
}
T4 [NOIP2015] 斗地主（普通版）
大模拟，不多说了，详见代码。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,n,ans,s[25];
void dfs(int x){
if(x>=ans) return;
//一、顺子
int k=0;//1.单顺子
for(int i=3;i<=14;i++){
if(!s[i]) k=0;
else k++;
if(k<5) continue;
for(int j=i;j>i-k;j--) s[j]--;
dfs(x+1);
for(int j=i;j>i-k;j--) s[j]++;
}k=0;//2.双顺子
for(int i=3;i<=14;i++){
if(s[i]<2) k=0;
else k++;
if(k<3) continue;
for(int j=i;j>i-k;j--) s[j]-=2;
dfs(x+1);
for(int j=i;j>i-k;j--) s[j]+=2;
}k=0;//3.三顺子
for(int i=3;i<=14;i++){
if(s[i]<3) k=0;
else k++;
if(k<2) continue;
for(int j=i;j>i-k;j--) s[j]-=3;
dfs(x+1);
for(int j=i;j>i-k;j--) s[j]+=3;
}//二、老带新
//先枚举三张牌/炸弹
for(int i=2;i<=14;i++){
if(s[i]<3) continue;
//1.三带一/二
s[i]-=3;
//(1)带单张牌
for(int j=2;j<=15;j++){
if(!s[j]||j==i) continue;
s[j]--;dfs(x+1);s[j]++;
}//(2)带对子（大小王不是对子）
for(int j=2;j<=14;j++){
if(s[j]<2) continue;
s[j]-=2;dfs(x+1);s[j]+=2;
}s[i]+=3;
if(s[i]<4) continue;
//2.四带二
s[i]-=4;
//(1)带俩单张牌
for(int j=2;j<=15;j++){
//枚举第一张牌
if(!s[j]) continue;
for(int l=2;l<=15;l++){
//枚举第二张牌
if(!s[l]||l==j) continue;
s[j]--;s[l]--;
dfs(x+1);
s[j]++;s[l]++;
}
}//(2)带俩对子
for(int j=2;j<=14;j++){
//枚举第一个对子
if(s[j]<2) continue;
for(int l=2;l<=14;l++){
//枚举第二个对子
if(s[l]<2||l==j) continue;
s[j]-=2;s[l]-=2;
dfs(x+1);
s[j]+=2;s[l]+=2;
}
}s[i]+=4;
}//三、就地解决
for(int i=2;i<=15;i++)
if(s[i]) x++;
ans=min(ans,x);
}int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t>>n;
while(t--){
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
if(!x) x=15;
if(x==1) x=14;
s[x]++;
}ans=25;dfs(0);
cout<<ans<<"\n";
}return 0;
}