二分图染色秒杀
思路：用深搜给节点染色。若(v,u)>k，则u应与v不同色。出现矛盾直接exit。

#include <iostream>
#include <cstdlib>

using namespace std;

int velocity[2000];
int colour[2000];

void paint(int v, int clr, int num, int bound){
colour[v] = clr;
for(int u=0; u<num; u++){
if(abs(velocity[u]-velocity[v]) <= bound)
continue;
if(colour[u] == 0){
paint(u, -clr, num, bound);
}else if(colour[u] == clr){
cout << "No" << endl;
exit(0);
}
}
}
int main(){
int num, bound;

cin >> num >> velocity[0] >> bound;
for(int i=1; i<num; i++){
cin >> velocity[i];
colour[i] = 0;
}
paint(0, 1, num, bound);
cout << "Yes" << endl;

return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;

long long int v[1000000];
vector<long long int> a;

int main()
{
int n,m;
long long int k;
cin>>n>>m>>k;
v[1]=m;
for(int i=2; i<=n; i++)
cin>>v[i];
sort(v+1,v+n);
a.push_back(v[1]);

for(int i=2; i<=n; i++)
if(abs(v[i]-v[i-1]) > k)
a.push_back(v[i]);

if(a.size()>2)
cout<<"No";
else
cout<<"Yes";
system("pause");
return 0;

}

weak
P1609银翼の舞
Accepted

记录信息

评测状态 Accepted
题目 P1609 银翼の舞
递交时间 2015-07-08 23:52:20
代码语言 C++
评测机 VijosEx
消耗时间 15 ms
消耗内存 288 KiB
评测时间 2015-07-08 23:52:31

评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:29:34: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
scanf( "%d" , &speed[i] );
^

测试数据 #0: Accepted, time = 15 ms, mem = 288 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 288 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 284 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 288 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 288 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 288 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 284 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 288 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 288 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 288 KiB, score = 10

Accepted, time = 15 ms, mem = 288 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n , v , k;
int i;
long long speed[1500 + 10];

long long max( long long a , long long b )
{
if( a > b )
return a;
return b;
}

long long min( long long a , long long b )
{
if( a > b )
return b;
return a;
}

int main()
{
scanf( "%d %d %d" , &n , &v , &k );
for( i = 0 ; i < n - 1 ; i++ )
scanf( "%d" , &speed[i] );
sort( speed , speed + n - 1 );
for( i = 0 ; i < n - 1 ; i++ )
if( speed[i] - speed[0] > k )
break;
if( speed[ n - 2 ] - speed[i] > k )
cout << "No\n";
else
cout << "Yes\n";
return 0;

var
a:array[1..100000]of int64;
n,k,i:longint;
procedure qsort(l,r:longint);
var
i,j,mid,t:int64;
begin
i:=l;j:=r;mid:=a[(l+r)shr 1];
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=a[i];inc(i);dec(j);end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
begin
readln(n,a[1],k);
for i:=2 to n do read(a[i]);
qsort(1,n);
for i:=1 to n do
if (a[i]-a[1]>k)and(a[n]-a[i]>k) then begin writeln('No');halt;end;
writeln('Yes');
end.

匈牙利写残了，tle第二个点，差不多是1.13s左右，差不多不超时，懒得下那个快排的方法。写匈牙利的第二个数据点直接cheat吧！或者哪个大神私信我怎么写二分不超时。

二分图？！傻掉了。。

靠，考虑了幻影和幻影错了，没考虑居然对了！！！坑···

第二个点坑了老子5次！操！

其实很简单啊，首先读入，然后依次判断某个幻影能否跟基德从一号门逃出，不能的话再保存至另一个数组中，再判断这个数组里有没有两数之差大于k，有输出no，没有yes，就可以啦！看清题啊！！！！！！

本人代码：program P1609;

var

n,v,k,i,j,l:longint;

a,b:array[1..1500] of longint;

begin

read(n,v,k);

l:=1;

for i:=1 to n-1 do

read(a[i]);

for i:=1 to n-1 do

if abs(a[i]-v)>k then begin b[l]:=a[i]; l:=l+1; end;

for i:=1 to l do

for j:=1 to l do

if abs(b[i]-b[j])>k then begin write('No'); halt; end;

write('Yes');

end.

编译通过...

├ 测试数据 01：答案正确... (0ms, 584KB)

├ 测试数据 02：答案正确... (0ms, 584KB)

├ 测试数据 03：答案正确... (0ms, 584KB)

├ 测试数据 04：答案正确... (0ms, 584KB)

├ 测试数据 05：答案正确... (0ms, 584KB)

├ 测试数据 06：答案正确... (0ms, 584KB)

├ 测试数据 07：答案正确... (0ms, 584KB)

├ 测试数据 08：答案正确... (0ms, 584KB)

├ 测试数据 09：答案正确... (0ms, 584KB)

├ 测试数据 10：答案正确... (0ms, 584KB)

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

Accepted / 100 / 0ms / 584KB

数据真水……冒泡都是0ms，一次AC

思路：读入所有的速度后进行排序，然后比较相邻的两个速度的差是否大于k，大于就把布尔变量b的值改为false。如果b的值已经是false，就说明有一个门不能再进了，即失败。

附程序：

{

ID:darkgod-z

PROG:vijos P1609

HANG:PASCAL

}

var

k,n,i,j,t:integer;

v:array [1..1500] of longint;

b:boolean;

begin

readln(n,v[1],k);

for i:=2 to n do read(v[i]);

readln;

for i:=1 to n-1 do

for j:=i+1 to n do

if v[i]>v[j] then begin

t:=v[i];

v[i]:=v[j];

v[j]:=t;

end;

b:=true;

for i:=2 to n do

if v[i]-v>k then

if b then b:=false

else begin

writeln('No');

exit;

end;

writeln('Yes');

end.

Flag 　　Accepted

题号 　　P1609

类型(?) 　　其它

通过 　　895人

提交 　　1897次

通过率 　　47%

难度 　　1

真够水的....

var a:array[1..1500]of longint; d,x,n,v,k,i,j:longint; l:boolean;

begin

readln(n,v,k);

d:=v;

x:=v;

for i:=2 to n do

begin

read(a[i]);

if a[i]>d then d:=a[i];

if a[i]=k)and((d-a[i])>=k) then begin l:=false; break; end;

end;

if l=true then write('Yes') else write('No');

end.

农夫山泉有点甜.........

program p1609;

var a:integer;

begin

randomize;

a:=random(100);

if odd(a) then writeln('Yes')

else writeln('No');

end.

刷RP。。。

当初比赛看一眼就放弃了 现在突然发现居然是怎么水的题..!

别的和楼下差不多 亮点只有一句:

if RPWT then writeln('No') else writeln('Yes') ;

---|交完AC2分钟后突然发现我居然没有考虑2个门的情况= =

本菜菜菜菜菜菜菜鸟宣告一星半~O(∩_∩)O

program dance;

var

n,k,max,min,i:longint;

can:boolean;

v:array[1..maxint] of longint;

begin

readln(n,v[1],k);

max:=v[1];

min:=v[1];

for i:=2 to n do

begin

read(v[i]);

if v[i]>max then max:=v[i];

if v[i]=k) and (max-v[i]>=k) then

begin

can:=false;

break;

end;

if can then writeln('Yes') else writeln('No');

end.

真的是瓶水

program p1609;

var n,k,i,j,tmp,p:longint;

a:array[1..2000] of longint;

max1,max2,min1,min2:longint;

begin

readln(n,a[1],k);

for i:=2 to n do read(a[i]);

for i:=1 to n-1 do

begin

p:=i;

for j:=i+1 to n do

if a[p]>a[j] then p:=j;

tmp:=a[p]; a[p]:=a[i]; a[i]:=tmp;

end;

max1:=a[n]; min2:=a[1];

for i:=n downto 1 do

if a[i]

我的题解，水题阿。因为把No打成NO，只过了四个点。再改，发现把k打成v了，改完，AC了。

Flag 　　Accepted

题号 　　P1609

类型(?) 　　其它

通过 　　777人

提交 　　1590次

通过率 　　49%

难度 　　1

program P1609;

var n,i,k,s,j:integer;

v:longint;

a:array[1..1500] of longint;

begin

read(n,v,k);

for i:= 1 to n-1 do read(a[i]);

for i:=1 to n-1 do

for j:= i+1 to n-1 do

begin

if (a[j]-a[i]>k) and (a[j+1]-a[j]>k) then begin writeln('No');exit;end

else s:=0;

end;

if s=0 then writeln('Yes');

end.

program kid;var x,n,i,v,k:longint;begin readln(n,v,k); for i:=1 to n-1 do begin read(x); if x-v>k then begin writeln('No'); halt end; end; writeln('Yes');end.

我的题解，别说你看不见

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次没看到2个门,10行程序90分`- -

改了一下结果60分`= = 更窘,

后来索性排一个快排