Archive for the ‘题解’ tag
Time Limit Exceeded 结束 && Happy Valentine’s Day~
昨天搞完了 Time Limit Exceeded, 现在还有一道题TESTGEN没有测试, 其余题目我们 YaohuaFree 的 Rank 是 41, 得分很诡异地竟然是 1234 分 (Rank List). 还算可以接受吧, 不过很可惜最后还是没有达成超过 lonelycorn 和搞掉 CLASS 这两个目标.
简单的说一下题目.
- Key to C (KEY)
这道题是我们第一道出的题目, 也是搞得最久的一道题目, 不过事实证明这道题根本拉不开分差 — 最高的 154 分, 而我们 126 分就 20 多名了. 和其他的题目的 rank 1 动辄上千分比起来, 这道题做了基本相当于没做.
题目要求读入一些数, 判断它们的二进制表示是否回文. 评分标准和很多东西有关, 比如程序中关键字的个数 (这个权重最大), 比如空格个数, 比如代码长度… 总之这些东西都是越多得分越低. 然后代码回文会得到 extra bonus, 貌似是 4 倍多分数吧.
基本的做法就是?:操作符加main递归, 貌似 rank 1 那个也就这么做的. - Play with Code (SHORTEN)
给出一个代码要求缩短. 这道题最终也不知道那个代码到底啥意思, 只看懂了一段求素数. 而且那个代码在我们几个人的机器上跑貌似都 RE 掉了… 评分规则是代码长度越长分数越少.
最终的做法是物理缩短… 也就是 define 一个 for 啊, 改一点变量名啊… 就这样子… - Produce the Code (INPUT)
给出一个输入文件和一个输出文件, 要求写一个程序, 对于这个输入文件能够输出给出的输出文件. 当然可以不理睬输入文件直接把输出文件打出来 (我的第一个 code 的确是这么干的), 不过这样代码长度会很长, 而这道题的评分规则也是代码长度越长分数越少…
这道题由三个人合力完成… 先是来帮忙的 xhy 同学看出了替换规则 (我就是一直卡在这里), 然后我折腾出了乱序的规则, 最后是木木同学的 coding… 虽然 rank 不高不过做得很爽. - #ED (CODEHASH)
给出一段代码, 给一个 hash 函数, 要求代码输出自身的 hash 值.
貌似有人用 whitespace 来搞, 不过还是比较 orz 那个 rank 1 的, 就一句代码… 很强大.
这题我们一点没动. - COMPILE ERROR (CLASS)
我最想做出来的题, 但可惜最后也没做出来.
要求写一个类 multiply, 里面包括一个函数 mult(int a, int b), 函数的功能是输出 a * b 的结果, a, b 都小于 10000. 变态就变态在不允许用空白字符…
见到了两种解决方法, 一种是官方的 (之所以说官方因为这道题提示了要用 typedef, 如果认为题目描述的那个 "typedefine a class" 不足以说明问题, 那么自己去翻 forum), 另一种很诡异, 用一个不可见字符替代了空白字符还编译通过了… 据说那个字符是 \f, 从来没见过… - PRINT D PENGUIN (PENGUIN)
给一个字符画, 是 Linux 那个企鹅. 要求输出这个东西.
基本就是考压缩, 我因为怕编译器没法处理所以只压缩成了可见字符, 但是事实证明编译器是可以处理不可见字符的, 因为 rank 前几名的都用了不可见字符. 我很无奈, 不过可见字符范围的压缩我基本是搞到极限了, 还比较有成就感. - PRINT ME (PRINT)
这道题是前来帮忙的 xhy 写的, 题目要求很简单, 输入一个数, 如果是偶数那么输出代码本身, 否则反转代码输出.
xhy 写了一个回文的代码, 这样就不用管奇数偶数了, 而且根据题目还可以获得 200 pts 的加分.很不错.
最后一天用了很短的时间完成的 code, 得分还不低 (貌似是所有题里 rank 最高的一个), 或许是性价比最高的一个 code 了. - P=NP (NP)
这道题的题目描述讨论了半天也没明白, 最终放弃. 直接贴出英文题目描述, 做出来的神牛 (比如 oldherl) 来讲解一下…
"Given an directed graph, find out the minimal set of vertex such that all vertex not in the set have atleast one edge in the set." - P!=NP (TESTGEN)
这道题是为上一道题出测试数据 (想起 SRM 了), 以上一道题 submit 的代码跑的情况评分. 因为前一道题没看懂, 加上最后还有 10 分钟的时候才开写, 所以输出了一个基本是完全图的图草草了事. 这道题至今还没出成绩. - Arbit Code (ARBIT)
此题做的比较爽. 给一段会 TLE 的代码 (实际测试证明还会 RE), 要求改成能够 AC 的代码. 不知道代码是干什么的, 只有数据范围.
这道题我们的做法是, 把一个范围内 (刚开始是 1~20, 后来为了测试增加到了 1~50) 的所有输入全部打出来, 然后分析规律.
刚开始的成果是, 求 f(a, b)的时候, 把 b 从 1 到 a 列出表格, 发现每到 a 的约数才发生变化.
接下来我发现对于素数和素数的幂, 它们的 f 的变化规律是按照比它小的幂变化 (不太好描述, 想知道的话自己输出几个比如 a = 27 或者 16 就能发现了).
然后木木又发现了 f(a, 1) = phi(a) (这里 phi 是欧拉函数).
最后时刻木木大胆猜测:
当 b = 1 时, f(a, b) = phi(a);
当 b 不是 a 的约数 (a % b != 0) 时, f(a, b) = f(a, b – 1);
当 b 是 a 的约数时, f(a, b) = f(a, b – 1) + f(a / b, 1).
然后写了个 code submit 上去, 挂了.
差点就认为这个推测不对, 但是本地测试 100 以内的数据发现和给出的程序输出完全匹配.
最后偶然发现, 有一句要做 t * ((i – 1) / i) (不用说也知道是求欧拉函数时候写的), 我当初写的是 t * (i – 1) / i, 而 t * (i – 1) 会爆掉 int… 改成 t / i * (i – 1) 就 AC 了. - Give It a try (THINK)
这道题是最有意思的, 要求破解三个密码, 没有任何提示.
第一个密码很简单, 一篇文章, 把里面所有的大写字母挑出来拼在一起, 就是答案了.
第二个密码是一个 32 * 241的 01 矩阵, 最后也不知道是啥意思, 只知道答案是 2.
第三个密码, 刚开始一看就感觉是一个简单的 26 个字母的置换, 然后还推出了 p => e, 另外还找到了三个 p 连在一起的一个突破口. 但是无奈没有破解经验, 加上文章里竟然 26 个字母都是齐全的, 让我有点打退堂鼓, 所以没有一鼓作气破解出来, 很遗憾. 其实想想, 当初直接按照统计学的字母出现频率解密, 然后再做微调, 应该都可以把密码破出来了… 很无奈.
比赛基本就是这样, 最后的 1234 分真的不是有意为之… 运气比较好吧.
——————-我是爱情的分隔线——————-
今天情人节, 白天在家待了一天 (本来说要和 lxc, djs 去打台球, 一想今天人应该多就没去), 晚上去 FNOI (还迟到了), 就这么度过了情人节.
放一张图, 从 M67 那里看到的, 来源是 Abstruse Goose (来源页面).
祝各位情人节快乐, 估计我能在本科上完之前找到第一个 GF 就很不错咯… 光棍节还可以一直过下去, 很满足很满足…
p.s. 文章写完正好 0:00, 情人节过去了… 这篇文章的分类想了很久是 About Computer 还是 About
Life, 最终还是放在了前者里…
NOIP 2008 第四题 双栈排序(twostack) 题解
这可能是第一份正确的完整题解.
这个帖子: http://www.oibh.org/bbs/thread-26983-1-2.html 是此算法的来源,但是帖子中说的不是很清楚,而且没有证明.题解中将把这些问题解决.
十分感谢inzaghi250(sqybi注:还好我不是inzaghi的fans…)提供的算法.
这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1q2的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1q2的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.
第一步需要解决的问题是,判断是否有解.
考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].
首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下:
…q1[i]…q1[j]…
因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的.
接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是”如果不满足条件p,那么这两个数一定可以压入同一个栈.”
不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数r,满足j<k<r且q1[r]<q1[j]<q1[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q1[k]对q1[j]没有影响).
第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.
这样,原命题的逆否命题得证,所以原命题得证.
此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证.
这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是否存在i<j<k满足p1[k]<p1[i]<p1[j].如果存在,那么在点i和点j之间连一条无向边,表示p1[i]和p1[j]不能压入同一个栈.此时想到了什么?那就是二分图~
二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中.
此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解.
此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解.
实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1.
又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~
还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了O(n^3).解决方法就是,首先预处理出数组b,b[i]表示从p1[i]到p1[n]中的最小值.接下来,只需要枚举所有数对(i,j),检查b[j+1]是否小于p1[i]且p1[i]是否小于p1[j]就可以了.
附代码(除去注释不到100行),带注释.代码中的a数组对应文中的队列p1.
已经过掉所有标准数据,以及5 7 2 4 1 6 3这组让很多贪心程序挂掉的数据~
xpycc November 29th, 2008 at 09:24
这位大牛不妨试试以下数据：
1000
2 3 4 5 … 1000 1
对于这组数据 MS 您的程序崩溃了……原因是这组数据中无向边的条数为 999*999 ，而您的内存只申请了 1002*2 。
sqybi November 29th, 2008 at 11:29
@xpycc
嗯…程序貌似是有bug的…
而且判无解的地方貌似也有问题…
#include
using namespace std;
const int nn = 1002, mm = nn * 2, inf = 1000000000;
int n, tot, now;
int a[nn], b[nn], head[nn], color[nn];
int adj[mm], next[mm];
int stack[3][nn];
bool result;
void addEdge(int x, int y) //加边
{
++ tot;
adj[tot] = y;
next[tot] = head[x];
head[x] = tot;
}
bool dfs(int i) //DFS染色,检查图是否是二分图的经典算法
{
int temp = head[i];
while (temp) //邻接表,检查每一条边
{
if (! color[adj[temp]]) //如果与当前结点的结点还未染色
{
color[adj[temp]] = 3 - color[i]; //进行染色
dfs(adj[temp]); //DFS
}
if (color[adj[temp]] == color[i]) return false;
//如果两个相邻结点染色相同,说明此图不是二分图,返回无解
temp = next[temp];
}
return true;
}
int main()
{
freopen("twostack.in", "r", stdin);
freopen("twostack.out", "w", stdout);
//输入
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
//预处理b数组
b[n + 1] = inf;
for (int i = n; i >= 1; -- i) b[i] = min(b[i + 1], a[i]); //"min" in STL
//枚举数对(i,j)并加边
tot = 0;
for (int i = 1; i <= n; ++ i)
for (int j = i + 1; j <= n; ++ j)
if (b[j + 1] < a[i] && a[i] < a[j])
{
addEdge(i, j);
addEdge(j, i);
}
//DFS染色
memset(color, 0, sizeof(color));
result = true;
for (int i = 1; i <= n; ++ i) //每次找当前未染色的编号最小的结点,并染颜色1
if (! color[i]) //当前位置尚未被染色
{
color[i] = 1;
if (! dfs(i)) //染色时出现矛盾,此时图不是一个二分图,即无法分配到两个栈中
{
result = false; //记录无解
break;
}
}
if (! result) //无解
printf("0");
else //有解
{
//模拟求解
now = 1;
for (int i = 1; i <= n; ++ i)
{
//将当前数字压入对应的栈
if (color[i] == 1)
printf("a ");
else
printf("c ");
stack[color[i]][0] ++;
stack[color[i]][stack[color[i]][0]] = a[i]; //this will work even if stack[1][0] = 0
//循环检查,如果可以的话就从栈顶弹出元素
while (stack[1][stack[1][0]] == now || stack[2][stack[2][0]] == now)
{
if (stack[1][stack[1][0]] == now)
{
printf("b ");
stack[1][0] --;
}
else if (stack[2][stack[2][0]] == now)
{
printf("d ");
stack[2][0] --;
}
now ++;
}
}
}
}
TopCoder SRM 413
Div 2果然是水题.第一次SRM,变黄.
yuhch不好好出题啊…
此文测试插件用 有爱者可以忽略
第一题,纯水.贴TC的标程:
double minTime(int length, int maxAcceleration, int maxVelocity) {
double t1 = sqrt(length / double(maxAcceleration));
if(maxAcceleration * t1 > maxVelocity) {
double t2 = maxVelocity / double(maxAcceleration);
return (length - maxAcceleration * t2 * t2) / maxVelocity + 2 * t2;
} else
return 2 * t1;
}
第二题,我的做法是求解一大堆不等式:
假设给出了a0,a1,a2,…其中a1,a2…分别等于[a1],[a2]…,那么
a1-a0<=d<a1-a0+1
a2-a0<=2*d<a2-a0+1
…
TC给出的代码如下:
double minCommonDifference(int a0, vector seq) {
// fraction representing 0/1 (minimum permissible value)
pair res(0, 1);
// find d
for(int i = 0; i < seq.size(); ++i)
if(res.first * (i + 1) < (seq[i] - a0) * res.second) {
res.first = seq[i] - a0;
res.second = i + 1;
}
// check whether a solution is possible
for(int i = 0; i < seq.size(); ++i)
if(seq[i] != a0 + (i + 1) * res.first / res.second)
return -1;
return res.first / double(res.second);
}
出现问题了…先测试到这里
刚才看了一下,Zoundry瞎改HTML.没办法,以后只能到blog后台来写了…装个增强的WYSIWYG插件去…
update:WLW竟然可以用!没想到啊.
继续写完.
第三题看似范围很大,实际用到的状态并不多,所以开一个map做记忆化搜索就解决问题.继续贴TC的代码:
map mem;
long long calc(long long n, int p, int q) {
if(n == 0)
return 1;
if(mem.count(n))
return mem[n];
mem[n] = calc(n / p, p, q) + calc(n / q, p, q);
return mem[n];
}
这次题目就这样,很水了…
WLW似乎也把line参数给吞了…泪奔…
关闭了可视化编辑器,希望这次能行…
以后就得这么发代码了…