首页 > 其他分享 >题解:牛客小白月赛102(A - C)

题解:牛客小白月赛102(A - C)

时间:2024-10-12 19:36:49浏览次数:7  
标签:std int 题解 sum cin solve 小白月赛 102 define

A 序列中的排列

题意:

每次给你两个正整数 \(n,k\) ,并给你一段长度为 \(n\) 的序列。(所有输入均为小于等于100的正整数)
问:原序列中是否存在子序列,使得这个子序列是 \(k\) 的排列
子序列:某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列。
排列:一个 \(k\) 的排列是一个长度为 \(k\) 的整数序列,其中包含了从 \(1\) 到 \(k\) 的每个数字,每个数字仅出现一次。

做法:

只要找到序列中是否存在 \(1 \sim k\) 的每一个数即可
可以使用计数数组(数据范围也不大)

代码:

#include <iostream>
#include <algorithm>
#include <map>

void solve() {
    int max = -1;
    int n,m,num,cnt = 0;
    std::cin >> n >> m;
    std::map<int,int> mp;
    for(int i = 0 ; i < n ; i ++) {
        std::cin >> num;
        if(num <= m && !mp.count(num)) cnt ++,max = std::max(max,num);;
        mp[num] ++;
    }
    std::cout << (max == m && cnt == m ? "YES\n" : "NO\n");
}

signed main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--) solve();
    return 0;
}

B 连分数

题意:

(有点抽象,我直接放原文吧)

给定 \(a\) ,定义

\[x = a + \frac{1}{a+\frac{1}{a+\frac{1}{a+\dots}}} \]

求 \(x\) 的值。

形式上说,设 \(f(n) = \left\{\begin{matrix} a & n=1\\ a+\frac {1}{f(n-1)} & n>1\end{matrix}\right.\) , \(x=\lim_{n \to + \infty}f(n)\),求 \(x\) 的值。

( \(a\) 是浮点数且是正实数,不超过 \(10^5\), \(x\) 精确到小数点后 \(9\) 位)

做法1及其代码:

大家都学过极限,了解了极限的思想,那这题我们就好做了
首先,当 \(n\) 趋近于正无穷时,\(f(n)\) 一定趋近于某一个数,这样子才有一个解
正因如此,假设 \(f(n)\) 趋近于某一个数成立,那我们可以把 \(f(n)\) 和 \(f(n-1)\) 视作等价的(之间的差值忽略不计)

于是我们可以列出以下式子

\[x = a + \frac{1}{x} \]

移项得(易证 \(x\) 不等于 \(0\)):

\[x^2 - ax - 1 = 0 \]

于是我们只要找出这个 \(x\) 的近似解即可

如果我们会求根公式的话,就可以求根公式直接上了

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f

void solve() {
    double a;
    std::cin >> a;
    printf("%.10f\n",(a +  sqrt(a*a + 4)) / 2);
}

signed main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--) solve();
    return 0;
}

如果不会求根公式的话,也没关系。
不难看出,\(x\) 的值随着 \(a\) 的值递增而递增
于是我们可以进行实数二分
最小值设置个 \(1\) 就好了,最大值可以设置 \(100001\)(最后一个样例告诉我们不会超过这个数)

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f

const double eps = 1e-9;

void solve() {
    double a;
    std::cin >> a;
    double l = 1,r = 1e5 + 1;
    while(fabs(l-r) >= eps) {
        double mid = (l + r) / 2;
        if(mid * mid - a * mid - 1 >= 0) r = mid;
        else l = mid;
    }
    printf("%.10f\n",l);
}

signed main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--) solve();
    return 0;
}

做法2及其代码:

如果说,我没想到上面的思想,能不能模拟?
可以!
但是要做一点小运算
举个例子:

因为是第一个是 \(a\)
第二个不就是 \(a + \frac{1}{a}\) 嘛
你手动模拟下就发现
每一次的值都是:前面得到的分数分子分母互换,然后分子加上分母的 \(a\) 倍

ok,然后我们直接写就可以了

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f

const double eps = 1e-9;

void solve() {
    double a;
    std::cin >> a;
    double fz = a,fm = 1,c = fz / fm;
    std::swap(fz,fm);
    fz += fm*a;
    while(fabs(c - fz / fm) > 1e-10) {
        c = fz / fm;
        std::swap(fz,fm);
        fz += fm*a;
    }
    printf("%.10f\n",fz/fm);
}

signed main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--) solve();
    return 0;
}

C sum

题意:

给你 \(n,sum\) 和序列 \(a\) ,
已知有 \(n\) 个数 \(a_i\) ,你可以进行若干次修改操作,每一次操作任意修改一个数的值为 \(x(-10^4 \le x \le 10^4)\)
问最少多少次操作使得这 \(n\) 个数的和为 \(sum\) 。

做法:

很经典的贪心,总和比 \(sum\) 大就把最大的尽可能变小,总和比 \(sum\) 小就把最小的尽可能变大,直到跨越 \(sum\) 为止。

代码:

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
#define all(x) x.begin(),x.end()

void solve() {
    int n,m,sum = 0,ans = 0;
    std::cin >> n >> m;
    std::vector<int> a(n);
    for(int i = 0 ; i < n ; i ++) std::cin >> a[i],sum += a[i];
    std::sort(all(a));
    if(sum == m) std::cout << 0 << "\n";
    else if(sum > m) {
        for(int i = n-1 ; i >= 0 ; i --) {
            ans ++;
            if(sum - (a[i] + 1e4) <= m) break;
            sum -= (a[i] + 1e4);
        }
        std::cout << ans << "\n";
    } else {
        for(int i = 0 ; i < n ; i ++) {
            ans ++;
            if(sum + (1e4 - a[i]) >= m) break;
            sum += (1e4 - a[i]);
        }
        std::cout << ans << "\n";
    }
}

signed main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--) solve();
    return 0;
}

标签:std,int,题解,sum,cin,solve,小白月赛,102,define
From: https://www.cnblogs.com/jiejiejiang2004/p/18461306

相关文章

  • BUUCTF_MISC题解析(7)
    7.wireshark下载文件发现里面是一个pcap格式的文件。而pcap格式就是网络分析工具保存的网络数据包,是捕获的从网卡发送或者接收的每一个数据包的离线网络流量。 在wireshark官网上下载wireshark,wireshark是网络封包分析工具。将文件用wireshark打开,发现有三个部分,上半部分绿......
  • P9020 [USACO23JAN] Mana Collection P 题解
    P9020[USACO23JAN]ManaCollectionP题解首先考虑对于长为\(d\les\)的最优路径,最优的方法一定是先在起点等\(s-d\)秒再走以确保收集到的最大。\(n\le18\)我们显然考虑状压dp。考虑最大法力值难以计算,正难则反,考虑使未被选择的最小。于是我们设\(dp_{sta,i}\)表示状......
  • 洛谷P1102 A-B数对
    A-B数对题目背景出题是一件痛苦的事情!相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的A+BProblem,改用A-B了哈哈!题目描述给出一串正整数数列以及一个正整数\(C\),要求计算出所有满足\(A-B=C\)的数对的个数(不同位置的数字一样的数对算不同的数对)。输入格......
  • Project Euler 728 题解
    Problem728CircleofCoins得到Wallbreaker5th的指导。\(F\)就是求这些环上区间(记为\(A\))的异或线性基大小。令\(A'_i\getsA_i\oplusA_{i+1}\)。现在求\(\langA'\rang\)的线性基。如果可能从全黑和全白间转换,那么\(\dim\langA'\rang=\langA\rang-1\),否则不\(-1......
  • [ABC227H] Eat Them All 题解
    唐唐题。思路容易发现,我们只要知道了一条边总共经过了多少次(不计方向),我们就可以跑欧拉回路。自己手玩一下,发现只要枚举四个变量,其他的都可以用方程解出来。求完之后,还需要判一下联通性。实际效率是很快的,远远跑不满。时间复杂度:\(O(a_i^4)\)。Code#include<bits/stdc++.h......
  • [ABC222H] Beautiful Binary Tree 题解
    第一次写拉格朗日反演。思路考虑如何操作。发现出根节点外有\(n-1\)个点是一。由于我们只能操作\(n-1\)次,相当于每一次操作必须把两个一合并。一个点最多往上跳两层,所以要求它的父亲或者爷爷是一。考虑设\(f_i\)表示当前节点为一并且整个子树总和为\(i\)的方案数,\(g......
  • 题解 QOJ5048【[ECFinal19K] All Pair Maximum Flow】
    题目描述给你一个\(n\)个点\(m\)条边的图,它是平面上的正\(n\)边形和一些对角线,节点按逆时针方向编号为\(1\)到\(n\)。对角线只可能在节点处相交。每条边有一个容量,求每个点对之间的最大流的和。\(n\leq200000,m\leq400000\)。solution做法每次找出边权最小的边\(......
  • 蓝桥杯真题 穿越时空之门(第十五届蓝桥杯省赛PythonB组A题) c++题解
    问题如下(附链接):穿越时空之门题解代码如下:#include<iostream>usingnamespacestd;intx1(inti){inta=0;while(i){a+=i%2;i/=2;}returna;}intx2(inti){intb=0;while(i){b+=i%4;i/=4;}returnb;}intmain()......
  • 线段树分治略解&杂题解析
    可能做到好题之后会再更新吧。总叙线段树与离线询问结合技巧又被称为线段树分治。使用线段树分治维护的信息通常会在某一个时间段内出现,要求在离线的前提下回答某一个时刻的信息并,则可以考虑使用线段树分治的技巧。以下是线段树分治的基本模板:change将信息按时间段覆盖在线......
  • [USACO23FEB] Hungry Cow P 题解
    T7[USACO23FEB]HungryCowP这题就比较正常了,蓝紫之间的水平。我们发现Bessie能活\(10^{14}\)天(,导致我们不好直接按照值域来维护。发现给某一天送干草,影响到的是后面很多天,这是个区间问题。所以考虑动态开点线段树。线段树的每个节点维护\(\mathit{ans},\mathit{cnt},\ma......