PhoenixWright

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

简单深搜,注意如何判断两个方块是否相通

#include <iostream>
using namespace std;
#define TOLEFT(T) ((T) == 'A' || (T) == 'C' || (T) == 'F' || (T) == 'G' || (T) == 'H' || (T) == 'I' || (T) == 'K')
#define TORIGHT(T) ((T) == 'B' || (T) == 'D' || (T) == 'F' || (T) == 'G' || (T) == 'I' || (T) == 'J' || (T) == 'K')
#define TOUP(T) ((T) == 'A' || (T) == 'B' || (T) == 'E' || (T) == 'G' || (T) == 'H' || (T) == 'J' || (T) == 'K')
#define TODOWN(T) ((T) == 'C' || (T) == 'D' || (T) == 'E' || (T) == 'H' || (T) == 'I' || (T) == 'J' || (T) == 'K')
int h, w;
char mp[60][60];
int v[60][60];
const int dh[] = {-1, 0, 1, 0};
const int dw[] = {0, 1, 0, -1};
const int ZONG = 0;
const int HENG = 1;
bool isConnect(int h1, int w1, int h2, int w2, int dir) {
    if(dir == HENG) {
        if(w1 > w2) {
            swap(h1, h2);
            swap(w1, w2);
        }
        return TORIGHT(mp[h1][w1]) && TOLEFT(mp[h2][w2]);
    } else {
        if(h1 > h2) {
            swap(h1, h2);
            swap(w1, w2);
        }
        return TODOWN(mp[h1][w1]) && TOUP(mp[h2][w2]);
    }
}
void dfs(int i, int j) {
    v[i][j] = 1;
    int th, tw;
    for(int k = 0; k < 4; ++k) {
        th = i + dh[k];
        tw = j + dw[k];
        if(th < 0 || th >= h || tw < 0 || tw >= w || v[th][tw] == 1 || !isConnect(i, j, th, tw, ((k&1)?HENG:ZONG))) continue;
        dfs(th, tw);
    }
}
int main() {
    int ans;
    while(scanf("%d%d", &h, &w)) {
        if(h < 0 || w < 0) break;
        ans = 0;
        for(int i = 0; i < h; ++i) scanf("%s", mp[i]);
        memset(v, 0, sizeof(v));
        for(int i = 0; i < h; ++i)
            for(int j = 0; j < w; ++j) if(v[i][j] == 0) {
                ++ans;
                dfs(i, j);
            }
        printf("%d\n", ans);
    }
}

持续了几天的雨,将我们从严热的夏天带进了寒风凛冽的冬天,依稀记得前些天还是短袖加短裤的清凉装扮,就这么突然间,裹得严严实实,福州的冬天就这样悄然而至.

没有北国冬天早晨一觉醒来满世界白雪皑皑的惊叹,也没有南国冬日暖和的太阳,唯有寒风阵阵,福州的冬季.

在这个寒冷的冬季,仿佛整个人也变得懒散起来,只想美美的躲在被窝里,睡上一整天,难得碰上个比较暖和的下午,泡杯热茶,就那么开着电脑,看看电影,原来生活可以这么简单,慵懒的季节.

人往往闲下来的时候,思考的东西就多了.自从今年的ACM/ICPC结束了之后,我仿佛就陷入了无事可做的囧境.两年的ACM/ICPC生涯,让我受益颇多,结识了很多的朋友,也让我的coding水平有了很大的一个提高.虽然期间有过艰难的抉择,但我最终选择了坚持,我相信,这两年我是很乐在其中的.现在一切都已经尘埃落定,而我是否也应该开始一段暂新的征程了.说来好笑,自从上海比赛结束之后,我电脑竟然再没打开过一次IDE,昨天要交操作系统作业时,悲剧的发现电脑上没有C++的编译器了,顿时感慨万千,难道,ACM结束之后,我真的就要远离coding了么.CODE IS POETRY.wordpress官网上如是写到.是的,代码如诗,正如同我搞ACM的目的一样,我是为了享受其间敲代码的乐趣,那种乐趣,是一般人所无法体会到的.所以我想,我是不会就此放弃coding的,给我些时间,我将在其他领域卷土重来,延续我的精彩.

冬季的安逸,是为了春天的萌芽.

CODE IS POETRY….

1062* 昂贵的聘礼 枚举等级限制+dijkstra
1087* A Plug for UNIX 2分匹配
1094 Sorting It All Out floyd 或 拓扑
1112* Team Them Up! 2分图染色+DP
1135 Domino Effect 最短路
1149* PIGS 网络流
1161* Walls floyd
1201 Intervals 差分约束
1236* Network of Schools 强联通
1251 Jungle Roads MST
1273 Drainage Ditches 最大流
1275* Cashier Employment 差分约束
1364 King 差分约束
1459 Power Network 网络流
1502 MPI Maelstrom floyd
1511* Invitation Cards 最短路
1637* Sightseeing tour 混合图欧拉回路-网络流
1716 Integer Intervals 差分约束
1724* ROADS 最短路-拆点
1780* Code 欧拉回路
1789 Truck History 最小生成树
1797 Heavy Transportation 最小生成树
1847 Tram 最短路
1904* King’s Quest 强联通
1949 Chores 最短路
2060 Taxi Cab Scheme 2分匹配
2075 Tangled in Cables 最小生成树
2112 Optimal Milking 网络流
2125 Destroying The Graph 最小割
2135 Farm Tour 费用流
2139 Six Degrees of Cowvin Bacon floyd
2230 Watchcow 欧拉回路
2267* From Dusk till Dawn or: Vladimir the Vampire 最短路
2289 Jamie’s Contact Groups 网络流
2337 Catenyms 欧拉通路
2349 Arctic Network 最小生成树
2369 Genealogical tree 拓扑序
2387 Til the Cows Come Home 最短路
2391* Ombrophobic Bovines 最大流
2394 Checking an Alibi 最短路
2396* Budget 网络流
2421* Constructing Roads 最小生成树
2455 Secret Milking Machine 网络流
2457 Part Acquisition 最短路
2516 Minimum Cost 费用流
2553* The Bottom of a Graph 强联通
2570 Fiber Network floyd
2584 T-Shirt Gumbo 网络流
2723 Get Luffy Out 2-sat
2724 Purifying Machine 2分匹配
2728 Desert King 最优比例生成树
2749* Building roads 2-sat
2762 Going from u to v or from v to u? 强联通
2949* Word Rings 差分约束
2983 Is the Information Reliable? 差分约束
2987 Firing 最小割(求解正确性??)
3020 Antenna Placement 2分匹配
3041 Asteroids 2分匹配
3072* Robot 最短路
3160 Father Christmas flymouse 强联通
3164 Command Network 最小树形图
3169 Layout 差分约束
3177 Redundant Paths 双联通分量
3189 Steady Cow Assignment 网络流
3204 Ikki’s Story I – Road Reconstruction 最大流
3207 Ikki’s Story IV – Panda’s Trick 2分图
3216 Repairing Company 2分匹配
3228 Gold Transportation 网络流
3255 Roadblocks 最短路
3259 Wormholes 最短路
3268 Silver Cow Party 最短路
3275 Ranking the Cows floyd
3281 Dining 最大流
3308 Paratroopers 最小割
3310 Caterpillar
3311 Hie with the Pie floyd
3328 Cliff Climbing 最短路
3343 Against Mammoths 2分匹配
3352 Road Construction 桥
3439 Server Relocation 最短路
3463 Sightseeing 最短路
3469 Dual Core CPU 最小割
3487 The Stable Marriage Problem 稳定婚姻
3522 Slim Span 最小生成树
3594 Escort of Dr. Who How 最短路
3623 Wedding 2-sat
3653 Here We Go(relians) Again 最短路
3659* Cell Phone Network 最小支配集
3660 Cow Contest 拓扑
3662* Telephone Lines 最短路
3678 Katu Puzzle 2-sat
3683* Priest John’s Busiest Day 2-sat求解
3687 Labeling Balls 差分约束 或 拓扑
3692 Kindergarten 2分匹配
3694 Network 无向图缩点

题目地址
给定一个不大于10^100的数K和一个不大于10^6的数L,求是否存在K的最小素因子,且该因子小于L
暴力即可,为了方便,使用JAVA
Memory: 9516K
Time: 1485MS

import java.io.*;
import java.util.*;
import java.math.*;
 
public class Main {
 
    private int[] a;
    private int top;
 
    private void init() {
        a = new int[1000001];
        a[0] = 2;
        top = 1;
        for (int i = 3; i <= 1000000; i += 2) {
            if (a[i] == 0) {
                a[top++] = i;
                for (int j = i + i; j <= 1000000; j += i) {
                    a[j] = 1;
                }
            }
        }
    }
 
    private void creat() {
        init();
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        next:
        while (true) {
            String b1 = cin.next();
            int b2 = cin.nextInt();
            if (b1.compareTo("0") == 0 && b2 == 0) {
                break;
            }
            BigInteger a1 = new BigInteger(b1);
            BigInteger a2 = new BigInteger("0");
            for (int i = 0; i < top && a[i] < b2; i++) {
                if (a1.mod(a2.valueOf(a[i])).compareTo(BigInteger.ZERO) == 0) {
                    System.out.println("BAD " + new Integer(a[i]).toString());
                    continue next;
                }
            }
            System.out.println("GOOD");
        }
    }
 
    public static void main(String[] args) {
        Main e = new Main();
        e.creat();
 
    }
}

题目地址
给定一个仅由小写字母组成的序列,按一定的规则排列,输出给定序列在排在所有序列中的哪里
规则是,长度短的排在前面,长度相同的,按字典序排序,而且序列是合法的当且仅当从左算起第i位的字母必须严格小于第i位后面的所有字母,即vwxyz是合法的,vwyxz是不合法的.
一个大致序列如下:
a -> 1
b -> 2
    .
    .
z -> 26
ab -> 27
ac -> 28
    .
    .
az -> 51
bc -> 52
    .
    .
vwxyz -> 83681
对于不合法序列,输出0
首先,我们先不考虑序列不合法的情况,那么对于一个n位的序列,其位置可能达到s=C(26,1)+C(26,2)+…+C(26,n),我们算出s的值,然后再减掉不合法的序列以及大于给定序列的其他序列的情况.假设给定序列是abcd,n=4,那么我们减掉所有以a以后字母开头的序列个数,即C(25,4),现在我们剩下的就是以a开头的不合法序列和大于abcd但小于axyz的合法序列,对于第二位,我们减掉以b以后字母为第二位的序列,即C(24,3),现在剩下的是以ab开头的不合法序列和大于abcd但小于abyz的合法序列,以此类推即可.
Memory: 132K
Time: 0MS

#include <iostream>
using namespace std;
int C(int n, int r) {
	int i, j, s = 1;
	if(n - r > r) r = n - r;
	for(i = 0, j = 1; i < r; i++)
		for(s *= n - i; j <= r && !(s % j); j++) s /= j;
	return s;
}
int main() {
	char s[6];
	int l, i, j, res;
	while(scanf("%s", s) != EOF) {
		l = strlen(s);
		res = 0;
		for(i = 0; i < l - 1; i++)
			for(j = i + 1; j < l; j++)
				if(s[i] >= s[j]) {
					puts("0");
					goto next;
				}
		for(i = 1; i <= l; i++) res += C(26, i);
		for(i = 0; i < l; i++) res -= C(122-s[i], l-i);
		printf("%d\n", res);
next:;
	}
	return 0;
}

题目地址
这题着实写了大半个下午..
题目大意是求A^B中,所有因数的和模9901的值.
稍微推下公式易知,对于一个数A,若A=p1^n1 * p2^n2 * P3^n3….,其中p1,p2,p3..都是A的质因数,则其所有因数和应该为(p1^0 + p1^1 + p1^2+…+p1^n1) * (p2^0 + p2^1+…+p2^n2) * …所以A^B的所有因子和为(p1^0 + p1^1 + p1^2+…+p1^(n1*B)) * (p2^0 + p2^1+…+p2^(n2*B)) * …,根据几何级数的求和公式有,sum = (p1^(n1*B+1) – 1) / (p1-1) * (p2^(n2*B+1) – 1) / (p2 – 2) *…
题目即求sum % 9901的值.
而对于该式,我们只需用对分子的积求模,然后乘以分母对9901的逆元即可,求逆元用扩展欧几里德.
这里有一个恶心的地方,对于某个数p1,如果p1%9901的值等于1,那么套用上述公式是不正确的,因为此时相当于几何级数中的倍数为1,那样是不能套用公式的,正确的和应该为n1*B+1.
Memory: 144K
Time: 0MS

#include <iostream>
using namespace std;
const int M = 9901;
const int N = 7073;
typedef long long ll;
int p[908] = {2}, l = 1, fac[35][2], top, ans;
bool prime[N+1] = {1, 1};
void init() {
	int i, j;
	for(i = 3; i <= N; i += 2) {
		if(!prime[i]) p[l++] = i;
		for(j = 1; j <= l && i * p[j] <= N; j++) {
			prime[i*p[j]] = 1 ;
			if(!(i%p[j])) break;
		}
	}
}
void split(int n) {
	int i;
	top = 0;
	for(i = 0; i < l; i++)
		if(!(n%p[i])) {
			fac[top][0] = 0, fac[top][1] = p[i];
			while(!(n%p[i])) fac[top][0]++, n /= p[i];
			top++;
			if(n == 1 || n < N && !prime[n]) break;
		}
	if(n != 1) fac[top][0] = 1, fac[top++][1] = n;
}
int Pow(int a, ll b) {
	int t = 1;
	while(b) {
		if(b & 1) t = t * a % M;
		a = a * a % M;
		b >>= 1;
	}
	return t;
}
int ex_gcd(int a, int b, int &x, int &y) {
	if(!b) {x = 1; y = 0; return a;}
	int ans = ex_gcd(b, a%b, x, y), t = x;
	x = y;
	y = t - (a / b) * y;
	return ans;
}
int main() {
	int a, b, res, i, res1, x, y, tmp;
	init();
	while(~scanf("%d%d", &a, &b)) {
		split(a);
		res = res1 = 1;
		for(i = 0; i < top; i++) {
			tmp = Pow(fac[i][1] % M, (ll)fac[i][0] * b + 1);
			if(tmp == 1) res = (res * ((ll)fac[i][0] * b + 1)) % M;
			else {
				res *= (tmp - 1 + M) % M;
				if(res >= M) res %= M;
				res1 = res1 * (fac[i][1] - 1);
				if(res1 >= M) res1 %= M;
			}
		}
		ex_gcd(res1, M, x, y);
		printf("%d\n", (res * ((x + M) % M)) % M);
	}
	return 0;
}

题目地址
for (variable = A; variable != B; variable += C)
statement;
题目给定A,B,C,问这个循环执行多少次会停止或者永远不停止.题目还给定一个k,代表当数值达到2^k时,会自动重新从0开始.
很明显,就是要我们求(A + C * x) % 2^k = B中,x的值即C*x % 2^k = B – A,即一个赤裸裸的扩展欧几里德
Memory: 132K
Time: 0MS

#include <iostream>
using namespace std;
typedef long long ll;
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
	if(!b) {x = 1; y = 0; return a;}
	ll ans = ex_gcd(b, a%b, x, y), t = x;
	x = y;
	y = t - (a / b) * y;
	return ans;
}
int main() {
	ll a, b, c, x, y, t, s;
	int k, i;
	while(scanf("%lld%lld%lld%d", &a, &b, &c, &k), a || b || c || k) {
		s = (ll)1 << k;
		t = ex_gcd(c, s, x, y);
		b -= a;
		if(b % t) {
			puts("FOREVER");
			continue;
		}
		printf("%lld\n", (x * b / t % (s/t) + (s / t)) % (s / t));
	}
	return 0;
}

题目地址
题目大意是，给定一个小于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表示抱歉，但是这也提醒我们，要注意到对各种边界数据的考虑，往往就是那么一组数据，就是成功与失败的差别。