【题解】毒瘤 OI 刷题汇总 [SCOI2013]

【题解】毒瘤 OI 刷题汇总 [SCOI2013]

由于不清楚题目顺序，就按照 ( ext{BZOJ}) 上面的排列好了。

【Day1 T1】摩托车交易

传送门：摩托车交易 ( ext{[P3280]}) ( ext{[Bzoj3322]})

【题目描述】

给出一个 (n) ((nleqslant 10^5)) 个点 (m) ((mleqslant 2*10^5)) 条边的无向连通图，图中的点、边带有边权，其中有 (q) ((0leqslant qleqslant n)) 为特殊点，对于任意两个特殊点之间都有一条权值为 (inf) 的边。

现需要按照给定顺序依次经过这 (n) 个点，在某些点可以购买本子，某些点可以卖出本子，在各点的本子交易量不能超过该点的点权，经过某条边时所携带的本子数量不能超过该边的边权。

在进行每次卖出交易时您想要使得本次的卖出量最大，并且在与最后一个点进行交易后手上不能有剩余的本子。请按照顺序依次输出最大卖出量。

【分析】

最大生成树 + 倍增 (LCA) 求路径最小值，模拟本子交易。

注意到我们只需要尽量携带最多的本子，不必在意是否卖光的问题，因为实际行动时可以通过调整数量来避免多余本子的出现。

很显然我们可以先求出这 (n) 个点的最大生成树，每次移动时走树上的路径就可以保证本子运送量最大。

处理特殊点显然不能暴力枚举，可以新建一个中转点 (n+1)，所有特殊点均向 (n+1) 连一条权值为 (inf) 的边即可（注意细节：新建节点后求生成树就是 (n+1) 个节点了，还有就是当不存在特殊点时不能新建中转点，否则会不连通）。

然后随便写个倍增 (LCA) 或者树剖求树上路径最小值，设个变量 (v) 表示目前携带的本子数量，瞎模拟一下就可以了。

时间复杂度：(O((m+q)log(m+q)+nlog n)) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const LL N=1e5+3,M=2e5+3,inf=1e18,logN=17;
LL n,m,x,y,o,T,A[N],ip[N],fa[N],head[N];
struct QAQ{LL w,to,next;}a[N<<1];
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;}
struct QWQ{LL x,y,z;inline bool operator<(const QWQ &O)const{return z>O.z;}}b[M+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;
}
inline LL find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct LCA{
    LL deep[N],dis[N][20],ant[N][20];
    inline void dfs(Re x,Re fa,Re w){
        deep[x]=deep[ant[x][0]=fa]+1,dis[x][0]=w;
        for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1],dis[x][i]=min(dis[x][i-1],dis[ant[x][i-1]][i-1]);
        for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x,a[i].w);
    }
    inline LL ask(Re x,Re y){
        if(deep[x]<deep[y])swap(x,y);Re ans=inf;
        for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])ans=min(ans,dis[x][i]),x=ant[x][i];
        if(x==y)return ans;
        for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])ans=min(ans,min(dis[x][i],dis[y][i])),x=ant[x][i],y=ant[y][i];
        return min(ans,min(dis[x][0],dis[y][0]));
    }
}T1;
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m),in(T);
    for(Re i=1;i<=n;++i)in(ip[i]);
    for(Re i=1;i<=n;++i)in(A[i]);
    for(Re i=1;i<=m;++i)in(b[i].x),in(b[i].y),in(b[i].z);
    if(T){
        while(T--)in(x),b[++m].x=x,b[m].y=n+1,b[m].z=inf;
        sort(b+1,b+m+1);
        for(Re i=1;i<=n+1;++i)fa[i]=i;
        for(Re i=1,t=0;i<=m&&t<n;++i)
            if((x=find(b[i].x))!=(y=find(b[i].y)))
                ++t,fa[x]=y,add(b[i].x,b[i].y,b[i].z),add(b[i].y,b[i].x,b[i].z);
    }
    else{
        sort(b+1,b+m+1);
        for(Re i=1;i<=n;++i)fa[i]=i;
        for(Re i=1,t=0;i<=m&&t<n-1;++i)
            if((x=find(b[i].x))!=(y=find(b[i].y)))
                ++t,fa[x]=y,add(b[i].x,b[i].y,b[i].z),add(b[i].y,b[i].x,b[i].z);
    }
    T1.dfs(1,0,inf);LL w=1,v=A[ip[1]];
    while(v<0)puts("0"),v=A[ip[++w]];
    for(Re i=w+1,x=ip[w];i<=n;x=ip[i],++i){
        Re to=ip[i];v=min(v,(LL)T1.ask(x,to));
        if(A[to]<0)printf("%lld
",min(v,(LL)-A[to])),v-=min(v,(LL)-A[to]);
        else v+=A[to];
    }
}

【Day1 T2】多项式的运算

传送门：多项式的运算 ( ext{[P3278]}) ( ext{[Bzoj3323]})

【题目描述】

你需要维护一个关于 (x) 的无穷多项式（初始时对于所有的 (i) 都有 (a_i=0)）：(f(x)=a_0x^0+a_1x^1+a_2x^2...)

现给出 (m) ((mleqslant 10^5)) 个操作，操作种类如下 ((0leqslant Lleqslant R leqslant 10^5,) (Tleqslant 10))：

  • (mul L R v:) 将 (x^L,x^{L+1}...x^R) 这些项的系数乘以 (v)

  • (add L R v:) 将 (x^L,x^{L+1}...x^R) 这些项的系数加上 (v)

  • (mulx L R:) 将 (x^L,x^{L+1}...x^R) 这些项乘以变量 (x)

  • (query x:) 询问 (f(x)) 的值（满足本操作只会出现 (T) 次）

【分析】

平衡树大水题。

用一颗 (splay) 维护 (a_0,a_1...a_{10^5+1}) 一共 (10^5+2) 个系数，

操作一和操作二就是个小学生懒标记的应用，

操作三可以分为两步：在 (a_{L-1}) 和 (a_{L}) 中间插入一个 (0)，然后把 (a_R) 累加到 (a_{R+1}) 头上。

操作四可以先预处理出 (x) 的 (0sim 10^5+1) 次幂，然后 (dfs) 中序遍历 (splay) 暴力计算答案即可。

时间复杂度：(O(mlog n+Tn))，其中 (n=10^5+2)。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+9,P=20130426;
int x,y,z,n=100002,T,now,ans,X[N];char op[10];
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;
}
struct Splay{
    #define pl tr[p].ps[0]
    #define pr tr[p].ps[1]
    #define pf tr[p].fa
    #define pv tr[p].v
    int O,root;queue<int>Q;
    struct QAQ{int v,fa,add,mul,size,ps[2];}tr[N];
    inline void pushup(Re p){if(p)tr[p].size=1+tr[pl].size+tr[pr].size;}
    inline void updata1(Re p,Re v){//mul
        tr[p].v=(LL)tr[p].v*v%P,tr[p].mul=(LL)tr[p].mul*v%P,tr[p].add=(LL)tr[p].add*v%P;
    }
    inline void updata2(Re p,Re v){//add
        (tr[p].v+=v)%=P,(tr[p].add+=v)%=P;
    }
    inline void pushdown(Re p){
        if(tr[p].mul!=1){
            if(pl)updata1(pl,tr[p].mul);
            if(pr)updata1(pr,tr[p].mul);
            tr[p].mul=1;
        }
        if(tr[p].add){
            if(pl)updata2(pl,tr[p].add);
            if(pr)updata2(pr,tr[p].add);
            tr[p].add=0;
        }
    }
    inline int which(Re p){return tr[pf].ps[1]==p;}
    inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
    inline void rotate(Re p){
        Re fa=pf,fas=which(p);
        Re pa=tr[fa].fa,pas=which(fa);
        Re x=tr[p].ps[fas^1];
        connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
        pushup(fa),pushup(p);
    }
    inline void splay(Re p,Re to){
        for(Re fa;pf!=to;rotate(p))
            if(tr[fa=pf].fa!=to)rotate(which(p)==which(fa)?fa:p);
        if(!to)root=p;
    }
    inline void clear(Re p){pl=pr=pf=pv=tr[p].add=0,tr[p].mul=tr[p].size=1;}
    inline void New(Re &p,Re fa){
        if(Q.empty())p=++O;
        else p=Q.front(),Q.pop();
        clear(p),pf=fa;
    }
    inline void CL(Re p){clear(p),Q.push(p);}
    inline void build(Re &p,Re L,Re R,Re fa){
        if(L>R)return;
        Re mid=L+R>>1;New(p,fa);
        build(pl,L,mid-1,p),build(pr,mid+1,R,p);
        pushup(p);
    }
    inline int find(Re p,Re k){
        pushdown(p);
        if(tr[pl].size>=k)return find(pl,k);
        else return k<=tr[pl].size+1?p:find(pr,k-tr[pl].size-1);
    }
    inline int split(Re L,Re R){
        Re p=find(root,L-1),q=find(root,R+1);
        splay(p,0),splay(q,p);
        return tr[q].ps[0];
    }
    inline void dfs(Re p){
        pushdown(p);
        if(pl)dfs(pl);
        if(now!=-1&&pv)(ans+=(LL)pv*X[now]%P)%=P;
        ++now;
        if(pr)dfs(pr);
    }
    inline void sakura(Re L,Re R){
        Re l=find(root,L-1),r=find(root,R+1);
        splay(l,0),splay(r,l);

        Re p=tr[r].ps[0];
        while(pl)pushdown(p),p=pl;
        pushdown(p),New(pl,p);
        while(p)pushup(p),p=pf;

        p=tr[r].ps[0];
        while(pr)pushdown(p),p=pr;
        pushdown(p),(tr[r].v+=pv)%=P;
        Re fa=pf,fas=which(p);
        if(pl)connect(pl,fa,fas);
        else tr[fa].ps[fas]=0;
        CL(p),p=fa;
        while(p)pushup(p),p=pf;
    }
}TR;
int main(){
//    freopen("123.txt","r",stdin);
    in(T),TR.build(TR.root,1,n+2,0);
    while(T--){
        scanf("%s",op);
        if(op[0]=='q'){
            in(x),ans=0,now=-1,X[0]=1;
            if(!x){puts("0");continue;}
            for(Re i=1;i<n;++i)X[i]=(LL)X[i-1]*x%P;
            TR.dfs(TR.root),printf("%d
",ans);
        }
        else{
            in(x),in(y),x+=2,y+=2;
            if(op[0]=='a')in(z),TR.updata2(TR.split(x,y),z);
            else if(strlen(op)<4)in(z),TR.updata1(TR.split(x,y),z);
            else TR.sakura(x,y);
        }
    }
}

【Day1 T3】火柴棍数字

传送门：火柴棍数字 ( ext{[P3283]}) ( ext{[Bzoj3324]})

【题目描述】

给出一个长度为 (n) ((nleqslant 500)) 的十进制数 (s)，现用一堆火柴棍摆成了这个数，您最多可以移动 (m) ((mleqslant 3500)) 根木棍，求最大能使这个数 (s) 变得多大。

【分析】

神仙 (dp) 。

注意到最优方案一定是在最左边不断地放 (1)，如果可操作木棍为奇数，则用剩下的一根把最左边的那个 (1) 变成 (7)。

先预处理一个转移数组 (val)，其中 (val[i][j]) 表示将数字 (i) 变为 (j) 所需要的移动次数。

设 (cnt[i]) 表示组成数字 (i) 所需木棍数量，则将数字 (i) 转换为 (j) 后所得到的空闲木棍数量就是 (cnt[i]-cnt[j]) 。这里的 “空闲木棍” 指的是不需要移动代价（移动代价的计算被放到了 (val) 里面），可以随便放的木棍，下同。

用 (dp[i][j]) 表示目前从右至左枚举到第 (i) 位，手里有 (j) 个空闲木根，所需要的最小移动木棍次数，

考虑枚举当前位数字 (s_i) 的转移目标 (k)，设 (J=j-(cnt[s_i]-cnt[k]))，则有 (dp[i][j]=min{dp[i+1][J]+val[s_i][k]]}) ((0leqslant J leqslant m))

注意输出答案时要满足左边的尽量大，所以不能直接记录每次转移的最优决策点（因为这个“最优”是针对移动次数最小而言），而应该写一个 (dfs) 从左至右枚举，每次在所有合法决策点中找到转移目标数字最大的那一个（由于寻找的是合法决策点，所以能保证最后火柴棍的使用一定合法）。发现在这个过程中 (j) 可能为负数（因为是倒着枚举），用递推转移写起来很不方便，可以把前面 (dp) 的转移也换成 (dfs) 。

时间复杂度：(O(nm)) 。

【Code】

（貌似应该把数组第二维开两倍处理负数的情况，但数据水直接过了，懒得去管这些细节了）

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=503,M=3503,inf=1e9;
int val[10][10]={
    {0,4,2,2,3,2,1,3,0,1},
    {0,0,2,0,0,1,1,0,0,0},
    {1,4,0,1,3,2,1,3,0,1},
    {1,3,1,0,2,1,1,2,0,0},
    {1,2,2,1,0,1,1,2,0,0},
    {1,4,2,1,2,0,0,3,0,0},
    {1,5,2,2,3,1,0,4,0,1},
    {0,1,1,0,1,1,1,0,0,0},
    {1,5,2,2,3,2,1,4,0,1},
    {1,4,2,1,2,1,1,3,0,0},
};
int cnt[10]={6,2,5,5,4,5,6,3,7,6};
int n,m,dp[N][M],vis[N][M];char s[N];
//dp[i][j]: 目前扫描到第i位，手里有j个空闲木根可以随意操作，所需要的最小移动木棍次数
inline void in(Re &x){
    Re 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 int dfs(Re i,Re j){
    if(j>m)return inf;
    if(i>n)return j?inf:0;
    if(vis[i][j])return dp[i][j];
    vis[i][j]=1,dp[i][j]=inf;
    for(Re k=9,j_,tmp;k>=0;--k)
        if((j_=j+cnt[k]-cnt[s[i]-'0'])>=0&&j_<=m)
            if((tmp=dfs(i+1,j_)+val[s[i]-'0'][k])<dp[i][j])
                if(tmp<=m)dp[i][j]=tmp;
    return dp[i][j];
}
inline void print(Re i,Re j){
    if(i>n)return;
    for(Re k=9,j_;k>=0;--k)
        if(dfs(i+1,j_=j+cnt[k]-cnt[s[i]-'0'])+val[s[i]-'0'][k]<=m){
            printf("%d",k),m-=val[s[i]-'0'][k],print(i+1,j_);return;
        }
}
int main(){
//    freopen("123.txt","r",stdin);
    scanf("%s%d",s+1,&m),n=strlen(s+1);
    for(Re j=m;j>1;--j)//枚举手中的空闲木棍数量
        if(dfs(1,j)<=m){
            Re now=j;
            if(now&1)putchar('7'),now-=3;
            while(now)putchar('1'),now-=2;
            print(1,j);return 0;
        }
    print(1,0);//如果不足2个就不能在前面补数，因此答案为print(1,0)而不能是print(1,1)
}

【Day2 T1】密码

传送门：密码 ( ext{[P3279]}) ( ext{[Bzoj3325]})

【题目描述】

已知某长为 (n (nleqslant 10^5)) 的字符串以每个位置/空隙为中心的最长回文串长度，现需构造一个字典序最小的合法字符串。

【分析】

详情见另一篇博客：【题解】密码 ( ext{[SCOI2013] [P3279]})

【Code】

不知道这儿能放啥，干脆买个萌吧(⊙ω⊙)

【Day2 T2】数数

传送门：数数 ( ext{[P3281]}) ( ext{[Bzoj3326]})

【题目描述】

略。

【分析】

毒瘤数位 (dp)，题解始终没看懂，先咕着。

【Code】

不知道这儿能放啥，干脆买个萌吧(⊙ω⊙)

【Day2 T3】泡泡鱼

传送门：泡泡鱼 ( ext{[P3282]}) ( ext{[Bzoj3327]})

【题目描述】

略

【分析】

毒瘤 (OI) 又在出毒瘤计算几何了，题倒是不难，但比较麻烦，不想写。

【Code】

不知道这儿能放啥，干脆买个萌吧(⊙ω⊙)
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Xing-Ling/p/12711497.html