yibaini / aoapc-book Goto Github PK

page XI
内容安排这一节，
“第1部分是语言篇（第1~4章）”，应为“1~5章”；
“第2部分是算法篇（第5~8章）”，应为“基础篇（第6~7章）�
��；
“第3部分是竞赛篇（第9~11章）”，应为“8~12章”。

我怎么感觉自己在做编辑的活儿啊╮(╯▽╰)╭

const int maxn = 100000+10; 
这里maxn开小了在LA上RE
应该是200000+10(因为一个点会产生2个事件)
---------------By Wumpus

“换句话说，不同的gcd值最多只有log_2 j种”
请问这个结论是如何得到的？

 只有这几处有涉及该数组
{{{
// UVa11248 Frequency Hopping：使用Dinic算法

  int cur[maxn];   // 当前弧指针
//=====================
  while(BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, INF); 
    }

//=====================
 for(int& i = cur[x]; i < G[x].size(); i++) {
}}}

该数组自始至终都为0，请问它是怎么起到 
当前弧指针的作用的？谢谢

这道题我写出来超时，第一次写平面域（PSLG）的题。我的这�
��面的知识算法都很少，判断点在某个域里我用的白书上的判
断在点在多边形内外的方法，枚举每个域（不包括无穷域）��
�不知道是不是这里的时间代价太大了。我希望能给点这方面�
��知识（训练指南的知识太少了只有一小段话），再给我点数
据和标程。最好能有点提示讲解，当然如果很忙就算了。
谢谢咯！

我的程序 
输入 1 5
输出
10
2 5 7 2 13 4 1 7 11 4 14 2 15 1 1 7 7 8 12 5
验证了一下 也可以满足题目 而且题目上要求输出字典序小的
所以为什么标准答案是下面这个
10
12 5 3 8 15 12 6 13 7 9 1 7 10 8 7 9 11 14 14 5

我认为问题描述中:最后一句应该是"你的目标是让尽量多的服
务完全瘫痪",而不是"服务器".
还有在枚举S的子集S0的代码中,是通过枚举S某一个子集的补集
来实现枚举S的子集,f[S^S0]才是这个子集么?

下载数目增加感觉只要点击就会增加了。弹出无法访问页面��
�

P186的表格中, 在"操作"下, "1x" 应为 "1 x".

P189例4的题目描述中, 最后一行:
"求这些和中最小的k值"
应为
"求这些和中最小的k个值"

P191代码下一行：
“注意（*）处，combine函数”
应为
“注意（*）处，merge函数”

:)

链接路径
git/  BeginningAlgorithmContests/ exercises/ ch2/ ex2-9.c 

代码没有解决类似xxxx.999999或xxxx.yyyyy9（末位是9）的进位问题
感觉应该用高精度除法方式整体解决进位问题

虽然代码跑下来是正确的，但是存在问题，计算height函数的sa
[rank[i]-1]可能会取到sa[-1]，我用gdb调试，发现读出来的sa[-1]=0�
��虽然这里不会影响代码运行，但是换了编译环境或换了个问
题，相似的代码可能会出现潜在的问题，没有RE，是因为访问
仍在程序的mem段里面。

RT,还有下面的例题《运送超级计算机》的输出格式描述有误��
�不是从行星A出发，可能是而是飞船的编号为A吧?
谢谢您的解答.

求刘汝佳老师教数据生成写法，或者uva的测试数据等

多边形的核只有一个点怎么处理啊，训练指南上的代码不能��
�理这种情况。
谢谢!

如图中所示，最长回文不应该是abccba么，但是为什么只返回��
�ada呢？是不是代码存在漏洞？

要保证每个结点的度数为偶数,不然
对于这组数据:
1
5
2 3
3 4
4 1
4 5
1 2
标程输出:
Case #1
1 2
2 3
3 4
4 5
4 1
答案应该是不存在

轮廓线动态规划铺放骨牌那题代码仓库的代码TLE了.
还有第六章LA3532圆并那一题getLineCircleIntersection在标程中似乎�
��有写完？可还是AC了.
谢谢.

如果这个交点是无效的呢?

书上写的例题11-10的UVa题号是11264，应该是1349。git中的代码的
题号是正确的。

第50页
left(i,j)= max(left(i-1,j), lo+1);

我认为应更改如下
left(i,j)= max(left(i,j-1), lo+1);

希望尽快核实

发现了几个貌似问题的，不知道是不。。。
P19 貌似i==4和i==5的情况写反了
P24 search的代码里
if(search(dep+1))return 
true;没有把改的改回来，直接return了，貌似只能找到一个解
还有貌似代码里没有体现前文所说的“每次只需要考虑编号��
�小的牌。

  如题，求教

倒数第二小节，复杂度那边，O(2^(n/2)*logn)即O(1.44^(n)*logn)
sqrt(2)=1.414

UVA 1621 Jumping Around
UVA 1670 Kingdom Roadmap
这两道题在UVA一直在WA，但是发现在CF的gym上提交可以通过。
然后应该不是多组数据的问题，而且把CF其他人的代码提交也
是WA。

时限只有1s, 不知道是服务器过慢还是时限改小了... 

标程没有考虑一些可以直接计算的情况:
1. m, n同时为偶数无解.
2. mn = 0, 无解.
3. m=1, n为偶数仅有一解.

而且数据中似乎存在大量重复, 个人以为应该预处理(m,n)为(2, 
50), (3, 33), (4, 25), ... ,(9, 11), (10,10)的情况, 可以得到诸如(2,2), 
(2,3), ... ,(2,49)的结果, 记录后直接输出即可.
加上上述优化可以在0.03s左右AC. :)
---------------------------------
另外P385 update函数中:
if(TEST(m,b)) d[cur][CLEAR(m,b)] += d[1-cur][a];
TEST函数和CLEAR函数中m, b的顺序和前文的描述不符, 应改为
if(TEST(b,m)) d[cur][CLEAR(b,m)] += d[1-cur][a];

对rank[]的注释说：“ 名次数组. 
rank[0]一定是n-1，即最后一个字符”，其实应该是“ 
名次数组. 
rank[n-1]一定是0，即最后一个字符”，代码中buildHeight()有rank[s
a[i]]=i;故rank[n-1]=rank[sa[0]]=0;

就像这个    Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide 
(Rujia Liu) :: Chapter 1. Algorithm Design :: General Problem Solving 
Techniques :: Exercises: Intermediate

What steps will reproduce the problem?
1.
2.
3.

What is the expected output? What do you see instead?


What version of the product are you using? On what operating system?


Please provide any additional information below.

由于我刚学到第三章结束，后面的内容都不了解
想向您请教这一题的算法或者思路（附件里是我自己写的程��
�，超时，而且不支持那么大的数据……）
对于进制转换的超大数据，是不是有什么技巧呢

例题26 约瑟夫问题的变形
约瑟夫原版问题答案为：f(n)=(f(n-1)+k)%n
该变形问题答案为：(m-k+1+f(n))%n
请问m-k+1是为什么呢？怎么变的？
谢谢！

题意应该是边的最小覆盖
但是文中的意思貌似并非如此 如1-2-3-4这四个点 
按文中的意思放到 1和4也ok 但是按题意应该要覆盖所有边 
这种情况下2-3这条边就没有被覆盖 

在分析中当n为奇数时,策略是:编号为偶数的人尽量往前取,编�
��为奇数的人尽量往后取.
在程序中是当(i%2 == 0)时尽量拿右边的礼物.这点不懂.

  刘老师您好，我是一名上海的学生，我在看这本书时收益匪浅，可唯一的问题就时有时一道例题会调试很久也不知道哪里错了，又找不到测试数据，很影响训练时间，请问哪里能找到例题的测试数据，谢谢 。

题目复述：
有n个任务，每个任务有3个参数r，d，w。r为任务开始时间，d�
��任务截至时间，工作量为w。任务在给定时间范围内可以被��
�度执行。
这n个任务可以在处理器上进行调度，处理器的工作速度为任�
��整数值。
限制为1<=n<=10000,1<=r<d<=20000,1<=w<=1000.
求出处理器在工作过程中的最大速度的最小值。

所求为最大最小值。
sample input：  
5  
1 4 2  
3 6 3  
4 5 2  
4 7 2  
5 8 1
总得来说，思路应该为二分和贪心，贪心选择最紧迫的任务��
�执行。我的问题是在贪心具体实现上
如样例：将每个时间点加入到一个set中，然后从begin()遍历到e
nd(),如样例所示：set中的时间点为1 3 4 5 6 7 
8，那每次取出一个时间片，然后贪心选择任务。结果是WA。��
�set换成了vector，先排序然后unique。。然后再取时间片，依旧�
��WA。。。。。。。。  
如1 3 4 5 6 7 8，分为1-3 3-4 4-5 5-6 6-7 
7-8这样的时间片，怎么会有错呢。。。
如果不使用时间片，从时间的开始（样例中为1）遍历至时间�
��结束（样例中为8），每循环走一个时间单位。结果为AC。
WA和AC代码对拍了一整夜了，同样也使用了if(w<=0) 
exit(-1)验证服务器数据是否有不合法。服务器数据都是合法的
，但是我的代码依旧为WA。
----------附上2份代码，首先是WA的------------
bool solve(int speed){
   priority_queue<job> q;
   int jobi = 0;
   set<int>::iterator endit = times.end();
   endit--;
   for(set<int>::iterator it = times.begin(); it != endit; it++){
     set<int>::iterator next = it; next++;
     for( ; jobi < n && jobs[jobi].r <= (*it) ; jobi++)
       q.push(jobs[jobi]);

     int work  = speed * ((*next) - (*it));

     while(work>0){
       if(q.empty()) break;
       job jtmp = q.top(); q.pop();
       //cout <<"work: " << work <<"@begin:" << *it << " taskbegin:"<< jtmp.r << " taskend:" << jtmp.d << endl;  
       if(jtmp.w == 0)
     continue;
       if(jtmp.d <= (*it))
     return false;
       if(jtmp.w > work) {
     jtmp.w -= work;
     q.push(jtmp);
     break;
       }else if(jtmp.w == work)
     break;
       else  //jtmp.w < work
     work -= jtmp.w;          
     }
   }
   while(!q.empty())
     if(q.top().w != 0)
       return false;
     else
       q.pop();  
   return true;
}
-----------------------------以下是AC代码-----------
bool solve(int speed){
   priority_queue<job> q;
   int jobi = 0;
   set<int>::iterator endit = times.end();
   endit--;
   int t = *endit,j=*(times.begin());
   while(j<t){
     for( ; jobi < n && jobs[jobi].r <= j ; jobi++)
       q.push(jobs[jobi]);

     int work  = speed ;

     while(work>0){
       if(q.empty()) break;
       job jtmp = q.top(); q.pop();
       //cout <<"work: " << work <<"@begin:" << *it << " taskbegin:"<< jtmp.r << " taskend:" << jtmp.d << endl;  
       if(jtmp.w == 0)
     continue;
       if(jtmp.d <= j)
     return false;      
       if(jtmp.w > work) {
     jtmp.w -= work;
     q.push(jtmp);
     break;
       }else if(jtmp.w == work)
     break;
       else  //jtmp.w < work
     work -= jtmp.w;          
     }
     j++;
   }
   while(!q.empty())
     if(q.top().w != 0)
       return false;
     else
       q.pop();  
   return true;
}
---------------------------------------------------
路过的同学老师工友们，求指教，谢谢。

[输入格式]的下一行: 即地图上的道路的条数(n<=0) 应改为 
即地图上的条数(n>=0)

我换了几台电脑都不行...

《训练指南》P259  例题1 Morley定理UVa11178 
输出格式应为“输出6个实数”而不是“输出6个整数”。

原题中说 This line contains six floating point numbers 

题目链接http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_pr
oblem&problem=2119

P388倒数第八行：
“如果新格子的颜色和它上方格子的颜色相同，则改成那个��
�子的颜色；”
应为
“如果新格子的颜色和它上方格子的颜色相同，则改成那个��
�子的联通分量编号；”

请问,奇数个条件做减法,偶数个条件做减法是怎么确定的?能��
�能详细说下容斥的过程

我是用半平面交的方法做这个题，但不知道为什么总是过不��
�？有trick吗？

What steps will reproduce the problem?
1.
2.
3.

What is the expected output? What do you see instead?


What version of the product are you using? On what operating system?


Please provide any additional information below.

题目：Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia 
Liu) :: Chapter 3. Data Structures :: Maintaining Interval Data :: 
Examples下的1400

测试案例：
499999 1
499999个1
1 499999

输出:
453688 499999

测速环境：
vs2013 + win8.1

问题是数组越界了，const int maxnode = 1000000 + 10; 
这个maxnode是错的。比如对于上面的案例，499998在线段树中对�
��的下标是1048573.

网上好像木有题解...谢谢!

P4 图1-1(b) 时间 应该是 
B[X]+B[Y]+J[Y]。对于图(a)，感觉加上时间的表达式会更加清楚些
。
P5 中间第三段 
对于1号来说，他给了4号x1枚金币，还剩下A1-x1枚。

感觉这两个地方有点问题。

想了好几天都没有想明白，网上也找不到题解，刘老师能提��
�一个具体思路吗？谢谢!

page 19 倒数第四行，
“因此i在循环体内不可见”
应为
“因此i在循环体外不可见”
。

这个链接里面的http://uva.onlinejudge.org/index.php?option=com_onlinejudge
&Itemid=8&category=93

另外《训练指南》的就把CII的题目都加入进去了

P30~31要求精确到10^-3，输出时却printf("%.5lf"....)