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