【题解】毒瘤 OI 刷题汇总 [SCOI2011]
由于不清楚题目顺序,就按照 ( ext{BZOJ}) 上面的排列好了。
一个小学生图论板子,一个数据结构胖题,一个恶心模拟,一个毒瘤插头 (dp),两道死题,我枯TAT....
【Day1 T1】糖果
传送门:糖果 ( ext{[P3275]}) ( ext{[Bzoj2330]})
【题目描述】
给出 (m) ((mleqslant 10^5)) 个约束条件,条件分为以下 (5) 种:
(1 x y:) (A[x]=A[y])
(2 x y:) (A[x]<A[y])
(3 x y:) (A[x]geqslant A[y])
(4 x y:) (A[x]>A[y])
(5 x y:) (A[x]leqslant A[y])
现要构造一个长为 (n) ((nleqslant 10^5)) 的合法序列 (A),使得序列中的数总和最小,并输出这个最小值,如果无解输出 (-1) 。
【分析】
差分约束板子题,没啥好说的,暴力建边瞎跑个 (SPFA) 就水过去了。
时间复杂度:(O(SPFA)) 。
【Code】
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=3e5+5,inf=2e9;
int x,y,n,m,o,op,chu[N],dis[N],pan[N],head[N];long long ans;
struct QAQ{int w,to,next;}a[M];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
inline int SPFA(Re st,Re ed){//求最小值跑最长路
for(Re i=0;i<=n;++i)dis[i]=-inf,chu[i]=0;
dis[st]=0,chu[st]=pan[st]=1,Q.push(st);
while(!Q.empty()){
x=Q.front(),Q.pop();
pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(dis[to=a[i].to]<dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w;
if((chu[to]=chu[x]+1)>n+1)return 1;
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return 0;
}
int main(){
in(n),in(m);
for(Re i=n;i>=1;--i)add(0,i,1); //a[i]>=a[0]=1,a[i]-a[0]>=1
while(m--){
in(op),in(x),in(y);
if(op<2)add(y,x,0),add(x,y,0);//a[x]==a[y]: a[x]-a[y]>=0且a[y]-a[x]>=0
else if(op<3)add(x,y,1);//a[x]<a[y]: a[y]-a[x]>=1
else if(op<4)add(y,x,0);//a[x]>=a[y]: a[x]-a[y]>=0
else if(op<5)add(y,x,1);//a[x]>a[y]: a[x]-a[y]>=1
else add(x,y,0);//a[x]<=a[y]: a[y]-a[x]>=0
if(!(op%2)&&x==y){puts("-1");return 0;}
}
if(SPFA(0,n))puts("-1");
else{
for(Re i=1;i<=n;++i)ans+=dis[i];
printf("%lld",ans);
}
}
【Day1 T2】地板
传送门:地板 ( ext{[P3272]}) ( ext{[Bzoj2331]})
【题目描述】
给出一个 (n*m) ((n*mleqslant 100)) 的方格图,其中一些格子有障碍,剩下的为空格。求用 ( ext{L}) 形地板把空格填满的方案数。
【分析】
一道简单三进制插头 (dp) 。
( ext{L}) 形实际上就是一根只拐了一次弯的线,考虑在轮廓线上另加一个状态表示插头是否拐过弯,用 (0) 表示没有插头,(1) 表示一个还没拐过弯的插头,(2) 表示一个已经拐过弯的插头,随便分类讨论下就完事了。
时间复杂度:(O(nm2^{10})) 。
洛谷上那几篇题解都用了各种各样的奇怪 ( ext{Hash})
(emm...) 不是很能理解那种写法,不仅增加了码量还会加大常数。
实际上存一下 (3) 的各次幂就可以了,常数会小很多。下面这份代码不开 (O2) 就直接跑到了 (rk2),( ext{loj}) 上 (rk1),而且把同类项合并起来说不定还能更快。
【Code】
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=177147+3,P=20110520;
int n,m,o,V,Mi[N],A[N][N],A_[N][N],dp[2][M];char s[N];//0:没有插头 1:还没拐过的插头 2:已经拐过的插头
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void mo(Re &x){if(x>P)x-=P;}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=1;i<=n;++i){
scanf("%s",s+1);
for(Re j=1;j<=m;++j)A[i][j]=(s[j]=='*');
}
if(n<m){
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
A_[j][i]=A[i][j];
swap(n,m);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
A[i][j]=A_[i][j];
}
Mi[0]=1;for(Re i=1;i<=m+1;++i)Mi[i]=Mi[i-1]*3;
V=Mi[m+1]-1,dp[o][0]=1;
for(Re i=1;i<=n;++i){
o^=1;
for(Re s=0;s<=V;++s)dp[o][s]=s%3?0:dp[o^1][s/3];
for(Re j=1;j<=m;++j){
o^=1;
for(Re s=0;s<=V;++s)dp[o][s]=0;
for(Re s=0;s<=V;++s)if(dp[o^1][s]){
Re L=s/Mi[j-1]%3,U=s/Mi[j+1-1]%3,ML=Mi[j-1],MU=Mi[j+1-1];
if(A[i][j]){//此处不能放插头
if(!L&&!U)mo(dp[o][s]+=dp[o^1][s]);
}
else{//此处可以放插头
if(L==0&&U==0){
mo(dp[o][s+ML]+=dp[o^1][s]);//下1
mo(dp[o][s+MU]+=dp[o^1][s]);//右1
mo(dp[o][s+2*ML+2*MU]+=dp[o^1][s]);//右下拐
}
if(L==0&&U==1){
mo(dp[o][s+MU]+=dp[o^1][s]);//右上拐,原来的1变成2
mo(dp[o][s+ML-MU]+=dp[o^1][s]);//下1
}
if(L==0&&U==2){
mo(dp[o][s+2*ML-2*MU]+=dp[o^1][s]);//下2
mo(dp[o][s-2*MU]+=dp[o^1][s]);//在这一格后便终止
}
if(L==1&&U==0){
mo(dp[o][s+ML]+=dp[o^1][s]);//左下拐,原来的1变成2
mo(dp[o][s-ML+MU]+=dp[o^1][s]);//右1
}
if(L==1&&U==1)mo(dp[o][s-ML-MU]+=dp[o^1][s]);//左上拐,原来的1变为0
if(L==1&&U==2);//无法继续
if(L==2&&U==0){
mo(dp[o][s-2*ML+2*MU]+=dp[o^1][s]);//右2
mo(dp[o][s-2*ML]+=dp[o^1][s]);//在这一格后便终止
}
if(L==2&&U==1);//无法继续
if(L==2&&U==2);//无法继续
}
}
}
}
printf("%d
",dp[o][0]);
}
【Day1 T3】植物大战僵尸
传送门:植物大战僵尸 ( ext{[P3274]}) ( ext{[Bzoj2332]})
【题目描述】
略。
【分析】
貌似是个毒瘤网络瘤。
死题,不会。
【Code】
不知道这儿能放啥,干脆买个萌吧(⊙ω⊙)
【Day2 T1】棘手的操作
传送门:棘手的操作 ( ext{[P3273]}) ( ext{[Bzoj2333]})
【题目描述】
有 (n) ((nleqslant 3*10^5)) 个初始相不连通的点,第 (i) 个节点的权值为 (a_i),给出 (m) ((mleqslant 3*10^5)) 个操作,操作有以下几种:
-
(U x y:) 增加一条连接节点 (x) 和节点 (y) 的边。
-
(A1 x v:) 将节点 (x) 的权值增加 (v) 。
-
(A2 x v:) 将节点 (x) 所在连通块的所有节点权值都增加 (v) 。
-
(A3 v:) 将所有节点的权值都增加 (v) 。
-
(F1 x:) 输出节点 (x) 的权值。
-
(F2 x:) 输出节点 (x) 所在连通块中的最大权值。
-
(F3:) 输出所有节点中的最大权值。
【分析】
冰茶姬预处理 + 线段树瞎搞。
由于只有连边没有断边,所以一定可以给所有节点找到一种编号的排列,使得在任意时刻同一联通块中的点均为一段编号连续的区间。
写个可回退的按秩合并冰茶姬预处理出编号,然后用线段树维护即可。
时间复杂度:(O(mlog n))。
【Code】
#include<algorithm>
#include<cstdio>
#include<stack>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+3,inf=2e9;
int n,T,O,A[N],id[N],idx[N];
struct QAQ{int x,y;char op[5];}a[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int fa[N],size[N];
struct QWQ{int x,fa,size;};stack<QWQ>Q;
inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
inline void merge(Re x,Re y){
if((x=find(x))==(y=find(y)))return;
if(size[x]<size[y])swap(x,y);
Q.push((QWQ){y,x,size[y]});
fa[y]=x,size[x]+=size[y];
}
inline void sakura(Re o){
if(o>T){
for(Re i=1;i<=n;++i)if(!id[find(i)])
id[find(i)]=++O,O+=size[find(i)]-1;
return;
}
Re tmp=Q.size();
if(a[o].op[0]=='U')merge(a[o].x,a[o].y);
sakura(o+1);
if(Q.size()!=tmp){
QWQ a=Q.top();Q.pop();
fa[a.x]=a.x,size[a.fa]-=(size[a.x]=a.size);
id[a.x]=id[a.fa]+size[a.fa];
}
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{int max,add;}tr[N<<2];
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].max=A[idx[L]];return;}
build(pl,L,mid),build(pr,mid+1,R);
tr[p].max=max(tr[pl].max,tr[pr].max);
}
inline void updata(Re p,Re v){tr[p].max+=v,tr[p].add+=v;}
inline void pushdown(Re p){
if(tr[p].add)updata(pl,tr[p].add),updata(pr,tr[p].add),tr[p].add=0;
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){updata(p,v);return;}
pushdown(p);
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
tr[p].max=max(tr[pl].max,tr[pr].max);
}
inline int ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].max;
Re ans=-inf;pushdown(p);
if(l<=mid)ans=max(ans,ask(pl,L,mid,l,r));
if(r>mid)ans=max(ans,ask(pr,mid+1,R,l,r));
return ans;
}
}TR;
#define op0 a[i].op[0]
#define op1 a[i].op[1]
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i)in(A[i]),fa[i]=i,size[i]=1;
in(T);
for(Re i=1;i<=T;++i){
scanf("%s",a[i].op);
if(a[i].op[0]=='F'&&a[i].op[1]=='3')continue;
in(a[i].x);
if(a[i].op[0]=='U'||(a[i].op[0]=='A'&&a[i].op[1]!='3'))in(a[i].y);
}
sakura(1);
for(Re i=1;i<=n;++i)idx[id[i]]=i;
TR.build(1,1,n);
for(Re i=1,dlt=0;i<=T;++i){
if(op0=='U')merge(a[i].x,a[i].y);
else if(op0=='A'){
if(op1=='1')TR.change(1,1,n,id[a[i].x],id[a[i].x],a[i].y);
else if(op1=='2')a[i].x=find(a[i].x),TR.change(1,1,n,id[a[i].x],id[a[i].x]+size[a[i].x]-1,a[i].y);
else dlt+=a[i].x;
}
else{
if(op1=='1')printf("%d
",dlt+TR.ask(1,1,n,id[a[i].x],id[a[i].x]));
else if(op1=='2')a[i].x=find(a[i].x),printf("%d
",dlt+TR.ask(1,1,n,id[a[i].x],id[a[i].x]+size[a[i].x]-1));
else printf("%d
",dlt+TR.tr[1].max);
}
}
}
【Day2 T2】镜像拆分
传送门:镜像拆分 ( ext{[P3276]}) ( ext{[Bzoj2334]})
【题目描述】
略。
【分析】
貌似是个毒瘤数位 (dp)。
死题,不会。
【Code】
不知道这儿能放啥,干脆买个萌吧(⊙ω⊙)
【Day2 T3】飞镖
传送门:飞镖 ( ext{[P3277]}) ( ext{[Bzoj2335]})
【题目描述】
略。
【分析】
毒瘤数学模拟题,恶心,不想做。
【Code】
不知道这儿能放啥,干脆买个萌吧(⊙ω⊙)