热门日志推荐
人人最热标签
分享这篇日志的人常去
北京千橡网景科技发展有限公司：
文网文[号··京公网安备号·甲测资字
文化部监督电子邮箱：wlwh@··
文明办网文明上网举报电话： 举报邮箱：&&&&&&&&&&&&
请输入手机号，完成注册
请输入验证码
密码必须由6-20个字符组成
下载人人客户端
品评校花校草，体验校园广场查询一个区间比v大的最小的数
和hdu4417的相似，可以用线段树离线，或者划分树+二分，或者分块。。。
划分树+二分：
#include&stdio.h&
#include&string.h&
#include&algorithm&
#define N 100010
int tree[20][N],sa[N],sum[20][N];
int t,n,m,op,l,r;
inline void build(int d,int l,int r)
int m=(l+r)&&1;
int lless=m-l+1;
for(int i=l;i&=r;i++)
if(tree[d][i]&sa[m])
int lp=l,rp=m+1;
for(int i=l;i&=r;i++)
if(l==i) sum[d][i]=0;
sum[d][i]=sum[d][i-1];
if(tree[d][i]&sa[m])
tree[d+1][lp++]=tree[d][i];
sum[d][i]++;
else if(tree[d][i]&sa[m])
tree[d+1][rp++]=tree[d][i];
sum[d][i]++;
tree[d+1][lp++]=tree[d][i];
tree[d+1][rp++]=tree[d][i];
build(d+1,l,m),build(d+1,m+1,r);
inline int query(int l,int r,int x,int y,int k,int d)
if(x==y) return tree[d][x];
int ss,s,m=(l+r)&&1;
ss=(l==x?0:sum[d][x-1]);
s=sum[d][y]-
int yy=l+ss+s-1;
return query(l,m,xx,yy,k,d+1);
int ll=x-1-l+1-
int rr=y-x+1-s;
int xx=m+1+
int yy=m+1+ll+rr-1;
return query(m+1,r,xx,yy,k-s,d+1);
int main()
scanf(&%d&,&t);
while(t--)
scanf(&%d%d&,&n,&m);
for(int i=1;i&=n;i++)
scanf(&%d&,&sa[i]);
tree[0][i]=sa[i];
sort(sa+1,sa+n+1);
build(0,1,n);
while(m--)
scanf(&%d%d%d&,&op,&l,&r);
int s=1,t=l-op+1;
int ans=-1;
while(s&=t)
int mid=(s+t)&&1;
int temp=query(1,n,op,l,mid,0);
if(temp&r) ans=
if(temp&=r) s=mid+1;
if(ans==-1)
puts(¬ exist&);
printf(&%d\n&,ans);
#include &stdio.h&
#include &string.h&
#include &algorithm&
#define N 100010
#define INF ~0U&&1
#define S 350
inline int input(){
int ret=0;
char c=getchar();
while(c&'0' || c&'9'){
c=getchar();
while(c&='0' && c&='9'){
ret=ret*10+c-'0';
c=getchar();
int a[N],block[N/S+1][S];
int t,n,m;
int l,r,v;
inline int query(int l,int r,int v){
int ll=l/S,lr=r/S;
int ans=INF;
if(ll == lr){
for(int i=l;i&=r;i++){
if(a[i]&v && a[i]&ans){
for(int i=l;i&(ll+1)*S;i++){
if(a[i]&v && a[i]&ans){
for(int i=lr*S;i&=r;i++){
if(a[i]&v && a[i]&ans){
for(int i=ll+1;i&i++){
if(block[i][0] & v){
ans=min(ans,block[i][0]);
else if(block[i][S-1] &= v){
int s=0,t=S-1,tag=INF;
while(s&=t){
int mid=(s+t)&&1;
if(block[i][mid]&v) tag=
if(block[i][mid]&=v) s=mid+1;
else t=mid-1;
ans=min(ans,block[i][tag]);
int main()
t=input();
while(t--){
n=input(),m=input();
cnt=num=0;
for(int i=0;i&n;i++){
a[i]=input();
block[cnt][num]=a[i];
if(num == S){
sort(block[cnt],block[cnt]+num);
if(num) sort(block[cnt],block[cnt]+num);
while(m--){
l=input(),r=input(),v=input();
int ans=query(l,r,v);
if(ans == INF){
printf(¬ exist\n&);
printf(&%d\n&,ans);
线段树离线:
#include &stdio.h&
#include &string.h&
#include &algorithm&
inline int input(){
int ret=0;
char c=getchar();
while(c&'0' || c&'9'){
c=getchar();
while(c&='0' && c&='9'){
ret=ret*10+c-'0';
c=getchar();
#define N 100010
#define INF ~0U&&1
#define L t&&1
#define R t&&1|1
struct node{
}root[N&&2];
inline void build(int t,int l,int r){
root[t].l=l,root[t].r=r;
root[t].val=INF;
int m=(l+r)&&1;
build(L,l,m);
build(R,m+1,r);
inline void modefiy(int t,int x,int val){
int l=root[t].l,r=root[t].r;
root[t].val=
int m=(l+r)&&1;
if(x&=m) modefiy(L,x,val);
modefiy(R,x,val);
root[t].val=min(root[L].val,root[R].val);
inline int query(int t,int x,int y){
int l=root[t].l,r=root[t].r;
if(l==x&&r==y){
return root[t].
int m=(l+r)&&1;
int ans=INF;
if(x&=m) ans=min(ans,query(L,x,min(m,y)));
if(y&m) ans=min(ans,query(R,max(m+1,x),y));
struct Point{
bool cmp1(Point i,Point j){
if(i.val == j.val) return i.id&j.
return i.val&j.
struct Query{
int l,r,v,
bool cmp2(Query i,Query j){
if(i.v == j.v){
if(i.l == j.l) {
return i.r&j.r;
return i.l&j.l;
return i.v&j.v;
int t,n,m,ans[N];
int main(){
t=input();
while(t--){
n=input(),m=input();
for(int i=1;i&=n;i++){
p[i].id=i,p[i].val=input();
sort(p+1,p+n+1,cmp1);
for(int i=1;i&=m;i++){
q[i].id=i,q[i].l=input(),q[i].r=input(),q[i].v=input();
sort(q+1,q+m+1,cmp2);
build(1,1,n);
for(int i=1;i&=m;i++){
while(j&=n && p[j].val&q[i].v){
modefiy(1,p[j].id,p[j].val),j++;
int tag=query(1,q[i].l,q[i].r);
if(tag &= q[i].v) tag=INF;
ans[q[i].id]=
printf(&%d %d %d %d \n&,q[i].id,ans[q[i].id],q[i].v,tag);
for(int i=1;i&=m;i++){
if(ans[i] == INF){
puts(¬ exist&);
printf(&%d\n&,ans[i]);
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：127073次
积分：4266
积分：4266
排名：第2817名
原创：291篇
转载：12篇
评论：96条
(1)(35)(15)(27)(19)(6)(11)(6)(6)(8)(11)(17)(28)(16)(19)(5)(1)(9)(1)(4)(11)(7)(11)(8)(12)(9)目前在哈工大的国内著名ACMer&br&在CF和TC都很活跃 （因为长期没有队友所以）综合能力比较犀利&br&对比赛非常有兴趣 最近去了好多现场赛&br&哦对了在B站上有TopCoder的实况当真是吓到我了。。。（原来作比赛还可以出视频。。。）&br&（当然最为广大人民群众喜闻乐见的是因为cos和伪。。。）
目前在哈工大的国内著名ACMer在CF和TC都很活跃 （因为长期没有队友所以）综合能力比较犀利对比赛非常有兴趣 最近去了好多现场赛哦对了在B站上有TopCoder的实况当真是吓到我了。。。（原来作比赛还可以出视频。。。）（当然最为广大人民群众喜闻乐见的是因为…
1 基础数学（组合数学，数论神马的应该是用的最多的，代数里面的工具也很重要，微积分的思想也在一些地方体现了）&br&&br&2
数据结构和算法（通读算法导论）算法复杂度的估计分析，可计算性理论&br&特别应该提出的：计算几何/动态规划/图论（网络流）/数论都可以单独作为一门学科来处理。&br&&br&3
程序设计语言（基础的程序设计语言，C语言就可以，C++熟练掌握STL的话代码速度得到很大提高，java常用于调用bigInterger 和bigDemical避免写高精度，但效率低）&br&&br&4
个人的灵性，尤其是对题目的“感觉”，以及和队友磨合、做题策略也是需要锻炼的。&br&&br&给出一个学习方法：&br&个人觉得需要看《算法导论》&br&另外按照《算法艺术与信息学竞赛》作为提纲进行阅读，对于每个知识点做题+看书，不必要特别指定具体什么。&br&这是一个非牛逼的ACMer的感觉。
1 基础数学（组合数学，数论神马的应该是用的最多的，代数里面的工具也很重要，微积分的思想也在一些地方体现了）2 数据结构和算法（通读算法导论）算法复杂度的估计分析，可计算性理论特别应该提出的：计算几何/动态规划/图论（网络流）/数论都可以单独作…
VK全称叫VKontakte，是俄罗斯最大的SNS，流行于俄语区。 &br&&br&&img src=&/6ba5bfd5b5bde935c9b252e9edbae927_b.jpg& data-rawwidth=&200& data-rawheight=&200& class=&content_image& width=&200&&&br&这个比赛就是VK赞助的啦。曾经有很长一段时间Codeforces都是VK赞助的， logo上都带有Sponsored
的字样，只不过现在换Telegram了。 废话几句，Telegram的创始人，叫Nikolai Durov，年两次WF冠军，SPbSU，读了计算机和数学两个PhD，wiki上介绍的头衔为数学家（&a href=&http://en.wikipedia.org/wiki/Nikolai_Durov& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Nikolai Durov&i class=&icon-external&&&/i&&/a&），曾经是VK的lead developer，后来创建了Telegram。&br&&br&VK Cup这是第二届了，第一届是在2012年，比赛只面向18~23岁的选手。2012年的时候，冠军是我们萌萌哒的Sevenkplus，亚军也是天朝的S-quark， tourist只获得了第三。 然后Sevenkplus在这次比赛后就以3W刀爷和阿华田弟弟的雅号走红啦。&br&&br&VK Cup再往后就停办了两年，今年重新办，但是限制了正式比赛题目只提供俄语版（一定是为了阻止Sevenkplus再次虐tourist），所以整个天朝选手就被排斥在外，只能做做比赛回放了。&br&&br&附当年的照片和排名(&a href=&/contest/211/standings& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Standings - VK Cup 2012 Finals&i class=&icon-external&&&/i&&/a&，哎，著名青年理论计算机科学家那一次又滚粗了)&br&&br&&img src=&/fb3f7d4c509dde2aaac9_b.jpg& data-rawwidth=&1313& data-rawheight=&879& class=&origin_image zh-lightbox-thumb& width=&1313& data-original=&/fb3f7d4c509dde2aaac9_r.jpg&&
VK全称叫VKontakte，是俄罗斯最大的SNS，流行于俄语区。 这个比赛就是VK赞助的啦。曾经有很长一段时间Codeforces都是VK赞助的， logo上都带有Sponsored
的字样，只不过现在换Telegram了。 废话几句，Telegram的创始人，叫Nikolai Durov，2000年20…
没事少评价别人，该干什么干什么去
没事少评价别人，该干什么干什么去
今天好无聊，娱乐写代码。&br&春晚好无聊，不如写代码。&br&晚上睡不着，起床写代码。&br&队友也无聊，一起写代码。
今天好无聊，娱乐写代码。春晚好无聊，不如写代码。晚上睡不着，起床写代码。队友也无聊，一起写代码。
看兴趣点和打算啦。acm竞赛中得到的训练，本身也就是打基础啦。&br&&br&说点个人推荐的。&br&&br&如果要想高端一点，就做个青年理论计算机科学家。&br&&br&想搞热门的和具体应用问题结合的，就Machine Learning, Data Mining, Natural Language Processing, Cloud Computing，虽然号称四大俗，不过毕竟是当前学术界和工业界都异常火热的内容。&br&&br&还有稍微冷门一点的就是做安全防护、操作系统、程序语言。说冷也并不是说不重要，只是做的人相对少，还是非常重要的偏基础性工作。&br&&br&如果想当码农挣大钱，非常推荐了解游戏相关的核心技术，游戏是个人傻钱多速来的行业，比一般的互联网职位性价比高。当然码农还是全面一点好，除了专长，什么技术都知道一点比较好。&br&&br&胡说八道了好多，还是开头的话follow your heart。
看兴趣点和打算啦。acm竞赛中得到的训练，本身也就是打基础啦。说点个人推荐的。如果要想高端一点，就做个青年理论计算机科学家。想搞热门的和具体应用问题结合的，就Machine Learning, Data Mining, Natural Language Processing, Cloud Computing，虽然号…
为什么非得要把ACM比赛和绩点关联或者对立起来？&br&&br&这是两种不同的考察模式。如果说可能有冲突的，只是因为时间上的分配；认为潜在的关联性，只是因为你都要投入精力、智慧和探索。 那些不能兼顾的人只是无法平衡或者没有投入罢了。&br&&br&当然也不能强求，看你需要什么。
为什么非得要把ACM比赛和绩点关联或者对立起来？这是两种不同的考察模式。如果说可能有冲突的，只是因为时间上的分配；认为潜在的关联性，只是因为你都要投入精力、智慧和探索。 那些不能兼顾的人只是无法平衡或者没有投入罢了。当然也不能强求，看你需要什…
信息安全专业的ACMer报道。。&br&&br&我跟你讲啊，ACM和信息安全简直扯不上半毛钱关系，唯一的关系是搞了ACM之后，数据结构课，算法课，信息安全实验课都能虐过去了。。其他的简直就是完全无关。。&br&&br&所以如果你想继续搞信安的话，建议不要搞ACM，据我所知信息安全的公司基本都不会在意ACM奖项。。。我开始搞ACM之后就完全没想过要继续搞信安了。。。。
信息安全专业的ACMer报道。。我跟你讲啊，ACM和信息安全简直扯不上半毛钱关系，唯一的关系是搞了ACM之后，数据结构课，算法课，信息安全实验课都能虐过去了。。其他的简直就是完全无关。。所以如果你想继续搞信安的话，建议不要搞ACM，据我所知信息安全的公…
以下结果来自网络：&br&&a href=&/aekdycoin/item/7d1de2e3bddb& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/aekdycoin/&/span&&span class=&invisible&&item/7d1de2e3bddb&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&br&提出一切皆网络流的BUPT现役神牛daizhenyang（中文名戴振阳）&br&&br&(1)&br&戴振阳是二十一世纪上半叶中国乃至全世界最伟大的数学家之一。他在横跨两个世纪的研究生涯中，几乎走遍了现代数学所有前沿阵地，从而把他的思想深深地渗透进了整个现代数学。戴振阳是中华数学学派的核心，他以其勤奋的工作和真诚的个人品质吸引了来自世界各地的年青学者，使中华传统在世界产生影响。德国《自然》杂志发表过这样的观点：现在世界上难得有一位数学家的工作不是以某种途径导源于戴振阳的工作。他像是数学世界的亚历山大，在整个数学版图上，留下了他那显赫的名字。&br&&br&2010年，戴振阳在北京数学家大会上提出了26个最重要的问题供二十一世纪的数学家们去研究，这就是著名的&戴振阳26个问题&。&br&&br&在美国数学家评选的美国数学的十大期望成就中，有三项就是戴振阳第1、第5、第26问题的解决。由此可见，能解决戴振阳问题，是当代数学家的无上光荣。&br&&br&(2)&br&据知情人士评价:&还有戴振阳（不太确定名字是不是都打对了，实在不好意思），大一就这么有激情，相当强悍还很谦虚。
我被那句“POJ我才A了200多题”吓着了。。。 &&br&&br&(3)&br&5月16日，在由国防科技大学主办的2010年ACM国际大学生程序设计竞赛中南地区全国邀请赛中，由我校计算机学院2008级学生戴振阳、李兆振和理学院2008级学生于卓组成的qwerty队获得银奖，由我校计算机学院2008级学生莫梓元、马庆元和赵大昊组成的AoiSola队获得铜奖。该项赛事是即将承担今年10月由浙江理工大学承办的第35届ACM国际大学生程序设计竞赛亚洲区预赛（杭州）竞赛的一次预演。共来自全国32所大学的101支队伍展开竞技。&br&&br&(4)&br&&strong&Value&/strong& 250 &strong&Submission Rate&/strong& 520 / 531 (97.93%) &strong&Success Rate&/strong& 378 / 520 (72.69%) &strong&High Score&/strong& &strong&daizhy&/strong& for 247.53 points (2 mins 50 secs) &strong&Average Score&/strong& 195.15 (for 378 correct submissions) &br&&strong&daizhy&/strong& 's APM orororz!!!&br&&a href=&/wiki/display/tc/SRM+480& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&/wiki/displ&/span&&span class=&invisible&&ay/tc/SRM+480&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&
以下结果来自网络：提出一切皆网络流的BUPT现役神牛daizhenyang（中文名戴振阳）(1)戴振阳是二十一世纪上半叶中国乃至全世界最伟大的数学家之一。他在横跨两个世纪的研究生涯中，几乎走遍了现代数学所有前沿阵地，从而把他的思想深深地…
算法导论里面的顺序统计学的那一章有讲一个最坏复杂度为线性的选择算法，并给出了复杂度分析，自己去看吧，代码自己写。自己搜索BFPRT。
算法导论里面的顺序统计学的那一章有讲一个最坏复杂度为线性的选择算法，并给出了复杂度分析，自己去看吧，代码自己写。自己搜索BFPRT。
因为memset是按字节进行赋值的（这也是为什么不能用memset对多个字节的变量赋值1的原因，-1就可以，因为-1是补码形式，所有位均为1），一个double型变量需要memset执行8次赋值才能将所有位置零，整形需要4次。&br&&br&不过我当初写图的时候，从没遇到过因为memset而TLE的情况。&br&&br&没做过测试，网传memset效率应该比for高。
因为memset是按字节进行赋值的（这也是为什么不能用memset对多个字节的变量赋值1的原因，-1就可以，因为-1是补码形式，所有位均为1），一个double型变量需要memset执行8次赋值才能将所有位置零，整形需要4次。不过我当初写图的时候，从没遇到过因为memset而…
来自子话题：
1、你做得太快，而不是太慢；&br&2、看答案是做题大忌，真去面试的话有人给你答案么；&br&3、如果真做不出来，看了答案，应该花更多的时间集中在这道题上，思考为什么没想到思路，自己哪里的知识有欠缺；&br&4、半个到一个小时做一道没见过的题本来就是面试的要求，没什么好畏难的。想做得更快，就要先从做得慢开始。
1、你做得太快，而不是太慢；2、看答案是做题大忌，真去面试的话有人给你答案么；3、如果真做不出来，看了答案，应该花更多的时间集中在这道题上，思考为什么没想到思路，自己哪里的知识有欠缺；4、半个到一个小时做一道没见过的题本来就是面试的要求，没什…
如果数对不变，则有可能找到一个最小完美哈希函数，使得时间复杂度为O（1）的同时空间复杂度为O（N)。&br&参考 &a href=&/link?url=Oly0qTtAwP-PjqVRHBkAEmqPoWe30PvLm2WonbE1PTWzzLtgS5WDkv5HvOs_157LkHQBSFQYzibSYfdNWmzH0ftJjSqijKqy2sd6r1LA0qK& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&最小完美哈希函数&i class=&icon-external&&&/i&&/a&&br&&br&如果是出于学习的目的这么做没什么问题。但是如果在工作中这么做小心后来维护的人骂你。过早优化绝对有害无利。
如果数对不变，则有可能找到一个最小完美哈希函数，使得时间复杂度为O（1）的同时空间复杂度为O（N)。参考 如果是出于学习的目的这么做没什么问题。但是如果在工作中这么做小心后来维护的人骂你。过早优化绝对有害无利。
&p&如果需要的是现成的解决方案，这个就不错：&/p&&p&&a href=&/mattgodbolt/gcc-explorer& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/mattgodbolt/&/span&&span class=&invisible&&gcc-explorer&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&p&效果预览：&/p&&p&&a href=&http://gcc.godbolt.org/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Compiler Explorer&i class=&icon-external&&&/i&&/a&&/p&&br&&p&如果是针对传统使用方法的编程语言实现一个的话涉及的内容很杂，包括：&/p&&ul&&li&Web服务器+Web服务器与后端程序交互的组件（这个可以用现成的，我用的是nginx+FCGI）&/li&&li&后端程序&/li&&/ul&&p&后端核心就是一个类似调用系统给的类似execl的API执行一下对应编译工具，用这个API时还得精心处理一下管道，把输出内容导出来显示回网页。&/p&&p&但是因为这类程序和OJ一样，是网络上的公共服务而且居然还允许用户上传代码编译执行，所以问题主要集中在安全处理上，而且安全问题的处理高度依赖操作系统。&/p&&p&以Linux为例，安全方面包括但不仅包括以下内容：&/p&&ol&&li&依赖环境构建、沙盒&/li&&li&运行身份，包括GID、UID&/li&&li&资源限制，包括socket、文件操作、核心转储大小、文件数、子进程数等等&/li&&li&syscall限制&/li&&li&执行时间限制，包括运行时间和CPU时间&/li&&li&文件系统压力&/li&&/ol&&p&Windows下是另一堆问题要解决，比Linux复杂得多（也许是我不太会用Windows）。&/p&&br&&p&我认识一人，自己实现了一个类似Haskell的东西，有和Go Playground差不多的在线运行网页，我问他怎么那么快把那么多东西都搞完了，他说，“整个语言就是用JS实现的，所以有浏览器就能运行，不需要后端”，这也是一种思路。&/p&
如果需要的是现成的解决方案，这个就不错：效果预览：如果是针对传统使用方法的编程语言实现一个的话涉及的内容很杂，包括：Web服务器+Web服务器与后端程序交互的组件（这个可以用现成的，我用的是nginx+FCGI）后端程…
按你给的a: [0-100], b: [0-255]，这不是现成的 hash(a, b) = a*256 + b吗？用一个不到3KB的bitmap就可以标记了: char bitmap[101*256/8];
按你给的a: [0-100], b: [0-255]，这不是现成的 hash(a, b) = a*256 + b吗？用一个不到3KB的bitmap就可以标记了: char bitmap[101*256/8];
如果你想攀登高峰，就去搞算法吧~&br&如果你想征服大海，就去搞安全吧~&br&在于精，在于博~&br&人的精力是有限的，如果你能做到又精又博，恭喜你，你已经超神了
如果你想攀登高峰，就去搞算法吧~如果你想征服大海，就去搞安全吧~在于精，在于博~人的精力是有限的，如果你能做到又精又博，恭喜你，你已经超神了
1，现在大量的国内优秀ACM选手都是在NOIP禁止使用STL时代成长起来的，他们非常熟悉数组，从初中就用数组，很多人5分钟用数组码个平衡树不在话下，因此STL就没那么有用了&br&2，没O2你试试看STL的速度。。如果要追求速度，数组确实很有优势
1，现在大量的国内优秀ACM选手都是在NOIP禁止使用STL时代成长起来的，他们非常熟悉数组，从初中就用数组，很多人5分钟用数组码个平衡树不在话下，因此STL就没那么有用了2，没O2你试试看STL的速度。。如果要追求速度，数组确实很有优势
&blockquote&#include &ext/rope&&br&using __gnu_cxx::&/blockquote&
#include &ext/rope&using __gnu_cxx::
经三鲜同学提醒，大于pi的情况疏忽了。重新写一个更详细的算了。&br&——————————————&br&如果n=1或n=2，成立显然，以下考虑n&=3的情况。&br&定义&br&&ul&&li&楔形wedge：从一点出发的两条射线围成的类似扇形的区域（但是无限延伸），称两条射线的夹角为楔形的张角，这个点为楔形的顶点。&br&&/li&&li&楔形的补complementary wedge：把这两条射线反向，围成的楔形（类似对顶角）。注意补的张角和原张角是相等的，和普通的补不一样，相当于旋转180度。&/li&&/ul&一个光源可照亮的范围，就是张角为&img src=&/equation?tex=2%5Cpi%2Fn& alt=&2\pi/n& eeimg=&1&&的一个楔形。&br&题目要求照亮整个平面，下面证明的思路是：&br&&ol&&li&先考虑特殊情况：对于张角&img src=&/equation?tex=%5Cleq%5Cpi& alt=&\leq\pi& eeimg=&1&&的楔形区域，假如光源在其补中，可以完全覆盖这个楔形。&/li&&li&但是我们需要照亮整个平面，平面可看做张角为&img src=&/equation?tex=2%5Cpi& alt=&2\pi& eeimg=&1&&的楔形，很遗憾不能直接用引理1。我们希望对于任意放置的光源，能够将平面分割为若干特别的张角&img src=&/equation?tex=%5Cleq%5Cpi& alt=&\leq\pi& eeimg=&1&&的楔形，这样：&/li&&li&用1中的结论，每个楔形里的光源都可照亮其补。于是整个平面被完全覆盖。&/li&&/ol&——————————开始——————————&br&引理1&br&&ul&&li&给出一楔形&img src=&/equation?tex=W& alt=&W& eeimg=&1&&，设其张角为&img src=&/equation?tex=%5Ctheta& alt=&\theta& eeimg=&1&&，在其补&img src=&/equation?tex=W%27& alt=&W'& eeimg=&1&&中有&img src=&/equation?tex=k& alt=&k& eeimg=&1&&个光源（各自位置任意给定），每个点可照亮张角为&img src=&/equation?tex=%5Ctheta%2Fk& alt=&\theta/k& eeimg=&1&&的楔形。则可以调整它们照射的角度，使其覆盖&img src=&/equation?tex=W& alt=&W& eeimg=&1&&。&/li&&/ul&可用归纳法证明,画出k=1的情况防止误解。&br&&img src=&/c9b9bcd8ba8c269eaa264e_b.jpg& data-rawwidth=&229& data-rawheight=&155& class=&content_image& width=&229&&引理2&br&&ul&&li&令&img src=&/equation?tex=p%3D%5Clfloor+n%2F3+%5Crfloor%2C+q%3Dn-2p%2C+%5Ctheta%3D2p%5Cpi%2Fn%2C%5Cphi%3D2q%5Cpi%2Fn.& alt=&p=\lfloor n/3 \rfloor, q=n-2p, \theta=2p\pi/n,\phi=2q\pi/n.& eeimg=&1&&对于任意放置的光源，都可将找到一个点，以其为顶点可做出张角分别为&img src=&/equation?tex=%5Ctheta%2C%5Ctheta%2C%5Cphi& alt=&\theta,\theta,\phi& eeimg=&1&&的三个楔形&img src=&/equation?tex=W_1%2CW_2%2CW_3& alt=&W_1,W_2,W_3& eeimg=&1&&，各包含&img src=&/equation?tex=p%2Cp%2Cq& alt=&p,p,q& eeimg=&1&&个光源。通俗地说，就是把平面近似平均切成了三块，每块近似包含了三分之一的光源，并且每块包含的光源能照亮的角度之和与楔形张角相等。“近似”是由于需要取整。&/li&&/ul&证明：&br&随意安排这三个楔形的顺序和边界的方向。假设像这个样子：&br&&img src=&/d0f40c806a660ceb6fc40_b.jpg& data-rawwidth=&178& data-rawheight=&163& class=&content_image& width=&178&&下面，边界的&b&方向&/b&固定，寻找这个合适的顶点。&br&把直线&img src=&/equation?tex=l_1& alt=&l_1& eeimg=&1&&从最下方慢慢向上移动。由于&img src=&/equation?tex=W_1& alt=&W_1& eeimg=&1&&要有&img src=&/equation?tex=p& alt=&p& eeimg=&1&&个光源，所以&img src=&/equation?tex=l_1& alt=&l_1& eeimg=&1&&右下的光源数要大于等于&img src=&/equation?tex=p& alt=&p& eeimg=&1&&，类似，左上的光源数大于等于&img src=&/equation?tex=q& alt=&q& eeimg=&1&&，这样限制了&img src=&/equation?tex=l_1& alt=&l_1& eeimg=&1&&的范围。做出&img src=&/equation?tex=W_1%2CW_3& alt=&W_1,W_3& eeimg=&1&&使其恰好包含&img src=&/equation?tex=p%2Cq& alt=&p,q& eeimg=&1&&个光源，设交点分别为&img src=&/equation?tex=x_1%2Cx_2& alt=&x_1,x_2& eeimg=&1&&。如果&img src=&/equation?tex=x_1%2Cx_2& alt=&x_1,x_2& eeimg=&1&&重合，则得解。如果不重合：&br&&img src=&/equation?tex=x_1%2Cx_2& alt=&x_1,x_2& eeimg=&1&&看做数轴的点。&img src=&/equation?tex=l_1& alt=&l_1& eeimg=&1&&处于最下方时，右下恰有&img src=&/equation?tex=p& alt=&p& eeimg=&1&&个光源，&img src=&/equation?tex=x_1& alt=&x_1& eeimg=&1&&可以取得任意小，直到小于&img src=&/equation?tex=x_2& alt=&x_2& eeimg=&1&&：&br&&img src=&/5b195c4bf4ffc8c46ec03e_b.jpg& data-rawwidth=&203& data-rawheight=&210& class=&content_image& width=&203&&&img src=&/equation?tex=l_1& alt=&l_1& eeimg=&1&&处于最上方时，左上恰有&img src=&/equation?tex=q& alt=&q& eeimg=&1&&个光源，&img src=&/equation?tex=x_2& alt=&x_2& eeimg=&1&&可以取得任意小，直到小于&img src=&/equation?tex=x_1& alt=&x_1& eeimg=&1&&：&br&&img src=&/e_b.jpg& data-rawwidth=&216& data-rawheight=&189& class=&content_image& width=&216&&当&img src=&/equation?tex=l_1& alt=&l_1& eeimg=&1&&向上移动时，由连续性，必有&img src=&/equation?tex=x_1%2Cx_2& alt=&x_1,x_2& eeimg=&1&&可行域重合时。相交时即找到目标顶点，由此可将平面三分。&br&&br&定理（目标）：&br&由引理2，我们可将平面三分，三分是保证每个楔形的张角都不大于&img src=&/equation?tex=%5Cpi& alt=&\pi& eeimg=&1&&，以利用引理1；由引理1，每个楔形的光源可完全覆盖这个楔形的补，这些补合起来就是完整平面，这样就得到了照亮完整平面的方法。证完。&br&程序实现，引理2中三分平面用时&img src=&/equation?tex=O%28n%5Clog+n%29& alt=&O(n\log n)& eeimg=&1&&, 引理1用时&img src=&/equation?tex=O%28n%29& alt=&O(n)& eeimg=&1&&，总体&img src=&/equation?tex=O%28n%5Clog+n%29& alt=&O(n\log n)& eeimg=&1&&。
经三鲜同学提醒，大于pi的情况疏忽了。重新写一个更详细的算了。——————————————如果n=1或n=2，成立显然，以下考虑n&=3的情况。定义楔形wedge：从一点出发的两条射线围成的类似扇形的区域（但是无限延伸），称两条射线的夹角为楔形的张角，这…
因为【我能】！ （Because we can！）
因为【我能】！ （Because we can！）
