43 条题解

• @ 2017-05-30 16:16:05

正解应该是差分约束，但是因为题目数据特殊性，可以用贪心

``````#include<stdio.h>
#include<algorithm>
struct dx{ int b,e,v; } s[3010]; bool v[5010];
inline bool c1(dx a,dx b){ return a.e==b.e?a.b<b.b:a.e<b.e; }
int main(){
int n,m,a=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
scanf("%d%d%d",&s[i].b,&s[i].e,&s[i].v);
std::sort(s,s+m,c1);
for(int i=0;i<m;++i){
for(int j=s[i].b;j<=s[i].e;++j) s[i].v-=v[j];
for(int j=s[i].e;s[i].v>0;--j)
if(!v[j]) { v[j]=1; s[i].v--; ++a; }
}
printf("%d\n",a);
}
``````

查分约束：

• @ 2020-11-13 08:55:17

題解（差分約束系統）
設從第0格到第i格一共種植X(i)個🍉

X(i-1)<=Xi<=X(i-1)+1(1<=i<=n),
0<=X(i)<=i(0<=i<=n),
對任意B,E,T有X(E)-X(B-1)>=T
求X(n)的最小值，將不等式轉化為
-X(n+1)<=-X(i)+i(0<=i<=n),
-X(i)<=-X(n+2)+0(0<=i<=n),
X(n+1)=X(n+2)=0,
-X(i)<=-X(i-1)+0(1<=i<=n),
-X(i-1)<=-X(i)+1(1<=i<=n),
對任意B,E,T有-X(E)<=-X(B-1)-T

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> vis;
vector<int> dist;
vector<vector<int>> e;
vector<vector<int>> l;
deque<int> q;

void clear()
{
e.resize(n+3),l.resize(e.size());
for (int i=0;i<e.size();i++)
e[i].clear(),l[i].clear();
}
{
e[x].push_back(y);
l[x].push_back(d);
}
int bfs()
{
vis.resize(e.size());
dist.resize(e.size(),oo_max);
dist[n+1]=dist[n+2]=0;
for (q.clear(),vis[n+1]=vis[n+2]=1,q.push_back(n+1),q.push_back(n+2);!q.empty();vis[q.front()]=0,q.pop_front())
{
int now=q.front();
for (int i=0;i<e[now].size();i++)
if (dist[now]+l[now][i]<dist[e[now][i]])
{
dist[e[now][i]]=dist[now]+l[now][i];
if (vis[e[now][i]]==0)
vis[e[now][i]]=1,q.push_back(e[now][i]);
}
}
return dist[n];
}

void main()
{
scanf("%d%d",&n,&m);
clear();
for (int i=0;i<=n;i++)
{
if (i>0)
{
}
}
for (int i=1;i<=m;i++)
{
int B,E,T;
scanf("%d%d%d",&B,&E,&T);
}
printf("%d\n",-bfs());
}
}

int main()
{
dts::main();
}
``````
• @ 2018-06-15 21:51:32

Accepted

状态 耗时 内存占用

#1 Accepted 4ms 384.0 KiB
#2 Accepted 7ms 256.0 KiB
#3 Accepted 3ms 340.0 KiB
#4 Accepted 9ms 360.0 KiB
#5 Accepted 7ms 352.0 KiB
#6 Accepted 5ms 352.0 KiB
#7 Accepted 10ms 256.0 KiB
#8 Accepted 3ms 364.0 KiB
#9 Accepted 8ms 372.0 KiB
#10 Accepted 9ms 380.0 KiB

#include<cstdio>
#include<algorithm>
using namespace std;
bool b[5005];
struct xigua
{
int x,y,t;
}a[3005];
bool cmp(xigua a,xigua b)
{
return a.y<b.y;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].t);
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++)
{
int t=0;
for(int j=a[i].y;j>=a[i].x;j--)
if(b[j])
t++;
int sum=0;
for(int j=a[i].y;sum<(a[i].t-t);j--)
{
if(!b[j])
{
b[j]=1;
sum++;
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
if(b[i])
ans++;
printf("%d",ans);
return 0;
}

• @ 2017-04-08 10:50:57

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
struct wa
{
int b,e,t;
bool operator<(const wa & a) const
{
if(e!=a.e) return e<a.e;
return b<a.b;
}
}w[3005];
int m,n,i,b,e,t,ans,j;
bool f[5005];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++) scanf("%d%d%d",&w[i].b,&w[i].e,&w[i].t);
sort(w,w+m);
for(i=1;i<=m;i++)
{
for(j=w[i].b;j<=w[i].e&&w[i].t>0;j++)
{
if(f[j]) w[i].t--;

}
for(j=w[i].e;j>=w[i].b&&w[i].t>0;j--)
{
if(!f[j])
{
f[j]=1;
ans++;
w[i].t--;
}
}
}
printf("%d\n",ans);
system("pause");
return 0;
}

• @ 2017-03-31 10:28:44

#include<iostream>
#include<memory.h>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
using namespace std;

struct node
{
int s,e,t;
bool operator < (const node & t) const
{
if(e != t.e) return e < t.e;
return s < t.s;
}
};
node p[3005];
int n,m,b,e,t,i,j,ans;
bool f[5005];

int main()
{
cin >> n >> m;
for( i = 0; i < m; ++i) cin >> p[i].s >> p[i].e >> p[i].t ;
sort(p,p+m);
for( i = 0; i < m; ++i)
{
for( j = p[i].s; j <= p[i].e && p[i].t; ++j)
{
if(f[j]) p[i].t--;
}
for( j = p[i].e; j >= p[i].s && p[i].t; --j)
{
if(!f[j])
{
p[i].t--;
f[j] = 1;
ans++;
}
}
}
cout << ans << endl;
//while(1);
return 0;
}

• @ 2016-11-26 10:49:46
``````#include<cstdio>
#include<algorithm>
struct node{
int b,e,t;
};
node melon[3010];
bool f[5010]={0};
{
char ch=getchar();int ans=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') {ans*=10;ans+=ch-'0';ch=getchar();}
return ans;
}
int my_comp(const node &a,const node &b)
{
if (a.e<b.e) return 1;
if (a.e>b.e) return 0;
return a.b<b.b;
}
int main()
{
for (int i=1;i<=m;++i)
{
}
std::sort(melon+1,melon+m+1,my_comp);
for (int i=1;i<=m;++i)
{
int q=melon[i].b;
while (q<=melon[i].e&&melon[i].t)
{if (f[q])
--melon[i].t;
++q;
}
int j=1;
while (melon[i].t>0)
{
if (!f[melon[i].e-j+1])
{f[melon[i].e-j+1]=1;melon[i].t--;++ans;}
++j;
}
}
printf("%d\n",ans);
return 0;
}
``````
• @ 2010-03-26 19:54:16

编译通过...├ 测试数据 01：答案正确...ms├ 测试数据 02：答案正确...ms├ 测试数据 03：答案正确...ms├ 测试数据 04：答案正确...ms├ 测试数据 05：答案正确...ms├ 测试数据 06：答案正确...ms├ 测试数据 07：答案正确...ms├ 测试数据 08：答案正确...ms├ 测试数据 09：答案正确...ms├ 测试数据 10：答案正确...msAccepted 有效得分：100 有效耗时：0ms

还是差分约束好~

SPFA秒。。。

（PS.树状数组优化的贪心竟然会WA，不解。。。）

• @ 2009-11-07 16:12:38

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1715495 Accepted 100 From song19931218－

P1589 FPC Vijos Easy 2009-11-7 16:04:44

From maa04

笨笨的西瓜种植（赛） 笨笨工作室系列 系列

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 56ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：169ms

dfs版的spfa写丑了,没能秒杀

• @ 2009-11-04 16:01:40

典型的差分约束系统，经典的模型

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program vijos_1589;

const

maxV=5000;

maxM=3000;

maxE=maxM+(maxV+1)2);

dist[0]:=0;

fillChar(v,sizeof(v),false);

v[0]:=true;

num:=1;

repeat

while i0 do begin

if dist[e[i]]

• @ 2009-11-01 14:56:32

还是查分约束稳~~~~~~

• @ 2009-10-24 20:19:12

大西瓜大西瓜！！

• @ 2009-10-21 18:18:50

水题

由于是1444的程序拿来，所以有点问题没改。。。超时好几次....

• @ 2009-10-13 20:12:03

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-10-09 16:46:19

给按头区间排序,

再从后往前枚举

快排写错

交了3次..

• @ 2009-10-04 16:10:56

差分约束

• @ 2009-10-03 18:23:59

Vivid Puppy:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Vijos Dragon:

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：34ms

评测机不同程序AC用时不同啊！

• @ 2009-08-27 22:27:18

希望有些同学尊重他人劳动成果，不要盗用他人题解和代码，就算盗用了也别说是你做的

马甲虽然穿在身，我心依然是中国心

• @ 2016-08-26 17:00:21

sb

• @ 2009-08-26 21:28:41

program p1589;

var f,b,e:array[0..5001]of integer;

use:array[0..5001]of boolean;

con:array[0..3000,1..3]of integer;

sum,i,j,k,n,m:longint;

procedure swap(a,b:integer);

var k:integer;

begin

k:=con[a,1];con[a,1]:=con;con:=k;

k:=con[a,2];con[a,2]:=con;con:=k;

k:=con[a,3];con[a,3]:=con;con:=k;

end;

procedure cal(x:integer);

var k,i,j:integer;

begin

for i:=con[x,1] to con[x,2] do

if use[i] then dec(con[x,3]);

for i:=1 to con[x,3] do

begin

k:=0;

for j:=con[x,1] to con[x,2] do

if not use[j] then

if f[j]>=f[k] then k:=j;

use[k]:=true;

end;

for i:=con[x,1] to con[x,2] do

dec(f[i]);

end;

begin

for i:=1 to m do

begin

inc(b[con]);

inc(e[con+1]);

end;

for i:=1 to m-1 do

for j:=i+1 to m do

if con

• @ 2009-08-14 19:24:38

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

差分约束系统

1次ac

• @ 2009-08-14 16:20:46

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 41ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 88ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：392ms

没有秒杀是因为我偷懒了，在对右端点排序时我没有快排，用了冒泡！

感谢1s的题解

ID
1589

6

2000

538

27%

1