1、水题,简单的画图,略过。
2、用到了贪心算法,需要把当前n个金币可以买到的最强能力保存下来,然后在可以达到终点的路径中取最小的即可。
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <cstdlib>
5 #include <cmath>
6 #include <map>
7 #include <stack>
8 #include <algorithm>
9 #include <list>
10 #include <ctime>
11 #include <set>
12 #include <queue>
13 using namespace std;
14
15 typedef long long ll;
16 ll pricepower[30][50];
17 class MonstersValley2 {
18 public:
19 int minimumPrice(vector<int> dread, vector<int> price) {
20 int dsz = dread.size();
21 pricepower[0][price[0]] = dread[0];
22 for (int i = 1; i < dsz; i++) {
23 for (int j = 45; j >= -1; j--) {
24 if (pricepower[i - 1][j] >= dread[i]) {
25 pricepower[i][j] = pricepower[i - 1][j];
26 }
27 }
28
29 for (int j = 45; j >= -1; j--) {
30 if (pricepower[i-1][j]!=0) {
31 pricepower[i][j+price[i]] = max(pricepower[i][j+price[i]],pricepower[i - 1][j]+dread[i]);
32 }
33 }
34 }
35 int res=0;
36 for (int i = 0; i < 45; i++) {
37 if(pricepower[dsz-1][i]!=0){
38 res=i;
39 break;
40 }
41 }
42 return res;
43 }
44
45 };
3、刚开始想到的办法是因子a到N的路径,时间复杂度太高了,N的因子个数是n,时间复杂度是O(Hn^2),后来发现矩阵相乘的时候可以优化,但是n的复杂度又上去了,达到O(log(H)n^3)(下边),超过了两秒,还是不行。
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <cstdlib>
5 #include <map>
6 #include <algorithm>
7 #include <stack>
8 #include <queue>
9 #include <cmath>
10 using namespace std;
11 const int mool = 1000000009;
12 typedef long long ll;
13 typedef vector<vector<int> > vvint;
14 typedef map<int, int>::iterator it_int_int;
15 typedef map<int, int> mii;
16 map<int, int> allmap;
17 class DivisibleSequence {
18 public:
19 int count(int N, int H) {
20 if (H == 1)
21 return 1;
22 int half = sqrt(N) + 10;
23 cout << half << endl;
24 int cur = N;
25 vector<int> div;
26 div.push_back(1);
27 div.push_back(N);
28 for (int i = 2; i < half; i++) {
29 if ((cur % i) == 0) {
30 while (1) {
31 div.push_back(i);
32 cur = cur / i;
33 if ((cur % i) != 0)
34 break;
35 }
36 }
37 }
38 if (cur != 1 && cur != N)
39 div.push_back(cur);
40 map<int, int> num_c;
41 for (int i = 0; i < div.size(); i++)
42 num_c[div[i]]++;
43 map<int, int> num_next;
44 num_next = num_c;
45 for (it_int_int j = num_next.begin(); num_next.end() != j; j++) {
46 j->second = 1;
47 }
48 while (1) {
49 bool judge = true;
50 for (it_int_int i = num_c.begin(); num_c.end() != i; i++) {
51 for (it_int_int j = num_next.begin(); num_next.end() != j;
52 j++) {
53 ll cnum = j->first;
54 ll mul = (i->first) * cnum;
55 if ((N % mul) == 0) {
56 it_int_int ittmp = num_next.find(mul);
57 if (num_next.end() == ittmp) {
58 judge = false;
59 num_next[mul] = 1;
60 }
61 }
62 }
63 }
64 if (judge)
65 break;
66 }
67
68 int tmpkaka = 0;
69 for (it_int_int j = num_next.begin(); num_next.end() != j; j++) {
70 allmap[tmpkaka] = j->first;
71 cout << allmap[tmpkaka] << endl;
72 tmpkaka++;
73 }
74 int nsz = num_next.size();
75 cout << nsz << endl;
76 vector<vector<int> > allzero(nsz, vector<int>(nsz, 0));
77
78 vvint pow = allzero;
79 int i1 = 0;
80 for (it_int_int i = num_next.begin(); num_next.end() != i; i++) {
81 int cur_nm1 = i->first;
82 int j1 = 0;
83 for (it_int_int j = num_next.begin(); num_next.end() != j; j++) {
84 int cur_nm = j->first;
85 if ((cur_nm % cur_nm1) == 0) {
86 ll tmp = (pow[i1][j1] + i->second) % mool;
87 pow[i1][j1] = tmp;
88 }
89 j1++;
90 }
91 i1++;
92 }
93
94 vvint a, c, res;
95 a = pow;
96 res = allzero;
97 for (int i = 0; i < nsz; i++) {
98 res[i][i] = 1;
99 }
100 int counter = H - 1;
101 int kaka = 0;
102 while (counter) {
103 cout << kaka << endl;
104 int remain = counter % 2;
105 cout << "here2\n";
106 if (remain == 1) {
107 multi(pow, res, res);
108 }
109 cout << "here\n";
110 counter /= 2;
111 multi(a, a, pow);
112
113 cout << "here1\n";
114 a = pow;
115 kaka++;
116 }
117 int finalres = 0;
118 for (int i = 0; i < nsz; i++) {
119 finalres = (finalres + res[i][nsz - 1]) % mool;
120 }
121 return finalres;
122 }
123 void multi(vvint& a, vvint b, vvint &c) {
124 int asz = a.size();
125 for (int i = 0; i < asz; i++) {
126 for (int j = i; j < asz; j++) {
127 if ((allmap[j] % allmap[i]) == 0) {
128 c[i][j] = 0;
129 for (int k = i; k < j + 1; k++) {
130 if (a[i][k] != 0 && b[k][j] != 0) {
131 ll tmp1 = a[i][k];
132 ll tmp2 = b[k][j];
133 ll tmp3 = c[i][j];
134 ll curval = (tmp3 + tmp1 * tmp2) % mool;
135 c[i][j] = curval;
136 }
137 }
138 }
139 }
140 }
141 }
142 };
今天看了看wiki,终于知道怎么办了,还是数学功底要深厚啊,费马小定理啊~~~泪奔,实在想不到
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <cstdlib>
5 #include <map>
6 #include <algorithm>
7 #include <stack>
8 #include <queue>
9 #include <cmath>
10 using namespace std;
11
12 typedef long long ll;
13 const ll mod = 1000000009;
14
15 class DivisibleSequence {
16 public:
17 ll modPow(ll x, ll y) { //计算x的y次方
18 ll r = 1, a = x;
19 while (y > 0) {
20 if ((y & 1) == 1) {
21 r = (r * a) % mod;
22 }
23 a = (a * a) % mod;
24 y /= 2;
25 }
26 return r;
27 }
28 ll modInverse(ll x) {
29 //计算x',使得 x * x' =1 (模 mod),mod是质数,可知 x * (x^(mod-2)) =1 (模 mod)
30 //可得x'=(x^(mod-2)) (模 mod)
31 return modPow(x, mod - 2);
32 }
33
34 ll modDivision(ll p, ll q) {
35 //若想计算 x/y (模mod),等价于计算 x*y' (模mod)
36 return (p * modInverse(q)) % mod;
37 }
38
39 ll C(ll n, int k) { //计算C(n,k)
40 if (k > n) {
41 return 0;
42 }
43 ll p = 1, q = 1;
44 for (int i = 1; i <= k; i++) {
45 q = (q * i) % mod;
46 p = (p * (n - i + 1)) % mod;
47 }
48 return modDivision(p, q);
49 }
50 int count(int N, int H) {
51 ll res = 1;
52 //获取质因子p以及它的幂c
53 for (int p = 2; p <= N / p; p++) {
54 int c = 0;
55 while (N % p == 0) {
56 N /= p;
57 c++;
58 }
59 res = (res * C(H - 1 + c, c)) % mod;
60 }
61
62 if (N > 1) {//如果还剩下一个质数因子
63 res = (res * C(H, 1)) % mod;
64 }
65 return (int) res;
66 }
67 };
div1-2
nim游戏的变种,同构映射加速部分蛮有意思。
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <cstdlib>
5 #include <map>
6 #include <algorithm>
7 #include <stack>
8 #include <queue>
9 #include <cmath>
10 using namespace std;
11
12 typedef long long ll;
13 typedef vector<int> vi;
14 typedef vector<long long> vll;
15 const ll mod = 1000000009;
16 class TheDivisionGame {
17 public:
18 ll countWinningIntervals(int L, int R) {
19 int n = R - L + 1;
20 // Find the list of n counts of prime factors:
21 vi nimber(n);
22 vi current(n);
23 for (int i = L; i <= R; i++) {
24 current[i - L] = i;
25 }
26 // A modified Sieve of Erathostenes:
27 for (int p = 2; p <= R / p; p++) {
28 int s = L;
29 if (L % p != 0) {
30 s += p - (L % p);
31 }
32 while (s <= R) {
33 while (current[s - L] % p == 0) {
34 current[s - L] /= p;
35 nimber[s - L]++;
36 }
37 s += p;
38 }
39 }
40 for (int i = L; i <= R; i++) {
41 if (current[i - L] != 1) {
42 nimber[i - L]++;
43 }
44 }
45 for (int i = L; i <= R; i++) {
46 cout << nimber[i - L] << " ";
47 }
48 cout << endl;
49
50 // Counting the number of consecutive subsequences with a xor different
51 // to 0.
52 ll s = 0; //We will first count the ones with a xor equal to 0:
53
54 // The following two codes are equivalent. Can you tell why?
55 // #1:
56 vll next(32);
57 for (int i = n - 1; i >= 0; i--) {
58 vll curr(32);
59 for (int x = 0; x < 32; x++) {
60 curr[nimber[i] ^ x] = next[x]; //等价于curr[x] = next[nimber[i] ^x];
61 } //1
62 curr[nimber[i]]++; //2
63 s += curr[0];
64 next = curr;
65 }
66
67 //方法1.5
68 // vll origin(32);
69 // ll fmap = nimber[n - 1];
70 // for (int i = n - 1; i >= 0; i--) {
71 // origin[0 ^ fmap]++;
72 // fmap ^= nimber[i];
73 // s += origin[fmap];
74 // }
75
76 //方法2
77 /* ll dp(32, 0);
78 int x = 0;
79 for (int i = n - 1; i >= 0; i--) {
80 dp[x]++;
81 x ^= nimber[i];
82 s += dp[x];
83 }*/
84
85 return (n + 1) * (ll) n / 2 - s;
86 }
87 };
原文链接: https://www.cnblogs.com/kakamilan/archive/2012/12/28/2827343.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/73926
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!