A:2022
问题描述
将 2022 拆分成 10 个互不相同的正整数之和, 总共有多少种拆分方法?
注意交换顺序视为同一种方法, 例如 2022=1000+1022 和 1022+1000 就视为同一种方法。
答案提交
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
运行限制
最大运行时间：1s
最大运行内存: 512M
dp动态规划，a[i][j][v]代表1到i个数中，选j个数，和为v的答案总数；每次到i时有两种状况，选i和不选i
选i: a[i][j][v] a[i-1][j-1][v-i] 相对上次来说，j要加一，i要加一，但是此次选i因此要求上 一次 是v-i；
不选i: a[i][j][v] a[i-1][j][v];
因此a[i][j][v] =a[i-1][j-1][v-i]+a[i-1][j][v];但是要考虑有时候i放不进去的情况，比如v=2,但i=5，i不能放因此递推公式有了
if(v - i >= 0 && j - 1 >= 0){ //v要大于等于i，并且至少要选一个数；
f[i][j][v] = f[i - 1][j - 1][v - i];
}
f[i][j][v] += f[i - 1][j][v]; //每次必定加上
#include <iostream> using namespace std; long long f[2030][11][2030]; int main(){ f[0][0][0]=1; for(int i=1;i<=2022;i++){ for(int j=0;j<=10;j++){ for(int v=0;v<=2022;v++){ if(v - i >= 0 && j - 1 >= 0){ f[i][j][v] = f[i - 1][j - 1][v - i]; } f[i][j][v] += f[i - 1][j][v]; } } } cout<<f[2022][10][2022]; return 0; }
B:钟表
问题描述
在 12 小时制的钟表中, 有分针、时针、秒针来表示时间。记分针和时 针之间的夹角度数为 A(0≤A≤180) 、分针和秒针之间的夹角度数为 (0≤B≤180)。而恰好在 s 时 f 分 m 秒时, 满足条件 A=2B 且 0≤f<60;0≤m<60, 请问 s,f,m 分别是多少。
请你找出一个 0 时 0 分 0 秒以外的解。
注意时针、分针、秒针都围绕中心匀速转动。
提交格式为三个由一个空格隔开的整数, 分别表示 s,f,m 。如 3 11 58 表示 3 点 11 分 58 秒。
答案提交
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为三个由一个空格隔开的整数, 在提交答案时只填写为三个由一个空格隔开的整数, 填写多余的内容将无法得分。
运行限制
最大运行时间：1s
最大运行内存: 512M
角度？我们把角度看为比例，比如30秒就是30/60=0.5,然后模拟就行了
#include <iostream> #include <cmath> using namespace std; int main(){ for(int h=0;h<=6;h++){ for(int fen=0;fen<60;fen++){ for(int miao=0;miao<60;miao++) { double miaoj=miao/60.00000; double fenj=fen/60.00000+(miao/60.00000)/60.000000; double hj= h/12.000000+(fen+miao/60.00000)/(12*60.00000); double a=fabs(fenj-hj); if(a>0.5) a=1-a; double b=fabs(fenj-miaoj); if(b>0.5) b=1-b; if(fabs(a-2*b)<=1e-8 && h!=0){ cout<<h<<' '<<fen<<' '<<miao; } } } } return 0; }
C:卡牌
问题描述
这天, 小明在整理他的卡牌。
他一共有 n 种卡牌, 第 i 种卡牌上印有正整数数 i(i∈[1,n]), 且第 i 种卡牌 现有 ai 张。
而如果有 n 张卡牌, 其中每种卡牌各一张, 那么这 n 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 m 张空白牌, 他可以在上面写上数 ii, 将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 ii 种牌最多手写 bi 张。
请问小明最多能凑出多少套牌?
输入格式
输入共 3 行, 第一行为两个正整数 n,m 。
第二行为 nn 个正整数 a1,a2,…,an 。
第三行为 nn 个正整数 b1,b2,…,bn 。
输出格式
一行, 一个整数表示答案。
样例输入
4 5 1 2 3 4 5 5 5 5
样例输出
3
样例说明
这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了3,3,3,4, 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。
评测用例规模与约定
对于 30% 的数据, 保证 0n≤2000;
对于 100% 的数据, 保证 ai,bi≤2n;m≤n2 。
运行限制
最大运行时间：1s
最大运行内存: 512M
暴力解法：
#include <iostream> using namespace std; int n,m; long long a[200005]; long long b[200005]; long long ans; int main(){ long long min=1e16; cin>>n>>m; for(int i=0;i<n;i++){ cin>>a[i]; if(min>a[i]){ min=a[i]; } } for(int i=0;i<n;i++){ cin>>b[i]; } ans=min; for(int i=0;i<n;i++){ a[i]=a[i]-min; } while(1){ for(int i=0;i<n;i++){ if(a[i]==0){ if(b[i]>0&&m>0) { m--; b[i]--; a[i]++; }else{ cout<<ans; return 0; } } if(i==n-1){ ans++; } a[i]--; } } cout<<ans; return 0; }
二分法：
#include<iostream> #include<algorithm> using namespace std; long long n,m,l,r; long long a[200005]; long long b[200005]; long long kk; bool check(long long x){ long long s = 0; for (int i = 0; i < n; i++) { //判断x套牌可以凑出来不 if (x - a[i] <= b[i]) { s += max(x - a[i],kk ); } else return false; } if (s <= m) return true; return false; } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ //输入，以最小值为左指针 cin>>a[i]; l = min(l, a[i]); } for(int i=0;i<n;i++){ cin>>b[i]; r=max(r,a[i]+b[i]); //以可以达到的最大数目为右指针 } int ans; while(l<=r){ long long mid=(l+r)/2; //二分查找可以凑成几套牌 if(check(mid)){ ans=mid; l=mid+1; }else{ r=mid-1; } } cout<<ans<<endl; return 0; }
D:最大数字
问题描述
给定一个正整数 N 。你可以对 N 的任意一位数字执行任意次以下 2 种操 作：
将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。
将该位数字减 1 。如果该位数字已经是 0 , 减 1 之后变成 9 。
你现在总共可以执行 1 号操作不超过 A 次, 2 号操作不超过 B 次。 请问你最大可以将 NN 变成多少?
输入格式
第一行包含 3 个整数: N,A,B 。
输出格式
一个整数代表答案。
样例输入
123 1 2
样例输出
933
样例说明
对百位数字执行 2 次 2 号操作, 对十位数字执行 1 次 1 号操作。
评测用例规模与约定
对于 30% 的数据, 0≤A,B≤10
对于 100% 的数据, 0≤A,B≤100
运行限制
最大运行时间：1s
最大运行内存: 512M
#include <iostream> #include <cmath> using namespace std; string n; long long ans; int a,b; void dfs(int x,long long an){ //a代表每次遍历的数 int t=n[x]-'0'; //位数转为int if(n[x]){ //防止为空 int c=min(a,9-t); a-=c; dfs(x+1,an*10+t+c); a+=c; if(b>t){ b=b-t-1; dfs(x+1,an*10+9); b=b+t+1; } }else{ ans=max(ans,an); } } int main(){ cin>>n>>a>>b; dfs(0,0); //0号字符 cout<<ans; return 0; }
