BestCoder

Solved Problems
ZYB’s Biology
ZYB’s Game
ZYB’s Premutation

ZYB’s Biology

平淡无奇的匹配

ZYB’s Game

惊异于“最优策略”的选取,最终结果竟与奇偶性挂钩。

ZYB’s Premutation

常规题型,旧题重演,竟然跑偏了。
半年多前的某基础题的逆向问题。
同样用线段树或树状数组解决,关键是实现查找第k大的数、删除第k大的数并维护。也有基于查询数的更抽象高效的解法。
树状数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
* Dec 5, 2015 8:39:53 PM
* PrjName: 1205-03-2
* @semprathlon
*/
import java.io.*;
import java.util.*;
public class Main {
static int[] a,f;
static BIT tr;
static HashSet<Integer> st=new HashSet<Integer>();
static void print(int[] a,PrintWriter out){
int n=a.length-1;
for(int i=1;i<=n;i++)
out.print(a[i]+(i<n?" ":""));
out.println();
}
public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
PrintWriter out=new PrintWriter(System.out);
int T=in.nextInt();
// tr=new BIT(5);
// out.print(tr.lowbit(2));
while(T-->0){
int n=in.nextInt();
a=new int[n+1];
f=new int[n+1];
tr=new BIT(n);
for(int i=1;i<=n;i++){
f[i]=in.nextInt();
tr.add(i, 1);
}

for(int i=n;i>=1;i--){
f[i]-=f[i-1];
int tmp=tr.find(i-f[i]-1);
// out.println(i+","+f[i]+","+tmp);
a[i]=tmp;
tr.add(tmp, -1);
}
print(a, out);
}
out.flush();
out.close();
}
}
class BIT{
int[] data;
int sz;
BIT(){}
BIT(int _sz){
sz=_sz;
data=new int[sz+1];
}
int lowbit(int x){
return x&(-x);
}
void add(int p,int v){
while(p<=sz){
data[p]+=v;
p+=lowbit(p);
}
}
int sum(int p){
int res=0;
while(p>0){
res+=data[p];
p-=lowbit(p);
}
return res;
}
int find(int p){
int l=1,r=sz;
while(l<r){
int mid=(l+r)>>1;
if (sum(mid)<=p)
l=mid+1;
else
r=mid;
}

return l;
}
}

线段树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
* Dec 6, 2015 4:42:31 PM
* PrjName: 1205-03-3
* @semprathlon
*/
import java.io.*;
import java.util.*;
public class Main {
static int[] a,f;
static ST tr;
static HashSet<Integer> st=new HashSet<Integer>();
static void print(int[] a,PrintWriter out){
int n=a.length-1;
for(int i=1;i<=n;i++)
out.print(a[i]+(i<n?" ":""));
out.println();
}
public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
PrintWriter out=new PrintWriter(System.out);
int T=in.nextInt();
while(T-->0){
int n=in.nextInt();
a=new int[n+1];
f=new int[n+1];
tr=new ST(n);
tr.build(1, 1, n);
for(int i=1;i<=n;i++)
f[i]=in.nextInt();

for(int i=n;i>=1;i--){
f[i]-=f[i-1];
int tmp=tr.query(1, 1, n, f[i]+1);
// out.println(i+","+f[i]+","+tmp);
a[i]=tmp;

}
print(a, out);
}
out.flush();
out.close();
}
}
class ST{
int[] l,r,m,v;
int sz;
ST(){}
ST(int _sz){
sz=_sz<<2;
l=new int[sz];
r=new int[sz];
m=new int[sz];
v=new int[sz];
}
void build(int k,int x,int y){
l[k]=x;r[k]=y;m[k]=(x+y)>>1;
if (x<y){
build(k<<1,x,m[k]);
build(k<<1|1,m[k]+1,y);
}
v[k]=y-x+1;
}
int query(int k,int x,int y,int q){
if (l[k]==r[k]){
v[k]=0;
return l[k];
}
int res=0;
if (v[k<<1|1]>=q)
res=query(k<<1|1, m[k]+1, y, q);
else
res=query(k<<1,x,m[k],q-v[k<<1|1]);
v[k]=v[k<<1]+v[k<<1|1];
return res;
}

}

EC-final赛前一周

为信仰充值,与神犇赛码!年度最终决战,剑不出鞘更待何时?下周末双日,12.12~13,2015 ACM/ICPC EC-final 上海大学站,蓄势待发!全力备战

wpid-screenshot_2015-12-05-21-55-28.png wpid-230c7f4a3a36cc1f.jpg wpid-351324c2c7cdabb1.jpg wpid-screenshot_2015-12-05-21-55-05.png

wpid-screenshot_2015-12-05-22-02-33.png wpid-img_20151205_220342.jpg

BestCoder

Solved Problems To be solved
Numbers Array
Sum

Numbers

没话可说。

Sum

基础一维DP的变异

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Nov 28, 2015 8:04:23 PM
* PrjName: Bc64-02
* @semprathlon
*/
import java.io.*;
import java.util.*;
public class Main {
static int[] a,s,f;
static int fn(int x){
return (1890*x+143)%10007;
}
public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
PrintWriter out=new PrintWriter(System.out);
while(in.nextLine()!=null){
int n=in.nextInt();
a=new int[n+1];
s=new int[n+1];
f=new int[n+1];
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
s[i]=s[i-1]+a[i];
}
int ans=s[n];
for(int i=1;i<=n;i++){
f[i]=Math.max(f[i-1]+fn(a[i]), s[i]);
ans=Math.max(ans, f[i]+s[n]-s[i]);
}
out.println(ans);
}
out.flush();
out.close();
}

}

Configure OpenCV with Python for Mac

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
-- General configuration for OpenCV 3.0.0 =====================================
-- Version control: unknown
--
-- Platform:
-- Host: Darwin 15.0.0 x86_64
-- CMake: 3.3.2
-- CMake generator: Unix Makefiles
-- CMake build tool: /usr/bin/make
-- Configuration: RELEASE
--
-- C/C++:
-- Built as dynamic libs?: YES
-- C++ Compiler: /Library/Developer/CommandLineTools/usr/bin/c++ (ver 7.0.0.7000176)
-- C++ flags (Release): -fsigned-char -W -Werror=return-type -Werror=non-virtual-dtor -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wno-narrowing -Wno-delete-non-virtual-dtor -Wno-unnamed-type-template-args -fdiagnostics-show-option -Wno-long-long -Qunused-arguments -Wno-semicolon-before-method-body -fno-omit-frame-pointer -msse -msse2 -mno-avx -msse3 -mno-ssse3 -mno-sse4.1 -mno-sse4.2 -fvisibility=hidden -fvisibility-inlines-hidden -O3 -DNDEBUG -DNDEBUG
-- C++ flags (Debug): -fsigned-char -W -Werror=return-type -Werror=non-virtual-dtor -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wno-narrowing -Wno-delete-non-virtual-dtor -Wno-unnamed-type-template-args -fdiagnostics-show-option -Wno-long-long -Qunused-arguments -Wno-semicolon-before-method-body -fno-omit-frame-pointer -msse -msse2 -mno-avx -msse3 -mno-ssse3 -mno-sse4.1 -mno-sse4.2 -fvisibility=hidden -fvisibility-inlines-hidden -g -O0 -DDEBUG -D_DEBUG
-- C Compiler: /Library/Developer/CommandLineTools/usr/bin/cc
-- C flags (Release): -fsigned-char -W -Werror=return-type -Werror=non-virtual-dtor -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wno-narrowing -Wno-delete-non-virtual-dtor -Wno-unnamed-type-template-args -fdiagnostics-show-option -Wno-long-long -Qunused-arguments -Wno-semicolon-before-method-body -fno-omit-frame-pointer -msse -msse2 -mno-avx -msse3 -mno-ssse3 -mno-sse4.1 -mno-sse4.2 -fvisibility=hidden -fvisibility-inlines-hidden -O3 -DNDEBUG -DNDEBUG
-- C flags (Debug): -fsigned-char -W -Werror=return-type -Werror=non-virtual-dtor -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wno-narrowing -Wno-delete-non-virtual-dtor -Wno-unnamed-type-template-args -fdiagnostics-show-option -Wno-long-long -Qunused-arguments -Wno-semicolon-before-method-body -fno-omit-frame-pointer -msse -msse2 -mno-avx -msse3 -mno-ssse3 -mno-sse4.1 -mno-sse4.2 -fvisibility=hidden -fvisibility-inlines-hidden -g -O0 -DDEBUG -D_DEBUG
-- Linker flags (Release):
-- Linker flags (Debug):
-- Precompiled headers: NO
-- Extra dependencies: -framework OpenCL -framework Cocoa -framework QTKit -framework QuartzCore -framework AppKit
-- 3rdparty dependencies: libjpeg libwebp libpng libtiff libjasper IlmImf zlib ippicv
--
-- OpenCV modules:
-- To be built: hal core flann imgproc ml photo video imgcodecs shape videoio highgui objdetect superres ts features2d calib3d stitching videostab python2
-- Disabled: world
-- Disabled by dependency: -
-- Unavailable: cudaarithm cudabgsegm cudacodec cudafeatures2d cudafilters cudaimgproc cudalegacy cudaobjdetect cudaoptflow cudastereo cudawarping cudev java python3 viz
--
-- GUI:
-- QT: NO
-- Cocoa: YES
-- OpenGL support: NO
-- VTK support: NO
--
-- Media I/O:
-- ZLib: build (ver 1.2.8)
-- JPEG: build (ver 90)
-- WEBP: build (ver 0.3.1)
-- PNG: build (ver 1.5.12)
-- TIFF: build (ver 42 - 4.0.2)
-- JPEG 2000: build (ver 1.900.1)
-- OpenEXR: build (ver 1.7.1)
-- GDAL: NO
--
-- Video I/O:
-- DC1394 1.x: NO
-- DC1394 2.x: NO
-- FFMPEG: NO
-- codec: NO
-- format: NO
-- util: NO
-- swscale: NO
-- resample: NO
-- gentoo-style: NO
-- GStreamer: NO
-- OpenNI: NO
-- OpenNI PrimeSensor Modules: NO
-- OpenNI2: NO
-- PvAPI: NO
-- GigEVisionSDK: NO
-- QuickTime: NO
-- QTKit: YES
-- V4L/V4L2: NO/NO
-- XIMEA: NO
-- gPhoto2: NO
--
-- Other third-party libraries:
-- Use IPP: 8.2.1 [8.2.1]
-- at: /Users/semprathlon/opencv-3.0.0/3rdparty/ippicv/unpack/ippicv_osx
-- Use IPP Async: NO
-- Use Eigen: NO
-- Use TBB: NO
-- Use OpenMP: NO
-- Use GCD YES
-- Use Concurrency NO
-- Use C=: NO
-- Use pthreads for parallel for:
-- NO
-- Use Cuda: NO
-- Use OpenCL: YES
--
-- OpenCL:
-- Version: static
-- libraries: -framework OpenCL
-- Use AMDFFT: NO
-- Use AMDBLAS: NO
--
-- Python 2:
-- Interpreter: /usr/bin/python2.7 (ver 2.7.10)
-- Libraries: /usr/lib/libpython2.7.dylib (ver 2.7.10)
-- numpy: /System/Library/Frameworks/Python.framework/Versions/2.7/Extras/lib/python/numpy/core/include (ver 1.8.0rc1)
-- packages path: lib/python2.7/site-packages
--
-- Python 3:
-- Interpreter: NO
--
-- Python (for build): /usr/bin/python2.7
--
-- Java:
-- ant: NO
-- JNI: /System/Library/Frameworks/JavaVM.framework/Headers /System/Library/Frameworks/JavaVM.framework/Headers /System/Library/Frameworks/JavaVM.framework/Headers
-- Java wrappers: NO
-- Java tests: NO
--
-- Matlab:
-- mex: NO
--
-- Documentation:
-- Doxygen: NO
-- PlantUML: NO
--
-- Tests and samples:
-- Tests: YES
-- Performance tests: YES
-- C/C++ Examples: YES
--
-- Install path: /usr/local
--
-- cvconfig.h is in: /Users/semprathlon/opencv-3.0.0/release
-- -----------------------------------------------------------------
--
-- Configuring done
-- Generating done
CMake Warning:
Manually-specified variables were not used by the project:

BUILD_PYTHON_SUPPORT

Java代码编译命令的微小而关键的细节

今天室友问我,为什么javac编译源代码完成后,用java执行就报错Error: Could not find or load main class呢?

我习惯性地认为是环境变量的值不合适(百度上很多解答也类同),但检查后并无问题……

Read more

Bestcoder

Solved Problems
Clarke and food
Clarke and five-pointed star

Clarke and food

非常轻易地完成填充。

Clarke and five-pointed star

辛辛苦苦地敲完了又挂了。。。

我这里独立思考得到的结论是:
以五角星的一个顶点为参考点,则该点必在其他四点所构成的四边形之外,且其他四点相对于该点所成的张角之和是确定的;尽管随着所取的四个点的顺序不同会有不同的值,但也仅有三种情况。
可是测样例数据时不知怎的多加了一个待判值,结果WA了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* Nov 14, 2015 7:35:56 PM
* PrjName: Bc62-02
* @semprathlon
*/
import java.io.*;
import java.util.*;
public class Main {
static Point[] pt=new Point[5];
static PrintWriter out=new PrintWriter(System.out);
static boolean check1(){
return !Point.isPointInRect(pt[0], pt[1], pt[2], pt[3], pt[4])&&
!Point.isPointInRect(pt[1], pt[2], pt[3], pt[4], pt[0])&&
!Point.isPointInRect(pt[2], pt[3], pt[4], pt[0], pt[1])&&
!Point.isPointInRect(pt[3], pt[4], pt[0], pt[1], pt[2])&&
!Point.isPointInRect(pt[4], pt[0], pt[1], pt[2], pt[3]);
}
static boolean check0(Point p,Point a,Point b,Point c,Point d){
double v1=Math.acos(-1.0)/5.0,v2=v1*2.0,v3=v1*3.0;
double angle=Vector.angle2(p, a, b)+Vector.angle2(p, b, c)+Vector.angle2(p, c, d);
angle=Math.abs(angle);
// out.println(v1+","+v2+","+v3+","+angle);
return Point.dcmp(angle-v1)==0||Point.dcmp(angle-v2)==0||Point.dcmp(angle-v3)==0;
}
static boolean check2(){
return check0(pt[0], pt[1], pt[2], pt[3], pt[4])&&
check0(pt[1], pt[2], pt[3], pt[4], pt[0])&&
check0(pt[2], pt[3], pt[4], pt[0], pt[1])&&
check0(pt[3], pt[4], pt[0], pt[1], pt[2])&&
check0(pt[4], pt[0], pt[1], pt[2], pt[3]);
}
public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);

int T=in.nextInt();
while(T-->0){
for(int i=0;i<5;i++)
pt[i]=new Point(in.nextDouble(), in.nextDouble());
if (pt[0].equals(pt[1])&&pt[1].equals(pt[2])&&pt[2].equals(pt[3])&&pt[3].equals(pt[4])&&pt[4].equals(pt[0])){
out.println("Yes");continue;
}
out.println(check2()?"Yes":"No");
}
out.flush();
out.close();
}
}