头像

mzhccc




离线:12小时前


新鲜事 原文

mzhccc
3个月前
NOIP rp++



mzhccc
3个月前

啊这,这个题我在find函数中返回的flow而不是maxflow结果也AC了!!!!!!




mzhccc
4个月前

如题。。。
贪心的话,貌似数组不满足严格单调递增了。。




mzhccc
4个月前

STL setinsertfind复杂度都是$O(\log n)$的
sort的复杂度是$O(n\log n)$,unique的复杂度是$O(O^2)$
手写离散化的复杂度:初始化$O(n^2)$且为离线 查找$O(\log n)$
STL set的复杂度:初始化$O(n\log n)$可在线 查找$O(\log n)$
且以上两个查找速度上是一样的,都是封装过的二分查找。
那么STL set是否更优呢?



活动打卡代码 AcWing 237. 程序自动分析

mzhccc
6个月前
#include<bits/stdc++.h>
#define For(i,l,r) for(int i = l;i<=r;i++)
#define N 2000010
#define PII pair<int,int>
#define PIII pair<bool,PII>
#define x first
#define y second
using namespace std;
int fa[N];
int dis[N],cnt;
int g[N];
int disc(){
    sort(dis+1,dis+1+cnt);
    return unique(dis+1,dis+1+cnt)-1-dis;
}
int find_disc(int x){
    return lower_bound(dis+1,dis+1+cnt,x)-dis;
}
int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}

int main(){
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        priority_queue<PIII>q;
        cnt=0;
        while(n--){
            int a,b,c;cin>>a>>b>>c;
            dis[++cnt]=a;dis[++cnt]=b;
            q.push({c,{a,b}});
        }
        cnt=disc();
        For(i,1,cnt)fa[i]=i;
        bool flag=1;
        while(q.size()){
            PIII t = q.top();q.pop();
            if(t.x)fa[find(find_disc(t.y.x))]=fa[find(find_disc(t.y.y))];
            else if(fa[find(find_disc(t.y.x))]==fa[find(find_disc(t.y.y))]){flag=0;break;}
        }
        if(flag)puts("YES");
        else puts("NO");
    }
}




新鲜事 原文

mzhccc
7个月前
看到高三,初中,小学都放假了,高一高二满满的寂寞啊。


活动打卡代码 AcWing 101. 最高的牛

mzhccc
8个月前
#include<bits/stdc++.h>
#define N 10010
#define PII pair<int,int>
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
map<PII,bool> st;
int q[N];
int main(){
    int n,p,h,m;int a,b;

    cin>>n>>p>>h>>m;
    q[1]=h;
    For(i,1,m){
        cin>>a>>b;
        if(a>b)swap(a,b);
        if(st[{a,b}])continue;
        st.insert({{a,b},1});st[{a,b}]=1;
        q[a+1]--,q[b]++;
    }
    For(i,1,n){
        q[i]+=q[i-1];
        cout<<q[i]<<endl;
    }
}


活动打卡代码 AcWing 100. IncDec序列

mzhccc
8个月前
#include<bits/stdc++.h>
#define N 100010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int q[N];
int n;
long long neg,pos;
int main(){
    cin>>n;
    For(i,1,n){
        cin>>q[i];
    }
    for(int i = n;i>=1;i--){
        q[i]-=q[i-1];

    }
    For(i,2,n){
        if(q[i]<0)neg-=q[i];
        else pos+=q[i];
    }
    long long limit = min(pos,neg)+abs(pos-neg);
    long long cnt = abs(pos-neg)+1;
    cout<<limit<<endl<<cnt;
}


活动打卡代码 AcWing 99. 激光炸弹

mzhccc
8个月前
#include<bits/stdc++.h>
#define N 5010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int g[N][N];
int n,r;
int x,y,w;
int main(){
    cin>>n>>r;
    r = min(r,5001);
    while(n--){
        cin>>x>>y>>w;
        g[++x][++y]+=w;
    }
    For(i,1,5001){
        For(j,1,5001){
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
        }
    }
    int res = 0;
    For(i,r,5001){
        For(j,r,5001){
            res = max(res,g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);
        }
    }
    cout<<res;

}



mzhccc
8个月前
#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int h[N],ne[N],e[N],w[N],idx;
bool st[N];int dist[N];
int n,m;
void add(int a,int b,int v){e[idx]=b,w[idx]=v,ne[idx]=h[a],h[a]=idx++;}
int Prim(int u){
    int res = 0;
    dist[u]=0;
    For(i,1,n){
        int t = -1;
        For(j,1,n){
            if(!st[j]&&(dist[j]<dist[t]||t==-1)){
                t=j;
            }
        }
        if(dist[t]==INF)return INF;
        res+=dist[t];
        st[t]=true;
        for(int i = h[t];i!=-1;i=ne[i]){
            t=e[i];
            dist[t]=min(dist[t],w[i]);
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;
    int a,b,v;
    For(i,1,m){
        cin>>a>>b>>v;
        add(a,b,v);add(b,a,v);
    }
    int t = Prim(1);
    if(t==INF)puts("impossible");
    else cout<<t;
}