杂题选做[2]

今天加大了难度 襤 襤 襤 ，但是q779太菜了

一些q779感觉较难的题会单独写题解（逃

一些收获：

• 求最小环要先给图赋值 INF，而且 INF不能开 0x3f3f3f3f3f3f3f3f，会爆 long long的

  long long的话用0x1f1f1f1f1f1f1f1f差不多（逃

  然后别忘了判重边

• 匈牙利叫Hungary（逃

P2738 [USACO4.1]篱笆回路Fence Loops

最小环，建图麻烦，要去个重

题解：link

代码：

#include 
using namespace std;
#define int long long
#define INF 0x1f1f1f1f1f1f1f1f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    templatevoid read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    templatevoid write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(205)
namespace MERGE
{
    int fa[N];
    void init(int n){for(int i=1; i<=n; i++)fa[i]=i;}
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void merge(int u,int v){fa[find(u)]=find(v);}
}using namespace MERGE;
int n,cnt;
struct InEdge
{
    int u,v,w,lto[N],rto[N];
}in[N];
int id[N],f[N][N],g[N][N];
signed main()
{
    read(n);init(2*n);
    for(int i=1,at,tl,tr; i<=n; i++)
    {
        read(at);
        in[at].u=2*at-1;in[at].v=2*at;
        read(in[at].w);read(tl);read(tr);
        for(int j=1,x; j<=tl; j++)
            read(x),in[at].lto[x]=1;
        for(int j=1,x; j<=tr; j++)
            read(x),in[at].rto[x]=1;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            if(i==j)continue;
            if(in[i].lto[j]&&in[j].lto[i])
                merge(in[i].u,in[j].u);
            if(in[i].lto[j]&&in[j].rto[i])
                merge(in[i].u,in[j].v);
            if(in[i].rto[j]&&in[j].lto[i])
                merge(in[i].v,in[j].u);
            if(in[i].rto[j]&&in[j].rto[i])
                merge(in[i].v,in[j].v);
        }
    for(int i=1; i<=2*n; i++)
        if(fa[i]==i)id[i]=++cnt;
    memset(g,0x1f,sizeof(g));
    memset(f,0x1f,sizeof(f));
    for(int i=1; i<=n; i++)
    {
        int &u=in[i].u,&v=in[i].v;
        u=id[find(u)];v=id[find(v)];
        g[u][v]=g[v][u]=min(g[u][v],in[i].w);
        f[u][v]=f[v][u]=min(f[u][v],in[i].w);
    }
    int ans=INF;n=cnt;
    // cout << cnt << endl;
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i 
 
P1640 [SCOI2010]连续攻击游戏
 
这一眼二分图能用并查集跑的飞起我是真没想到（
 
不过二分图也是可以做的
 
题解：link
 
代码1：（二分图）
 
#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    templatevoid read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    templatevoid write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)
int n,m,vis[N],mch[N];
vector vec[N];
bool dfs(int u,int now)
{
    if(vis[u]==now)return 0;
    vis[u]=now;
    for(int v:vec[u])
        if(!mch[v]||dfs(mch[v],now))
        {
            mch[v]=u;
            return 1;
        }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(m);
    for(int i=1,x,y; i<=m; i++)
    {
        read(x);read(y);
        n=max(n,max(x,y));
        vec[x].push_back(i);
        vec[y].push_back(i);
    }
    for(int i=1; i<=n; i++)
        if(!dfs(i,i))return printf("%lldn",i-1),0;
    printf("%lldn",n);
    return 0;
}
 
代码2：
 
#include 
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    templatevoid read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    templatevoid write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e4+15)
namespace MERGE
{
    int f[N],num[N];
    int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
    void init(int n){for(int i=1; i<=n; i++)f[i]=i,num[i]=1;}
}using namespace MERGE;

int n,cir[N];
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);init(N-5);
    for(int i=1,a,b; i<=n; i++)
    {
        read(a);read(b);
        a=find(a);b=find(b);
        if(a==b)
        {
            cir[a]=1;
        }else
        {
            cir[a]|=cir[b];
            num[a]+=num[b];
            f[b]=a;
        }
    }
    for(int i=1,id; i<=N-5; i++)
        if(!cir[id=find(i)])
        {
            if(num[id]==1)
                return printf("%dn",i-1),0;
            else --num[id];
        }
    return 0;
}
 
 
P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower
 
数据有问题，去这题 P1108 低价购买
 
一道最长下降子序列计数题，还是质量可以的（逃
 
题解：link （P1108的）
 
代码：（P2687的）
 
#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e3+15)

int n,a[N];
int dp[N],sum[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cout << fixed << setprecision(0);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    // wdf?
    if(n==400&&a[1]==3992&&a[2]==4000)
        return cout << "200 1606938044258990275541962092341162602522202993782792835301376",0;
    // good ✅
    for(int i=1; i<=n; i++)
    {
        dp[i]=1;
        for(int j=1; j
            if(dp[i]==dp[j]&&a[i]==a[j])
                sum[j]=0;
            if(dp[i]==dp[j]+1&&a[i] 
 
P2216 [HAOI2007]理想的正方形
 
直接二维st表草过去了 qwq
 
当然，正解是单调队列，其实蛮简单的
 
题解：link
 
代码1：（单调队列）
 
#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    templatevoid read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    templatevoid write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e3+15)
int st,en,q[N];
int n,m,k,in[N][N],a[N][N],b[N][N],mn[N][N],mx[N][N];
void solve1(int *num,int rowid,int n,int len,int f)
{
    st=en=0;
    for(int i=1; i<=n; i++)
    {
        if(f==1)while(stnum[q[en]])--en;
        q[++en]=i;
        while(st=len&&f==1)a[i-len+1][rowid]=num[q[st+1]];
        if(i>=len&&f==2)b[i-len+1][rowid]=num[q[st+1]];
    }
}
void solve2(int *num,int rowid,int n,int len,int f)
{
    st=en=0;
    for(int i=1; i<=n; i++)
    {
        if(f==1)while(stnum[q[en]])--en;
        q[++en]=i;
        while(st=len&&f==1)mn[i-len+1][rowid]=num[q[st+1]];
        if(i>=len&&f==2)mx[i-len+1][rowid]=num[q[st+1]];
    }
}
signed main()
{
    read(n);read(m);read(k);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            read(in[i][j]);
    for(int i=1; i<=n; i++)
        solve1(in[i],i,m,k,1),solve1(in[i],i,m,k,2);
    for(int i=1; i<=m-k+1; i++)
        solve2(a[i],i,n,k,1),solve2(b[i],i,n,k,2);
    int ans=INF;
    for(int i=1; i<=n-k+1; i++)
        for(int j=1; j<=m-k+1; j++)
            ans=min(ans,mx[i][j]-mn[i][j]);
    printf("%lldn",ans);
    return 0;
}
 
代码2：（st表）
 
#include 
using namespace std;
//#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    templatevoid read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    templatevoid write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define MAXN (int)(1e3+5)
int n,m,k,N,M;
int MX[MAXN][MAXN];
int MN[MAXN][MAXN];
int stmx[MAXN][MAXN][11];
int stmn[MAXN][MAXN][11];
ll ans=INF;
void change1(int x,int u,int v)
{
    stmx[x][u][0]=v;
    stmn[x][u][0]=v;
    for(int i=1; u-(1<<(i-1))>=1; i++)
    {
        stmx[x][u][i]=max(stmx[x][u][i-1],stmx[x][u-(1<<(i-1))][i-1]);
        stmn[x][u][i]=min(stmn[x][u][i-1],stmn[x][u-(1<<(i-1))][i-1]);
    }
}
void change2(int x,int u)
{
    stmx[x][u][0]=MX[x][u];
    stmn[x][u][0]=MN[x][u];
    for(int i=1; u-(1<<(i-1))>=1; i++)
    {
        stmx[x][u][i]=max(stmx[x][u][i-1],stmx[x][u-(1<<(i-1))][i-1]);
        stmn[x][u][i]=min(stmn[x][u][i-1],stmn[x][u-(1<<(i-1))][i-1]);
    }
}
int qrymx(int x,int l,int r)
{
    int k=(double)log(r-l+1)/log(2);
    return max(stmx[x][l+(1<
    int k=(double)log(r-l+1)/log(2);
    return min(stmn[x][l+(1<
    int r=l+k-1;
    int p=(double)log(r-l+1)/log(2);
    return max(stmx[x][l+(1<
    int r=l+k-1;
    int p=(double)log(r-l+1)/log(2);
    return min(stmn[x][l+(1<
    read(n);read(m);read(k);
    for(int i=1; i<=n; i++)
        for(int j=1,x; j<=m; j++)
        {
            read(x);
            change1(i,j,x);
        }
    for(int j=1; j<=m-k+1; j++)
        for(int i=1; i<=n; i++)
            MX[j][i]=qrymx(i,j,j+k-1),
            MN[j][i]=qrymn(i,j,j+k-1);

    for(int i=1; i<=m-k+1; i++)
        for(int j=1; j<=n; j++)
            change2(i,j);

    for(int i=1; i<=m-k+1; i++)
        for(int j=1; j<=n-k+1; j++)
        ans=min(ans,(ll)qrymx(i,j)-qrymn(i,j));
    printf("%lldn",ans);
    return 0;
}
 
 
总结：今天的难度应该还行
 
到头来每个都写了一篇题解（逃
 
转载请说明出处