Veröffentlicht am

题意：

有很多牛，每头牛有两个吃草的要求，每个种草有这两种属性，并且每头牛吃的草都不能一样，问你价格最少是多少

题解：

先考虑没有第二维的限制，那么问题就转换成了一个很简单的贪心问题，每次二分既可。现在加入第二维的限制，如果要保持运算中不受影响，那么必须把第二维的限制排序后，像一维的那样维护一个multiset即可。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/POJ/3622.cpp

Veröffentlicht am | in

题意：

给你平面上若干直线，问你在$(L,R)$这个区间内，有多少直线会相交

题解：

想象一下怎样的直线能够相交，设直线$Line_1$，直线$Line_2$与$x=L$的交点分别是$L_1,L_2$，与$x=R$的交点分别是$R_1,R_2$，设$L_1>L_2$，那么如果这两根直线在这个区间相交，则必有$R_1<R_2$。
所以这个问题就转换成了求逆序对的个数，维护一个树状数组即可。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/ZOJ/3157.cpp

Veröffentlicht am | in

C++

1
#pragma comment(linker, "/STACK:102400000,102400000")

G++

1
2
3
int size = 256 << 20; // 256MB  
char *p = (char*)malloc(size) + size;  
__asm__("movl %0, %%esp\n" :: "r"(p));

Veröffentlicht am | in

什么是ACM？

想必打开这篇博客的人已经知道什么是ACM了吧，如果不知道，请自行百度或者谷歌

搞ACM需要学习什么知识？

搜索引擎

这里不是让你设计一个搜索引擎，而是让你学会正确使用搜索引擎，当你有任何不解的时候（包括阅读下文），问问谷歌或者百度，这不只是ACM才需要的技能。

一门编程语言

虽然现在编程语言总类繁多，有些OJ也支持多种语言，不过C++还是搞ACM不二的选择，另外最好也学会使用java，因为无论在什么地方，什么国家，什么网站的比赛，C++和java都是支持的。ACM是算法的比拼，所以并不需要将编程语言钻研过深，毕竟语言只是工具。

良好的英语

ACM是国际比赛，英文交流能力是无可厚非的。英文差，但是想搞怎么办？对于这样的问题，我的答案是：请自行学习英语，世上无难事，只怕有心人。

数学能力

算法算法，无论怎样都脱离不了数学。我认为，几何学、线性代数、离散数学、初等数论和微积分是必须掌握的。太多了怎么办？这点请放心，你可以在不断的比赛中积累这些知识。

在哪里可以训练/做题？

可以在OJ上训练

全球有非常多非常多的OJ，即Online Judge，在线评测平台，他们可以将你的代码进行在线评测，来判断正误。推荐的国内的OJ有CDOJ（电子科技大学），POJ（北京大学），HDUOJ（杭州电子科技大学），BNUOJ（北京师范大学）。

如何提交我的代码

我不打算详细讲解，所以可以的话，请看每个OJ的F.A.Qs，英文怎么办？自己想办法。

有没有线上的比赛

国内的线上比赛有HDU的bestcoder，这个是有奖金的比赛，国外的推荐codeforces，会不定期的进行比赛，比赛的难度适合新手（英语较好），另外就是Topcoder，这个是相当有名的比赛，不过入手较为困难，你可以百度或者谷歌相关教程，这里就不详细解释了。这些比赛都有着积分的规则，简单说，你打得好，积分就会上涨，否则下跌。高排名总是被各大公司相中，如Google、阿里等，特别是Topcoder，在这里的高排名相当有价值。

推荐的书籍？

英语我就不推荐了，自己想办法。下列书籍中的任何习题，都推荐去完成。

编程语言类

《C++大学基础教程》作者是Deitel，这个作者所著的编程书籍都是值得学习的。

算法入门类

《挑战程序设计》，《算法竞赛入门经典》作者刘汝佳。

数学类

《组合数学》，《算法导论》，《具体数学》

常见的问题

算法无法理解

多看书，多想，细细琢磨，别人能懂，你也可以。问问老师同学，周围的大牛肯定有人知道。

这道题怎么做，完全不会

碰到不会的题是很正常的事，此时你就需要搜索题解，怎么搜索？当然谷歌百度。

那些家伙为啥那么厉害

勤能补拙，每个大神的背后都有着辛勤的付出。凡事靠坚持，每个人都有着无限的潜能，也许你会看见比你更厉害的大神，但只要你努力，你就是下一个大神。

学习这个会不会占用我很多时间

有得便有失，投入和专注是获得成绩的充要条件。

最后的话

时间不会因为你的犹豫而止步，既然你决定了搞ACM，那么就应当立马开始行动，要知道有很多人已经在你的前面走了很远。

Veröffentlicht am | in

什么是输入挂？

众所周知scanf比cin快的多，那么有没有比scanf更快的东西呢？答案就是输入挂，输入挂利用了告诉读取的函数getchar()，然后再人工处理成整数或浮点，比使用scanf快太多。

什么时候用输入挂？

当输入规模达到1×10^6次方的时候，就需要输入挂，否则很有可能超时。

代码

不是我写的

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //getchar->read
    inline void read1(int &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(ll &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(double &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (ch=='.'){
            double tmp=1;
            for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
        }
        if (bo)x=-x;
    }
    inline void read1(char *s){
        char ch=getchar();
        for (;blank(ch);ch=getchar());
        for (;!blank(ch);ch=getchar())*s++=ch;
        *s=0;
    }
    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
    //scanf->read
    inline void read2(int &x){scanf("%d",&x);}
    inline void read2(ll &x){
        #ifdef _WIN32
            scanf("%I64d",&x);
        #else
        #ifdef __linux
            scanf("%lld",&x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void read2(double &x){scanf("%lf",&x);}
    inline void read2(char *s){scanf("%s",s);}
    inline void read2(char &c){scanf(" %c",&c);}
    inline void readln2(char *s){gets(s);}
    //fwrite->write
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    //puts->write
    char Out[OUT_SIZE],*o=Out;
    inline void print1(int x){
        static char buf[15];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(int x){print1(x);*o++='\n';}
    inline void print1(ll x){
        static char buf[25];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(ll x){print1(x);*o++='\n';}
    inline void print1(char c){*o++=c;}
    inline void println1(char c){*o++=c;*o++='\n';}
    inline void print1(char *s){while (*s)*o++=*s++;}
    inline void println1(char *s){print1(s);*o++='\n';}
    inline void println1(){*o++='\n';}
    inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
    struct puts_write{
        ~puts_write(){flush1();}
    }_puts;
    inline void print2(int x){printf("%d",x);}
    inline void println2(int x){printf("%d\n",x);}
    inline void print2(char x){printf("%c",x);}
    inline void println2(char x){printf("%c\n",x);}
    inline void print2(ll x){
        #ifdef _WIN32
            printf("%I64d",x);
        #else
        #ifdef __linux
            printf("%lld",x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void println2(ll x){print2(x);printf("\n");}
    inline void println2(){printf("\n");}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;