- A - Can you get AC?
- No
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pb push_back
- #define mp make_pair
- using namespace std;
- typedef long long int64;
- char s[15];
- int main() {
- scanf("%s",s + 1);
- int l = strlen(s + 1);
- for(int i = 1 ; i <l ; ++i) {
- if(s[i] == 'A' && s[i + 1] == 'C') {
- puts("Yes");return 0;
- }
- }
- puts("No");return 0;
- }
- B - Similar Arrays
dp[i][1/0] 表示到第 i 个数乘积是奇数或偶数
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pb push_back
- #define mp make_pair
- #define enter putchar('\n')
- #define space putchar(' ')
- //#define ivorysi
- using namespace std;
- typedef long long int64;
- template<class T>
- void read(T &res) {
- res = 0;T f = 1;char c = getchar();
- while(c <'0' || c> '9') {
- if(c == '-') f = -1;
- c = getchar();
- }
- while(c>= '0' && c <= '9') {
- res = res * 10 + c - '0';
- c = getchar();
- }
- res *= f;
- }
- template<class T>
- void out(T x) {
- if(x <0) {x = -x;putchar('-');}
- if(x>= 10) {
- out(x / 10);
- }
- putchar('0' + x % 10);
- }
- int N,A[15];
- int64 dp[15][2];
- int main() {
- #ifdef ivorysi
- freopen("f1.in","r",stdin);
- #endif
- read(N);
- for(int i = 1 ; i <= N ; ++i) read(A[i]);
- dp[0][1] = 1;
- for(int i = 1 ; i <= N ; ++i) {
- for(int j = -1 ; j <= 1 ; ++j) {
- if((A[i] + j) & 1) {
- dp[i][1] += dp[i - 1][1];
- dp[i][0] += dp[i - 1][0];
- }
- else {
- dp[i][0] += dp[i - 1][0] + dp[i - 1][1];
- }
- }
- }
- out(dp[N][0]);enter;
- }
- C - Inserting 'x'
从左右两边各一个指针, 如果匹配就往里走
如果不匹配且某一个为 x, 则把为 x 的那个往里走
如果不是则无法变成回文串
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pb push_back
- #define mp make_pair
- #define enter putchar('\n')
- #define space putchar(' ')
- //#define ivorysi
- using namespace std;
- typedef long long int64;
- template<class T>
- void read(T &res) {
- res = 0;T f = 1;char c = getchar();
- while(c <'0' || c> '9') {
- if(c == '-') f = -1;
- c = getchar();
- }
- while(c>= '0' && c <= '9') {
- res = res * 10 + c - '0';
- c = getchar();
- }
- res *= f;
- }
- template<class T>
- void out(T x) {
- if(x <0) {x = -x;putchar('-');}
- if(x>= 10) {
- out(x / 10);
- }
- putchar('0' + x % 10);
- }
- char s[100005];
- int N;
- int main() {
- #ifdef ivorysi
- freopen("f1.in","r",stdin);
- #endif
- scanf("%s",s + 1);
- N = strlen(s + 1);
- int p = 1,q = N;
- int ans = 0;
- while(p <q) {
- if(s[p] == s[q]) {++p;--q;}
- else {
- if(s[p] == 'x') {++p;++ans;}
- else if(s[q] == 'x') {--q;++ans;}
- else {puts("-1");return 0;}
- }
- }
- out(ans);enter;return 0;
- }
- D - Yet Another Palindrome Partitioning
记录一下一个位置前缀和奇偶性, 压成一个 27bit 的数 s
这个位置能从前面和 s 相同的位置和 s 改了一位的位置转移过来
不同的 s 只有 n 个, 拿 map 记一下就好
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define MAXN 200005 #define eps 1e-10 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) { res = 0;T f = 1;char c = getchar(); while(c <'0' || c> '9') { if(c == '-') f = -1; c = getchar(); } while(c>= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } template<class T> void out(T x) { if(x <0) {x = -x;putchar('-');} if(x>= 10) { out(x / 10); } putchar('0' + x % 10); } char s[MAXN]; int sum[MAXN],N; int dp[MAXN]; map<int,int> zz; void Init() { scanf("%s",s + 1); N = strlen(s + 1); for(int i = 1 ; i <= N ; ++i) { sum[i] = sum[i - 1]; sum[i] ^= (1 <<s[i] - 'a'); } } void Solve() { zz[0] = 0; for(int i = 1 ; i <= N ; ++i) { dp[i] = i; if(zz.count(sum[i])) dp[i] = min(dp[i],zz[sum[i]] + 1); for(int j = 0 ; j < 26 ; ++j) { if(zz.count(sum[i] ^ (1 << j))) dp[i] = min(dp[i],zz[sum[i] ^ (1 << j)] + 1); } if(!zz.count(sum[i])) zz[sum[i]] = dp[i]; else zz[sum[i]] = min(zz[sum[i]],dp[i]); } out(dp[N]);enter; } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Init(); Solve(); } E - Cubes
注意读题, 有句话是 ABC 两两互质
那么一共经过的方块数是
A + B + C - 2
认为有一位经过某个整数则经过了一个方块
那么其实可以这么认为
A + B + C - gcd(A,B) - gcd(B,C) - gcd(B,A) + gcd(A,B,C)
由于 A,B,C 互质, 那么每次路径上的相邻两个方块肯定有一个面重合
如果去掉那个方块的限制, 那么答案是
\((2D + 1)^3 + (A + B + C - 3) \cdot (2D + 1)^2\)
就是以路径上一个点为中心上下左右各 \(D\) 个点
每次增量是一个面
那么如何计算交呢, 我们需要三维每一维分别取出前不足 D 的点和后不足 D 的点
可以用分数记录一下这些点, 个数只有 \(O(D)\) 个
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define enter putchar('\n') #define space putchar(' ') //#define ivorysi using namespace std; typedef long long int64; template<class T> void read(T &res) { res = 0;T f = 1;char c = getchar(); while(c <'0' || c> '9') { if(c == '-') f = -1; c = getchar(); } while(c>= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } template<class T> void out(T x) { if(x <0) {x = -x;putchar('-');} if(x>= 10) { out(x / 10); } putchar('0' + x % 10); } const int MOD = 1000000007; int64 t[3],D; vector<pair<int64,int64>> v; int ans; int inc(int a,int b) { return a + b>= MOD ? a + b - MOD : a + b; } int mul(int a,int b) { return 1LL * a * b % MOD; } int mul3(int a,int b,int c) { return mul(mul(a,b),c); } void update(int &x,int y) { x = inc(x,y); } void Solve() { for(int i = 0 ; i <3 ; ++i) read(t[i]);read(D); for(int64 i = 0 ; i <= D ; ++i) { for(int j = 0 ; j < 3 ; ++j) { if(i && i < t[j]) v.pb(mp(i,t[j])); if(t[j] - 1 - i> 0) v.pb(mp(t[j] - i - 1,t[j])); } } sort(v.begin(),v.end(),[](pair<int64,int64> a,pair<int64,int64> b){return a.fi * b.se <b.fi * a.se;}); v.erase(unique(v.begin(),v.end()),v.end()); int64 a[3] = {0,0,0}; update(ans,mul3(min(t[0],D + 1),min(t[1],D + 1),min(t[2],D + 1))); for(auto k : v) { int64 b[3] = {a[0],a[1],a[2]}; for(int j = 0 ; j < 3 ; ++j) { a[j] = t[j] * k.fi / k.se; } int64 d[3]; for(int j = 0 ; j < 3 ; ++j) { d[j] = min(b[j] + D,t[j] - 1) - max(b[j] - D,0LL) + 1; } for(int j = 0 ; j < 3 ; ++j) { if(a[j] + D < t[j]) { int t = a[j] - b[j]; for(int h = 0 ; h < 3 ; ++h) { if(h != j) t = mul(t,d[h]); } update(ans,t); } } } out(ans);enter; } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); } F - Three Gluttons
做 atc 总觉得自己是个智障, 早点退役保平安
条件我都没分析出来...= =
就是认为我们把这个分成三个数字不同的序列, 每个长度是 \(N / 3\)
第 \(t\) 次吃要满足 \(a_{1},a_{2},....a_{i_t},b_{1},b_{2},...b_{j_t}\)
中 \(a_{i_t}\) 和 \(b_{j_t}\) 只出现了一次
这样保证了两个序列里不会选重
然后第三个序列假如吃的是 \(x_{1},x_{2}...x_{\frac{N}{3}}\)
我要满足 \(x_{t}\)
在 \(a_{1},a_{2},....a_{i_t},b_{1},b_{2},...b_{j_t}\) 没有出现过
然后呢, 如果我们找出一个满足条件的吃的三个序列, 你会发现, 这样第三种序列填数的方案, 和我选了什么并没有关系!!!!!
然后设 \(dp[i][j]\) 表示考虑到第 i 个, 已经填在 c 序列里的有 j 个
i 没增加 1, 能填的数会多两个, 直接 dp 就行
然后就是怎么求三个合法序列了
从后往前推, 发现 \(x_{t}\) 不能填的数就是 \(a_{1},a_{2},....a_{i_t},b_{1},b_{2},...b_{j_t}\) 出现过的数, a,b,c 的后 \(n - t\) 个
前缀和优化一下可以做到 \(N^{3}\)
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define MAXN 20000005 #define eps 1e-10 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) { res = 0;T f = 1;char c = getchar(); while(c <'0' || c> '9') { if(c == '-') f = -1; c = getchar(); } while(c>= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } template<class T> void out(T x) { if(x <0) {x = -x;putchar('-');} if(x>= 10) { out(x / 10); } putchar('0' + x % 10); } const int MOD = 1000000007; int inc(int a,int b) { return a + b>= MOD ? a + b - MOD : a + b; } int mul(int a,int b) { return 1LL * a * b % MOD; } void update(int &x,int y) { x = inc(x,y); } int fpow(int x,int c) { int res = 1,t = x; while(c) { if(c & 1) res = mul(res,t); t = mul(t,t); c>>= 1; } return res; } int dp[150][405],N,f[150][405][405],w,ans; int a[405],b[405],fac[405],invfac[405]; bool visa[405],visb[405],vis[405][405]; int cnt[405][405],g[405]; int A(int n,int m) { if(n <m) return 0; return mul(fac[n],invfac[n - m]); } void Solve() { read(N); for(int i = 1 ; i <= N ; ++i) read(a[i]); for(int i = 1 ; i <= N ; ++i) read(b[i]); fac[0] = 1; for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i); invfac[N] = fpow(fac[N],MOD - 2); for(int i = N - 1 ; i>= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1); dp[1][2] = 1; for(int i = 1 ; i <N / 3 ; ++i) { for(int j = 0 ; j <= i * 2 ; ++j) { for(int h = 0 ; h <= j; ++h) { update(dp[i + 1][j + 2 - h],mul(A(j,h),dp[i][j])); } } } for(int j = 0 ; j <= (N / 3) * 2 ; ++j) update(w,mul(dp[N / 3][j],fac[j])); for(int i = 1 ; i <= N ; ++i) { visa[a[i]] = 1; cnt[i][0] = i; memset(visb,0,sizeof(visb)); for(int j = 1 ; j <= N ; ++j) { visb[b[j]] = 1; cnt[i][j] = cnt[i][j - 1]; if(!visa[b[j]]) cnt[i][j]++; if(!visa[b[j]] && !visb[a[i]]) vis[i][j] = 1; } } for(int t = N / 3 ; t>= 1 ; --t) { memset(g,0,sizeof(g)); for(int i = N ; i>= 1 ; --i) { int s = (t == N / 3); for(int j = N ; j>= 1 ; --j) { if(vis[i][j]) f[t][i][j] = mul(s,N - 3 * (N / 3 - t) - cnt[i][j]); update(s,g[j]); update(g[j],f[t + 1][i][j]); } } } for(int i = 1 ; i <= N ; ++i) { for(int j = 1 ; j <= N ; ++j) { update(ans,f[1][i][j]); } } ans = mul(ans,w); out(ans);enter; } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); } [AtCoder] CODE FESTIVAL 2017 qual C
来源: http://www.bubuko.com/infodetail-2942122.html