头像

溪染




离线:1天前



溪染
1天前

暴力上线段树即可,比二分+差分思路简单多了
线段树维护区间最小值然后和需要借教室的多少比较
再区间减即可

/*
线段树维护最小值 
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define N 1000006
using namespace std;
int n,m;
int R[N];
int MIN[N*8];
int lazy[N*8];
void down(int x){
    if(lazy[x]){
        MIN[x*2]-=lazy[x];
        MIN[x*2+1]-=lazy[x];
        lazy[x*2]+=lazy[x];
        lazy[x*2+1]+=lazy[x];
        lazy[x]=0;
    }
}
void buit(int bh,int l,int r)
{
    if(l==r){
        MIN[bh]=R[r];
        return;
    }
    int mid=(l+r)/2;
    buit(bh*2,l,mid);
    buit(bh*2+1,mid+1,r);
    MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int ask(int bh,int l,int r,int cl,int cr)
{
    down(bh);
    if(cl<=l&&r<=cr){
        return MIN[bh];
    }
    int mid=(l+r)/2,ans=INT_MAX;
    if(cl<=mid) ans=min(ans,ask(bh*2,l,mid,cl,cr));
    if(cr>mid) ans=min(ans,ask(bh*2+1,mid+1,r,cl,cr));
    MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
    return ans;
}
void xg(int bh,int l,int r,int cl,int cr,int k)
{
    down(bh);
    if(cl<=l&&r<=cr){
        MIN[bh]-=k;
        lazy[bh]+=k;
        return;
    }
    int mid=(l+r)/2;
    if(cl<=mid) xg(bh*2,l,mid,cl,cr,k);
    if(cr>mid) xg(bh*2+1,mid+1,r,cl,cr,k);
    MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&R[i]);
    buit(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int d,s,t;
        scanf("%d%d%d",&d,&s,&t);
        int M=ask(1,1,n,s,t);
        if(M>=d){
            xg(1,1,n,s,t,d);
        }else{
            puts("-1");
            cout<<i<<"\n";
            return 0;
        }
    }
    puts("0");
    return 0;
}



溪染
5天前

费用流问题

#include<bits/stdc++.h>
#define N 205
using namespace std;
int inf=10000000;
int m,n;
int a[N],b[N];
int c[N][N];
int S,T;
struct oppo{
    int to,s,nex,k;
}rod[N*N*3];
int head[N],tot=1;
void add(int from,int to,int s,int k)
{
    rod[++tot].to=to;
    rod[tot].s=s;
    rod[tot].k=k;
    rod[tot].nex=head[from];
    head[from]=tot;
}
void buit_rod(int t)
{
    for(int i=1;i<=m;i++){
        add(S,i,0,a[i]);
        add(i,S,0,0);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
            add(i,j+m,c[i][j]*t,inf);
            add(j+m,i,-c[i][j]*t,0);
        }
    for(int i=1;i<=n;i++){
        add(i+m,T,0,b[i]);
        add(T,i+m,0,0);
    }
}
int dis[N];
bool flag[N];
int pre[N];
queue<int> v;
bool bfs()
{
    memset(dis,0x3f,sizeof(dis));
    memset(flag,0,sizeof(flag));
    memset(pre,-1,sizeof(pre));
    dis[S]=0;
    v.push(S);
    while(v.size()){
        int lxl=v.front();
        v.pop();flag[lxl]=0;
        for(int i=head[lxl];i;i=rod[i].nex){
            int to=rod[i].to;
            if(rod[i].k&&dis[to]>dis[lxl]+rod[i].s){
                dis[to]=dis[lxl]+rod[i].s;
                pre[to]=lxl;
                if(!flag[to]){
                    flag[to]=1;
                    v.push(to);
                }
            }
        }
    }
    return pre[T]!=-1;
}
int ans=0;
int dinic(int x,int low)
{
    if(x==T) return low;
    int all=0;
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(rod[i].k&&pre[to]==x){
            int t=dinic(to,min(low-all,rod[i].k));
            if(!t) pre[to]=-1;
            rod[i].k-=t;
            rod[i^1].k+=t;
            all+=t;
            ans+=t*rod[i].s;
        }
    }
    return all;
}
void work()
{
    while(bfs())
        while(dinic(S,inf));
}
int main()
{
    cin>>m>>n;
    T=m+n+1;
    for(int i=1;i<=m;i++)   
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&c[i][j]);
    buit_rod(1);
    work();
    cout<<ans<<"\n";
    ans=0;
    tot=1;
    memset(head,0,sizeof(head));
    buit_rod(-1);
    work();
    cout<<-ans<<"\n";
    return 0;
}



溪染
5天前
#include<bits/stdc++.h>
#define N 300000
using namespace std;
int n,m;
struct oppo{
    int to,nex;
}rod[N*2];
int head[N],tot;
void add(int from,int to)
{
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    head[from]=tot;
}
int w[N];
int S[N],T[N],LCA[N],tim[N];
int fa[N][22];
int dep[N];
void ddd(int x,int father)
{
    fa[x][0]=father;
    dep[x]=dep[father]+1;
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(to==father) continue;
        ddd(to,x);
    }
}
int ask(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];
}
int ans[N];
vector<int> s[N];
vector<int> t[N];
vector<int> lca[N];
int fs[N*2];
int ft[N*2];
int cale(int x)
{
    int ans=fs[w[x]+dep[x]]+ft[w[x]-dep[x]+N];
    return ans;
}
void dfs(int x,int father)
{
    int k=cale(x);
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(to==father) continue;
        dfs(to,x);
    }
    for(int i=0;i<s[x].size();i++){
        fs[dep[x]]++;
    }
    for(int i=0;i<t[x].size();i++){
        int k=t[x][i];
        ft[tim[k]-dep[x]+N]++;
    }
    ans[x]=cale(x)-k;
    for(int i=0;i<lca[x].size();i++){
        int k=lca[x][i];
        if(w[x]+dep[x]==dep[S[k]])
            ans[x]--;
        fs[dep[S[k]]]--;
        ft[tim[k]-dep[T[k]]+N]--;
    }
}
void work()
{
    dep[0]=-1;
    ddd(1,0);
    for(int k=1;k<=20;k++)
        for(int i=1;i<=n;i++)
            fa[i][k]=fa[ fa[i][k-1] ][k-1];
    for(int i=1;i<=m;i++){
        LCA[i]=ask(S[i],T[i]);
        tim[i]=dep[S[i]]+dep[T[i]]-2*dep[LCA[i]];
    }
    for(int i=1;i<=n;i++){
        s[S[i]].push_back(i);
        t[T[i]].push_back(i);
        lca[LCA[i]].push_back(i);
    }
    dfs(1,0);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&S[i],&T[i]);
    work();
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}



溪染
5天前

此题有o(n)解法
此代码为o($n log_n$)

线段树优化dp转移方程

#include<bits/stdc++.h>
#define N 1000006
using namespace std;
int n,m=1000006;
class oppo{
    public:
        int MAX[N*4];
        void xg(int bh,int l,int r,int k,int to)
        {
            if(l==r){
                MAX[bh]=max(MAX[bh],to);
                return;
            }
            int mid=(l+r)/2;
            if(k<=mid) xg(bh*2,l,mid,k,to);
            else xg(bh*2+1,mid+1,r,k,to);
            MAX[bh]=max(MAX[bh*2],MAX[bh*2+1]);
        }
        int ask(int bh,int l,int r,int cl,int cr){
            if(cl<=l&&r<=cr)
                return MAX[bh];
            int ans=0;
            int mid=(l+r)/2;
            if(cl<=mid) ans=max(ans,ask(bh*2,l,mid,cl,cr));
            if(cr>mid) ans=max(ans,ask(bh*2+1,mid+1,r,cl,cr));
            return ans;
        }
}xd[2];//0 奇数 1 偶数 
int h[N],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
        h[i]++;
    }
    for(int i=1;i<=n;i++){//010
        int k;
        // 0
        k=xd[1].ask(1,0,m,h[i]+1,m);
        xd[0].xg(1,0,m,h[i],k+1);
        ans=max(ans,k+1);
        // 1
        k=xd[0].ask(1,0,m,0,h[i]-1);
        if(k) xd[1].xg(1,0,m,h[i],k+1);
        ans=max(ans,k+1);
    }
    memset(xd,0,sizeof(xd));
    for(int i=1;i<=n;i++){//010
        int k;
        // 0
        k=xd[1].ask(1,0,m,0,h[i]-1);
        xd[0].xg(1,0,m,h[i],k+1);
        ans=max(ans,k+1);
        // 1
        k=xd[0].ask(1,0,m,h[i]+1,m);
        if(k) xd[1].xg(1,0,m,h[i],k+1);
        ans=max(ans,k+1);
    }
    cout<<ans<<"\n";
    return 0;
}


新鲜事 原文

溪染
6天前
好不容易下完了某日本动漫电影,发现没有字幕,好不容易在网上搞到了字幕,结果是英语字母,难受QWQ


新鲜事 原文

溪染
9天前
在机房空闲电脑上搭建了FTP服务器(直接多出800G的空间存东西,哈哈哈)
图片



溪染
9天前

推建使用FileZilla

以下图片以及教程均来自这里

1.png

2.png

3.png




溪染
10天前

如下,此代码应该输出什么鸭?

j = 0
result = 0
p = 8497980875583539713991243773941802042180496489377326522174599746685528850719812035800799014030522052269804143947777659192760008656733593814889715667890907
a = 11451419198101926081719260817111

while j < p:
    if pow(j, 2, p) == a:
        result += j
        break
    j += 1
print("flag is scuctf{%d}"%(result%1145141145141145141145141919810))



溪染
11天前

题目描述

B 国境内有 nnn 所学校,每所学校都有一个 1∼n 的编号。

由于管理过于宽松,可能存在两个学校同时用一个编号的情况,当然也存在一个编号没有学校用的情况。

现在国王决定重新给所有学校编号,使得任意两个学校的编号不同。

当然,改变编号是一个很繁重的工作,学校不希望自己的编号改变太多。每个学校都有一个可以接受的新编号区间 [a,b],以及改变编号的单位成本 kkk。如果一个学校的旧编号为 mmm,新编号为 m′,那么给这个学校改变编号的成本即为 k×∣m′−m∣

现在你需要告诉国王完成编号更新的最低成本是多少,或者说明这是不可能的。
输入格式

第一行一个整数 n。

接下来 nnn 行,每行四个整数 $m_i,a_i,b_i,k_i$,代表 iii 号学校的旧编号为 $m_i$,新编号的范围为 $[a_i,b_i]$,改变编号的单位成本为 $k_i$。
输出格式

如果不存在一种方案,使得任意两个学校的编号不同,输出 NIE。

否则输出一个整数,代表最小成本。

输入输出样例

输入 #1

5
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1

输出 #1

9

说明/提示

【数据范围】
对于 100%100\%100% 的数据,1≤ai≤mi≤bi≤n≤2001

分析

题目中需要学校和编号匹配,可以想到二分图匹配
二分图匹配可以用匈牙利算法或网络流实现
但是此题匹配时有权值的计算,匈牙利算法无法实现
考虑最小费用流
建立超级源点连接各个学校
建立超级汇点连接各个编号
学校和编号的连接由输入自行处理
输出时判断一下是否每个学校都用一个编号即可

参考代码

#include<bits/stdc++.h>
#define N 405
using namespace std;
const int inf=0x3f3f3f3f;
struct oppo{
    int to,nex,s,k;
}rod[N*N];
int head[N],tot=1;
void add(int from,int to,int s,int k)
{
    rod[++tot].to=to;
    rod[tot].s=s;
    rod[tot].k=k;
    rod[tot].nex=head[from];
    head[from]=tot;
}
int n,en;
int m[N],a[N],b[N],k[N];

int dis[N];
bool flag[N];
queue< int > v;
bool bfs()
{
    memset(dis,0x3f,sizeof(dis));
    flag[0]=1;
    v.push(0);
    dis[0]=0;
    while(v.size()){
        int lxl=v.front();
        v.pop();flag[lxl]=0;
        for(int i=head[lxl];i;i=rod[i].nex){
            int to=rod[i].to;
            if(rod[i].k&&dis[to]>dis[lxl]+rod[i].s){
                dis[to]=dis[lxl]+rod[i].s;
                if(!flag[to]){
                    flag[to]=1;
                    v.push(to);
                }
            }
        }
    }
    return dis[en]!=inf;
}
int ans;
bool vis[N];
int dinic(int x,int low)
{
    if(x==en) return low;
    vis[x]=1;
    int all=0;
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(!vis[to]&&rod[i].k&&dis[to]==dis[x]+rod[i].s){
            int t=dinic(to,min(low-all,rod[i].k));
            if(!t) dis[to]=-1;
            ans+=rod[i].s*t;
            all+=t;
            rod[i].k-=t;
            rod[i^1].k+=t;
        }
    }
    vis[x]=0;
    return all;
}
void work()
{
    int all=0,kkk;
    while(bfs())
        while(kkk=dinic(0,INT_MAX))
            all+=kkk;
    if(all==n) cout<<ans<<"\n";
    else puts("NIE");
}
int main()
{
    cin>>n;
    en=2*n+1;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&m[i],&a[i],&b[i],&k[i]);
    }
    for(int i=1;i<=n;i++){
        add(0,i,0,1);
        add(i,0,0,0);
    }
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=b[i];j++){
            add(i,j+n,k[i]*abs(j-m[i]),1);
            add(j+n,i,-abs(j-m[i])*k[i],0);
        }
    }
    for(int i=1;i<=n;i++){
        add(i+n,en,0,1);
        add(en,i+n,0,0);
    }
    work();
    return 0;
}



溪染
13天前
#include<bits/stdc++.h>
#define N 2005
using namespace std;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    cin>>n>>m;
    scanf("%s",a+1);
    scanf("%s",b+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m]<<"\n";
    return 0;
}