PhoenixWright

比赛地址
题目不分难易，即使题目很简单，不同的人也会有不同的做法，多看别人的程序，可以拓宽自己的思路
Read more…

题目地址
题目大意是，给定一个小于50W位的数N，正常情况下，该数应该等于n^n,如果能找到一个n,使得n^n=N，则输出N，否则有可能是该数N中其中唯一的一位发生了错误(N的长度不变)，则应该输出-1
容易知道如果N的长度为1,则只有N＝＝1或N＝＝4才有解。
对于其他情况，首先我们知道n^n的位数应该等于w=log10(n^n)+1=nlog10(n)+1,由于数N最多为50W位，故容易得出n最大为100000,那么我们可以先二分找出n的值，然后判断n^n与N是否相等，如果相等则输出n,否则输出-1,那么如何判断相等呢
假设N原来的值为a,变化后的值为b,因为最多只可能改变一位，我们假设a+k*10^(n-1)=b,即a的第n位多了k,这里我们只假设k为正的情况，为负的同理，那么有0<=k<=9,且第n位加了k后不产生进位。我们即要判断a跟a+k*10^(n-1)是否相等，为了避免直接计算a的值，我们想到了应该对两边进行取模运算，那么应该对什么数求模，则如果发生改变，那么余数绝对不相等呢，这里我们取该数为99,那么对于n>=3有
(a+k*10^(n-1))%99 = a%99 + k * 10^(n-1)%99,因为10^(n-1)%99=1(n>=3)
所以(a+k*10^(n-1))%99 = a%99 + k %99
如果看出当k!=0时，a%99+k%99的值绝对不等于a%99的值，所以要判断n^n与N是否相等，只需判断n^n%99与N%99是否相等即可。
Memory: 808K
Time: 0.06S

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int M = 99;
char a[500002];
int Pow(int a, int b, int c) {
	int t = 1;
	while(b) {
		if(b & 1) t = t * a % c;
		a = a * a % c;
		b >>= 1;
	}
	return t;
}
int main() {
	int t, i, l, r, m, len, res, len1;
	scanf("%d", &t);
	while(t--) {
		scanf("%s", a);
		for(i = len = res = 0; a[i]; i++, len++) res = (res * 10 + a[i] - '0') % M;
		if(len == 1) {
			printf("%d\n", res == 1 ? 1 : (res == 4 ? 2 : -1));
			continue;
		}
		l = 3, r = 100000;
		while(l <= r) {
			m = (l + r) >> 1;
			len1 = (int)(m * log10((double)m)) + 1;
			if(len1 == len) break;
			if(len1 < len) l = m + 1;
			else r = m - 1;
		}
		if(Pow(m%M, m, M) == res) printf("%d\n", m);
		else puts("-1");
	}
	return 0;
}

比赛地址
题目其实都不是很难，但是细节要注意挺多的
Problem A: 数论+组合？
其实很容易就能得出公式为ans = (sum! / (a[0]! * a[1]! * ….*a[n-1]!)) % 200009，其中sum = a[0] + a[1] +… + a[n-1], 而难点就在于如何快速求得解。
我们先简化一下，求解ans = a / b % m的值，该式可以化为ans = ((a%m) * (x%m))%m,其中,x为b的逆元，即b * x = 1 (mod m), 容易得出，此即为求b*x + m * y = 1的解，这个可以用扩展欧几里德求解(m为素数的前提下)。
所以原题就是对除数求逆元，比赛时，有一个福大的同学很快就写出了正确的算法，可是却一直TLE或WA，在这里，对于求除数逆元，不能一个一个求逆元再乘起来，对于(a[0]!*a[1]!*…*a[n-1]!) * x = 1 (mod m),我们可以先求得a[0]!*a[1]!*…*a[n-1]!) % m 的值A,然后再去求A * x = 1 (mod m),可以知道，这样求出来的结果是等价的。
注意到数据的范围，可以一开即始预处理出1到40000内所有阶乘mod 200009的值，计算过程可能会超出32位，必须用long long,刚才说的那位同学，好像在求逆元的x%m处理上有问题，导致后面优化后的程序虽然不TLE了，可是却会出现负数造成WA。
Problem B: 题目很长，实际很水。。
Problem C: 算不上几何的几何？
这题就很简单了，也没有什么坑人的地方。给定一些圈圈，和两个点，问从一个点从到另一个点需要穿过几条弧。
这题是Topcoder上的一道题目，记得那时比赛时，算是最水的一道题了，可是不知为啥Petr竟然这题写了相当相当的长，匪疑所思，神牛也有考虑的太复杂的时候？
其实就是枚举每一个圈圈，对于每一个圈圈，如果两点都不在这个圈内或都在这个圈内，则不做任何处理，否则穿过的弧形数量+1
Problem D: 模拟题?
很有意思的一道简单模拟题。
其实，按逆时针方向进行打表，那么对于每次改变方向s,假设一开始方向为t,如果s==1，则t = (t+1)%8,如果是其他情况，则为t = (t + 1 + (s – 1) * 2) % 8 = (t + 2 * s – 1) % 8.土土模拟直到光线射出那个框为止
Problem E: 还没看，据说很恶心
Problem F: ???
其实这题应该也是很简单的，可是却是全场提交最多次，过的却很少的，相当WS的一道题，其实在其他细节的处理方面，很多同学第一次写的就都做的很好了，可是却是一直WA。其实在比赛的前几分钟，geng又对这题加了一组数据，也就是这组数据，卡住了众多的人，而这组数据很简单，就是只有一个常数。很多同学处理时，如果遇到系数为0的，都是直接忽略掉，这样在有其他项的时候是没有错，但是如果数据只有一个常数，那么他们那样处理，结果就是对该组数据没有任何输出，而这组数据其实应该是输出0.
对于为此题纠结了一个下午的同学，我替geng表示抱歉，但是这也提醒我们，要注意到对各种边界数据的考虑，往往就是那么一组数据，就是成功与失败的差别。

 比赛地址
这次的题目总体是比较水的，不过今天一直没在状态上，每道题平均起来都写了半小时以上-_-……….
Problem A:
求一个二叉树以某点为开始结点时，其他点到该点的最小路径（定义为到该结点的距离乘以结点的权值)
建好二叉树后依次对每个点进行深搜，求得最小值即可。
Problem B:
USACO上的题，莫名其妙的WA，过不了，解题详见USACO
Problem C:
给定一个n*n的01矩阵，求该矩阵里大小为2*2,3*3,4*4,…,n*n的子矩阵有几个，要求这些子矩阵里元素全为1,矩阵可以有重叠，即每两个子矩阵可以共用一部分方格。
预处理出该n*n矩阵中所有以(1,1)为左上角，(i,j) {i<= i, j<=n}为右下角的矩阵中所有元素的和f[i][j],然后枚举矩阵中的每个元素，以该元素的位置(i,j)为起始位置，测试从左上角(i,j)到右下角(i+k-1,j+k-1)的矩阵的和是否等于k*k{2<=k<=n},如果相等则k*k的子矩阵增加一个。
Problem D:
给定t,n和t个系数n1,n2,n3,…nt{n1+n2+…nt=n}，求(x1+x2+…+xt)^n展开式中x1^n1*x2^n2*…*xt^nt的系数的值
转变下思想，其实题目就是一个简单的组合数学题，给定n样物品放到t个箱子中，要求箱子1中有n1个物品，箱子2中有n2个物品…求所有可能的放法总数。
所以有res = C(n,n1) * C(n-n1,n2) * C(n-n1-n2,n3)*…*(n-n1-n2…nt-1,nt)
Problem E:
1+q+q^2+q^3+……+q^(n-1) 的和对1000000007的模
注意到1<=q<=10^18,1<=n<=10^9，故简单的一个线性扫描肯定会超时。
                                  q      1                    q^n     1+q+q^2+…+q^(n-1)
我们构造一个矩阵A=     0      1,则有A^n =   0         1
故二分求B=A^n，结果存放在B[0][1]中。
Problem F:
给定两个字符串A和B，它们的距离是这样定义的，在A B这两字符串中的任意位置添加任意个空格，当添加后两个字符串相等时，从第一个字符开始比较，如果第i个字符都是非空字母，则距离加上两字母相减的绝对值，如果一个为字母一个为空格，则加上一个给定的值k,如果两个都是空格，则不用加，要求在所有添加空格的方法中，最后得出的距离值最小的即为A和B的距离，求该距离
我们构造一个二维数组f[i][j]代表当匹配到A[i],B[j]时两者的最小距离，那么有
如果将A[i],B[j]进行配对，则f[i][j] = f[i-1][j-1] + abs(A[i]-B[j])
如果将A[i],与空格配对，则f[i][j] = f[i-1][j] + k
如果将B[j]与空格配对，则f[i][j] = f[i][j-1] + k
所以状态转移为f[i][j] = min(f[i-1][j-1] + abs(A[i]-B[j]),f[i-1][j] + k,f[i][j-1] + k)
最终结果在f[la][lb]中，la,lb为字符串A,B的长度（下标从1开始）注意f[i][j]的初始问题，f[0][0]=0,
f[0][j] = j * k, f[i][0] = i * k,具体原因自己想一下即可知道。

这次题目是面向新生的，所以总体来说是比较简单的，除了B题有考到简单深搜的算法，其他都算是比较入门的题目，稍微注意点细节应该就能通过。
A: 雷达系统
用S记录合法的总时速，用T记录不合法行驶的车辆总数。
对于每个测到的时速，如果在限定范围内，则加到总时速S里，否则T增加一，最后判断不合法行驶的车辆总数是否超过总车辆数的10%,如超过则直接输出0.00,否则用S除以合法行驶的车辆数 (总车辆-T)
B: 粉刷迷宫
这题算是这些题里比较中等的一道题。
设总墙数为S。
因为要求的是从外部进去所能看到的墙壁数，所以只须先对矩阵最外围的一圈遍历一下，如果遇到墙，则S加1,如果是space,那么首先将该点标记一下，然后遍历递归遍历其四周，如果是墙，则S加1但不递归,如果是已标记则不递归，如果是space，则继续递归执行。最终S的值即为答案。
C: 跑商
模拟题。
这题或许在读题时会稍微耗点时间。
在模拟的过程中，必须记录两个值，一个是当前所买货物总量T，一个是当前总钱数S。
注意到对于地点的变化，是每5个一个循环，时间的变化是每12一个循环，所以每次模拟，对于地点的变化，只须直接模5,对时间变化模12,再找到相应的值，按题目要求的卖出再买进，然后判断是否S会大于等于原始钱数的两倍即可。
D: 圆柱体
首先注意，对于这种要用到PI的题目，为了保证精度，都取PI=acos(-1.0)。
我们知道圆柱体表面积S=2*PI*R^2+2*PI*R*H (1),体积V=PI*R^2*H (2),两者连立，易得R*S/2-PI*R^3=V,我们对f(R)=R*S/2-PI*R^3进行求导得，f’(R)=S/2-3*PI*R^2,因为要V的最大值，所以令S/2-3*PI*R^2＝0,易得R=sqrt(S/(6*PI)),再将R代入(1),(2)两式即可求出H跟V的值。
E: 陶陶抢苹果
用一个结构体记录每个陶陶的体重和其初始位置以及拿到的苹果总重量，首先将该结构体按体重降序排序，将给定苹果重量降序排序，然后依次模拟将苹果赋给相应的陶陶，最后将结构体按初始位置升序排序，输出每个陶陶拿到的苹果总重量
F: 最小非负值
咋一看很可怕的题，原来是道彻彻底底的水题。任取连续的4个数a,b,c,d，易知a+d=b+c,因而对于数列
A1,A2,…,An,我们从后往前构造，可以有 + An-3 – An-2 – An-1 + An = 0,那么到最后有4种情况
(1)刚好全部四个四个一起配对，所以数列An总和为0
(2)只剩1个，即剩下1,则和为1
(3)只剩2个，即1, 2,那么和应为-1+2=1
(4)只剩3个，即1, 2, 3,那么和应为+1+2-3=0
所以只须对给定的n对4求余，再对余数进行判断即可。

很囧很囧。。。结果就不说了，Just 总结下目前会的题目。。
比赛地址
A：Accept
枚举4个点，判断是垂直，一个O(n^4)就能过
B：Choose ACMer
模拟题，注意09级比08级年轻，应该排在前面，，还有在计算最优的前n-2个分数时，，要直接用加的，不要用总的n个的和减去最差的2个，这样会造成精度问题。。
C：Heroes General Assembly
数论题。
题目即求a^b = 1 (mod c)中,b的最小值。
设b的最小值为e, 根据欧拉定理有，e | phi(c),其中phi(c)为欧拉函数，但是反过来并不成立，即不是充要条件。
所以我们先求出c的欧拉函数，然后对其分解素因子，再暴力枚举所有c的因子（不一定为素因子），取符合a^b = 1 (mod c)的最小值即可。
D：Largest Group
线段树。还没想到建树的方法。。
E：Magic String
找规律题。题目还没看。。
F：Put Coin Game
博弈题。试放所有位置的圆，求出每个table的SG值，再将所有的table的SG值求异或即可
G：Rotate rotate and rotate
几何题？？直接一个体积公式解决。注意PI要取acos(-1.0)….
H：Try
图论题。据说正解是拆点套用网络流，此方法不会-_-。偶是将每个钥匙能用几次就拆成几个点，然后建图套用二分图的最大匹配，，，如果数据过大，这方法就不行了。。。
I：Number Cutting Game
DP题。定义dp[i][j]=true代表前i个数，进行任意组合能得到余数j。那么有
if(dp[j][k]) dp[i][(k+num[j+1][i])%m] = true;{j<=i-1}
其实m为要模的数，num[j+1][i]代表数串中第j+1到第i个形成的数字对m求余的值。这个要首先通过预处理求得，否则会超时。总的复杂度为O(n^3)。
J：Number Reversing Game
搜索题。双向广搜+hash，赤裸裸的暴力。。
K：Special max_heap
组合数学？题目还没看。。。