250pt:
题意：定义一种函数f(x),表示ｘ不断/2直到出现非素数的操作次数。现在给定N，D。求X<= N, 并且f(x) >= D的最大的数
思路：直接先弄一个1000w以内的质数表，然后直接dp。由于题目给定内存才64M。。所以没法开1000w的int数组
所以dp时我直接对每个素数做。dp[i]表示以第i个质数结尾的f值。。
code：
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> using namespace std; #define PB push_back #define MP make_pair #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI; typedef vector<string> VS; typedef vector<double> VD; typedef long long LL; typedef pair<int,int> PII; bool vis[10000010]; vector<int> P; int dp[1000000]; class PrimeSequences { public: void getPrime(int n){ P.clear(); for (int i = 2; i <= n; ++i){ if (vis[i]) continue; P.push_back(i); for (int j = i * 2; j <= n; j += i) vis[j] = true; } } int getLargestGenerator(int N, int D) { getPrime(N); int n = P.size(); int p, x; int ans = 0; for (int i = 0; i < n; ++i){ x = (P[i] >> 1); p = lower_bound(P.begin(), P.end(), x) - P.begin(); if (x == P[p]) dp[i] = dp[p] + 1; else dp[i] = 1; ans = max(dp[i], ans); } if (ans < D) return -1; for (int i = n-1; i >= 0; --i) if (dp[i] >= D) return P[i]; return -1; } };
500pt：
题意：题目给了最多n(n <= 25)个点的有向图，编号0~n-1, 现在求一条0号点到n-1点的最短路，并且该最短路上任意两点距离不为13倍数。
思路：很明显的动态规划。
后面改成3维dp[i][j][k]，表示到达点i，从起点到点i所有路径%13的集合为j，并且此时最短路%13为k时的最短路。
那么转移就很明显了。。
不过此题很容易想入非非了，刚开始就是用2维写错了。少枚举了第三维。直接用最短路%13作为第三维。。
这样的结果就可能导致当前最优而后面不一定最优。。
code：
1 #line 7 "ThirteenHard.cpp" 2 #include <cstdlib> 3 #include <cctype> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <vector> 9 #include <string> 10 #include <iostream> 11 #include <sstream> 12 #include <map> 13 #include <set> 14 #include <queue> 15 #include <stack> 16 #include <fstream> 17 #include <numeric> 18 #include <iomanip> 19 #include <bitset> 20 #include <list> 21 #include <stdexcept> 22 #include <functional> 23 #include <utility> 24 #include <ctime> 25 using namespace std; 26 27 #define PB push_back 28 #define MP make_pair 29 #define Inf 0xfffffff 30 #define REP(i,n) for(i=0;i<(n);++i) 31 #define FOR(i,l,h) for(i=(l);i<=(h);++i) 32 #define FORD(i,h,l) for(i=(h);i>=(l);--i) 33 #define two(i) (1 << i) 34 typedef vector<int> VI; 35 typedef vector<string> VS; 36 typedef vector<double> VD; 37 typedef long long LL; 38 typedef pair<int,int> PII; 39 struct oo{ 40 int x, y, z; 41 oo(){} 42 oo(int _x, int _y, int _z):x(_x), y(_y), z(_z){} 43 }; 44 int dp[26][1 << 14][15]; 45 bool vis[26][1 << 14][15]; 46 class ThirteenHard 47 { 48 public: 49 int g[30][30], n; 50 int calcTime(vector <string> s) 51 { 52 n = s.size(); 53 for (int i = 0; i < n; ++i) 54 for (int j = 0; j < n; ++j){ 55 if (s[i][j] == '#') g[i][j] = Inf; 56 if (s[i][j] >= 'A' && s[i][j] <= 'Z') g[i][j] = s[i][j] - 'A' + 1; 57 if (s[i][j] >= 'a' && s[i][j] <= 'z') g[i][j] = s[i][j] - 'a' + 27; 58 } 59 memset(dp, -1, sizeof(dp)); 60 memset(vis, 0, sizeof(vis)); 61 dp[0][1][0] = 0; 62 queue<oo> q; 63 q.push(oo(0,1,0)); 64 int x, y, z; 65 vis[0][1][0] = true; 66 oo cur; 67 while (!q.empty()){ 68 cur = q.front(); 69 for (int i = 0; i < n; ++i) if (g[cur.x][i] < Inf){ 70 z = (cur.z + g[cur.x][i]) % 13; 71 if (two(z) & cur.y) continue; 72 y = (cur.y | two(z)); 73 x = i; 74 if (dp[x][y][z] == -1 || dp[x][y][z] > dp[cur.x][cur.y][cur.z] + g[cur.x][x]){ 75 dp[x][y][z] = dp[cur.x][cur.y][cur.z] + g[cur.x][x]; 76 if (!vis[x][y][x]){ 77 vis[x][y][z] = true; 78 q.push(oo(x, y, z)); 79 } 80 } 81 } 82 q.pop(); 83 vis[cur.x][cur.y][cur.z] = false; 84 } 85 int ans = -1; 86 for (int i = 0; i < two(13); ++i) 87 for (int j = 0; j < 13; ++j) 88 if (dp[n-1][i][j] > -1) 89 if (ans == -1 || dp[n-1][i][j] < ans) ans = dp[n-1][i][j]; 90 return ans; 91 } 92 93 };