#4

无心随笔 / 2023-08-25 / 原文

[COCI2012-2013#2] INFORMACIJE

题面

因为是排列,所以一个位置和一个值是一一对应的,容易想到匹配上,我们只需要考虑如何建边即可。先每个位置向每个值连边,然后再删掉不合法的边。注意题意,是最大值或最小值为 \(x\),所以权值 \(x\) 的位置必然在 \([l,r]\) 内,删掉 \([1,l-1]\)\([r+1,n]\)\(x\) 连的边。对于 \([l,r]\) 内的点,如果限制最大值,则 \([l,r]\) 内的位置的权值不能大于 \(x\),删掉 \([l,r]\)\([x+1,n]\) 连的边,如果限制最小值,则删去 \([l,r]\)\([1,x-1]\) 连的边。最后跑匈牙利即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=410;
int n,m,head[N],ad[N][N],tot=1,couple[N],vis[N];
struct edge{
    int v,nxt;
}e[N*N];
void add(int u,int v){
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int find(int u){
    if(vis[u]){
        return 0;
    }
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(!couple[v]||find(couple[v])){
            couple[v]=u;
            couple[u]=v;
            return 1;
        }
    }
    return 0;
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ad[i][j]=1;
        }
    }
    for(int i=1;i<=m;i++){
        int opt,l,r,val;
        read(opt),read(l),read(r),read(val);
        if(opt==1){
            for(int j=l;j<=r;j++){
                for(int k=val+1;k<=n;k++){
                    ad[j][k]=0;
                }
            }
            for(int j=1;j<l;j++){
                ad[j][min(val,n+1)]=0;
            }
            for(int j=r+1;j<=n;j++){
                ad[j][min(val,n+1)]=0;
            }
        }
        else{
            for(int j=l;j<=r;j++){
                for(int k=1;k<min(n+1,val);k++){
                    ad[j][k]=0;
                }
            }
            for(int j=1;j<l;j++){
                ad[j][min(val,n+1)]=0;
            }
            for(int j=r+1;j<=n;j++){
                ad[j][min(val,n+1)]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(ad[i][j]){
                add(i,j+n);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            vis[j]=0;
        }
        if(!find(i)){
            puts("-1");
            return;
        }
    }
    for(int i=1;i<=n;i++){
        write_space(couple[i]-n);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

[NOI2015] 品酒大会

题面

SA经典题,将LCP大于等于 \(r\) 的和转化为倒序处理,每次只处理LCP等于 \(r\) 的情况,再做一个后缀和。根据性质可以知道 \(LCP(i,j)=\min\limits_{p=\min(rk_i,rk_j)}^{\max(rk_i,rk_j)}ht_p\),维护若干个集合,每个集合中的任意两个后缀的LCP都大于等于当前处理的 \(ht_i\)。新添的 \(ht_i\) 会将 \(sa_i\)\(sa_{i-1}\) 所在的集合合并,用并查集维护,每个集合记录一下大小,最大值,最小值即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=3e5+10,inf=1e18;
char s[N];
int n,sa[N],ht[N],rk[N],ork[N<<2],buc[N],id[N],pid[N],a[N];
bool cmp(int x,int y,int w){
    return ork[x]==ork[y]&&ork[x+w]==ork[y+w];
}
void build(){
    int m=(1<<7),p=0;
    for(int i=1;i<=n;i++){
        rk[i]=s[i];
        buc[rk[i]]++;
    }
    for(int i=1;i<=m;i++){
        buc[i]=buc[i-1]+buc[i];
    }
    for(int i=n;i;i--){
        sa[buc[rk[i]]--]=i;
    }
    for(int w=1;;w<<=1,m=p,p=0){
        for(int i=n;i>n-w;i--){
            id[++p]=i;
        }
        for(int i=1;i<=n;i++){
            if(sa[i]>w){
                id[++p]=sa[i]-w;
            }
        }
        for(int i=0;i<=m;i++){
            buc[i]=0;
        }
        for(int i=1;i<=n;i++){
            pid[i]=rk[id[i]];
            buc[pid[i]]++;
        }
        for(int i=1;i<=m;i++){
            buc[i]=buc[i-1]+buc[i];
        }
        for(int i=n;i;i--){
            sa[buc[pid[i]]--]=id[i];
        }
        for(int i=0;i<=n;i++){
            ork[i]=rk[i];
        }
        p=0;
        for(int i=1;i<=n;i++){
            rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
        }
        if(p==n){
            break;
        }
    }
    for(int i=1,k=0;i<=n;i++){
        if(k){
            k--;
        }
        while(s[i+k]==s[sa[rk[i]-1]+k]){
            k++;
        }
        ht[rk[i]]=k;
    }
}
int sum,mx=-inf,ans_sum[N],ans_mx[N];
vector<int>q[N];
namespace dsu{
    int fa[N],siz[N],mx[N],mn[N];
    void init(){
        for(int i=1;i<=n;i++){
            fa[i]=i;
            siz[i]=1;
            mx[i]=mn[i]=a[sa[i]];
            q[ht[i]].pb(i);
        }
    }
    int getfa(int u){
        if(fa[u]!=u){
            fa[u]=getfa(fa[u]);
        }
        return fa[u];
    }
    void merge(int u,int v){
        u=getfa(u),v=getfa(v);
        ::sum+=siz[u]*siz[v];
        ::mx=max(::mx,max(mx[u]*mx[v],mn[u]*mn[v]));
        fa[v]=u;
        siz[u]+=siz[v];
        mx[u]=max(mx[u],mx[v]);
        mn[u]=min(mn[u],mn[v]);
    }
}
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        s[i]=getchar();
        while(s[i]<'a'||s[i]>'z'){
            s[i]=getchar();
        }
    }
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    build();
    dsu::init();
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<q[i].size();j++){
            dsu::merge(q[i][j],q[i][j]-1);
            ans_sum[i]=sum;
            ans_mx[i]=mx;
        }
    }
    for(int i=0;i<n;i++){
        write_space(ans_sum[i]);
        write_endl(ans_mx[i]);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

[ARC140D] One to One

题面

\(n\) 个点 \(n\) 条边,可以得到的是这必然是一个基环树森林,为了方便,此处将环也视作基环树。

先将确定的边连上,根据上述结论,如果一个连通块是基环树,无论剩下的边怎么连,这都是一个独立的连通块。贡献为 \(n^{cnt}\),其中 \(cnt\) 表示还没连的边的数量。

剩下的就是树的部分,以这棵树中的 \(-1\) 节点为根。如果它连到了一个基环树上,那么肯定没有贡献,所以不考虑,只考虑树与树之间的相连带了的贡献。因为最后一定是基环树,所以我们的问题就是基环树的环是怎么组成。假定形成的环是由 \(x\) 棵树组合而成,设 \(f_{i,j}\) 表示仅使用树 \([1,j]\) 形成大小为 \(i\) 的环的方案数,\(siz_j\) 表示树 \(j\) 的大小。可以得到转移 \(f_{i,j}=f_{i,j-1}+f_{i-1,j-1}*\max(j-1,1)*siz_j\)

容易理解,若 \(i\not= 1\),任选原来的一种由 \(i-1\) 个树构成的环,选择断掉原来一个树连到另一个树上的边,并自己连到这条边原来的终点共有 \(j-1\) 种方案,如果 \(i=1\) 则是往自己连边,共有 \(1\) 种方。,此时原来的断掉的边还没有终点,可以将其连到当前这棵树上的任意点,共有 \(siz_j\) 种方案。无论剩下的树怎么连,这颗由 \(i\) 棵树组成的基环树都会产生贡献,贡献为 \(n^{cnt-i}\)

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2010,mod=998244353;
int n,a[N],siz[N],val[N],cnt,vis[N],fac[N],Pow[N],f[N],ans;
vector<int>e[N];
void dfs(int u){
    vis[u]=siz[u]=1;
    for(auto v:e[u]){
        if(!vis[v]){
            dfs(v);
            siz[u]+=siz[v];
        }
    }
}
void solve(){
    read(n);
    fac[0]=Pow[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=1ll*fac[i-1]*i%mod;
        Pow[i]=1ll*Pow[i-1]*n%mod;
    }
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(~a[i]){
            e[i].pb(a[i]);
            e[a[i]].pb(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(!(~a[i])){
            dfs(i);
            val[++cnt]=siz[i];
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
            ans=(ans+Pow[cnt])%mod;
        }
    }
    f[0]=1;
    for(int i=1;i<=cnt;i++){
        for(int j=i;j;j--){
            f[j]=(f[j]+1ll*f[j-1]*val[i]%mod*max(j-1,1)%mod)%mod;
        }
    }
    for(int i=1;i<=cnt;i++){
        ans=(ans+1ll*f[i]*Pow[cnt-i]%mod)%mod;
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Buying gifts

题面

\(a\) 为关键字排序,枚举钦定哪个为 \(a\) 的最大值,那么 \(a\) 中大于这个的部分必选 \(b\)。维护这些必选的数的最大值。

若大于钦定的 \(a\) 的最大值,那么此时差的最小值就为两个数之差;若小于,维护前面可选的数中大于钦定的 \(a\) 的最小值和小于钦定的 \(a\) 的最大值。用 multiset 维护这三个信息即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=5e5+10,inf=1e9;
int n;
pii a[N<<1];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i].first),read(a[i].second);
    }
    sort(a+1,a+n+1);
    multiset<int>s_bac,s_front;
    for(int i=1;i<=n;i++){
        s_bac.insert(a[i].second);
    }
    int less=-inf,ans=inf;
    for(int i=1;i<=n;i++){
        s_bac.erase(s_bac.find(a[i].second));
        while(s_front.size()&&*s_front.begin()<a[i].first){
            less=max(less,*s_front.begin());
            s_front.erase(s_front.begin());
        }
        int bac_mx=-inf;
        if(s_bac.size()){
            auto it=s_bac.end();
            it--;
            bac_mx=*it;
        }
        if(bac_mx>=a[i].first){
            ans=min(ans,bac_mx-a[i].first);
        }
        else{
            int mn=a[i].first-less;
            mn=min(a[i].first-bac_mx,mn);
            if(s_front.size()){
                mn=min(mn,*s_front.begin()-a[i].first);
            }
            ans=min(ans,mn);
        }
        s_front.insert(a[i].second);
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

Tweetuzki 爱序列

题面

如果数 \(x,y\) 满足 \(x\) 可以通过一次两操作之一变为 \(y\),从 \(x\)\(y\) 连边,得到的图一定是个拓扑图。

证明:设 \(\div 3\) 操作进行了 \(a\) 次,\(\times 2\) 操作进行了 \(b\) 次,\(3^{-a}\times 2^b=1\)\(2^b=3^a\) ,因为 \(a,b>0\),所以无正整数解。因此生成的图一定为拓扑图,直接dp即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e5+10;
int f[N],a[N],nxt[N],val[N],n,m,ans_num,ans_pos;
vector<int>e[N];
int find(int x){
    int l=1,r=m;
    while(l<=r){
        int mid=(l+r)>>1;
        if(val[mid]>x){
            r=mid-1;
        }
        else if(val[mid]<x){
            l=mid+1;
        }
        else{
            return mid;
        }
    }
    return 0;
}
int dfs(int u){
    if(f[u]){
        return f[u];
    }
    f[u]=1;
    for(auto v:e[u]){
        if(dfs(v)+1>f[u]){
            f[u]=f[v]+1;
            nxt[u]=v;
        }
    }
    return f[u];
}
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        val[i]=a[i];
    }
    sort(val+1,val+n+1);
    m=unique(val+1,val+n+1)-val-1;
    for(int i=1;i<=m;i++){
        int x=find(val[i]*2),y=0;
        if(val[i]%3==0){
            y=find(val[i]/3);
        }
        if(x){
            e[i].pb(x);
        }
        if(y){
            e[i].pb(y);
        }
    }
    for(int i=1;i<=m;i++){
        dfs(i);
        if(f[i]>ans_num){
            ans_num=f[i];
            ans_pos=i;
        }
    }
    write_endl(ans_num);
    while(ans_pos){
        write_space(val[ans_pos]);
        ans_pos=nxt[ans_pos];
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Ryoku 与最初之人笔记

题面

有趣题,直接模异或肯定没什么想法,考虑拆开。一般拆异或有两种拆法,拆位或者变为或减与,显然这里后者是可做的。

\(a\)\(b\) 中为 \(1\) 的位置可以变成 \(a\)\(b\) 中为 \(1\) 的位置并只有 \(a\)\(1\) 的位置并只有 \(b\)\(1\) 的位置。令三个部分的权值分别为 \(x,y,z\)。式子转化为 \(x+y\equiv x+z\pmod {y+z}\),再化一步得 \(z-y\equiv 0 \pmod {y+z}\)\(z-y=k(z+y)\)。因为 \(k,y,z\ge 1\),所以 \(y=0\),也就是 $a& b=a。

求这样的数对的对数,直接枚举 \(b\)\(1\) 的个数,求 \(1\) 的个数为 \(s\) 时的数的个数,此时 \(a\) 的选择方案数有 \(2^s-1\) 种,求个数时用数位dp求解即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=100,mod=1e9+7;
int n,num[N],f[N][N][10],cnt,ans;
int dfs(int now,int tot,int flag){
    if(tot<0){
        return 0;
    }
    if(!now){
        if(!tot){
            return 1;
        }
        return 0;
    }
    if(f[now][tot][flag]!=-1){
        return f[now][tot][flag];
    }
    f[now][tot][flag]=0;
    for(int i=0;i<=(flag?num[now]:1);i++){
        f[now][tot][flag]=(f[now][tot][flag]+dfs(now-1,tot-i,flag&&(i==num[now])))%mod;
    }
    return f[now][tot][flag];
}
int calc(int k){
    memset(f,-1,sizeof(f));
    int res=dfs(cnt,k,1);
    return res;
}
void solve(){
    read(n);
    while(n){
        num[++cnt]=n%2;
        n/=2;
    }
    for(int i=1;i<=cnt;i++){
        ans=(ans+((1ll<<i)%mod-1+mod)%mod*calc(i)%mod)%mod;
    }
    // calc(1);
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}