目录
试题 A: 九进制转十进制
试题 B: 顺子日期
试题 C: 刷题统计
试题 D: 修剪灌木
试题 E: X 进制减法
试题 F: 统计子矩阵
试题 G: 积木画
试题 H: 扫雷
试题 I: 李白打酒加强版
试题 J: 砍竹子
试题 A: 九进制转十进制
九进制正整数 ( 2022 )转换成十进制等于多少?
#include
using namespace std;
int main()
{
int c, ans = 0;
while (c = getchar(), '0' <= c && c <= '9')
ans = ans * 9 + c - '0';
cout< return 0; } 试题 B: 顺子日期 小明特别喜欢顺子。顺子指的就是连续的三个数字: 123 、 456 等。顺子日期指的就是在日期的 yyyymmdd表示法中,存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期,因为它出现了一个顺子:123;而 20221023则不是一个顺子日期,它一个顺子也没有。小明想知道在整个 2022 年份中,一共有多少个顺子日期。 #include using namespace std; int date1[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //确定2022年的每月的天数 int main() { int b[8]; //b[0]到b[4]表示的是2022年 b[0] = 2; b[1] = 0; b[2] = 2; b[3] = 2; int sum = 0; for (int i = 1; i <= 12; i++) //从一月到12月 { b[4] = i / 10; //月数的高位 b[5] = i % 10; //月数的低位 for (int j = 1; j <= date1[i]; j++) //从每月的第一天到最后一天 { b[6] = j / 10; //表示天数的高位 b[7] = j % 10; //表示天数的低位 if ((b[4] + 1 == b[5] && b[5] + 1 == b[6]) || (b[5] + 1 == b[6] && b[6] + 1 == b[7])) //如果是顺子日期就+1 { sum++; } } } cout << sum << endl; return 0; } 试题 C: 刷题统计 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a道题目,周六和周日每天做 b道题目。请你帮小明计算,按照计划他将在第几天实现做题数大于等于 n题? 输入格式:输入一行包含三个整数a,b和n。 输出格式:输出一个整数代表天数。 样例输入:10 20 99 样例输出:8 #include using namespace std; int main() { long long a,b,n,ans; cin>>a>>b>>n; ans = n / (5 * a + 2 * b) * 7; n %= 5 * a + 2 * b; if (n > 5 * a) ans += 5 + ((n - 5 * a) + b - 1) / b; else ans += (n + a - 1) / a; cout< return 0; } 试题 D: 修剪灌木 爱丽丝要完成一项修剪灌木的工作。 有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木,让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始,每天向右修剪一棵灌木。当修剪了最右侧的灌木后,她会调转方向,下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。 灌木每天从早上到傍晚会长高 1 厘米,而其余时间不会长高。在第一天的早晨,所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。 输入格式:一个正整数N,含义如题面所述。 输出格式:输出N行,每行一个整数,表示从左到右第i棵树最高能长到多高。 样例输入:3 样例输出: 4 2 4 #include using namespace std; int n,a[10005]; int main() { int n; cin>>n; for(int i = 1;i <= n;i++) { cout< } return 0; } 试题 E: X 进制减法 进制规定了数字在数位上逢几进一。 X 进制是一种很神奇的进制,因为其每一数位的进制并不固定!例如说某种 X 进制数,最低数位为二进制,第二数位为十进制,第三数位为八进制,则 X进制数 321 转换为十进制数为 65 。 现在有两个 X 进制表示的整数 A 和 B ,但是其具体每一数位的进制还不确定,只知道 A 和 B 是同一进制规则,且每一数位最高为 N 进制,最低为二进制。请你算出 A − B 的结果最小可能是多少。 请注意,你需要保证 A 和 B 在 X 进制下都是合法的,即每一数位上的数字要小于其进制。 输入格式: 第一行一个正整数N,含义如题面所述。 第二行一个正整数Ma,表示x进制数A的位数。 第三行Ma个用空格分开的整数,表示x进制数A按从高位到低位顺序各个数位上的数字在十进制下的表示。 第四行一个正整数Mb,表示x进制数B的位数。 第五行Mb个用空格分开的整数,表示x进制数B按从高位到低位顺序各个数位上的数字在十进制下的表示。 请注意,输入中的所有数字都是十进制的。 输出格式: 输出一行一个整数,表示x进制数A-B的结果的最小可能值转换为十进制后再模1000000007的结果。 样例输入: 11 3 10 4 0 3 1 2 0 样例输出: 94 #include using namespace std; const int vinf = 100010; const int mod = 1000000007; typedef long long ll; int a[vinf],b[vinf]; int weights[vinf]; //单个位数上的权值 ll ans; int main() { /* 例如:3 的进制为8,2的进制为10,1的进制为2 3 2 1 8 10 2 1 + 2 * 2 + 3 * 10 * 2 = 65 10 4 0 11 5 2 0 + 4 * 2 + 10 * 5 * 2 = 108 当进制为:最低位 2 进制,第二数位 5 进制,第三数位 11 进制时,减法得到的差最小。 */ int N; //最大进制数 cin>>N; int na,nb; cin>>na; for(int i = na;i >= 1;i--) //从高位开始输入 cin>>a[i]; cin>>nb; for(int i = nb; i >= 1;i--) cin>>b[i]; //选取位数多的 int max_num = max(na,nb); //计算每一位上的权值 for(int i = 1;i <= max_num;i++) weights[i] = max(max(a[i], b[i]) + 1, 2); //计算两个数字的按权展开的和 ll A = 0, B = 0; for(int i = na;i >= 1;i--) A = (A * weights[i] + a[i]) % mod; for(int i = nb;i >= 1;i--) B = (B * weights[i] + b[i]) % mod; ans = (A - B) % mod; cout< return 0; } 试题 F: 统计子矩阵 给定一个N*M的矩阵A,请你统计有多少个子矩阵(最小1*1,最大N*M)满足子矩阵中所有数的和不超过给定的整数K? 输入格式: 第一行包含三个整数N,M和K。 之后N行每行包含M个整数,代表矩阵A。 输出格式: 一个整数代表答案。 样例输入: 3 4 10 1 2 3 4 5 6 7 8 9 10 11 12 19 #include using namespace std; const int MAX = 501; typedef long long ll; int area[MAX][MAX]; ll ans = 0; int main() { int n,m,k; cin>>n>>m>>k; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { cin>>area[i][j]; area[i][j] += area[i-1][j]; //前缀和 } } //滑动窗口算法 for(int start = 1;start <= n;start++) //起始行 { for(int end = start;end <= n;end++) //最终行 { //滑动窗口的边界 int l = 1,r = 1,sum = 0; for(;r <= m;r++) { //扩大窗口 sum += area[end][r] - area[start - 1][r]; while(sum > k) { //缩小窗口 sum -= area[end][l] - area[start - 1][l]; //左边界右移 l++; } //算数 ans += r - l + 1; } } } cout< return 0; } 试题 G: 积木画 样例输入: 3 样例输出: 5 #include using namespace std; typedef long long ll; const int mod = 1e9+7; const int m = 10000000; int f[m][3]; ll n; int main() { cin.tie(0),cout.tie(0); ios::sync_with_stdio(false); //设f[i][0]表示当前拼完了前i列的方案数, //f[i][1]表示当前拼完了前i-1列,且第i列拼完了上面方格的方案数, //f[i][2]表示当前拼完了前i-1列,且当前第i列拼完了下面方格的方案数。 f[0][0] = 1; cin>>n; for(int i = 1;i <= n;i++) { f[i][0] = (f[i-1][0] + f[i-1][1] + f[i-1][2]) % mod; if(i >= 2) { f[i][0] = (f[i][0] + f[i-2][0]) % mod; f[i][1] = (f[i-1][2] + f[i-2][0]) % mod; f[i][2] = (f[i-1][1] + f[i-2][0]) % mod; } } cout< return 0; } 试题 H: 扫雷 样例输入: 2 1 2 2 4 4 4 2 0 0 5 样例输出: 2 #include using namespace std; typedef long long ll; const int M = 999997; const ll Base = 1e9 + 7; int hash[M]; //哈希值,用于维护find函数 int num[M]; //当前位置有多少个炸弹 int radius[M]; //当前位置的半径 int visited[M]; //是否访问过 int res; //降维 ll get_key(int x,int y) { return x * Base + y; } //哈希函数 int find(int x) { int t = (x % M + M) % M; while(hash[t] != -1 && hash[t] != x) { t++; while(t == M) t = 0; } return t; } //判断是否在范围内 bool judge(int x,int y,int r,int x2,int y2) { int d = (x2 - x) * (x2 - x) + (y2 - y) * (y2 - y); return d <= r * r; } void dfs(int x,int y,int r) { for(int i = -r;i <= r;i++) { for(int j = -r;j <= r;j++) { int dx = x + i; int dy = y + j; int k = get_key(dx,dy); int t = find(k); while(hash[t] && judge(x,y,r,dx,dy) && !visited[t]) { res += num[t]; //答案加上该点地雷个数 visited[t] = 1; dfs(dx,dy,radius[t]); //搜索下一个点 } } } } int main() { cin.tie(0),cout.tie(0); ios::sync_with_stdio(false); int n,m; cin>>n>>m; memset(hash,-1,sizeof hash); for(int i = 0;i < n;i++) { int x,y,r; cin>>x>>y>>r; int k = get_key(x,y); int t = find(k); hash[t] = k; num[t]++; //统计该点地雷数量 radius[t] = max(r,radius[t]); //记录该点地雷半径的最大值 } for(int i = 0;i < m;i++) { int x,y,r; cin>>x>>y>>r; dfs(x,y,r); //从每一个排雷火箭引爆点开始dfs } cout< return 0; } 试题 I: 李白打酒加强版 样例输入: 5 10 样例输出: 14 #include using namespace std; int mod = 1e9 + 7; int dp[101][101][101]; int main() { cin.tie(0),cout.tie(0); ios::sync_with_stdio(false); int n,m; cin>>n>>m; dp[0][0][2] = 1; for(int i = 0;i <= n;i++) for(int j = 0;j <= m;j++) for(int k = 0;k <= m;k++) { //遇到花 if(j && k) dp[i][j][k] = (dp[i][j][k] + dp[i][j-1][k+1]) % mod; //遇到店 if(i && k % 2 == 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k/2]) % mod; } //最后一次需要是花 cout< return 0; } 试题 J: 砍竹子 样例输入: 6 2 1 4 2 6 7 样例输出: 5 #include using namespace std; typedef long long ll; struct Node { ll h; int idx; bool operator <(const Node &rhs) const { if(h == rhs.h) return idx > rhs.idx; //索引升序 return h < rhs.h; //高度降序 } }; priority_queue int ans; int main() { cin.tie(0),cout.tie(0); ios::sync_with_stdio(false); int n,h; cin>>n; for(int i = 1;i <= n;i++) { cin>>h; q.push((Node){h,i}); } while(!q.empty()) { Node node = q.top(); q.pop(); if(node.h == 1) continue; while(!q.empty() && q.top().h == node.h && q.top().idx == node.idx + 1) { node.idx = q.top().idx; q.pop(); } node.h = sqrtl(node.h / 2 + 1); if(node.h > 1) q.push(node); ans++; } cout< return 0; } 文章链接
发表评论