01 质数
质数
题目描述
给定一个正整数N,请你输出N以内(不包含N)的质数以及质数的个数。
输入描述
输入一行,包含一个正整数N。1≤N≤10^3
输出描述
共两行。
第1行包含若干个素数,每两个素数之间用一个空格隔开,素数从小到大输出。
第2行包含一个整数,表示N以内质数的个数。
输入输出样例
示例
输入
10
输出
2 3 5 7
4
#include
#include
using namespace std;
bool isprime(int n){
if(n==2) return true;
else{
for(int i=2;isqrt(n);i++){
if(n%i==0)
return false;
}
}
return true;
}
int main(){
int x,cnt=0; cin>>x;
for(int i=2;ix;i++){
if(isprime(i)){
couti" ";
cnt++;
}
}
cout"n"cnt;
return 0;
}
02 字符统计
字符统计
问题描述
给定一个只包含大写字母的字符出S,请你输出其中出现次数最多的字符。
如果有多个字母均出现了最多次,按字母表顺序依次输出所有这些字母。
输入格式
一个只包含大写字母的字等串S.
输出格式
若干个大写字母,代表答案。
样例输入
BABBACAC
样例输出
AB
#include
using namespace std;
int main(){
string s;
getline(cin,s);
int b[10000]={0};
for(int i=0;is.length();i++){
b[s[i]]++;
}
int max=0;
for(int i='A';i'z';i++){
if(b[i]>max){
max=b[i];
}
}
for(int i='A';i'z';i++){
if(b[i]==max){
coutchar(i);
}}
return 0;
}
03 大乘积
问题描述
小蓝有30个数,分别为:99,22,51,63,72,61,20,88,40,21,63,30,
11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。
小蓝可以在这些数中取出两个序号不同的数,共有3029/2=435种取法。
请问这435种取法中,有多少种取法取出的两个数的乘积大于等于2022。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为
一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
#include
#include
int main(int argc, char *argv[])
{
int i,k,sum=0;
int a[30]={99,22,51,63,72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7,
53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77};
for(i=0;i30;i++){
for(k=i+1;k30;k++){
if(a[i]*a[k]>=2022){
sum++;
}
}
}
printf("%d",sum);
return 0;
}
04 组合数问题
输入输出样例
示例
输入
1 2
3 3
输出
1
#include
using namespace std;
typedef long long ll;
const ll MOD = 1E9 +7;
ll t, k;
ll n, m, ans, len;
ll a[70], b[70];
ll dp[70][4];
ll ans0(ll x, ll y) {
// if (x
if (x y) return (x % MOD + 2) * (x % MOD + 1) / 2 % MOD;
x %= MOD, y %= MOD;
return ((y + 2) * (y + 1) / 2 % MOD + (x - y) * (y + 1) % MOD) % MOD;
}
ll ans1(ll x, ll y) {
// if (x
return min(x, y) + 1;
}
ll ans2(ll x, ll y) {
// if (x
return max(x - y + 1, 0LL);
}
int main() {
cin >> t >> k;
while (t--) {
cin >> n >> m;
if (m > n) m = n;
ans = ans0(n, m);
memset(b, 0, sizeof b);
for (len = 0; n; len++, n /= k) a[len] = n % k;
for (int i = 0; m; i++, m /= k) b[i] = m % k;
n = len;
// memset(dp, 0, sizeof dp);
dp[n][0] = dp[n][1] = dp[n][2] = 0;
dp[n][3] = 1;
for (int i = n - 1; i >= 0; i--) {
dp[i][0] = dp[i + 1][0] * ans0(k - 1, k - 1);
dp[i][0] += dp[i + 1][1] * ans0(a[i] - 1, k - 1) + dp[i + 1][2] * ans0(k - 1,b[i] - 1);
dp[i][0] += dp[i + 1][3] * ans0(a[i] - 1, b[i] - 1);
dp[i][1] = dp[i + 1][1] * ans1(a[i], k - 1) + dp[i + 1][3] * ans1(a[i], b[i] - 1);
dp[i][2] = dp[i + 1][2] * ans2(k - 1, b[i]) + dp[i + 1][3] * ans2(a[i] - 1, b[i]);
dp[i][3] = ((a[i] >= b[i]) && dp[i + 1][3]);
dp[i][0] %= MOD; dp[i][1] %= MOD;
服务器托管网 dp[i][2] %= MOD; dp[i][3] %= MOD;
}
ans -= (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3]) % MOD;
ans = (ans % MOD + MOD) % MOD;
cout ans endl;
}
return 0;
}
05 糖果
输入输出样例
示例
输入
1 2
3 3
输出
1
#include
using namespace std;
int dp[(120)+1];//dp数组
int n,m,k,a[101];
//状态压缩动态规划(简称状压dp)是另一类非常典型的动态规划,通常使用在NP问题的小规模求解中,虽然是指数级别的复杂度
//该算法主要以二进制的方式 思维
//入门:https://www.cnblogs.com/ibilllee/p/7651971.html https://zhuanlan.zhihu.com/p/131585177
int main()
{
fill(dp,dp+(120)+1,0xffff);//初始化 dp数组
cin >> n >> m >> k;//输入
int c[m];//占位数组 有则是1 无为0
fill(c,c+m,0);//用来鉴定是否能全尝到
bool NUL=false;//用来鉴定是否能全尝到
for(int i=1;in;++i)//有n包
{
int x=0,y;
for(int j=1;jk;++j)//每包中的 类型
{
//比如有5类糖果即5位 二进制0表示没有 1表示有 如果某一组是有 1(1
//然后这一组进行 ‘|’ 或运算 然后就可以表示这一组就是 01101 然后这个数字十进制13就可以表示这个 这一包的种类
cin >> y;
y--;//上面有过程 解释
x|=(1y);//或运算是在(十进制也是在二进制中)二进制中 0|1=1 0|0=0 1|1=1 1
c[y]++; //先检验糖果是否全 只和鉴定是否能全得到有关
}
a[i]=x;//将每一包所有的种类给它
}
for(int i=0;im;i++)//用来鉴定是否能全尝到
if(!c[i])NUL=true;//用来鉴定是否能全尝到
if(NUL)cout "-1";//糖果种类不全打印-1
else{
dp[0]=0;//初始化 当然下面这个肯定从这里开始的
for(int i=1;in;i++)
{
// (1 length(1 (1
for(int j=(1m)-1;j>=0;--j)//
dp[j|a[i]]=min(dp[j|a[i]],dp[j]+1);//从第一包开始
/** 解释::
dp[j|a[i]] 表示在所有糖果类中的 j|a[i] 类中的 最优解
① 当j=0 时 j|a[i]=a[i] dp[a[i]]=1;
② 当j=a[i1] 时 dp[[j|a[i2]] 就是 a[i1]与a[i2] 并集的 最优解
③ 进一步向上迭代 直至完全
④ 当计算出j|a[i]=(1)n 时(进制全为一 ) 即包含所有种类 这个就是最终解
*/
}
cout dp[(1m)-1];//打印最终解
}
return 0;
}
06 外卖店优先级
输出描述
输出一个整数代表答案。
输入输出样例
示例
输入
2 6 6
11
5 2
3 1
6 2
2 1
6 2
输出
1
样例解释:
6时刻时,1号店优先级降到3,被移除出优先缓存;2号店优先级升到6,加入优先缓存。所以是有1家店(2号)在优先缓存中。
#include
#include
using namespace std;
int main()
{
int num,m,t;cin>>num>>m>>t;
pairint,int> ti[m];//订单列表
int p[num]={0};//存优先级
int flag[num]={0};//1表示在优先缓存,0表示不在
int last[num]={0};//存对应id外卖店的上一次接订单时间
int cnt=0;
for(int i=0;im;i++)cin>>ti[i].first>>ti[i].second;//读取订单列表
sort(ti,ti+m);//按时间升序排列订单
for(int i=0;im;i++)//遍历订单列表
{
int tt=ti[i].first,id=ti[i].second-1;
if(tt!=last[id])//该外卖店在下一个时刻接到了订单
p[id]-=tt-last[id]-1;
if(p[id]0)p[id]=0;
if(p[id]3)flag[id]=0;
p[id]+=2;
if(p[id]>5)flag[id]=1;
last[id]=tt;
}
for(int i=0;inum;i++)
{
p[i]-=t-last[i];
if(p[i]3)flag[i]=0;
}
int ans=0;
for(int i=0;inum;i++)if(flag[i]==1)ans++;
coutans;
return 0;
}
07 完全二叉树的权值
输出描述
输出一个整数代表答案。
输入输出样例
示例
输入
7
1 6 5 4 3 2 1
输出
2
#include
using namespace std;
int sum[10008] = {0};
int main()
{
int n;
int w;
int ans;
int maxn = 0;
cin >> n;
for(int i = 1; i n; i++)
{
cin >> w;
int d = ceil(log(i+1)/log(2));
sum[d] += w;
}
for(int i = 1; i 10008; i++)
{
if(sum[i] > maxn)
服务器托管网 {
maxn = sum[i];
ans = i;
}
}
cout ans;
return 0;
}
08 修改数组
输入输出样例
示例
输入
5
2 1 1 3 4
输出
2 1 3 4 5
#include
using namespace std;
int main()
{
int n;
int a[100005]={0}, b[1000005] = { 0 };
cin >> n;
for (int i = 0; i n; i++)
{
cin >> a[i];
while (b[a[i]] != 0)
{
b[a[i]]++;
a[i]+=(b[a[i]]-1);
}
b[a[i]]++;
cout a[i] ' ';
}
return 0;
}
09 小明的背包1
输入输出样例
示例1
输入
5 20
1 6
2 5
3 8
5 15
3 3
输出
37
#include
#include
int val[1001],v[1001],dp[1001][1001]={0};//dp第一个为物品下标,第二个为背包体积,值为价值(确定dp数组以及下标的含义)
int n,V;
int max(int a,int b)
{
return a>b?a:b;
}
void backpack()
{
for(int i=v[0];iV;i++)
{
dp[0][i]=val[0];// 当背包容量大于物品0的容量时,将物品0放入到背包中
}
for(int i=1;in;i++)
{
for(int j=1;jV;j++)//先遍历物品,再遍历体积
{
if(jv[i])//当前背包体积小于物品体积
dp[i][j]=dp[i-1][j];//不放,价值不变,i-1相当于没放物品i之前的
else
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+val[i]);//比较放之前和放之后的价值
//放之后的价值=放之前的价值+物品i的价值
//j-v[i]表示放了物品i,还剩下j-v[i]的容量可以放其他物品
//dp[i-1][j-v[i]],表示不放物品i时,背包的容量也减去物品i的容量之后,背包所能放的最大价值
}
}
}
}
int main()
{
scanf("%d%d",&n,&V);
for(int i=0;in;i++)scanf("%d %d",&v[i],&val[i]);
backpack();
printf("%d",dp[n][V]);
return 0;
}
10 求阶乘
问题描述
满足N!的末尾恰好有K个0的最小的N是多少?
如果这样的N不存在输出-1。
输入格式
一个整数K。
输出格式
一个整数代表答案。
样例输入
2
样例输出
10
#include
#include
#include
//末尾有几个0取决于从1到N的因子中2和5的组合个数
//因为5的倍数个数比2少,所以只要计算5的倍数个数
//满足5^p
//此函数用于计算因子5的个数
long long int js( long long int a )
{
long long int ans = 0;
while ( a > 0 )
{
ans += a / 5; //因为遇见 5^2要加两个0 5^3要加三个零 以此类推
a/=5;
}
return ans;
}
int main(int argc, char *argv[])
{
long long int k;
scanf("%lld",&k);
long long int l = 1, r = pow(2,63)-1;//pow(2,63)-1表示N的最大值
//从1到N的阶乘中5的倍数个数计算出来,再用与k比较的二分法查找出最小的N!
while(lr)
{
long long int mid = l + ( r - l ) / 2;
if ( js(mid) k ) l = mid + 1;
else r = mid;
}
long long int ans = js(l);
if ( ans == k ) printf("%lld",l);//如果找到打印,否则打印-1;
else printf("%d",-1);
// 请在此输入您的代码
return 0;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: LeetCode LCR 179. 查找总价格为目标值的两个商品
和为 s 的两个数字 题目链接 LCR 179. 查找总价格为目标值的两个商品 购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品服务器托管网的价格总和刚好是 target。若存在多种情况,返回任一结果即可。 示例 1: 输入:pric…