首页 > 其他分享 >河南工大2024新生周赛（7）----命题人 刘义 题解

河南工大2024新生周赛（7）----命题人 刘义 题解

时间：2024-12-10 22:10:23浏览次数：2  
标签：周赛 int 题解 s1 ---- ++ s2 using include

问题 A: 圆：

这是一个数学题，画图可得，4 个圆时，分割成 14 个区域，可以推导出结论：当圆为0个时，区域数为1个，当圆有x个的时候，区域数有x*x-x+2;

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
signed main(){
    int a,b;//a为圆的个数，b为区域数
    cin>>n;
    while(n--)
    {
        cin>>a;
        if(a==0)
        b=1;
        else
        b=a*a-a+2;
        cout<<b<<" ";
    }
    return 0;
}

问题 B: 旅人分宝：

这是一个经典的海盗分金问题，每个旅人只会选择一个对自己最有利的情况，并且要求50%以上的同意，所以当老大给一半的人每一个人一个金币，他们就会同意了。

#include<bits/stdc++.h>
using namespace std;
int t;
int n,x;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>x;
        if(x%2==0)
        {
            cout<<n-x/2+1<<endl;
        }
        else
        {
            cout<<n-x/2<<endl;
        }
    }
    return 0;
}

 

问题 C: A*B：

经典的高精度乘法：

#include <stdio.h>
#include <string.h>

//翻转函数
void reverse (int d[510], int len) {
    int temp, mid = len/2;
    for (int i = 0, j = len - 1; i < mid, j >= mid; i++, j--) {
        temp = d[i];
        d[i] = d[j];
        d[j] = temp;
    }
}

int main () {
    char s1[2005], s2[2005];
    int a[2005], b[2005], c[4010] = {0};
    scanf("%s", s1);
    scanf("%s", s2);
    int lena = strlen(s1);
    int lenb = strlen(s2);
    int lenc = lena + lenb;
    
    //将char的1转为int的1
    for (int i = 0; i < lena; i++) {
        a[i] = s1[i] - '0';
    }
    for (int i = 0; i < lenb; i++) {
        b[i] = s2[i] - '0';
    }
    
    reverse(a, lena);
    reverse(b, lenb);
    
    //核心代码
    for (int i = 0; i < lenb; i++) {
        for (int j = 0; j < lena; j++) {
            c[i+j] += b[i] * a[j];
            c[i+j+1] += c[i+j] / 10;
            c[i+j] = c[i+j] % 10;
        }
    }
    
    //处理前导0
    lenc = lenc - 1;
    while (c[lenc] == 0 && lenc >= 1) {
        lenc--;
    }
    
    //输出
    for (int i = lenc; i >= 0; i--) {
        printf("%d", c[i]);
    }
    
    return 0;
}

问题 D: 时间加速器：

由于数据比较大，所以可以用二分，用二分查找，可以定位到确定的时间，大大节省了时间。

#include<iostream>
#define int long long
using namespace std;
int n,a,b,x[600006];
bool check(int mid)//判断函数 
{
    int tot=0;
    for(int i=1;i<=n;i++)
    {
        if(x[i]<=mid*a)continue;
        else 
        {
            
            if((x[i]-mid*a)%b==0)tot+=(x[i]-mid*a)/b;
            else tot+=((x[i]-mid*a)/b+1);
        }
    }
    return tot<=mid;
}
signed main()
{
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)cin>>x[i];
    int l=0,r=1e9,mid;
    while(l<=r)//二分搜索 
    {
        mid=(l+r)/2;
        if(check(mid))r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}

问题 E: 切巧克力：

输入

4 2

4

5 6 1

输出

19

如果先切横的，结果就是1+2∗4+2∗5+2∗6=311+2∗4+2∗5+2∗6=31。

如果先切竖的，结果就是4+5+6+1∗4=194+5+6+1∗4=19。

显然先切竖的更优。

由此，可以得出一个结论：先切代价大的。

于是，思路就出来了。先把两个数组从大到小排序，然后两个数组挨个比较，较大的就在答案上加上这个代价（要乘上切了多少刀），再把指针往后挪一位，直到全部算完即可。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n, m;
int a[10005], b[10005];//横线和竖线的代价

int main()
{
    cin >> n >> m;
    int s1 = 1, s2 = 1;//s1和s2可以是a数组和b数组的指针，也可以是横纵分成的块数
    for (int i = 1; i <= n-1; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m - 1; i++)
    {
        cin >> b[i];
    }
    for(int i=1;i<=n-1;i++)
    {
        for(int j=1;j<=n-1-i;j++)
        {
            if(a[j]<a[j+1])
            {
                int t;
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
    for(int i=1;i<=m-1;i++)
    {
        for(int j=1;j<=m-1-i;j++)
        {
            if(b[j]<b[j+1])
            {
                int t;
                t=b[j];
                b[j]=b[j+1];
                b[j+1]=t;
            }
        }
    }
    long long ans = 0;
    for (int i = 2; i < n + m; i++)
    {
        if (a[s1] > b[s2])
            ans += s2 * a[s1++];//选择大的，这里s2表示块数，s1指针后移一位
        else
            ans += s1 * b[s2++];//同理，和上面相反
    }
    cout << ans << endl;
    return 0;
}

问题 F: 建房子：

构建一个01背包。

思路是将体力看做背包 将石子看做物品 然后就很自然地得出了本题的状态转移方程：

f[j]=max(f[j],f[j-w[i]]+v[i])

#include<stdio.h>
 #include<bits/stdc++.h>
 using namespace std;
 int n,V,c;
 int v[100001],l[100001];//v：石头体积 l；所需的体力 
 int dp[100001];
 int main()
 {
     scanf("%d %d %d",&V,&n,&c);
     int sum=0;
     for(int i=1;i<=n;i++)
     {
         scanf("%d %d",&v[i],&l[i]);
         sum+=v[i];
     }
     if(sum<V)//若石子总体积<V 
     {
         printf("Impossible");
         return 0;
     }
     for(int i=1;i<=n;i++)
     {
         for(int j=c;j>=l[i];j--)
         {
             dp[j]=max(dp[j],dp[j-l[i]]+v[i]);
         }
     }
     for(int i=0;i<=V;i++)//从小到大搜 第一个大于V的直接输出
     {
         if(dp[i]>=V)
         {
             printf("%d",c);
             return 0;
         }
     }
     printf("Impossible");
     return 0;
 }

 

问题 G: 命运之桥：

此题可以用排序做（高档一点的模拟）

核心思想：两个人相遇转身，相当于交换灵魂后继续走

最大值：最靠近端点两个人各自向对方走,时间较长的那个人的时间

最小值：所有人中走完桥最小值中的最大值

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int l, a[100001];
int main()
{
    int n;
    scanf("%d",&l);
    scanf("%d",&n);
    if (!n)
    {
        printf("0 0\n");
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + 1 + n); //从小到大排序（算最长时间时可能方便一些）
    int max_time, min_time;
    for (int i = 1; i <= n; i++)
    {
        min_time = max(min(a[i], l + 1 - a[i]), min_time);//最短时间就是所有人中走完桥最小值中的最大值 
    }
    max_time = max(l + 1 - a[1], a[n]);//最长时间就是最靠近端点两个人各自向对方走,
    printf("%d %d", min_time, max_time);
    return 0;
}

问题 H: 恶魔：

一个恶魔能杀掉的最大个数应该为两侧小于它血量的第一个的恶魔能杀掉的个数 + 1，先固定左侧，用单调栈维护一下该侧比当前恶魔更小的第一个位置，右侧同理

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
int a[N],l[N],r[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    stack<int>s;
    for(int i=1;i<=n;i++)//左边
    {
        while(!s.empty()&&a[s.top()]>a[i]) s.pop();
        if(!s.empty()) l[i]=l[s.top()]+1;
        else l[i]=0;
        s.push(i);
    }
    reverse(a+1,a+1+n);//反转一次，开始做右边
    stack<int>s1;
    for(int i=1;i<=n;i++)//右边
    {
        while(!s1.empty()&&a[s1.top()]>a[i]) s1.pop();
        if(!s1.empty()) r[i]=r[s1.top()]+1;
        else r[i]=0;
        s1.push(i);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<l[i]+r[n-i+1]<<" ";
    }
    return 0;
}

 

标签：周赛,int,题解,s1,----,++,s2,using,include
From： https://www.cnblogs.com/hautacm/p/18598057

相关文章

  • MyBatis-Plus主键生成策略
    MyBatis-Plus提供了内置的主键生成策略，可以在不改动业务代码的前提下自动生成主键值，而无需依赖数据库的自增主键。以下是解决方法和配置方式：(1)IdType.ASSIGN_ID（默认雪花算法）使用MyBatis-Plus提供的雪花算法生成全局唯一主键。此策略适用于Long或String类型的主键。@Ta......
  • 【推荐算法】单目标精排模型——FiBiNET
    keyword:学术论文Motivation：传统的Embedding&MLP算法是通过内积和Hadamardproduct实现特征交互的，这篇文章的作者提出了采用SENET实现动态学习特征的重要性；作者认为简单的内积和Hadamardproduct无法有效对稀疏特征进行特征交互，因此提出bilinearfunction实现特征交互，提出了FI......
  • UIViewController的view在有navBar和tabBar影响下布局区域的问题
    转自:https://www.cnblogs.com/bridge-wuxl/p/10790888.html影响View布局区域的有以下三个属性:self.edgesForExtendedLayout(影响View布局区域的主要属性)self.navigationController.navigationBar.translucent(navigationBar是否半透明)self.tabBarController.tabBa......
  • 【Linux】————网络基础相关内容
                                 作者主页：   作者主页                           本篇博客专栏：Linux                ......
  • [一行代码搞定！如何快速初始化多种语言模型]
    #一行代码搞定！如何快速初始化多种语言模型##引言在开发语言模型应用时，许多场景需要允许终端用户指定希望应用所使用的模型提供商和模型版本。为了应对这种需求，我们需要编写逻辑来根据用户配置初始化不同的聊天模型。然而，通过使用`init_chat_model()`方法，我们可以轻......
  • 利用Eden AI在Python中自动化多功能AI任务
    #利用EdenAI在Python中自动化多功能AI任务##引言在现代AI应用中，集成多种AI能力至关重要。EdenAI通过将顶尖AI服务提供商集成到单一平台上，极大地简化了AI功能的部署。本篇文章将介绍如何使用EdenAI工具组合来创建一个具备多种功能的Agent，从而开启无限AI可能性。##......
  • 【NVIDIA orin nx 安装ultralytics yolov11】
    注意：不同用户安装的python可能会在不同的路径，因此不同的pip管理会导致安装的torch和torchvision会在不同的路径下记得区分用户来运行yolo一、确认系统JetPack版本此处使用5.1.11、查看JetPack版本jtop二、安装ultralytics、pytorch、torchvision、onnxruntime-......
  • 7-4 字符串中最长的连续出现的字符分数
    求一个字符串中最长的连续出现的字符，输出该字符及其出现次数，字符串中无空白字符（空格、回车和tab），如果这样的字符不止一个，则输出第一个。输入格式:第一行输入整数N，表示测试数据的组数。每组数据占一行，包含一个不含空白字符的字符串，字符串长度不超过200。输出格式:共一行，......
  • 7-10 孔融分梨(函数实现)分数 10
    孔融没有兄弟姐妹，到了周末，就找堂兄孔明、堂姐孔茹、堂弟孔伟等7个堂兄妹来到家里玩。孔融妈妈买了8个梨给孩子们吃，结果小黄狗桐桐淘气叼走了一个，大花猫鑫鑫偷偷藏了一个。孔融抢过剩下的6个梨，妈妈止住他，说他要和大家平分吃。孔融不高兴，说8个人怎么分6个梨？妈妈说可以用分数解决......
  • 梳理你的思路(从OOP到架构设计)_基本OOP知识02
    目录1、<基类/子类>结构用途：表达继承2、<基类/子类>结构用途：表达组合1、<基类/子类>结构用途：表达继承对众多对象加以分门别类，就可形成一个类继承体系。例如对学校人员加以分门别类，而得出类继承体系，如下图：软件代码的表达是： Step-1.定义基类。如：classPerson......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99