题解 | # JYUACM新生训练周赛1#

小红的签到题

https://ac.nowcoder.com/acm/contest/98442/A

小红的签到题

思路

输出 即可。

复杂度

时间复杂度 ,空间复杂度

代码实现

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<c/a;
}

异或故事

思路

如果 二进制下表示有两个及以上的 ,可以把其中的一个 拿出来作为 ,剩下的部分作为 。 比如 二进制表示下为 ,可以把 取出来作为 , 作为 ,当然, 也是可以的。

否则,这个数就是个二次幂,如果是 的话,可以把 作为答案,不然就是 这样大于 的二次幂,可以将 分别作为

综上,其实总存在一个二次幂 可以作为答案的一项, 做为答案的另一项。

(异或的交换律:若 ,可以得到

复杂度

时间复杂度 O(1)$

代码实现

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    cin>>T;
    int r = 1e9;
    while(T--){
        int x;
        cin>>x;
        for(int i=0;i<32;i++){
            int a = 1<<i;
            int b = x^a;
            if(a<=r && b<=r && a>0 && b>0){
                cout<<a<<' '<<b<<'\n';
                break;
            }
        }
    }
}

石子合并

思路

堆石子,每次选择减少一堆,最后剩下一堆,会有 次选择。

因为每次都是删取较小的数,所以最后一定剩下最大值。

有一个想法是不如每次都选择最大值和最大值相邻的数,直到选完 次,这样的做法是可以使得最后的价值最大的。

因为每次选择都会累加两个选择的数到价值里面,所以如果除了一个最大值外的总和为 ,最大值为 ,那么按上面的想法得到的价值为

如果不按上面的想法进行选择,那么至少会有一次,选择的两个数 都不是最大值,会剩下 中的较大值 ,然后 可能与一个数 选择在一起,累加的总和为

如果按上面的想法,这两个数是分别与最大值 选择了一次,累加的总和为

显然,,不按上面的想法进行选择,是不会让价值变得更大的。

(这里只是讨论了不按上面的想法进行选择,改变了原来两次选择的情况,可能还有改变到 次选择的情况,但是把改变前累加的总和与改变后累加的总和进行比较,可以发现总是后者总是不超过前者的)

复杂度

时间复杂度 ,空间复杂度

代码实现

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    long long sum = 0,ma = 0;
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;
        sum += x;
        ma = max(ma,x);
    }
    long long ans = (sum-ma) + (n-1)*ma;
    cout<<ans;
}

小红的口罩

思路

因为每个口罩使用后不舒适度都会翻倍,翻倍到大于 时,这个口罩显然一定不能使用,所以每个口罩的使用次数是 级别的,换句话说,每个口罩不舒适度的变化序列,有效的范围是 级别的。

可以将所有口罩变化序列有效的部分(不大于 的部分)都放到一起,然后把所有的可能的不舒适度从小到大排序,从最小的不舒适度开始累加(因为累加小的可以给后面累加的有更多空间,使得累加的数量尽可能大),直到累加到超过 为止。

复杂度

时间复杂度 ,空间复杂度

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    int n,k;
    cin>>n>>k;
    vector<int>all;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        while(x<=k){
            all.push_back(x);
            x *= 2;
        }
    }
    sort(all.begin(),all.end());
    
    int cnt = 0,sum = 0;
    for(int x:all){
        if(sum+x>k) break;
        cnt++;
        sum+=x;
    }
    cout<<cnt;
}
全部评论

相关推荐

码农索隆:有点耳熟,你们是我教过最差的一届
点赞 评论 收藏
分享
今天 13:16
湖南工学院 Java
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 12:31
以前小时候我最痛恨出轨、偷情的人,无论男女,为什么会出轨?现在我成了自己最讨厌的人,没想到分享的东西在牛客会被这么多人看,大家的评价都很中肯,我也认同,想过一一回复,但我还是收声了,我想我应该说说这件事,这件事一直压在我心里,是个很大的心结,上面说了人为什么出轨,我大概能明白了。我们大一下半年开始恋爱,开始恋爱,我给出了我铭记3年的承诺,我对她好一辈子,我永远不会背叛,我责任心太重,我觉得跟了我,我就要照顾她一辈子,我们在一起3年我都没有碰过她,她说往东我就往东,她说什么我做什么,她要我干什么,我就干什么!在学校很美好,中途也出过一些小插曲,比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了,我...
牛客刘北:两个缺爱的人是没有办法好好在一起的,但世界上哪有什么是非对错?你后悔你们在一起了,但是刚刚在一起的美好也是真的呀,因为其他人的出现,你开始想要了最开始的自己,你的确对不起自己,21岁的你望高物远,你完全可以不谈恋爱,去过你想要的生活,你向往自由,在一起之后,你要想的不是一个人,而是两个人,你不是变心了,就像你说的,你受够了,你不想包容了,冷静几天是你最优的选择,爱人先爱己。
社会教会你的第一课
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务