43 条题解
-
3
!TNT! LV 8 @ 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); }查分约束：
-
1
Sky1231 (sky1231) LV 10 @ 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(); } void add_edge(int x,int y,int d) { 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++) { add_edge(i,n+1,i); add_edge(n+2,i,0); if (i>0) { add_edge(i-1,i,0); add_edge(i,i-1,1); } } for (int i=1;i<=m;i++) { int B,E,T; scanf("%d%d%d",&B,&E,&T); add_edge(B-1,E,-T); } printf("%d\n",-bfs()); } } int main() { dts::main(); } -
0
2501953407 LV 8 @ 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;
} -
0
#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;
} -
0
robert_xuzhen LV 8 @ 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;
} -
0
#include<cstdio> #include<algorithm> struct node{ int b,e,t; }; node melon[3010]; bool f[5010]={0}; inline int read() { 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() { int n=read(),m=read(),ans=0; for (int i=1;i<=m;++i) { melon[i].b=read(); melon[i].e=read(); melon[i].t=read(); } 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; } -
0
编译通过...├ 测试数据 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，不解。。。）
-
0
song19931218 LV 9 @ 2009-11-07 16:12:38
记录号 Flag 得分 记录信息 环境 评测机 程序提交时间
R1715495 Accepted 100 From song19931218－
P1589 FPC Vijos Easy 2009-11-7 16:04:44From maa04
笨笨的西瓜种植（赛） 笨笨工作室系列 系列编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 88ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 56ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 25ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：169msdfs版的spfa写丑了,没能秒杀
-
0
典型的差分约束系统，经典的模型
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msprogram 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
i:=head[q[r]];
while i0 do begin
if dist[e[i]] -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
SecretAgent LV 10 @ 2009-10-09 16:46:19
给按头区间排序,
再从后往前枚举快排写错
交了3次.. -
0
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用时不同啊！ -
0
希望有些同学尊重他人劳动成果，不要盗用他人题解和代码，就算盗用了也别说是你做的
马甲虽然穿在身，我心依然是中国心
-
hsez_woixia1314 @ 2016-08-26 17:00:21
sb
-
-
0
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
readln(n,m);
for i:=1 to m do
begin
readln(con,con,con);
inc(b[con]);
inc(e[con+1]);
end;
for i:=1 to m-1 do
for j:=i+1 to m do
if con -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 41ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 88ms
├ 测试数据 05：答案正确... 88ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 166ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：392ms
没有秒杀是因为我偷懒了，在对右端点排序时我没有快排，用了冒泡！
感谢1s的题解
!TNT!
LV 8
@ 2017-05-30 16:16:05
