因为期末了本来不想写了 但是觉得挂篇空文也无所谓 还是写了
12.27
去西工大玩。
12.28-12.29
什么都没干。
12.30
上次挂的BC。
HDU 5602
一开始以为A用1表示。
WA了pretest。
看clar改完过了pre然后fst。
一直以为是dp错。找了很久很久找不出来。
后来看div2的clar才知道只有10用T表示。JQK还是JQK。
这样都能过pre。sample也没有。无语了。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 double dp1[22][22], dp2[22][22];//x z 7 double p[11] = { 0, 8 1.0 / 13, 1.0 / 13, 1.0 / 13, 9 1.0 / 13, 1.0 / 13, 1.0 / 13,10 1.0 / 13, 1.0 / 13, 1.0 / 13, 4.0 / 1311 };12 13 void pre()14 {15 for(int i = 2; i <= 21; i++)16 for(int j = i; j <= 21; j++)17 dp1[i][j] = 1;18 19 for(int i = 21; i >= 2; i--)20 for(int j = i - 1; j >= 2; j--)21 for(int k = 10; k >= 1; k--)22 if(j + k <= 21) dp1[i][j] += p[k] * dp1[i][j+k];23 24 for(int i = 21; i >= 2; i--)25 {26 for(int j = 21; j >= 2; j--)27 {28 double tmp = 0;//draw->lose29 for(int k = 10; k >= 1; k--)30 {31 if(i + k > 21) tmp += p[k];32 else tmp += p[k] * dp2[i+k][j];33 }34 dp2[i][j] = min(dp1[i][j], tmp);35 }36 }37 return;38 }39 40 int num(char c)41 {42 if(c == 'A') return 1;43 if(c >= '0' && c <= '9') return c - '0';44 return 10;45 }46 47 int main(void)48 {49 pre();50 int T;51 scanf("%d", &T);52 while(T--)53 {54 int s1, s2;55 char s[11];56 scanf("%s", s);57 s1 = num(s[0]) + num(s[1]);58 s2 = num(s[2]) + num(s[3]);59 puts(dp2[s1][s2] < 0.5 ? "YES" : "NO");60 }61 return 0;62 }
12.31
CF 611 D
n2搞下LCP就好了。QAQ
1 #include2 #include 3 #include 4 using namespace std; 5 typedef long long LL; 6 const LL mod = 1e9 + 7; 7 LL dp[5005][5005]; 8 char num[5005]; 9 int com[5005][5005];10 11 bool bigger(int pos1, int pos2, int len)12 {13 int x = com[pos1][pos2];14 if( x >= len) return false;15 return num[pos1+x] > num[pos2+x];16 }17 18 int main(void)19 {20 int n;21 scanf("%d%s", &n, num + 1);22 23 for(int i = n; i >= 1; i--)24 for(int j = n; j >= 1; j--)25 com[i][j] = num[i] == num[j] ? ( com[i+1][j+1] + 1 ) : 0 ;26 27 for(int i = 1; i <= n; i++)28 {29 for(int j = 1; j <= i; j++)30 {31 if(num[i-j+1] == '0') dp[i][j] = dp[i][j-1];32 else if(i == j) dp[i][j] = ( dp[i][j-1] + 1LL ) % mod;33 else if( i >= 2 * j && bigger(i-j+1, i-2*j+1, j) ) dp[i][j] = ( dp[i][j-1] + dp[i-j][j] ) % mod;34 else dp[i][j] = ( dp[i][j-1] + dp[i-j][min(i-j,j-1)]) % mod;35 }36 }37 printf("%I64d\n", dp[n][n]);38 return 0;39 }
1.1
CF 611 E
多重集搞搞。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 multiset M; 7 multiset ::iterator it; 8 int m[3]; 9 10 int main(void)11 {12 int n;13 scanf("%d", &n);14 for(int i = 0; i < 3; i++) scanf("%d", m + i);15 sort(m, m + 3);16 int a = m[0], b = m[1], c = m[2];17 18 for(int i = 0; i < n; i++)19 {20 int t;21 scanf("%d", &t);22 if(t > a + b + c) {puts("-1"); return 0;}23 M.insert(t);24 }25 26 int ans = 0;27 28 while(!M.empty())29 {30 it = M.lower_bound(b + c + 1);31 if(it == M.end()) break;32 M.erase(it); ans++;33 }34 35 while(!M.empty())36 {37 it = M.lower_bound(a + c + 1);38 if(it == M.end()) break;39 M.erase(it); ans++;40 if(M.empty()) break;41 it = M.lower_bound(a + 1);42 if(it != M.begin()) M.erase(--it);43 }44 45 while(!M.empty())46 {47 it = M.lower_bound(max(c, a + b) + 1);48 if(it == M.end()) break;49 M.erase(it); ans++;50 if(M.empty()) break;51 it = M.lower_bound(b + 1);52 if(it != M.begin()) M.erase(--it);53 }54 55 int x = 0, y = 0, k = 0;56 for(it = M.begin(); it != M.end(); it++)57 {58 if(*it <= a + b) x++;59 if(*it <= c) y++;60 }61 62 int s = max( (max(x, y) + 1) /2, max(x-y, y-x) );63 while(!M.empty() && y)64 {65 it = M.lower_bound(c + 1);66 if(it != M.begin())67 {68 --it;69 if(*it <= a + b) x--;70 if(*it <= c) y--;71 M.erase(it);72 }73 it = M.lower_bound(b + 1);74 if(it != M.begin())75 {76 --it;77 if(*it <= a + b) x--;78 if(*it <= c) y--;79 M.erase(it);80 }81 it = M.lower_bound(a + 1);82 if(it != M.begin())83 {84 --it;85 if(*it <= a + b) x--;86 if(*it <= c) y--;87 M.erase(it);88 }89 s = min( s, ++k + max( (max(x, y) + 1)/2, max(x-y, y-x) ) );90 }91 92 printf("%d\n", ans + s);93 94 return 0;95 }
1.2
矩阵快速幂！矩阵快速幂！矩阵快速幂！
一直懒得自己码板。每次都是用到去搜。受不了了！
1 struct Matrix 2 { 3 LL m[maxn][maxn]; 4 Matrix(){memset(m, 0, sizeof(m));} 5 void E(){ for(int i = 0; i < maxn; i++) m[i][i] = 1;} 6 }; 7 8 Matrix M_mul(Matrix a, Matrix b) 9 {10 Matrix ret;11 for(int i = 0; i < maxn; i++)12 for(int j = 0; j < maxn; j++)13 for(int k = 0; k < maxn; k++)14 ret.m[i][j] = ( ret.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod ) % mod;15 return ret;16 }17 18 Matrix M_qpow(Matrix P, LL n)19 {20 Matrix ret;21 ret.E();22 while(n)23 {24 if(n & 1LL) ret = M_mul(ret, P);25 n >>= 1LL;26 P = M_mul(P, P);27 }28 return ret;29 }
HDU 5607
直接搞！
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long LL; 7 const int maxn = 55; 8 const LL mod = 1e9 + 7; 9 int G[maxn][maxn], deg[maxn]; 10 LL ans[22][maxn]; 11 12 struct query 13 { 14 int id, u; 15 LL K; 16 }q[22]; 17 18 bool cmp(query a, query b) 19 { 20 return a.K < b.K; 21 } 22 23 LL qpow(LL a, LL b) 24 { 25 LL ret = 1LL, tmp = a; 26 while(b) 27 { 28 if(b & 1LL) ret = ret * tmp % mod; 29 tmp = tmp * tmp % mod; 30 b >>= 1LL; 31 } 32 return ret; 33 } 34 35 LL inv(LL a) 36 { 37 LL k = 1e9 + 5; 38 return qpow(a, k); 39 } 40 41 struct Matrix 42 { 43 LL m[maxn][maxn]; 44 Matrix(){memset(m, 0, sizeof(m));} 45 void E(){ for(int i = 0; i < maxn; i++) m[i][i] = 1;} 46 }; 47 48 Matrix M_mul(Matrix a, Matrix b) 49 { 50 Matrix ret; 51 for(int i = 0; i < maxn; i++) 52 for(int j = 0; j < maxn; j++) 53 for(int k = 0; k < maxn; k++) 54 ret.m[i][j] = ( ret.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod ) % mod; 55 return ret; 56 } 57 58 Matrix M_qpow(Matrix P, LL n) 59 { 60 Matrix ret; 61 ret.E(); 62 while(n) 63 { 64 if(n & 1LL) ret = M_mul(ret, P); 65 n >>= 1LL; 66 P = M_mul(P, P); 67 } 68 return ret; 69 } 70 71 int main(void) 72 { 73 int N, M; 74 scanf("%d%d", &N, &M); 75 for(int i = 1; i <= M; i++) 76 { 77 int X, Y; 78 scanf("%d%d", &X, &Y); 79 deg[X]++; 80 G[X][Y] = 1; 81 } 82 int Q; 83 scanf("%d", &Q); 84 for(int i = 0; i < Q; i++) 85 { 86 scanf("%d%I64d", &q[i].u, &q[i].K); 87 q[i].id = i; 88 } 89 sort(q, q + Q, cmp); 90 Matrix A, B = M_qpow(A, 0LL); 91 for(int i = 1; i <= N; i++) 92 { 93 LL R = inv(deg[i]); 94 for(int j = 1; j <= N; j++) 95 if(G[i][j]) A.m[j][i] = R; 96 } 97 for(int i = 0; i < Q; i++) 98 { 99 LL nn;100 if(!i) nn = q[i].K;101 else nn = q[i].K - q[i-1].K;102 B = M_mul(B, M_qpow(A, nn));103 for(int j = 1; j <= N; j++) ans[q[i].id][j] = B.m[j][q[i].u];104 }105 for(int i = 0; i < Q; i++)106 {107 for(int j = 1; j <= N; j++) printf("%d ", ans[i][j]);108 puts("");109 }110 return 0;111 }