您现在的位置是:网站首页> 内容页

Kickstart Round H 2018

  • 恒峰娱乐g22娱乐
  • 2019-05-14
  • 462人已阅读
简介打了ks好久都没有更新诶,自己的粗心真的是没救了,A题大数据都能错A#include<iostream>#include<cstdio>#include&

打了ks好久都没有更新诶,自己的粗心真的是没救了,A题大数据都能错A

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cstring>#include <vector>#include <list>#include <queue>#include <stack>#include <map>#include <set>#include <bitset>#include <algorithm>#include <functional>#include <assert.h>#include <iomanip>using namespace std;// const int N = 7005;// const int M = 2e5 + 5;const int INF = 0x3f3f3f3f;const int MOD = 1000000007;typedef long long ll;char seq[105][55];int tot, Root;int nx[10005][2];int tag[10005];int newNode() { nx[tot][0] = nx[tot][1] = -1; tag[tot] = 0; return tot ++;}int N, P; void Insert(char* s) { int len = strlen(s); int root = Root; for(int i = 0; i < len; ++i) { int id = s[i] == "R"; if(nx[root][id] == -1) { nx[root][id] = newNode(); } root = nx[root][id]; } tag[root] ++;}ll dfs(int rt, int deep) { if(tag[rt]) return 1ll<<(N - deep); ll ans = 0; if(nx[rt][0] != -1) ans += dfs(nx[rt][0], deep + 1); if(nx[rt][1] != -1) ans += dfs(nx[rt][1], deep + 1); return ans;}int main() { freopen("A-large-practice2.in", "r", stdin); freopen("A-large-practice2.out", "w", stdout); int T; scanf("%d", &T); for(int _ = 1; _ <= T; ++_) { tot = 0; Root = newNode(); scanf("%d %d", &N, &P); for(int i = 0; i < P; ++i) { scanf("%s", seq[i]); Insert(seq[i]); } printf("Case #%d: %lld", _, (1ll<<N) - dfs(Root, 0)); } return 0;}

B

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cstring>#include <vector>#include <list>#include <queue>#include <stack>#include <map>#include <set>#include <bitset>#include <algorithm>#include <functional>#include <assert.h>#include <iomanip>using namespace std;const int M = 5e6 + 5;const int INF = 0x3f3f3f3f;const int MOD = 1000000007;typedef long long ll;char seq[M];int main() { freopen("B-large.in", "r", stdin); freopen("B-large.out", "w", stdout); int T; scanf("%d", &T); for(int _ = 1; _ <= T; ++_) { int n; scanf("%d %s", &n, seq + 1); int ans = 0; int tmp = 0; for(int i = 1; i <= (n+1)/2; ++i) { tmp += seq[i] - "0"; } ans = max(ans, tmp); for(int i = (n+1)/2 + 1, j = 1; i <= n; ++i, ++j) { tmp -= seq[j] - "0"; tmp += seq[i] - "0"; ans = max(ans, tmp); } printf("Case #%d: %d", _, ans); } return 0;}

C容斥原理

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cstring>#include <vector>#include <list>#include <queue>#include <stack>#include <map>#include <set>#include <bitset>#include <algorithm>#include <functional>#include <assert.h>#include <iomanip>using namespace std;// const int N = 7005;const int M = 2e5 + 5;const int INF = 0x3f3f3f3f;const int MOD = 1000000007;typedef long long ll;ll Mul[M];ll Pow(ll x, ll y) { ll ans = 1; while(y) { if(y & 1) ans = 1ll * ans * x % MOD; x = 1ll * x * x % MOD; y >>= 1; } return ans;}ll C(int x, int y) { if(y == 0) return 1; if(x == y) return 1; return 1ll* Mul[x] * Pow(Mul[y] * Mul[x - y] % MOD, MOD - 2) % MOD;}int main() { freopen("C-small-attempt0.in", "r", stdin); freopen("C-small-attempt0.out2", "w", stdout); int T; scanf("%d", &T); Mul[1] = 1; Mul[0] = 1; for(int i = 2; i < M; ++i) { Mul[i] = Mul[i-1] * i % MOD; } for(int _ = 1; _ <= T; ++_) { int n, m; scanf("%d %d", &n, &m); ll ans = Mul[2*n]; int init = 2*n; ll mul2 = 1; for(int i = 1; i <= m; ++i) { init --; mul2 = mul2 * 2 % MOD; ll tmp = mul2 * Mul[init] % MOD * C(m, i) % MOD; ans = (ans + ( (i % 2) ? -tmp : tmp) + MOD) % MOD; } printf("Case #%d: %lld", _, ans); } return 0;}

文章评论

Top