想知道各位大佬还有什么奇怪的解题方式

P1001 A+B Problem

zhengpie @ 2023-12-20 22:21:11

该题看似简单,实则却很险恶 请求各位大佬有没有什么奇怪的方法解题,本人想收集一波~~~


by shinzanmono @ 2023-12-20 22:26:55

任何算法都可以


by zzrrxx @ 2023-12-20 22:28:40

@zhengpie


by zhengpie @ 2023-12-21 11:58:27

@shinzanmono ???


by Union_of_Britain @ 2023-12-23 08:43:26

@zhengpie Fast zhengpie Transform


by dulinfan2023 @ 2023-12-23 15:54:04

dp dfs


by zhengpie @ 2023-12-24 16:47:08

666


by yzm0325 @ 2023-12-31 09:47:35

宣一波


by _qingshu_ @ 2024-01-03 13:33:13

@zhengpie

好像是有点晚了。预流推进写法。

#include<bits/stdc++.h>
using namespace std;
int n,m,r,c,s,t,sum;
char mp[100][100];
struct edge{
    int to,nxt;
    long long val;
}e[5200010];
int head[5200010],tot=1,h[5200010];
struct cmp{
    inline bool operator ()(int x,int y)const{
        return h[x]<h[y];
    }
};
priority_queue<int,vector<int>,cmp>qq;
queue<int>q;
long long over[5200010],vist[5200010],gap[5200010];
void add(int u,int v,long long w){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    e[tot].val=w;
    head[u]=tot;

    e[++tot].to=u;
    e[tot].nxt=head[v];
    e[tot].val=0;
    head[v]=tot;
}
bool bfs(){
    for(int i=1;i<=t;i++){
        h[i]=1e9;
    }
    h[t]=0;
    q.push(t);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i^1].val&&h[v]>h[x]+1){
                h[v]=h[x]+1;
                q.push(v); 
            }
        }
    }
    return (h[s]!=0);
}
void push(int x){
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].val&&h[x]==h[v]+1){
            int k=min(over[x],e[i].val);
            e[i].val-=k;
            e[i^1].val+=k;
            over[x]-=k;
            over[v]+=k;
            if(v!=s&&v!=t&&!vist[v]){
                vist[v]=1;
                qq.push(v);
            }
            if(!over[x]){
                return;
            }
        }
    }
}
void relable(int x){
    h[x]=1e9;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].val&&h[x]>h[v]+1){
            h[x]=h[v]+1;
        }
    }
}
long long hlpp(){
    if(!bfs()){
        return 0;
    }
    h[s]=2*n*m+2;
    for(int i=1;i<=2*n*m+2;i++){
        if(h[i]!=1e9){
            gap[h[i]]++;
        }
    }
    for(int i=head[s];i;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].val&&h[v]!=1e9){
            e[i^1].val+=e[i].val;
            over[v]+=e[i].val;
            e[i].val=0;
            if(v!=s&&v!=t&&!vist[v]){
                vist[v]=1;
                qq.push(v);
            }
        }
    }
    while(!qq.empty()){
        int x=qq.top();
        qq.pop();
        vist[x]=0;
        push(x);
        if(over[x]){
            gap[h[x]]--;
            if(!gap[h[x]]){
                for(int i=1;i<=2*n*m+2;i++){
                    if(i!=t&&i!=s&&h[i]<=2*n*m+2&&h[i]>h[x]){
                        h[i]=2*n*m+2+1;
                    }
                }
            }
            relable(x);
            gap[h[x]]++;
            vist[x]=1;
            qq.push(x);
        }
    }
    return over[t];
}
int main(){
    n=2,s=2;
    s=1;
    t=2;
    long long kk;
    cin>>kk;
    add(1,2,kk);
    cin>>kk;
    add(1,2,kk);
    cout<<hlpp();
}

by ReverBer @ 2024-01-03 18:12:54

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
struct node{
    ll l,r;
    mutable ll v;
    bool operator < (const node &o) const {return l<o.l;}
};

set <node> tree;
auto split(ll pos){
    auto it=tree.lower_bound({pos,0,0});
    if(it->l==pos and it!=tree.end()) return it;
    -- it;
    ll l=it->l,r=it->r,v=it->v;
    tree.erase(it);
    tree.insert({l,pos-1,v});
    return tree.insert({pos,r,v}).first;
}
ll a,b;
void assign(ll l,ll r,ll v){
    auto end=split(r+1),begin=split(l);
    tree.erase(begin,end);
    tree.insert({l,r,v});
}
ll query(ll l,ll r){
    ll res=0;
    auto end=split(r+1);
    for(auto it=split(l);it!=end;it++){
        res+=it->v*(it->r-it->l+1);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>a>>b;
    tree.insert({1,100000,0});
    assign(1,1,a);
    assign(2,2,b);
    cout<<query(1,2);
    return 0;
}

odt.


by zhengpie @ 2024-01-03 20:32:50

@qingshu 6


| 下一页