SRM 520

250:傻叉题,枚举即可

500:对每个人算出他是多少分的方法数,然后做一次简单的dp即可

Code:

#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>#define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)using namespace std;class SRMIntermissionPhase { public: int countWays(vector<int>, vector<string>);};const int MOD = int(1e9) + 7;inline int add(int a, int b) { int c = a + b; if (c >= MOD) c -= MOD; return c;}int SRMIntermissionPhase::countWays(vector<int> points, vector<string> description) { const int MAX_VALUE = 200000 + 10; vector<int> am(MAX_VALUE, 0); am[MAX_VALUE – 1] = 1; for (int i = 0; i < description.size(); ++i) { vector<int> cur(MAX_VALUE, 0); cur[0] = 1; for (int j = 0; j < 3; ++j) { if (description[i][j] == ‘Y’) { int v = points[j]; vector<int> ncur(MAX_VALUE, 0); partial_sum(cur.begin(), cur.end(), cur.begin(), add); for (int i = 1; i < ncur.size(); ++i) { ncur[i] = cur[i – 1] – (i >= v + 1 ? cur[i – v – 1] : 0); if (ncur[i] < 0) ncur[i] += MOD; } cur = ncur; } } vector<int> nam(MAX_VALUE, 0); partial_sum(am.rbegin(), am.rend(), am.rbegin(), add); for (int i = 0; i + 1 < am.size(); ++i) { nam[i] = 1LL * am[i + 1] * cur[i] % MOD; } am = nam; } return accumulate(am.begin(), am.end(), 0LL) % MOD;}//Powered by [KawigiEdit] 2.0!

1000:

我们令一个人如果只能Cha别人,就叫他攻G,如果只能被Cha就叫受S,如果能自攻自受就叫他B,

那么一个人在被爆了之后不能爆别人(大雾)

稍作分析可以发现不成功的Cha,Cha谁都可以,所以只考虑成功的Cha

G和S都很好分析,关键是B,可以假设

g->b1->b2->b3->b4,

可以发现在这个攻受链中,Cha的顺序必须是b4倒过来到g,那么这个顺序就给定了

也就是说这么一个链条等价于一个G

进一步的分析可以发现不同的链条方案数就是斯特林第二数列。。。

那么把这个乘上去就只需要考虑G和S了。。就傻叉了。。

 

P.S.语法高亮是用vim做的。。。