算法集训热身赛课后复盘
2021/4/23 22:57:53
本文主要是介绍算法集训热身赛课后复盘,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Codeforces-1513C Add One
+++
Example
input
5 1912 1 5 6 999 1 88 2 12 100
output
5 2 6 4 2115
+++
1.暴力dp(TLE版本)
思路:f(i, j)表示第i次操作,j有多少个,集合属性cnt,表示序列中j的个数。
转移:f(i, j) = f(i - 1, j - 1) (i 属于1到9) 然后考虑9分裂成1和0的情况:
f(i, 0) = f(i - 1, 9), f(i, 1) += f(i - 1, 9)。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10, MOD = 1e9 + 7; int f[N][15]; int t; int n, m; int main() { scanf("%d", &t); while (t -- ) { scanf("%d%d", &n, &m); int k = n; for (int i = 0; i <= 9; i ++ ) f[0][i] = 0; while (k) { f[0][k % 10] ++ ; k /= 10; } //for (int i = 0; i <= 9; i ++ ) cout << f[0][i] << endl; for (int i = 1; i <= m; i ++ )//操作数 { int temp = f[i - 1][9];//记录上一次操作9的次数 for (int j = 9; j >= 1; j -- ) { f[i][j] = f[i - 1][j - 1];//[i][9] = [i - 1][8] [i][1] = [i - 1][0]; } f[i][0] = temp; f[i][1] = (f[i][1] + temp) % MOD; //for (int j = 0; j <= 9; j ++ ) cout << "f[" << i << "][" << j << "]:" << f[i][j] << endl; } LL ans = 0; for (int i = 0; i <= 9; i ++ ) { ans = (ans + f[m][i]) % MOD; //printf(" ! %d ", f[m][i]); } printf("%lld\n", ans); } return 0; }
2.ac code
没思路了看大佬博客学习到的做法。(自己想到了所有数字最后都会变成10,但是忘记预处理数组来优化了)
思路: 0到9每个数字经过若干次变换都会变成10,之后的变换就是固定形式的了,所以我们可以预处理出来f数组,数组含义和前一个tle code的含义相同,处理出来初始状态是10的f数组,然后用sum数组存下来经过i次变换数字长度,然后之后的每次操作直接访问sum数组就可以得到答案。
具体细节看code注释
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int N = 2e5 + 10, MOD = 1e9 + 7; int f[N][15];//要预处理的数组 int a[15];//存储数字n的每一位 int sum[N];//存储变化i次目前长度变成了多少 int n, m; int t; void init()//预处理f数组 { f[0][0] = f[0][1] = 1, sum[0] = 2;//初始状态10 for (int i = 1; i < N; i ++ )//操作数 { int temp = f[i - 1][9];//记录上一次操作9的次数 for (int j = 9; j >= 1; j -- ) { f[i][j] = f[i - 1][j - 1]; } f[i][0] = temp; f[i][1] = (f[i][1] + temp) % MOD; sum[i] = (1ll * sum[i - 1] + temp) % MOD;//记录长度 } } int main() { init(); scanf("%d", &t); while (t -- ) { scanf("%d%d", &n, &m); //学习大佬博客学到的写法 a[0] = 0;//一个含义是a数组索引,另一个含义是统计数字位数 while (n) { a[ ++ a[0]] = n % 10; n /= 10; } LL ans = 0; for (int i = 1; i <= a[0]; i ++ )//看每一位 { int cnt = 10 - a[i];//距离10差多少步 if (m < cnt)//不够分裂 ans = (1ll * ans + 1) % MOD;//加上这一位的长度 else ans = (1ll * ans + sum[m - cnt]) % MOD;//加上这一位变换后的长度 } printf("%lld\n", ans); } return 0; }
+++
Codeforces-1513B AND Sequences
+++
Example
Input
4 3 1 1 1 5 1 2 3 4 5 5 0 2 0 3 0 4 1 3 5 1
Output
6 0 36 4
推论提要:
a1 = a2 & a3 & a4 & ... & an 等价于 a1 & a2 & ... & ai = ai+1 & ai+2 & ... & an. (i > 1 && i < n)
思路:分析等式:
a1 = a2 & a3 & a4 & a5 & ... & an = a1 & a2 & a3 & ... & an.
a1 & a2 = a3 & a4 & a5 & ... & an = a1 & a2 & a3 & ... & an.
a1 & a2 & a3 & ... & an-1 = an = a1 & a2 & a3 & ... & an.
由上述推论得到即等价于: a1 = a1 & a2 & ... & an = an.所以我们要做到的就是找到出现次数超过两次的数,挑两个放在首尾,中间位置为剩余数字的全排列。
ac code
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 2e5 + 10, MOD = 1e9 + 7; int t; LL num[N]; LL f[N]; int main() { scanf("%d", &t); f[0] = 1; for (int i = 1; i < N - 5; i ++ ) f[i] = f[i - 1] * i % MOD; while (t -- ) { LL n, last; scanf("%lld", &n); for (int i = 1; i <= n; i ++ ) { scanf("%lld", &num[i]); if (i == 1) last = num[i]; else last &= num[i]; } int cnt = 0; for (int i = 1; i <= n; i ++ ) if (num[i] == last) cnt ++ ; //这里刚开始忘记成1ll,一直wa。。卡了好久 //以后建议所有单变量直接开LL if (cnt >= 2) printf("%lld\n", 1ll * cnt * (cnt - 1) % MOD * f[n - 2] % MOD); else printf("0\n"); } return 0; }
这篇关于算法集训热身赛课后复盘的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南