头像

朝暮不思


访客:1602

离线:19小时前


活动打卡代码 AcWing 287. 积蓄程度

朝暮不思
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
const int inf=0x3f3f3f3f;
int h[N],ne[N],e[N],w[N],idx;
int in[N];
int d[N],f[N];
int ans;
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs(int u,int fa){
    int i;
    if(in[u]==1){
        d[u]=inf;
        return d[u];
    }
    d[u]=0;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)
            continue;
        d[u]+=min(w[i],dfs(j,u));
    }
    return d[u];
}
void get(int u,int fa){
    int i;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)
        continue;
        if(in[j]==1){
            f[j]=d[u]-w[i];
        }
        else{
            f[j]=d[j]+min(f[u]-min(d[j],w[i]),w[i]);
            get(j,u);
        }

    }
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int i;
        ans=0;
        idx=0;
        for(i=1;i<=n;i++)
            h[i]=-1;
        memset(in,0,sizeof in);
        for(i=1;i<n;i++){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            add(b,a,c);
            in[a]++;
            in[b]++;
        }
        int root=1;
        while (root<=n&&in[root] == 1) root ++ ;

        if (root>n){
            cout << w[0] << endl;
            continue;
        }
        dfs(root,-1);
        f[root]=d[root];
        get(root,0);
        for(i=1;i<=n;i++)
            ans=max(ans,f[i]);
        cout<<ans<<endl;
    }
}


活动打卡代码 AcWing 2171. EK求最大流

朝暮不思
1个月前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int h[N],ne[N],e[N],idx;
int f[N];
int n,m,S,T;
int pre[N];
int st[N];
int d[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}
bool bfs(){
    memset(st,0,sizeof st);
    d[S]=inf;
    queue<int> q;
    q.push(S);
    st[S]=1;
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!st[j]&&f[i]){
                st[j]=1;
                d[j]=min(d[t],f[i]);
                pre[j]=i;
                if(j==T)
                return true;
                q.push(j);
            }
        }
    }
    return false;
}
int ek(){
    int res=0;
    while(bfs()){
        int i;
        for(i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=d[T],f[pre[i]^1]+=d[T];
        }
        res+=d[T];
    }
    return res;
}
int main(){
    cin>>n>>m>>S>>T;
    int i;
    memset(h,-1,sizeof h);
    for(i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<ek()<<endl;
}


活动打卡代码 AcWing 116. 飞行员兄弟

朝暮不思
2个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pll;
const int N=2e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
char s[5][5];
int g[5][5];
int tmp[5][5];
int res;
int ans[5][5];
int cal(int x){
    int res=0;
    while(x){
        if(x%2)
            res++;
        x/=2;
    }
    return res;
}
bool check(int x){
    int i,j;
    memcpy(tmp,g,sizeof tmp);
    for(i=1;i<=4;i++){
        for(j=1;j<=4;j++){
            if(x&(1<<((i-1)*4+(j-1)))){
                tmp[i][j]=!tmp[i][j];
                for(int l=1;l<=4;l++) tmp[l][j]=!tmp[l][j];
                for(int l=1;l<=4;l++) tmp[i][l]=!tmp[i][l];
            }
        }
    }
    for(i=1;i<=4;i++){
        for(j=1;j<=4;j++){
            if(tmp[i][j]==1)
                return 0;
        }
    }
    return 1;
}
void solve(){
    int i;
    for(i=1;i<1<<16;i++){
        int cost=cal(i);
        if(cost<res&&check(i)){
            res=cost;
            for(int l=1;l<=4;l++){
                for(int r=1;r<=4;r++){
                    if(i&(1<<((l-1)*4+(r-1)))){
                        ans[l][r]=1;
                    }
                    else{
                        ans[l][r]=0;
                    }
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    int i,j;
    for(i=1;i<=4;i++){
        for(j=1;j<=4;j++){
            cin>>s[i][j];
            if(s[i][j]=='+')
                g[i][j]=1;
            else
                g[i][j]=0;
        }
    }
    res=0x3f3f3f3f;
    solve();
    cout<<res<<endl;
    for(i=1;i<=4;i++){
        for(j=1;j<=4;j++){
            if(ans[i][j]){
                cout<<i<<" "<<j<<endl;
            }
        }
    }
    return 0;
}



活动打卡代码 AcWing 114. 国王游戏

朝暮不思
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

int n;
PII p[N];

vector<int> mul(vector<int>a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

vector<int> div(vector<int>a, int b)
{
    vector<int> c;
    bool is_first = true;
    for (int i = a.size() - 1, t = 0; i >= 0; i -- )
    {
        t = t * 10 + a[i];
        int x = t / b;
        if (!is_first || x)
        {
            is_first = false;
            c.push_back(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}

vector<int> max_vec(vector<int> a, vector<int> b)
{
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend())) return a;
    return b;
}

int main()
{
    cin >> n;
    for (int i = 0; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        p[i] = {a * b, a};
    }
    sort(p + 1, p + n + 1);

    vector<int> product(1, 1);

    vector<int> res(1, 0);
    for (int i = 0; i <= n; i ++ )
    {
        if (i) res = max_vec(res, div(product, p[i].first / p[i].second));
        product = mul(product, p[i].second);
    }

    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    cout << endl;

    return 0;
}




活动打卡代码 AcWing 112. 雷达设备

朝暮不思
2个月前
 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=8e5+10;
const int mod=1e9+7;
struct node{
    double l,r;
    bool operator <(const node& t) const{
        return l<t.l;
    }
}s[N];
int main(){
    ios::sync_with_stdio(false);
    int n;
    double d;
    cin>>n>>d;
    int i;
    int sign=0;
    for(i=1;i<=n;i++){
        double x,y;
        cin>>x>>y;
        if(y>d){
            sign=1;
        }
        double tmp=sqrt(d*d-y*y);
        s[i]={x-tmp,x+tmp};
    }
    if(sign){
        cout<<-1<<endl;
        return 0;
    }
    sort(s+1,s+1+n);
    int ans=0;
    double pos=-1e9;
    for(i=1;i<=n;i++){
        if(pos<s[i].l){
            ans++;
            pos=s[i].r;
        }
        else{
            pos=min(s[i].r,pos);
        }
    }
    cout<<ans<<endl;
}



活动打卡代码 AcWing 111. 畜栏预定

朝暮不思
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int,int> PII;
const int N = 50010;

int n;
int id[N];
pair<PII, int> cows[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> cows[i].first.first >> cows[i].first.second;
        cows[i].second = i;
    }

    sort(cows, cows + n);

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (int i = 0; i < n; i ++ )
    {
        if (heap.empty() || heap.top().first >= cows[i].first.first)
        {
            PII stall = {cows[i].first.second, heap.size()};
            id[cows[i].second] = stall.second;
            heap.push(stall);
        }
        else
        {
            auto stall = heap.top();
            heap.pop();
            stall.first = cows[i].first.second;
            id[cows[i].second] = stall.second;
            heap.push(stall);
        }
    }

    cout << heap.size() << endl;
    for (int i = 0; i < n; i ++ ) cout << id[i] + 1 << endl;
    return 0;
}




活动打卡代码 AcWing 110. 防晒

朝暮不思
2个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+10;
struct node{
    int l,r;
    bool operator<(const node &t) const{
        return l>t.l;
    }
}s[N];
int a[N],b[N];
int main(){
    ios::sync_with_stdio(false);
    int n,l;
    cin>>n>>l;
    int i;
    for(i=1;i<=n;i++){
        cin>>s[i].l>>s[i].r;
    }
    for(i=1;i<=l;i++){
        cin>>a[i]>>b[i];
    }
    sort(s+1,s+1+n);
    int ans=0;
    for(i=1;i<=n;i++){
        int mx=-1;
        int id=0;
        for(int j=1;j<=l;j++){
            if(a[j]>mx&&b[j]&&(a[j]>=s[i].l&&a[j]<=s[i].r)){
                mx=a[j];
                id=j;
            }
        }
        if(id){
            b[id]--;
            ans++;
        }
    }
    cout<<ans<<endl;

}



活动打卡代码 AcWing 109. 天才ACM

朝暮不思
2个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll n,m,p;
ll a[N];
ll tmp[N];
bool check(int l,int r,int x){
    int i,j;
    ll cnt=0;
    for(i=l;i<=r+x;i++){
        tmp[++cnt]=a[i];
    }
    ll res=0;
    sort(tmp+1,tmp+1+cnt);
    int sign=0;
    for(i=1,j=cnt;i<j;i++,j--){
        if(sign==m)
        break;
        res+=(tmp[j]-tmp[i])*(tmp[j]-tmp[i]);
        sign++;
    }
    return res<=p;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>p;
        int i;
        for(i=1;i<=n;i++)
            cin>>a[i];
        int x=1,l=1,r=1;
        ll ans=0;
        while(r<=n){
            if(!x){
                ans++;
                x=1;
                l=++r;
            }
            else if(r+x<=n&&check(l,r,x)){
                r+=x;
                x<<=1;
            }
            else{
                x>>=1;
            }
        }
        cout<<ans<<endl;
    }
}



活动打卡代码 AcWing 107. 超快速排序

朝暮不思
2个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=1e6+10;
int a[N];
int tr[N];
int lowbit(int x){
    return x&-x;
}
void add(int x,int c){
    for(int i=x;i<N;i+=lowbit(i)){
        tr[i]+=c;
    }
}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n,n){
        memset(tr,0,sizeof tr);
        int i;
        ll res=0;
        vector<int> num;
        num.clear();
        for(i=1;i<=n;i++){
            cin>>a[i];
            num.push_back(a[i]);
        }
        sort(num.begin(),num.end());
        num.erase(unique(num.begin(),num.end()),num.end());
        int cnt=(int)num.size();
        for(i=1;i<=n;i++){
            int pos=lower_bound(num.begin(),num.end(),a[i])-num.begin()+1;
            add(pos,1);
            res+=i-sum(pos);

        }
        cout<<res<<endl;
    }
}



活动打卡代码 AcWing 106. 动态中位数

朝暮不思
2个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=1e6+10;
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int m,n;
    // 大根堆维护1-i/2+1,因此大根堆堆顶是答案
    //维护大根堆只比小根堆大1, 先插入大根堆后比较堆顶
    //保证顺序
    while(t--){
        cin>>m>>n;
        int i;
        priority_queue<int,vector<int>,greater<int> > q1;
        priority_queue<int> q2;//big
        cout<<m<<" "<<(n+1)/2<<endl;
        int cnt=0;
        for(i=0;i<n;i++){
            int x;
            cin>>x;
            q2.push(x);
            if(q1.size()&&q1.top()<q2.top()){
                int a=q1.top(),b=q2.top();
                q1.pop();q2.pop();
                q2.push(a);
                q1.push(b);
            }
            if(q2.size()>q1.size()+1){
                q1.push(q2.top());
                q2.pop();
            }
            if(i%2==0){
                cnt++;
                if(cnt%10)
                cout<<q2.top()<<" ";
                else{
                    cout<<q2.top()<<endl;
                }
            }
        }
        if(cnt%10)
            cout<<endl;
    }
}