noip模拟75 solutions
这是一场完全失败的考试，总分0pts
的确是暴露了我很多问题
第一题难，第二题难，我直接心态炸了，根本做不下题去
还是我的心态有问题，一撞到自己一点都不会的考试就完蛋了
就应该拿儒略日练练我
考场心态极其重要，不能因为某个题或者某几个正解不会而放弃
所以以后一定要让自己不被题的难度所影响
该拿的分一定得拿到！！
T1 洛希极限
在此说一下我的心路历程：
上来肯定是先开第一题的
我读完题之后，发现并不是那么可做，甚至很高的部分分都不能拿到
直接就开始想正解了，然而此时的我题意是理解错误的，没仔细读题
45分钟之后，我发现我好想会正解了！！
于是我开始打了，此时的我以为是小于等于就可以转移
然后我打完之后并不能过样例，调了一会，手摸了样例，发现自己读错题了，此时已经一个小时10分钟
我不知道该咋办，这个题已经有了一个初步的思路但是并没有正解，可是我想继续思考下去
但是另一个思想警惕着我，开题顺序可能会把第一题放在最后
于是我毅然决然的继续和第一题死刚，然而并不能做出来
最后只发现了那个重要的性质，但是并没有优化我的复杂度，并且我多测未清导致爆零
性质：按照最优策略，当前点一定从前一行或者前一列转移过来，不然的话一定可以找到这样一个人路径
所以我们就是要找前一行或者前一列的最大转移点，单调队列
预处理的时候用一个数组记录右侧距离当前点最近的未更新的点，直接跳过去
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2005;
const int Q=5e5+5;
const int mod=1e9+7;
int T,n,m,q;
struct ma{
int r1,r2,c1,c2;
ma(){}
}sca[Q],use[Q];
int buc[Q];
struct node{
int ans,sum;
node(){}
node(int x,int y){ans=x;sum=y;}
node operator + (node x)const{
node ret;
if(ans>x.ans)ret=*this;
if(ans<x.ans)ret=x;
if(ans==x.ans)ret.ans=ans,ret.sum=(sum+x.sum)%mod;
return ret;
}
bool operator < (node x)const{
return ans<x.ans;
}
}dp[N][N],ans;
void print(node x){printf("%lld %lld\n",x.ans,x.sum);}
int le[N][N],ri[N][N],up[N][N],dw[N][N];
int getri(int x,int y){return ri[x][y]==0?x:ri[x][y]=getri(ri[x][y],y);}
int getup(int x,int y){return up[x][y]==0?y:up[x][y]=getup(x,up[x][y]);}
struct Queue{
node q[N];
int w[N],cnt[N];
int bot,top;
void init(){
bot=1;top=0;
fo(i,0,min(n,m))cnt[i]=0;
}
void push(int x,node v){
while(bot<=top&&q[top]<v)cnt[q[top].ans]=(cnt[q[top].ans]-q[top].sum+mod)%mod,top--;
q[++top]=v;cnt[q[top].ans]=(cnt[q[top].ans]+q[top].sum)%mod;w[top]=x;
}
node query(int x){
while(bot<=top&&w[bot]<x)cnt[q[bot].ans]=(cnt[q[bot].ans]-q[bot].sum+mod)%mod,bot++;
return node(q[bot].ans+1,cnt[q[bot].ans]);
}
}r[N],c[N];
signed main(){
#ifdef oj
freopen("roche.in","r",stdin);
freopen("roche.out","w",stdout);
#endif
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&n,&m,&q);
fo(i,1,n)fo(j,1,m)up[i][j]=le[i][j]=dw[i][j]=ri[i][j]=0;
fo(i,1,q)scanf("%lld%lld%lld%lld",&sca[i].r1,&sca[i].c1,&sca[i].r2,&sca[i].c2);
fo(i,1,q)buc[sca[i].r1]++;
fo(i,1,n)buc[i]+=buc[i-1];
fo(i,1,q)use[buc[sca[i].r1]--]=sca[i];
fo(i,1,n)buc[i]=0;
fo(i,1,q){
fo(y,use[i].c1+1,use[i].c2){
for(int x=use[i].r1+1;x<=use[i].r2;){
if(!ri[x][y]){
le[x][y]=use[i].r1;
ri[x][y]=x+1;
x++;
}
else x=getri(x,y);
}
}
}
//cout<<"fuck"<<endl;
ans=node(0,0);
fo(i,1,q)buc[sca[i].c1]++;
fo(i,1,m)buc[i]+=buc[i-1];
fo(i,1,q)use[buc[sca[i].c1]--]=sca[i];
fo(i,1,m)buc[i]=0;
fo(i,1,q){
fo(x,use[i].r1+1,use[i].r2){
for(int y=use[i].c1+1;y<=use[i].c2;){
if(!up[x][y]){
dw[x][y]=use[i].c1;
up[x][y]=y+1;
y++;
}
else y=getup(x,y);
}
}
}
//cout<<"SB"<<endl;
fo(i,1,n)fo(j,1,m)dp[i][j]=node(1,1);
fo(i,1,n)r[i].init();
fo(i,1,m)c[i].init();
fo(i,1,n){
fo(j,1,m){
r[i].push(j,dp[i][j]);
c[j].push(i,dp[i][j]);
if(i<n&&j<m&&le[i+1][j+1]&&dw[i+1][j+1]){
dp[i+1][j+1]=dp[i+1][j+1]+r[i].query(dw[i+1][j+1]);
dp[i+1][j+1]=dp[i+1][j+1]+c[j].query(le[i+1][j+1]);
if(dp[i][j].ans+1==dp[i+1][j+1].ans)dp[i+1][j+1].sum=(dp[i+1][j+1].sum-dp[i][j].sum+mod)%mod;
}
//cout<<i<<" "<<j<<" ";print(dp[i][j]);
ans=ans+dp[i][j];
}
}
print(ans);
}
}
T2 特立独行的图
差分约束吧，不会
T3 玩游戏
推导吧，不会，但是我会抄式子
T4 骆驼
这个5*5的棋盘好走，多搜出几个来
然后规划好路线，直接干就好了
还没有改