头像

cbio


访客:567

离线:1个月前


活动打卡代码 AcWing 247. 亚特兰蒂斯

cbio
4个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 255. 第K个数

cbio
4个月前
#include<bits/stdc++.h>
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define fornext(x,i) for(int i=head[x]; i; i=nxt[i])
#define mset(a,b) memset(a,b,sizeof(a))
#define dbg cout<<"c "
#define Rep(i,a,b) for(int i=(a); i<=(b); ++i)
#define pos(x) (lower_bound(b+1,b+tot+1,x)-b)
using namespace std;
typedef long long ll;

template<typename _T>
inline void read(_T &dig) {
    int flg; char c;
    flg=dig=0;
    while(c=getchar(), !isdigit(c)) if(c == '-') flg=1;
    while(isdigit(c)) dig=dig*10+c-'0', c=getchar();
    if(flg) dig=-dig;
}

template <typename _T, typename ...Args>
inline void read(_T &x, Args &...args) {
    read(x); read(args...); 
}

const int N=10000000;
int ls[N],rs[N],root[N],sum[N],ori[N];
int n,m,a[N],b[N],tot,cnt;

int build(int l,int r) {
    int tmp=++cnt;
    if(l == r) return tmp;
    ls[tmp]=build(l,(l+r)/2), rs[tmp]=build((l+r)/2+1,r);
    return tmp;
}

int add(int la,int l,int r,int p) {
    int tmp=++cnt;
    sum[tmp]=sum[la]+1;
    if(l == r) {
        ori[tmp]=p;
        return tmp;
    }
    if(p <= (l+r)/2) {
        rs[tmp]=rs[la],
        ls[tmp]=add(ls[la],l,(l+r)/2,p);
    }
    else {
        ls[tmp]=ls[la],
        rs[tmp]=add(rs[la],(l+r)/2+1,r,p);
    }
    return tmp;
}

int query(int l,int r,int k) {
    if(ori[r]) return ori[r];
    if(sum[ls[r]]-sum[ls[l]] >= k) return query(ls[l],ls[r],k);
    else return query(rs[l],rs[r],k-(sum[ls[r]]-sum[ls[l]]));
}

int main() {
    read(n,m);
    Rep(i,1,n) read(a[i]);
    Rep(i,1,n) b[i]=a[i];
    sort(b+1,b+n+1);
    tot=unique(b+1,b+n+1)-b-1;
    //cout<<tot<<endl;
    root[0]=build(1,tot);
    Rep(i,1,n) root[i]=add(root[i-1],1,tot,pos(a[i]));
    ++m;
    int u,v,k;
    while(--m) {
        read(u,v,k);
        printf("%d\n",b[query(root[u-1],root[v],k)]);
    //  cout<<query(root[u-1],root[v],k)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

cbio
6个月前
#include<bits/stdc++.h>
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(NULL),cout.tie(NULL),ios::sync_with_stdio("false")
#define fornext(x,i) for(int i=head[x]; i; i=nxt[i])
#define mset(a,b) memset(a,b,sizeof(a))
#define dbg cout<<"c "
using namespace std;
typedef long long ll;
int s[300005],n,ans,m;
deque<int> q;

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; ++i) scanf("%d",&s[i]), s[i]+=s[i-1];
    q.push_back(0);
    for(int i=1; i<=n; ++i) {
        while(q.size() && i-q.back() > m) q.pop_back();
        ans=max(s[i]-s[q.back()], ans);
        while(q.size() && s[q.front()] >= s[i]) q.pop_front();
        q.push_front(i);
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 367. 学校网络

cbio
6个月前
#include<bits/stdc++.h>
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(NULL),cout.tie(NULL),ios::sync_with_stdio("false")
#define fornext(x,i) for(int i=head[x]; i; i=nxt[i])
#define mset(a,b) memset(a,b,sizeof(a))
#define dbg cout<<"c "
using namespace std;
typedef long long ll;
const int N=200005;
int n,eds,tot=1,head[N],ver[N],nxt[N],ed[N];
int flg,instk[N],b[N],nh[N],nv[N],nnx[N],low[N],dfn[N],cnt,ntot;
int in[N],out[N];
stack<int> s;

void add(int u,int v) {
    nxt[++tot]=head[u], head[u]=tot, ver[tot]=v;
}

void n_add(int u,int v) {
    nnx[++ntot]=nh[u], nh[u]=ntot, nv[ntot]=v;
}

void tarjan(int x) {
    int y;
    dfn[x]=low[x]=++cnt;
    s.push(x), instk[x]=1;
    for(int i=head[x]; i; i=nxt[i]) {
        if(!dfn[y=ver[i]]) tarjan(y), low[x]=min(low[y],low[x]);
        else if(instk[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x] == low[x]) {
        ++flg;
        while(s.top() != x) instk[y=s.top()]=0, b[y]=flg, s.pop();
        b[x]=flg, instk[x]=0, s.pop();
    }
}

int main() {
    int u;
    cin>>n;
    for(int i=1; i<=n; ++i) {
        while(1) {
            cin>>u;
            if(!u) break;
            add(i,u);
        }
    } 
    for(int i=1; i<=n; ++i) if(!dfn[i]) tarjan(i);
    for(int i=1; i<=n; ++i) {
        fornext(i,j) {
            if(b[u=ver[j]] == b[i]) continue;
            ++in[b[u]], ++out[b[i]];
        }
    }
    int inc=0,outc=0;
    for(int i=1; i<=flg; ++i) {
        if(in[i] == 0) ++inc;
        if(out[i] == 0) ++outc;
    }
    cout<<inc<<endl<<(flg == 1?0:max(inc,outc))<<endl;
    return 0;
}


活动打卡代码 AcWing 382. K取方格数

cbio
6个月前
#include<bits/stdc++.h>
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(NULL),cout.tie(NULL),ios::sync_with_stdio("false")
#define fornext(x,i) for(int i=head[x]; i; i=nxt[i])
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int N=200005,inf=1<<26;
int mx,ans,s,t,tot=1,head[N],ver[N],nxt[N],ed[N];
int pre[N],v[N],in[N],incf[N],cost[N];
int n,k,a[100][100],id[100][100]; 

void add(int u,int v,int val,int co) {
    nxt[++tot]=head[u], head[u]=tot, ver[tot]=v, ed[tot]=val, cost[tot]=co;
    nxt[++tot]=head[v], head[v]=tot, ver[tot]=u, ed[tot]=0, cost[tot]=-co;
}

bool spfa() {
    int x,y;
    queue<int> q;
    mset(v,0xcf), clear(in), v[s]=0, q.push(s), incf[s]=1<<28;
    while(q.size()) {
        x=q.front(), q.pop(), in[x]=0;
        fornext(x,i) {
            if(!ed[i]) continue;
            y=ver[i];
            if(v[y] < v[x]+cost[i]) {//×· 
                v[y] = v[x]+cost[i];
                incf[y] = min(incf[x],ed[i]);
                pre[y] = i;
                if(!in[y]) in[y]=1, q.push(y);
            } 
        }
    }
    if(v[t] == 0xcfcfcfcf) return 0;
    return 1;
}

void update() {
    int x=t,i;
    mx += incf[t], ans += v[t]*incf[t];
    while(x != s) {
        i=pre[x];
        ed[i]-=incf[t], ed[i^1]+=incf[t];
        x=ver[i^1];
    }
}

int main() {
    int cnt=0;
    cin>>n>>k;
    for(int i=1; i<=n; ++i) 
        for(int j=1; j<=n; ++j) cin>>a[i][j],id[i][j]=++cnt;

    s=0,t=2*n*n+1;
    add(s,id[1][1],k,0), add(id[n][n]+n*n,t,k,0);

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j) {
            add(id[i][j],id[i][j]+n*n,inf,0), add(id[i][j],id[i][j]+n*n,1,a[i][j]);
            if(i+1 <= n) add(id[i][j]+n*n,id[i+1][j],inf,0);
            if(j+1 <= n) add(id[i][j]+n*n,id[i][j+1],inf,0);
        }   

    while(spfa()) update();
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 346. 走廊泼水节

cbio
6个月前
#include<bits/stdc++.h>
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(NULL),cout.tie(NULL),ios::sync_with_stdio("false")
using namespace std;
const int N=200005;
int n,ans,uf[N],size[N];
struct ele {
    int f,t,val;
    friend bool operator <(ele a,ele b) {
        return a.val<b.val;
    }
#define f(x) a[x].f
#define t(x) a[x].t
#define val(x) a[x].val
} a[N];

int fd(int x) {
    if(uf[x] == x) return x;
    return uf[x]=fd(uf[x]);
}

int main() {
    int T;
    cin>>T;
    while(T--) {
        clear(a), ans=0;
        int u,v,val;
        cin>>n;
        for(int i=1; i<=n-1; ++i) {
            scanf("%d%d%d",&u,&v,&val);
            a[i]=(ele) {
                u,v,val
            };
        }
        sort(a+1,a+n);
        for(int i=1; i<=n; ++i) uf[i]=i, size[i]=1;
        int x,y;
        for(int i=1; i<=n-1; ++i) {
            x=fd(f(i)), y=fd(t(i));
            if(x == y) continue;
            ans+=(size[x]*size[y]-1)*(val(i)+1);
            uf[x]=y, size[y]+=size[x];
        }
        cout<<ans<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

cbio
7个月前
#include<bits/stdc++.h>
#define ll long long
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(NULL)
using namespace std;
int t[2][3000000],tot=1;
int n,m;

void insert(int in) {
    int p=1, c;
    for(int i=31; i>=0; --i) {
        c=(in>>i)&1;
        if(t[c][p] == 0) t[c][p]=++tot;
        p=t[c][p];
    }
}

int calc(int in) {
    int p=1, c, ans=0;
    for(int i=31; i>=0; --i) {
        c=(in>>i)&1;
        if(t[c^1][p] != 0) ans+=(1<<i), p=t[c^1][p];
        else p=t[c][p];
    }
    return ans;
} 

int main() {
    cin>>n;
    int mx=0,in;
    while(n--) {
        cin>>in;
        insert(in);
        mx=max(mx,calc(in));
//      cout<<mx<<endl;
    }
    cout<<mx<<endl;
    return 0;
}


活动打卡代码 AcWing 142. 前缀统计

cbio
7个月前

3 2 ab bc abc abc efg
要注意tot=1!!!



活动打卡代码 AcWing 373. 車的放置

cbio
7个月前
#include<bits/stdc++.h>
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(NULL)
using namespace std;
typedef long long ll;
const int N=100005,S=300;
int n,eds,tot=0,head[N],ver[N],nxt[N],ed[N],match[N],vis[N];
int line,col,b[S][S],k;

void add(int u,int v) {
    nxt[++tot]=head[u], head[u]=tot, ver[tot]=v;
}

bool dfs(int x) {
    int u;
    for(int i=head[x]; i; i=nxt[i]) {
        if(vis[u=ver[i]]) continue;
        vis[u]=1;
        if(match[u] == 0 || dfs(match[u])) {
            match[u]=x;
            return true;
        }
    }
    return false;
}

int main() {
    int u,v;
    cin>>line>>col>>k;
    for(int i=1; i<=k; ++i) cin>>u>>v, b[u][v]=1;
    for(int i=1; i<=line; ++i)
        for(int j=1; j<=col; ++j) if(!b[i][j]) add(i,j);
    int ans=0;
    for(int i=1; i<=line; ++i) {
        clear(vis);
        if(dfs(i)) ++ans;
    } 
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 376. 机器任务

cbio
7个月前
#include<bits/stdc++.h>
#define clear(a) memset(a,0,sizeof(a))
#define full(a) memset(a,0x3f,sizeof(a))
#define iosfast cin.tie(NULL)
using namespace std;
typedef long long ll;
const int N=10005;
int l,r,n;
int ans,eds,tot=0,head[N],ver[N],nxt[N],match[N],vis[N];

void add(int u,int v) {
    nxt[++tot]=head[u], head[u]=tot, ver[tot]=v;
}

bool dfs(int x) {
    int u;
    for(int i=head[x]; i; i=nxt[i]) {
        if(vis[u=ver[i]]) continue;
        vis[u]=1;
        if(match[u] == 0 || dfs(match[u])) {
            match[u]=x;
            return true;
        }
    }
    return false;
}

int main() {
    while(1) {
        cin>>l;
        if(l == 0) break;
        clear(nxt), clear(head), clear(match), ans=0;
        cin>>r>>n;
        int u,v;
        for(int i=1; i<=n; ++i) {
            cin>>u>>u>>v;
            if(u != 0 && v != 0) add(u,v);
        }
        for(int i=0; i<l; ++i) {
            clear(vis);
            if(dfs(i)) ++ans;
        }
        cout<<ans<<endl;
    }
    return 0;
}