42 条题解
-
1
Lifi LV 10 @ 2019-09-05 23:26:47
差分约束不会写，只能用贪心和树状数组。
第一步：按区间的尾端的升序进行排序。
第二步：循环每个区间，树状数组求前缀和，检查区间内的点是否满足需求。
第三步：如果某个区间不满足需求，则从区间尾部向前添加整数，并调整树状数组，直到数量满足要求为止。#include <bits/stdc++.h> using namespace std; typedef struct { int a,b,v; }li; int n; li lis[50000]; int trarr[50005]={0}; bool vis[50005]={0}; bool comp(li a,li b) { if(a.b==b.b) { return a.a<b.a; } else { return a.b<b.b; } } int lowbit(int x) { return x&(-x); } void add(int x,int a) { if(x<1) return; while(x<50005) { trarr[x]+=a; x+=lowbit(x); } } int fi(int x) { int ans=0; while(x>0) { ans+=trarr[x]; x-=lowbit(x); } return ans; } int main() { cin>>n; int i,j,k,ans=0; for(i=0;i<n;i++) { cin>>lis[i].a>>lis[i].b>>lis[i].v; lis[i].a++; lis[i].b++; } sort(lis,lis+n,comp); for(i=0;i<n;i++) { k=fi(lis[i].b)-fi(lis[i].a-1); if(k<lis[i].v) { for(j=lis[i].b;k<lis[i].v;j--) { if(!vis[j]) { vis[j]=true; add(j,1); k++; ans++; } } } } cout<<ans<<endl; return 0; } -
1
sysky (fyy2017) LV 8 @ 2018-10-16 18:31:40
貌似有个差分约束……
本蒟蒻不会……#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<queue> using namespace std; const int lim=50055; const int inf=999999999; int d[lim<<2]; struct self{int x,y,w;}s[lim<<2]; int first[lim<<2],nxt[lim<<2]; int m,n,a,b,c,tn,x,y,w; queue<int>q; bool inq[lim]; void add(int x,int y,int w) { n++; s[n].x=x;s[n].y=y;s[n].w=w; nxt[n]=first[x];first[x]=n; } void spfa() { int a,b; for(a=0;a<=m+1;a++)d[a]=-inf; d[0]=0; q.push(0); while(!q.empty()) { int u=q.front();q.pop();inq[u]=0; for(int e=first[u];e!=-1;e=nxt[e]) { if(d[s[e].y]<d[u]+s[e].w) { d[s[e].y]=d[u]+s[e].w; if(!inq[s[e].y]) { q.push(s[e].y); inq[s[e].y]=1; } } } } cout<<d[m+1]<<endl; } int main() { memset(first,-1,sizeof(first));memset(nxt,-1,sizeof(nxt)); scanf("%d",&tn); m=50000; for(a=1;a<=tn;a++) { scanf("%d%d%d",&x,&y,&w); x++;y++; m=max(m,x);m=max(m,y); add(x-1,y,w); } for(a=1;a<=m+1;a++) { add(a,a-1,-1); add(a-1,a,0); } spfa(); return 0; } -
1
miraclejzd LV 9 @ 2017-07-12 19:30:36
比较好想的差分约束。（似乎是裸题？）
我们可以令s[n]表示0到n中元素的个数，则对于题目给的三元组（a,b,c）我们有s[b]-s[a-1]>=c，最后答案即是s[50000]-s[-1]。
故我们可以连接一条a-1到b边权为c的有向边来建图。还要注意隐藏的条件，对于一个元素i，有选和不选这两种决策，所以还要满足0<=s[i]-s[i-1]<=1。
所以还需要连接2×50000条边，然后就可以以-1为源点跑最长路。但是-1在数组中没有映射，所以要把数组整体右移一位，使得0为源点就可以跑出来啦.
一遍AC。
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define For(i,j,k) for(register int i=j; i<=(int)k; ++i)
#define Forr(i,j,k) for(register int i=j; i>=(int)k; --i)
#define INF 0x3f3f3f3f
using namespace std;int n;
int dis[50005], tot[50005];
int cnt, Begin[50005], Next[150005], To[150005], w[150005];
bool vis[50005];
queue<int> q;inline void add(int x, int y, int z){
To[++cnt] = y;
w[cnt] = z;
Next[cnt] = Begin[x];
Begin[x] = cnt;
}inline bool SPFA(){
memset(dis, -INF, sizeof(dis));
memset(tot, 0, sizeof(tot));
memset(vis, 0, sizeof(vis));vis[0] = true;
dis[0] = 0;
q.push(0);
while(!q.empty()){
int x=q.front();
q.pop();
vis[x] = false;
++ tot[x];if(tot[x] >= n)
return false;for(register int i=Begin[x]; i; i=Next[i]){
int v=To[i], val=w[i];
if(dis[v] < dis[x]+val){
dis[v] = dis[x]+val;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
return true;
}int main(){
int x, y, z;scanf("%d", &n);
For(i,1,n){
scanf("%d%d%d", &x, &y, &z);
add(x, y+1, z);
}
For(i,1,50001){
add(i-1,i,0);
add(i,i-1,-1);
}if(!SPFA()){
puts("-1");
return 0;
}
else{
printf("%d", dis[50001]-dis[0]);
}
return 0;
}
``` -
1
论卡常。。再也不用前向星啦（逃）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstdlib>
using namespace std;/*
T[i]:= 是否有i元素
S[i]:= T[0]+...+T[i]
S[i]:= 0～i元素个数
S[b]-S[a-1]>=C --> S[a-1]<=S[b]-C
S[i]-S[i-1]>=0 --> S[i-1]<=S[i]+0
S[i-1]-S[i]>=-1 --> S[i]<=S[i-1]+1
*/int tot=0;
struct E{int from,to,cost;}e[200000];
int first[200000],rest[200000];int n;
int d[200000];
int v[200000];
int MAX_N=50000;void add(int u,int v,int c){
++tot;
e[tot]=(E){u,v,c};
rest[tot]=first[u];
first[u]=tot;
}void SPFA(){
for(int i=0;i<=MAX_N;i++)d[i]=-0x3f3f3f3f;
d[0]=0;
queue<int>q;
q.push(0);
while(q.size()){
int t=q.front();q.pop();
v[t]=0;
for(int i=first[t];i!=-1;i=rest[i]){
int from=e[i].from,to=e[i].to,cost=e[i].cost;
if(d[to]<d[t]+cost){
d[to]=d[t]+cost;
if(!v[to]){
v[to]=1;
q.push(to);
}
}
}
}printf("%d\n",d[MAX_N]);
}int main(){
memset(first,-1,sizeof(first));
memset(rest,-1,sizeof(rest));
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a++,b++;MAX_N=max(MAX_N,max(a,b));
add(a-1,b,c);
}
MAX_N++;
for(int i=1;i<=MAX_N;i++){
add(i,i-1,-1);
add(i-1,i,0);//顺便完成了g[0].push_back((e){i,0});
}
SPFA();
} -
0
这题用了标准差分约束系统后又改造了下，但不清楚正确性，也许是数据太弱没查出错
var m,i,x,y,z,t:longint;
s,w:array[-1..50000] of longint;
e:array[1..50000] of record
v,w,ne:longint;
end;
procedure add_edge(x,y,z:longint);
begin
inc(t);
e[t].v:=y;
e[t].w:=z;
e[t].ne:=w[x];
w[x]:=t;
end;
begin
readln(m);
for i:=1 to m do begin
readln(x,y,z);
add_edge(x-1,y,z);
end;
s[-1]:=0;
for i:=-1 to 50000 do begin
if (i>-1)and(s[i-1]>s[i]) then s[i]:=s[i-1];
x:=w[i];
while x>0 do begin
y:=s[i]+e[x].w;
z:=e[x].v;
if y>s[z] then begin
s[z]:=y;
while s[z]-1>s[z-1] do begin
s[z-1]:=s[z]-1;
dec(z);
end;
end;
x:=e[x].ne;
end;
end;
writeln(s[50000]);
end.
标准差分约束系统
测试数据 #0: Accepted, time = 156 ms, mem = 3340 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 3160 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 3164 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 3164 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 3996 KiB, score = 10
测试数据 #5: Accepted, time = 78 ms, mem = 3996 KiB, score = 10
测试数据 #6: Accepted, time = 156 ms, mem = 3996 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 3996 KiB, score = 10
测试数据 #8: Accepted, time = 500 ms, mem = 3996 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 3268 KiB, score = 10
乱搞之后
测试数据 #0: Accepted, time = 15 ms, mem = 1724 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1720 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 1720 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1716 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 1720 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 1720 KiB, score = 10
测试数据 #6: Accepted, time = 78 ms, mem = 1720 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 1720 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1716 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1720 KiB, score = 10
Accepted, time = 339 ms, mem = 1724 KiB, score = 100
也许是因为后来的选择性松弛边节约了时间吧
如果这种做法有误希望大神能指正，谢谢！-
308454 @ 2014-07-17 23:37:11
可能是因为这题肯定没有正环，然后可以从小到大枚举边的起点，当枚举到i时才松弛i-1至i的边，当点i被松弛时才松弛往回走的负边，而往回走的边连出的点一定是还没被当做起点枚举到的（语言表达能力好差！），所以当被枚举时都已经被所有可以松弛的边松弛完毕，达到了最大值，所以不会影响结果。。。
-
-
0
gaojiaxuan LV 8 @ 2014-07-14 20:23:47
这题是差分约束系统：
对于每个三元组[a,b,c]，从a-1到b连一条长度为c的边
对于每个i，从i到i-1连一条长度为-1的边,从i-1到i连一条长度为0的边
做一次最长路（spfa/dij……）； -
0
qaz3685079 LV 7 @ 2014-07-07 20:02:33
program cfys;
type data=record
x,nex,d:longint;
end;var n,i,j,max,a,b,c,p:longint;
edge:array[0..500000]of data;
head,dis:array[0..500000]of longint;
dl:array[0..500000]of longint;
procedure build(a,b,c:longint);
begin
edge[p].nex:=head[a];
edge[p].x:=b;
edge[p].d:=c;
head[a]:=p;
inc(p);
end;procedure spfa;
var i,node,t,w:longint;
begin
t:=1;w:=1;
dl[1]:=max;
inc(w);
while t<w do
begin
node:=dl[t mod max];
i:=head[node];
while i<>0 do
begin
if dis[edge[i].x]>dis[node]+edge[i].d then
begin
dl[w mod max]:=edge[i].x;
inc(w);
dis[edge[i].x]:=dis[node]+edge[i].d;
end;
i:=edge[i].nex;
end;
inc(t);
end;
end;begin
read(n);
max:=0;p:=1;
for i:=1 to n do
begin
read(a,b,c);
if a>max then max:=a;
if b>max then max:=b;
build(b,a-1,-c);
end;
for i:=0 to max-1 do
begin
dis[i]:=100000;
build(i,i+1,1);
build(i+1,i,0);
end;
dis[max]:=0;dis[0]:=100000;
spfa;
writeln(-dis[0]);
end. -
0
评测状态 Accepted
题目 P1532 区间
递交时间 2014-07-07 19:58:59
代码语言 Pascal
评测机 Jtwd2
消耗时间 716 ms
消耗内存 12484 KiB
评测时间 2014-07-07 19:59:01
评测结果
编译成功Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(6,11) Note: Local variable "j" not used
Linking foo.exe
62 lines compiled, 0.1 sec , 28320 bytes code, 1628 bytes data
1 note(s) issued
测试数据 #0: Accepted, time = 78 ms, mem = 12484 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 12484 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 12484 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 12484 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 12484 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 12484 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 12484 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 12484 KiB, score = 10
测试数据 #8: Accepted, time = 250 ms, mem = 12484 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 12484 KiB, score = 10
Accepted, time = 716 ms, mem = 12484 KiB, score = 100
program cfys;
type data=record
x,nex,d:longint;
end;var n,i,j,max,a,b,c,p:longint;
edge:array[0..500000]of data;
head,dis:array[0..500000]of longint;
dl:array[0..500000]of longint;
procedure build(a,b,c:longint);
begin
edge[p].nex:=head[a];
edge[p].x:=b;
edge[p].d:=c;
head[a]:=p;
inc(p);
end;procedure spfa;
var i,node,t,w:longint;
begin
t:=1;w:=1;
dl[1]:=max;
inc(w);
while t<w do
begin
node:=dl[t mod max];
i:=head[node];
while i<>0 do
begin
if dis[edge[i].x]>dis[node]+edge[i].d then
begin
dl[w mod max]:=edge[i].x;
inc(w);
dis[edge[i].x]:=dis[node]+edge[i].d;
end;
i:=edge[i].nex;
end;
inc(t);
end;
end;begin
read(n);
max:=0;p:=1;
for i:=1 to n do
begin
read(a,b,c);
if a>max then max:=a;
if b>max then max:=b;
build(b,a-1,-c);
end;
for i:=0 to max-1 do
begin
dis[i]:=100000;
build(i,i+1,1);
build(i+1,i,0);
end;
dis[max]:=0;dis[0]:=100000;
spfa;
writeln(-dis[0]);
end. -
0
JackDavid127 LV 10 @ 2009-11-11 18:12:06
神奇的差分约束系统……
Orz
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 509ms
├ 测试数据 06：答案正确... 25ms
├ 测试数据 07：答案正确... 166ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：700ms好丑……
SPFA.......写挂了
改成bellman-forld（无视我的拼写）
短了很多...
好不容易过了 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 181ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 338ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：519ms写了个好丑的查分约束
-
0
不会差约分数啊，用了贪心+线段树求和。
程序又长又丑：
program p1532(input,output);
const
n=50000;
var
a,b,c,d,sum,left,right:array[1..1000000] of longint;
i,j,k,m,t,s:longint;
procedure creat(root,h,t:longint);
var
m:longint;
begin
if h>t then exit;
if h=t then
begin
sum[root]:=0;
left[root]:=h;
right[root]:=t;
end
else
begin
m:=(h+t) div 2;
sum[root]:=0;
left[root]:=h;
right[root]:=t;
creat(root*2,h,m);
creat(root*2+1,m+1,t);
end;
end;
procedure change(root,i:longint) ;
begin
if (left[root]=i) then
begin
if left[root]=right[root] then sum[root]:=1
else
begin
change(root*2+1,i);
change(root*2,i);
sum[root]:=sum[root*2]+sum[root*2+1];
end;
end;
end;
function count(root,h,t:longint):longint;
begin
if (h>right[root])or(t -
0
贪心
type
link =^node;
node =record
a,c:longint;
n:link;
end;
var
s :array[-1..50000]of longint;
p :link;
f :array[0..50000]of link;
vis :array[0..50000]of boolean;
n,i,x,y,k,min,max,j :longint;
begin
fillchar(vis,sizeof(vis),false);
readln(n);
max:=0;
for i:=1 to n do
begin
readln(x,y,k);
if y>max then max:=y;
if not vis[y] then
begin
new(f[y]);
f[y]:=nil;
vis[y]:=true;
end;
new(p);
p^.a:=x-1;
p^.c:=k;
p^.n:=f[y];
f[y]:=p;
end;
fillchar(s,sizeof(s),0);
for i:=1 to max do
if not vis[i] then s[i]:=s else
begin
p:=f[i];
min:=s;
k:=i;
while pnil do
begin
if s[p^.a]+p^.c>min then
begin
min:=s[p^.a]+p^.c;
k:=p^.a+1;
end;
p:=p^.n;
end;
s[i]:=min;
j:=i-1;
while (j>=k)and(s[i]-s[j]>i-j) do
begin
s[j]:=s[i]-i+j;
dec(j);
end;
end;
writeln(s[max]);
end. -
0
181818181818 LV 10 @ 2009-08-31 11:41:17
差分约束系统
但不会编
Lifi
LV 10
@ 2019-09-05 23:26:47
