首页 > 代码库 > Weekly 10 小结
Weekly 10 小结
A题
模拟
1 T = int(input()) 2 while T: 3 T -= 1 4 s = raw_input() 5 n = len(s) 6 res, pre = 0, 0 7 for i in xrange(1, n): 8 if (s[i] == s[pre]): 9 res += 110 else:11 pre = i12 print res
B题
模拟
1 n, k = map(int, raw_input().split()) 2 s = raw_input() 3 4 res = [] 5 ans = 0 6 for i in xrange(n): 7 if i >= k: 8 ans ^= int(res[i-k]) 9 tmp = ans ^ int(s[i])10 res.append(tmp)11 ans ^= tmp12 print ‘‘.join(map(str, res))
C题
题目大意:给出k种高度不同的积木,每种积木可以使用无数次,问使用这些积木拼成高度为N的塔的方法数对1e9 + 7的模是多少。
另F(x)为拼接成高度为x的方法数,则F(x) = sigma(F(i)) (1 <= i <= k && high[i] <= x)
可先处理出1~15的F函数的值,当N>15时,使用矩阵加速即可。
1 #include <cmath> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 using namespace std; 8 9 typedef long long LL;10 const int MOD = 1e9 + 7;11 #define rep(i, n) for (int i = (1); i <= (n); i++)12 LL N, K, A[20], f[20];13 struct Matrix {14 LL a[20][20];15 Matrix() {memset(a, 0, sizeof(a));}16 17 Matrix operator * (const Matrix &x) const {18 Matrix c;19 rep (i, 15) rep (k, 15) rep (j, 15) c.a[i][j] = (c.a[i][j] + x.a[k][j] * a[i][k]) % MOD;20 return c;21 }22 };23 24 Matrix pow_mod(Matrix a, LL b) {25 if (b < 0) return a;26 Matrix res; 27 rep (i, K) res.a[i][i] = 1;28 while (b > 0) {29 if (b & 1) res = res * a;30 a = a * a;31 b >>= 1;32 }33 return res;34 }35 36 37 int main() {38 ios::sync_with_stdio(false);39 cin >> N >> K;40 rep (i, K) cin >> A[i];41 42 sort(A + 1, A + K + 1);43 f[0] = 1;44 rep (i, 15) rep (j, K) if (i >= A[j]) f[i] = (f[i] + f[i - A[j]]) % MOD;45 rep (i, 15) cerr << f[i] << endl;46 if (N <= 15) {47 cout << f[N] * 2 % MOD << endl;48 return 0;49 }50 51 Matrix a; rep (i, 15) a.a[i][i-1] = 1;52 a.a[1][1] = 0; rep (i, K) a.a[1][A[i]] = 1;53 Matrix res = pow_mod(a, N - 15);54 LL ans = 0;55 rep (i, 15) ans = (ans + res.a[1][i] * f[16 - i]) % MOD;56 ans = (ans * 2) % MOD;57 cout << ans << endl;58 return 0;59 }
D题
题目大意:给出N个点,每个点有两个值V和P。要求从1开始走到N,在每个点选择有两种选择,要么将总得分加上V,要么还可以向前走P步。
目标是使得走到N时的总得分最大。题目保证至少存在一种解。
这题DP方程很明显,从后往前进行dp, dp[i] = min(dp[i], dp[j]), i < j <= i + P[i];
所以对于每个点,要快速的求出dp[i]~dp[i + P[i]] 的最小值。
直到做这个题我才知道原来BIT也可以用来求最值,原来0base和1base是这个含义。。(数组下标从0/1开始)
原来BIT数组下标可以从0开始,貌似被称为0base邪教,如:for (int x = i; x >= 0; x -= ~x & x + 1) {}
这里很巧妙的利用了~x = - x + 1,即~x = -(x + 1),还有运算符的优先级。摘自叉姐代码。
1 #include <cmath> 2 #include <cstdio> 3 #include <vector> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 #define rep(i, n) for (int i = (1); i <= (n); i++) 9 typedef long long LL;10 const int MAX_N = 500050;11 const LL INF = (LL)1e18;12 int V[MAX_N], P[MAX_N]; 13 LL tree[MAX_N];14 int N;15 16 int main() {17 scanf("%d", &N);18 for (int i = 1; i <= N; i++) scanf("%d %d", V+i, P+i);19 20 fill(tree+1, tree+N+1, -INF); 21 LL ans = tree[N] = V[N], sum = 0;22 for (int i = N-1; i >= 1; i--) {23 ans = -INF;24 for (int x = min(i+P[i], N); x > 0; x -= x&-x) 25 ans = max(ans, tree[x]);26 if (ans > -INF) {27 for (int x = i; x <= N; x += x&-x) 28 tree[x] = max(tree[x], ans - V[i]);29 }30 31 ans += sum;32 sum += V[i];33 }34 printf("%lld\n", ans);35 36 return 0;37 }
E题
Weekly 10 小结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。