Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 580 words)

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;
    }
    
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 55 words)

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

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 193 words)

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();
    }

}
Posted Updated  Semprathlon / Simfae Dean Developing / Environment5 minutes read (About 737 words)

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

Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker2
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview4
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python11
RMQ1
React2
Regional3
Repost1
Ryzen1
SQLserver1
SSH1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
TypeScript2
UEFI4
UX1
Ubuntu15
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network2
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×