博文
Zju 1893 A Multiplication Game(2007-01-01 19:43:00)
摘要：
2187944
2007-01-01 19:14:20
Accepted
1893
C++
00:00.00
388K
Crux.D
这题好X难。
题目大概意思是：两人轮流乘一个2－9的数，从1开始乘，求谁的乘积先大于N。
如果是加法就好做了。凑到剩下的数能整除11，然后对称着加。问题是乘法。
所以寻找必胜点（段）。以1000为例。
1000 | 999 ... 112 | 若占住999到112，则对手必胜。必须让对手占领此段。
1000 | 999 ... 112 | 111 ... 56 | 因此必占段是 111 －? 。如果56被对手占住，则56×2＝112，入必败段。问题转化成为占56。
如此循环。如下 1000 | 999 ... 112 | 111 ... 56 | 55 ... 7 | 6 ... 4 | 3 ... 1
仔细考虑端点，我在处理端点情况时想了好久。
这是牛人的代码。
#include <stdio.h>
unsigned int N;
bool StanWins ()
{
// printf ( "%u\n" , N );
if ( N == 1 ) return true;
int step;
for ( step = 1; N > 1; step ++ )
if ( step & 1 ) N = ( N - 1 ) / 9 + 1;
else N = ( N + 1 ) / 2;
return ( step &a......
Zju 1184 Counterfeit Dollar(2006-09-15 17:49:00)
摘要：
2068160
2006-09-15 17:18:10
Accepted
1184
C++
00:00.00
844K
St.Crux
这是一个古老的题目，12枚硬币称3次，求出其中那枚轻或重的硬币。
当然，这道题比求解法简单多了，只需求证明。而我们知道，证明一样物体的存在，只需要把与其对立面的物体从物理层面乃至精神层面完全地、不留遗迹地消灭，这点在人类文明史中得到了最有力的支持......因此，最简单的办法是枚举24种情况，然后一一搜索，不满足者剔除即可。但显然这比较笨拙。
有没有简单一点的办法——假如不是12枚，而是12亿枚？好吧，同样是剔除，我们可以从判断语句入手。
比如 ABCD EFGH even 我们知道了这八枚都是even的。
又比如 ABCI EFJK up 我们知道了ABCI里必然有一枚是heavy的，而EFJK必然有一枚light。因此ABCI就是heavy的嫌疑对象，反之亦然。这是可能性。
从上面的语句中，我们还能得到隐含的条件：DGHL必然是even的。这是必然性。
所以，只要把不满足必然性的可能性剔除就OK了。
至于这个问题的解法，大致是用到二分，具体怎么写还有待研究。
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
int n, b[12], l0, l1, c[12];
string s0, s1, s2;
void proc();
void print();
int main()
{
//freopen("in.txt", "r", stdin);
cin >> n;
int i, k;......