我果然是题短了就能做得好- -。Div 2的三道题都短，于是迅速的过掉了250和500，rating涨了150^ ^。
Div 2 250pt
题意：给一个vector<int> A，对其中任意的数x，可以将其变为2^t * x(t为正整数)，判断能不能将A变为所有数全部一样。
解法：我的方法是，将A排序，对第i个，while(A[i] < A[i+1]) A[i] *= 2，如果最终A[i] != A[i+1]，则答案为不能。若对所有的i都可以，则答案为能。
水题就不贴代码了。
Div 2 500pt/ Div 1 250pt
题意：给两个等长的字符串s1和s2，对s1进行操作，每次操作能将s1中某个字符提前到s1中的第一个。问最少进行多少次操作，能将s1变成s2。若不能返回-1。
解法：首先，对s1和s2所含字符的数量进行统计，判断能不能将s1变为s2。
然后，改变后的s1有两种字符，被操作过的字符全部在s1的前部分，没被操作过的字符全部在s1的后部分，而且，对于后部分的字符，相对顺序在s1改变前后并没有改变。
所以，从后往前用i枚举s1的所有字符，同时置一个idx对s2从后往前移动。if (s1[i] == s2[idx]) {-- i; -- idx} else -- i;
这样，idx+1即为答案。
tag:greedy
1 // BEGIN CUT HERE 2 /* 3 * Author: plum rain 4 * score : 5 */ 6 /* 7 8 */ 9 // END CUT HERE 10 #line 11 "LittleElephantAndString.cpp" 11 #include <sstream> 12 #include <stdexcept> 13 #include <functional> 14 #include <iomanip> 15 #include <numeric> 16 #include <fstream> 17 #include <cctype> 18 #include <iostream> 19 #include <cstdio> 20 #include <vector> 21 #include <cstring> 22 23 using namespace std; 24 25 #define CLR(x) memset(x, 0, sizeof(x)) 26 #define PB push_back 27 28 char a[1000], b[1000]; 29 int num[50][2]; 30 31 32 class LittleElephantAndString 33 { 34 public: 35 int getNumber(string A, string B){ 36 char x = 'A'; 37 38 int n = A.size(); 39 for (int i = 1, j = n-1; j >= 0; ++ i, -- j){ 40 a[i] = A[j]; 41 b[i] = B[j]; 42 } 43 44 CLR (num); 45 for (int i = 1; i <= n; ++ i){ 46 num[a[i]-x][0] ++; 47 num[b[i]-x][1] ++; 48 } 49 50 for (int i = 0; i < 30; ++ i) 51 if (num[i][0] != num[i][1]) return -1; 52 53 int cnt = n - 1; 54 for (int i = n-1; i >= 0; -- i){ 55 if (A[i] == B[cnt]) 56 -- cnt; 57 } 58 if (cnt == n-1) return -1; 59 return cnt+1; 60 } 61 };
Div2 1000pt
题意：给定一个数n，称这样的集合为关于n的好集合：所有元素的值均在n以内，且将所有元素写在黑板上，所需要写的0, 1, 2..9的次数均不超过1次。给定n求好数组的数量。(n <= 10^9)，答案关于1000000007取模。
解法：对于任意给定的数n，首先用dfs求出所有能被放在关于n的好集合中的数，并将他们分好类。分类的方法为，对于数k，将它写在黑板上需要写的数字有a0, a1, a2..at，则它属于类((0 | 1<<a0) | (1<<a1) | ... | (1<<at))。比如1属于类2，10属于类3，123属于类14。
分好类之后，就发现，同一个集合之中，最多一个能出现在关于n的好集合中，且不同集合的数也不一定能同时出现在关于n的好集合中，比如类2和类3(因为都含有1)。
这样的话，就变成了一个01背包问题。设d[i][j]表示前i类中去数，状态为j的情况下能有多少好集合。
注意到，此处第i类所代表的状态也为i，所以状态转移方程为d[i][i|j] += d[i-1][j] * num(类i)。num(类i)表示类i中含有元素的个数。
tag：dp, 背包, good
1 // BEGIN CUT HERE 2 /* 3 * Author: plum rain 4 * score : 5 */ 6 /* 7 8 */ 9 // END CUT HERE 10 #line 11 "LittleElephantAndSubset.cpp" 11 #include <sstream> 12 #include <stdexcept> 13 #include <functional> 14 #include <iomanip> 15 #include <numeric> 16 #include <fstream> 17 #include <cctype> 18 #include <iostream> 19 #include <cstdio> 20 #include <vector> 21 #include <cstring> 22 //#include <cmath> 23 //#include <algorithm> 24 //#include <cstdlib> 25 //#include <set> 26 //#include <queue> 27 //#include <bitset> 28 //#include <list> 29 //#include <string> 30 //#include <utility> 31 //#include <map> 32 //#include <ctime> 33 //#include <stack> 34 35 using namespace std; 36 37 #define CLR(x) memset(x, 0, sizeof(x)) 38 #define PB push_back 39 //#define SZ(v) ((int)(v).size()) 40 //#define zero(x) (((x)>0?(x):-(x))<eps) 41 //#define out(x) cout<<#x<<":"<<(x)<<endl 42 //#define tst(a) cout<<#a<<endl 43 //#define CINBEQUICKER std::ios::sync_with_stdio(false) 44 45 //typedef vector<int> VI; 46 //typedef vector<string> VS; 47 //typedef vector<double> VD; 48 typedef long long int64; 49 // 50 //const double eps = 1e-8; 51 //const double PI = atan(1.0)*4; 52 //const int maxint = 2139062143; 53 const int64 mod = 1000000007; 54 // 55 56 int n, num; 57 bool vis[20], opt[2500]; 58 int64 d[1<<10]; 59 vector<int> a[2500]; 60 61 int64 max64(int64 a, int64 b) 62 { 63 return a > b ? a : b; 64 } 65 66 void dfs(int x, int p) 67 { 68 int64 y = (int64)x * 10 + p; 69 if (y > n) return; 70 71 int sta = 0; 72 for (int i = 0; i <= 9; ++ i) 73 if (vis[i]) sta |= (1 << i); 74 a[sta].PB((int)y); 75 76 for (int i = 0; i <= 9; ++ i) if(!vis[i]){ 77 vis[i] = 1; 78 dfs((int)y, i); 79 vis[i] = 0; 80 } 81 } 82 83 bool ok(int a, int b) 84 { 85 for (int i = 0; i < 10; ++ i){ 86 int t1 = a & (1 << i), t2 = b & (1 << i); 87 if (t1 && t2) return 0; 88 } 89 return 1; 90 } 91 92 class LittleElephantAndSubset 93 { 94 public: 95 int getNumber(int N){ 96 n = N; num = 1 << 10; 97 for (int i = 0; i < num; ++ i) 98 a[i].clear(); 99 CLR (vis); 100 101 for (int i = 1; i <= 9; ++ i){ 102 vis[i] = 1; 103 dfs(0, i); 104 vis[i] = 0; 105 } 106 107 CLR (d); 108 for (int i = 0; i < num; ++ i){ 109 if (a[i].size()) d[i] = (a[i].size() + d[i]) % mod; 110 for (int j = num-1; j >= 0; -- j) if (ok(i, j)) 111 d[i|j] = ((d[j]%mod) * ((int64)a[i].size()%mod) + d[i|j]) % mod; 112 } 113 114 int ret = 0; 115 for (int i = 0; i < num; ++ i) 116 ret = (d[i] + ret) % mod; 117 return ret; 118 } 119 120 // BEGIN CUT HERE 121 public: 122 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); } 123 private: 124 template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '"' << *iter << "","; os << " }"; return os.str(); } 125 void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << " Expected: "" << Expected << '"' << endl; cerr << " Received: "" << Received << '"' << endl; } } 126 void test_case_0() { int Arg0 = 3; int Arg1 = 7; verify_case(0, Arg1, getNumber(Arg0)); } 127 void test_case_1() { int Arg0 = 10; int Arg1 = 767; verify_case(1, Arg1, getNumber(Arg0)); } 128 void test_case_2() { int Arg0 = 47; int Arg1 = 25775; verify_case(2, Arg1, getNumber(Arg0)); } 129 void test_case_3() { int Arg0 = 4777447; int Arg1 = 66437071; verify_case(3, Arg1, getNumber(Arg0)); } 130 131 // END CUT HERE 132 133 }; 134 135 // BEGIN CUT HERE 136 int main() 137 { 138 freopen( "a.out" , "w" , stdout ); 139 LittleElephantAndSubset ___test; 140 ___test.run_test(-1); 141 return 0; 142 } 143 // END CUT HERE