SRM 470
DIV1 250pt
题意：有n个房间排成一排，相邻两个房间之间有一扇关闭着的门(共n-1扇)，每个门上都标有‘A’-‘P’的大写字母。给定一个数n，表示第n个房间。有两个人John和Gogo，两人轮流按下面的规则选择一个大写字母(‘A’-‘P’)，每选择一次字母，标有该字母的门就打开了。
某次选择之后：若所有门全部打开，则平手游戏结束，输出0；n房间之前的门全部打开，则John胜游戏结束，输出两人总共选择了的颜色的数量；n房间后的门全部打开，则Gogo胜游戏结束，输出-1 × 两人总共选择了的颜色的数量。否则游戏继续。
选择颜色的规则：
1、若选择某个颜色后，无论对方如何选择，都可以使自己获得胜利，则选择该颜色。若有多个这种颜色，则选择可以使游戏结束时总共选择颜色数最少的那种颜色。
2、在1不成立的情况下，若选择某中颜色后，无论对方如何选择，都可以与对手打成平局，则选择该颜色。若有多个这种颜色，处理方法同上。
3、在1,2均不成立的情况下，选择能够使得游戏结束时选择颜色种数最多的颜色。
score: 0
解法：直接看代码把- -，感觉能看懂的，不复杂
tag: think
/*
* Author: plum rain
*/
#line 10 "DoorsGame.cpp"
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <vector> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl string a, b;
bool hav1[], hav2[]; int gao()
{
int an = SZ (a), bn = SZ (b);
CLR (hav1); CLR (hav2);
int num1 = , num2 = ;
for (int i = ; i < an; ++ i){
if (hav1[a[i]-'A']) continue;
hav1[a[i]-'A'] = ;
num1 ++;
}
for (int i = ; i < bn; ++ i){
if (hav2[b[i]-'A']) continue;
hav2[b[i]-'A'] = ;
num2 ++;
} int dif = ;
for (int i = ; i <= 'P'; ++ i)
if (hav1[i] && hav2[i])
++ dif; if (num1 == num2){
if (!dif) return *num1 - ;
return ;
}
if (num1 < num2){
if (dif <= num2 - num1) return *num1 - ;
return ;
}
if (num1 > num2){
if (dif < num1 - num2) return - * num2;
return ;
}
} class DoorsGame
{
public:
int determineOutcome(string tmp, int t){
a.clear(); b.clear();
int n = SZ (tmp);
for (int i = ; i < n; ++ i){
if (i < t) a.PB (tmp[i]);
else b.PB(tmp[i]);
}
return (gao());
}
};
DIV1 500pt
题意：给出一个矩形，在矩形上下两边分别标记出n个点，并且已经在上下两边所标记的点中连出若干条线段(每个点只能在一条线段上)。给定n和所连线段。每次随机在矩形上边和下边取一个没连线段的点(取到没点概率相同)，将它们相连，直到所有点都被连接。求最终所形成交点数的期望(多点共线算C(k, 2)个交点)。
解法：用l[n]表示线段，a[i]表示线段l[i]在矩形上边的端点，b[i]表示线段l[i]在矩形下边的端点。称题目中给出线段的端点为不可连接点，其余矩形边上的点为可连接点。用E(a[i], a[j])表示由a[i], a[j]分别与矩形下边的两点相连，形成交点的期望。题目中给出的线段的数量为size。
若a[i]，a[j]均为可连接点：该种情况下，(a[i], a[j])一共有(n-size) * (n-size-1) / 2对，每对产生交点的概率是0.5，所以这种情况期望之和为sum{E(a[i], a[j])} = (n-size) * (n-siez-1) / 4。
若a[i]，a[j]均为不可连接点：暴力算出交点个数即可，概率为1，所以该情况下交点期望之和即为交点数。
若a[i]，a[j]中一个为可连接点，另一个不可连接点：该种情况下，对每条题目给定边分别分析，期望之和即为该种情况的期望。对于某条题目给定边l[i]，在矩形上边在a[i]左侧有tl个可连接点，右侧有tr个可连接点，在矩形下边b[i]左侧有bl个可连接点，b[i]右侧有br个可连接点，则期望为Ei = tl*br/(tl+tr) + tr*bl/(tl+tr)。所以，该种情况的期望和为sum{Ei}。
三个部分相加，此题得解。
Ps：此题解法真的很巧秒。
tag:math, expectation, think, good
/*
* Author: plum rain
*/
#line 10 "DrawingLines.cpp"
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <vector> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size()) const int N = ; struct dot{
int first, second;
}; dot a[N+];
int top[N+], bot[N+]; bool cmp(dot a, dot b)
{
return a.first < b.first;
} double gao(int size, int n)
{
double ret = (n-size) * (n-size-1.0) / 4.0; for (int i = ; i < size; ++ i){
for (int j = i+; j < size; ++ j)
if (a[j].second < a[i].second) ret += 1.0; int tl = top[a[i].first], tr = n - size - tl;
int bl = bot[a[i].second], br = n - size - bl;
ret += tl*br*1.0 / (n-size-0.0) + tr*bl*1.0 / (n-size-0.0);
}
return ret;
} class DrawingLines
{
public:
double countLineCrossings(int n, vector <int> s, vector <int> e){
int size = SZ (s);
for (int i = ; i < size; ++ i){
a[i].first = s[i];
a[i].second = e[i];
}
sort (a, a+size, cmp); CLR (top); CLR (bot);
sort (s.begin(), s.end());
for (int i = ; i < size; ++ i)
top[s[i]] = s[i] - i - ;
sort (e.begin(), e.end());
for (int j = ; j < size; ++ j)
bot[e[j]] = e[j] - j - ; return (gao(size, n));
}
};
SRM 471
DIV1 250pt
题意：对于一个质数p，定义其“p的质数长度为d“ 等价于”集合{p / (2^i) | i = 0, 1, 2...d-1}中全部为质数“。给定数n和d，找到最大的数m使得m <= n且m的质数长度至少为d。
解法：水题。只需要一个素数表和一个二分查找，然后暴力就好了。
score: 128.03
tag:math
Ps：如果还用以前自己的素数打表模板而不是换成刘汝佳的，感觉就要超时了- -
/*
* Author: plum rain
* score : 128.03
*/
#line 10 "PrimeSequences.cpp"
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cmath>
#include <vector>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <stdexcept>
#include <functional>
#include <ctime> using namespace std; #define CLR(x) memset(x, 0, sizeof(x)) const int N = ;
bool vis[N+];
int prm[N+]; void sieve(int n)
{
int m = (int)sqrt(n+0.5);
CLR (vis);
for (int i = ; i <= m; ++ i) if (!vis[i])
for (int j = i*i; j <= n; j += i) vis[j] = ;
} int primes(int n)
{
sieve(n);
int ret = ;
for (int i = ; i <= n; ++ i)
if (!vis[i]) prm[ret++] = i;
return ret;
} int bin_search(int n, int all)
{
int l = , r = all-;
while (l <= r){
int mid = (l + r) >> ;
if (prm[mid] < n) l = mid + ;
else r = mid - ;
}
return l;
} bool gao(int n, int d)
{
if (vis[n]) return false;
int times = ;
while (times < d){
n >>= ;
if (vis[n] == || n == ) return false;
++ times;
}
return true;
} class PrimeSequences
{
public:
int getLargestGenerator(int n, int d){
int all = primes(N+);
int pos = bin_search(n, all);
while (prm[pos+] < n)
++ pos;
while (prm[pos] > n)
-- pos;
while (pos >= ){
if (gao(prm[pos], d)) return prm[pos];
-- pos;
}
return -;
}
};
DIV1 500pt
题意： 给定N个地点，标号0-(N-1)，N个地点之间有一些路，每条路都有长度。问从0号地点走到N-1号地点，最短且满足以下条件的路的长度：设路径为P[0], P[1], P[2]....P[k](其中P[0] = 0)，T[m]为从P[m]到P[m+1]的长度，则不存在0 <= i <= j < k，使得T[i] + T[i+1] +...T[j]为13的倍数。
解法：如果没有限制条件，就是一道很简单的最短路的题。而限制条件等价于不存在0 <= i <= j < k，使得T[-1]+T[0]+T[1]+T[2]+T[i-1]与T[0]+T[1]+T[2]+...T[j]同余(其中T[-1]视为0)。这样，12位的状态压缩就解决了问题。
Ps：好不容易想出了500pt，可是，由于我没学图论(- -)，这道题还是不能写- -。
tag: math, 最短路, 未做
SRM 472
DIV1 250pt
题意：A和B轮流做游戏。给定一个数m(1<= m <= 10^9)，每人每轮必须使m = m - 4^k(k是使得4^k <= m的任意非负整数)，使m = 0的人胜利。给定m，A先，都使用最优策略，问谁能获胜。
解法：手算模拟，找出规律为：令t = m % 5，当t为1, 3, 4的时候A胜，否则B胜。通过数学归纳法验证：
引理：if (k为偶数) (4^k) = 1(mod 5)，if (k为奇数) （4^k) = 4(mod 5)。(易证)
当m = 1, 2, 3, 4, 5时符合规律。
设当m <= 5*n时均符合规律，则当5*n < m < 5*(n+1)时：
当m = 5*n + 1，先手使m = m - 1，则m = 5*n，由归纳假设知m=5*n为先手必败，所以m = 5*n+1为先手必胜(即A胜)。
当m = 5*n + 2，先手m = m - 4，则m = 5*n - 2，由归纳假设知m = 5*n-2为先手必败，所以m = 5*n-2为先手必胜。
当m = 5*n + 3，引理知，对于任意k，均有(m - 4^k) = 2或4(mod 5)，由归纳假设知他们均为先手必胜，所以m = 5*n + 3先手必败。
当m = 5*n + 4，先手使m = m - 1则必胜。
当m = 5*n + 5，同5*n+3理，易证为必败。
DIV1 600pt
题意：给定数字1-n的两个排列(可能相同)，记为a[n]，b[n](0~n-1)。新构造一个数列k[n]使得k[i] = a[i]或则b[i]，则所有k[n]的不同排列有多少种。比如，a[] = {1,3,2}，b[] = {1,2,3}，则k[] = {1,2,2}或{1,2,3}或{1,3,2}或{1,3,3}，则所有k[n]的不同排列有：123,132,213,231,312,321,122,212,221,133,313,331，共12种。
解法：首先，将a[n]置换到b[n]记为置换A，将置换A有若干个循环，对每个循环单独分析，分析每个循环有多少种排列。对每个循环，设其长度为m，其中含有的每个数字都只可能出现0,1,2次，而且，注意到，每选择一个数出现两次，则注定同时会有一个数出现0次。所以枚举出现两次的数的个数为k时该循环能产生多少个排列，k = 0 -> (m/2)，则当k=0，排列个数为A[m][m]，否则为C[m][2*k] * 2 * A[m][m]/(2^k)。注意到，选择k个数出现0次和k个数出现2次只能用C[m][2*k]*2，这也是我没想到的点之一，不信可以试试别的方法。
求出每个循环的排列数以后，就只需要在长度为n的空序列上找位置就好了。
tag:math, counting, good
score: 0
/*
* Author: plum rain
* score : 0
*/
#line 11 "TwoSidedCards.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <map> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl typedef long long int64; const int mod = ; map<int, int> mp;
int64 A[][];
int64 C[][]; int pow_mod(int64 p, int64 n)
{
int64 ret = ;
while (n > ){
if (n & ) ret = (ret * p) % mod;
n >>= ;
p = (p * p) % mod;
}
return (int)ret;
} void C_init()
{
C[][] = ;
for (int i = ; i <= ; ++ i){
C[i][] = C[i][i] = ;
for (int j = ; j < i; ++ j)
C[i][j] = (C[i-][j] + C[i-][j-]) % mod;
}
} void A_init()
{
A[][] = ;
A[][] = ; A[][] = ;
for (int i = ; i <= ; ++ i){
A[i][] = ;
for (int j = ; j <= i; ++ j)
A[i][j] = (A[i][j-] * (i-j+)) % mod;
}
} int64 gao2(int n)
{
if (n == ) return ; int64 ret = ;
for (int i = ; *i <= n; ++ i){
int64 tmp;
if (!i) tmp = ;
else tmp = C[n][*i] * ;
tmp = (tmp * A[n][n]) % mod;
tmp = (tmp * pow_mod(pow_mod(, i), mod-)) % mod;
ret = (tmp + ret) % mod;
}
return ret;
} int gao(int n)
{
int64 ret = ;
int tot = n;
for (int i = ; i <= n; ++ i){
int tmp = , pos = i; while (mp[pos] != -){
++ tmp;
int x = pos;
pos = mp[pos];
mp[x] = -;
}
if (tmp){
int64 xxx = gao2(tmp);
ret = (((C[tot][tmp] * xxx) % mod) * ret) % mod;
}
tot -= tmp;
}
return ret;
} class TwoSidedCards
{
public:
int theCount(vector <int> t, vector <int> h){
C_init();
A_init(); mp.clear();
int n = SZ (t);
for (int i = ; i < n; ++ i)
mp[t[i]] = h[i]; return gao(n);
}
};
SRM 473
DIV1 250pt
题意：给定一个字符串作为机器人的行走指令。字符串(最多50个字母)含三种字母——S向前走一步，L向左转，R向右转。问一直重复，无限次地进行这个字符串指令，问是否存在数R使得以初始点为圆心，以R为半径的圆能够包含所有机器人走过的地方。
解法：我的解法是，暴力让机器人走10000次，判断点的位置到初始点的距离。题解的方法很好懂很好做的，水题我就不多写了...
score: 0
/*
* Author: plum rain
* score : 0
* for better method: http://apps.topcoder.com/wiki/display/tc/SRM+473
*/
#line 11 "SequenceOfCommands.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath> using namespace std; #define SZ(v) ((int)(v).size()) typedef vector<string> VS;
typedef long long int64; VS c;
// 0
//1 3
// void move (int& x, int& y, int& d)
{
int size = SZ (c);
for (int i = ; i < size; ++ i){
int n = SZ (c[i]);
for (int j = ; j < n; ++ j){
if (c[i][j] == 'L') d = (d-+) % ;
if (c[i][j] == 'R') d = (d+) % ; if (c[i][j] == 'S'){
if (d == ) ++ y;
if (d == ) -- x;
if (d == ) -- y;
if (d == ) ++ x;
}
}
}
} class SequenceOfCommands
{
public:
string whatHappens(vector <string> com){
c.clear(); c = com;
int x = , y = , d = ;
for (int i = ; i < ; i ++)
move (x, y, d);
double dis = (int)sqrt((int64)x*x + (int64)y*y + 0.0);
if (dis < 1000.0) return "bounded";
return "unbounded";
}
};
div1 500pt
题意：在圆上有n个点按顺时针方向标记为0, 1, 2....(n-1)，将其中的rnum个涂红。给定a，b，c，for i = 0 to (rnum-1)，将(a*i^2 + b*i + c) mod n之后的第一个没涂红的点涂红。最终，求完全由红点组成的直角三角形的数量。如n = 4, rnum = 3, a = 4, b = 4, c = 2，则依次涂红点2, 3, 0。
a, b, c, n <= 10^6, rnum <= 10^5, 且rnum <= n。
解法：其实，这道看上去的做法很简单，只需要按题意求出哪些点为红点，然后只需要用到圆直径所有对的角为直角这一性质就能轻松解决。但是，注意到这几个字“之后的第一个没涂红的点涂红”，导致暴力的时间复杂度为O(n^2)，所以要用比较机智的hash来解决问题。hash方法见代码，很好懂。
tag:hash
score: 0
Ps:这实在是这几场里最水的500了，我虽然提交了多次(循环变量i爆int和TLE的问题)，但最终也能在没看题解的情况下解出这道题(^_^)。
/*
* Author: plum rain
* score : 0
*/
#line 11 "RightTriangle.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
//#include <string> using namespace std; #define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl typedef vector<int> VI;
typedef long long int64; int cnt[];
bool has[]; class RightTriangle
{
public:
long long triangleCount(int n, int rnum, int aa, int bb, int cc){
if (n & || rnum <= ) return ;
int dif = n / ; int64 a = (int64)aa, b = (int64)bb, c = (int64)cc;
a %= n; b %= n; c %= n;
memset(has, , sizeof (has));
memset(cnt, , sizeof (cnt));
for (int64 i = ; i < rnum; ++ i){
int64 tmp = (i*i) % n;
tmp = (tmp * a) % n;
tmp = (tmp + (b * i) % n) % n;
tmp = (tmp + c) % n;
++ cnt[tmp];
} int num = , i = ;
while (num < rnum){
if (i == ) cnt[i] += cnt[n-];
else cnt[i] += cnt[i-]; if (cnt[i] && !has[i]){
++ num;
has[i] = ;
-- cnt[i];
}
++ i;
if (i == n) i = ;
} int64 ret = ;
for (int i = ; i < dif; ++ i){
if (has[i] && has[i+dif])
ret ++;
}
return ret * (int64)(rnum - );
}
};
SRM 474
DIV1 250pt
题意：在N维空间(x1, x2,...., xn)中移动某个点，每次移动可以使某一维的坐标加1或者减1，一共移动m次。(1<= N <= 10^9，1 <= m <= 50)
解法：N这么大完全是吓人的，因为最多50次操作，每次操作最多在某一维中进行，所以直接暴力记录50维即可。
tag:water
score: 155.33
/*
* Author: plum rain
* score : 155.33
*/
#line 11 "RouteIntersection.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl struct pos{
int a[];
void clr(){
CLR (a);
}
bool operator == (pos b){
for (int i = ; i < ; ++ i)
if (a[i] != b.a[i]) return false;
return true;
}
};
pos p[];
int cnt[]; class RouteIntersection
{
public:
string isValid(int N, vector <int> c, string m){
for (int i = ; i < ; ++ i)
p[i].clr();
CLR (cnt);
int num = ; int n = SZ (c);
for (int i = ; i < n; ++ i){
int flag = -;
for (int j = ; j < num; ++ j)
if (c[i] == cnt[j]) flag = j;
if (flag == -)
cnt[num] = c[i], flag = num ++; if (i) p[i] = p[i-];
if (m[i] == '+') ++ p[i].a[flag];
if (m[i] == '-') -- p[i].a[flag];
} ++ n;
for (int i = ; i < n; ++ i)
for (int j = i+; j < n; ++ j)
if (p[i] == p[j]) return "NOT VALID";
return "VALID";
}
};
DIV1 500pt
这场SRM带“member”,所以没有题解。不会。