玩游戏
考场思路
想了一个极为麻烦的贪心，但是没时间写了。
正解：
将左标记向左移，寻找每个左标记右标记最靠右的位置
#include<bits/stdc++.h>
#define lt long long
#define int long long
using namespace std;
const lt N=100050;
int n,k,r,T;
int a[N];
int sum[N];
bool flag=0;
signed main(){
// freopen("shuju.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%lld",&T);
for(int w=1;w<=T;++w){
memset(sum,0,sizeof(sum));
flag=0;
scanf("%lld%lld",&n,&k);
r=k;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int j=k-1;j>=1;--j){
sum[j]=sum[j+1]+a[j+1];
}
for(int j=k+1;j<=n;++j){
sum[j]=sum[j-1]+a[j];
}
// cout<<r<<endl;
// for(int i=1;i<=n;++i){
// cout<<sum[i]<<" |";
// }
for(int j=k;j>=1;--j){
while(sum[r+1]+sum[j]<=0&&r<n) r++;
while(sum[r]+sum[j]>0&&r>0) r--;
if(r<k){
flag=1;
break;
}
}
// cout<<r<<endl;
if(flag==0&&r==n){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}
排列
考场思路:
通过k=1的点骗了些分，想到了k不可能大于logN，但是输出是零的这一块并没有设置数据点。
正解
dp题
对于一个大区间，可以被区间内最大的值分为两个小区间，两个小区间是相互独立的互不干扰的，所以一个大区间的方案数是两个小区间的方案数乘组合数（因为是从大区间随意选数进入第一个区间，剩下的进入第二个区间）。
对于每一个区间都有四种情况，左边是挨着一个更大数还是靠墙，右边是挨着一个更大数还是靠墙，设置dp数组f[i][j][1/0][1/0]，i表示区间长度，j表示操作几次，并且处理为，从操作一次到操作j次的前缀和(记住，后面会用到多次），后面两维分别表示左右两边是否靠墙。
考虑转移，对于00的情况（意为两边都靠墙）可以由j相同的左小区间01和右小区间10转移过来，因为对于两边都靠墙的情况，当两边的小区间消除完之后，他本身也就结束了
对于10的情况我们如果想让它在次内完成操作，就必须让区间内的最大值在j-1次的时候与左边界相遇，才能使得在第j次时被消除，所以由左边的j-1的11和右边的j的10转移过来
01同理
对于11的情况，我们可以让中间值在j-1的时候靠左或靠右，
因为j代表的是前缀和，所以我们只要先由两边都是j转移过来，再将两边恰好同时选j的情况减去即可
#include<bits/stdc++.h>
#define lt long long
using namespace std;
const lt N=1005;
lt n,kk,mod;
lt f[N][100][2][2],c[N][N];
int main(){
scanf("%lld%lld%lld",&n,&kk,&mod);
for(int i=0;i<=kk+1;++i){
f[0][i][0][0]=f[0][i][0][1]=f[0][i][1][0]=f[0][i][1][1]=1;
}
for(int i=0;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=i;j++){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
// cout<<c[i][j]<<"|";
}
// cout<<endl;
}
for(int i=1;i<=n;++i){
for(int k=1;k<=kk+1;k++){
for(int j=1;j<=i;++j){
f[i][k][0][0]+=((f[j-1][k][0][1]*f[i-j][k][1][0])%mod*c[i-1][j-1])%mod;
f[i][k][0][1]+=((f[j-1][k][0][1]*f[i-j][k-1][1][1])%mod*c[i-1][j-1])%mod;
f[i][k][1][0]+=((f[j-1][k-1][1][1]*f[i-j][k][1][0])%mod*c[i-1][j-1])%mod;
f[i][k][1][1]+=(((f[j-1][k][1][1]*f[i-j][k][1][1])-(f[j-1][k][1][1]-f[j-1][k-1][1][1])*(f[i-j][k][1][1]-f[i-j][k-1][1][1]))%mod*c[i-1][j-1])%mod;
f[i][k][0][0]%=mod;
f[i][k][0][1]%=mod;
f[i][k][1][0]%=mod;
f[i][k][1][1]%=mod;
// printf("%d %d %d\n",i,k,f[i][k][0][0]);
}
}
}
lt ens=((f[n][kk][0][0]-f[n][kk-1][0][0])%mod+mod)%mod;
printf("%lld\n",ens);
}
（最短路暂咕咕咕）
矩形
考场思路
在考场上想到了正解，但数组开小了所以只得了50分，考完之后直接10倍数组就过了(到现在都不明白为什么四倍数组都过不去)
正解：
（其实是我的想法，正解又难写又慢）（而且还看不懂）
从左往右扫，遇到左边界便加进线段树中，搜索线段树中的这一段区间，将线段树中将线段树的这一部分点中的标号的矩形与当前矩形连边，并且标成当前矩形。当到达右边界，删除矩形时，如果线段树的这一部分只剩一层矩形，则直接删除；如果还有其他矩形，则只将矩形的层数减一即可，不必修改这一部分的标号（因为它和剩余矩形肯定是相交的,所以两者等价）
#include<bits/stdc++.h>
using namespace std;
const int N=1000050;
int n,tot,cnt;
int x[N],y[N],xx[N],yy[N],head[N];
int t[N*4],sum[N*4],co[N*4],lz[N*4];
bool clen[N*4],vis[N];//记得消除
int xmx,ymx;
vector<int> in[N],out[N];
struct edge{
int fr,nxt,to;
}e[N*8];//记得双向建边
void ade(int x,int y){
e[++tot].to=y;
e[tot].fr=x;
e[tot].nxt=head[x];
head[x]=tot;
}
void pushdown(int u){
if(clen[u]){
t[u<<1]=0;
t[u<<1|1]=0;
clen[u<<1]=1;
clen[u<<1|1]=1;
co[u<<1]=co[u];
co[u<<1|1]=co[u];
clen[u]=0;
}
if(lz[u]){
lz[u<<1]+=lz[u];
lz[u<<1|1]+=lz[u];
sum[u<<1]+=lz[u];
sum[u<<1|1]+=lz[u];
lz[u]=0;
}
if(sum[u<<1]==0){
co[u<<1]=0;
t[u<<1]=0;
}
if(sum[u<<1|1]==0){
co[u<<1|1]=0;
t[u<<1|1]=0;
}
// if(u==5){
// printf("%d %d %d %d %d" ,lz[u],co[u],clen[u],co[u<<1],co[u<<1|1]);
// }
}
void pushup(int u){
if(co[u<<1]!=co[u<<1|1]&&co[u<<1]&&co[u<<1|1]){
co[u]=0;
t[u]=1;
}
if(!co[u<<1]&&co[u<<1|1]){
co[u]=co[u<<1|1];
}
if(!co[u<<1|1]&&co[u<<1]){
co[u]=co[u<<1];
}
if(co[u<<1]==co[u<<1|1]){
co[u]=co[u<<1|1];
}
sum[u]=max(sum[u<<1],sum[u<<1|1]);
if(t[u<<1]||t[u<<1|1]){
t[u]=1;
}
}
void ask(int u,int l,int r,int ll,int rr,int x){
if(l>rr||r<ll){
return;
}
// if(1){
// printf("[%d %d %d %d %d]\n",l,r,u,t[u],co[u]);
// }
if(l>=ll&&r<=rr){
if(!t[u]){
if(co[u]){
ade(co[u],x);
ade(x,co[u]);
}
}
else{
pushdown(u);
int mid=(l+r)>>1;
ask(u<<1,l,mid,ll,rr,x);
ask(u<<1|1,mid+1,r,ll,rr,x);
}
return;
}
pushdown(u);
int mid=(l+r)>>1;
ask(u<<1,l,mid,ll,rr,x);
ask(u<<1|1,mid+1,r,ll,rr,x);
}
void edit(int u,int l,int r,int ll,int rr,int x){
if(l>rr||r<ll){
return;
}
if(l>=ll&&r<=rr){
t[u]=0;
clen[u]=1;
sum[u]+=1;
lz[u]+=1;
co[u]=x;
return;
}
pushdown(u);
int mid=(l+r)>>1;
edit(u<<1,l,mid,ll,rr,x);
edit(u<<1|1,mid+1,r,ll,rr,x);
pushup(u);
// if(1){
// printf("<%d %d %d %d %d>\n",l,r,u,t[u],co[u]);
// }
}
void del(int u,int l,int r,int ll,int rr){
if(l>rr||r<ll){
return;
}
if(l>=ll&&r<=rr){
if(sum[u]==1){
sum[u]--;
co[u]=0;
t[u]=0;
lz[u]--;
}
else{
sum[u]--;
lz[u]--;
}
return;
}
pushdown(u);
int mid=(l+r)>>1;
del(u<<1,l,mid,ll,rr);
del(u<<1|1,mid+1,r,ll,rr);
pushup(u);
}
void dfs(int u){
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]){
dfs(v);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d%d%d",&x[i],&y[i],&xx[i],&yy[i]);
xmx=max(xx[i],xmx);
ymx=max(yy[i],ymx);
in[x[i]].push_back(i);
out[xx[i]].push_back(i);
}
// cout<<endl;
for(int i=1;i<=xmx;i++){
int sze=in[i].size();
for(int j=0;j<sze;++j){
// printf("%d %d %d %d \n",i,in[i][j],y[in[i][j]],yy[in[i][j]]);
ask(1,1,ymx,y[in[i][j]],yy[in[i][j]],in[i][j]);
edit(1,1,ymx,y[in[i][j]],yy[in[i][j]],in[i][j]);
}
int sz=out[i].size();
for(int j=0;j<sz;++j){
int ot=out[i][j];
del(1,1,ymx,y[ot],yy[ot]);
}
}
// for(int i=1;i<=tot;++i){
// cout<<e[i].fr<<" "<<e[i].to<<endl;
// }
for(int i=1;i<=n;++i){
if(!vis[i]){
++cnt;
dfs(i);
}
}
cout<<cnt<<endl;
return 0;
}