当前位置：首页 > article >正文

笔试强训day15

article 2024/9/21 1:48:07

平方数

牛妹是一个喜欢完全平方数的女孩子。
牛妹每次看到一个数 x，都想求出离 x 最近的完全平方数 y。
每次手算太麻烦，所以牛妹希望你能写个程序帮她解决这个问题。
形式化地讲，你需要求出一个正整数 y，满足 y 可以表示成 a2a^2a2（a 是正整数），使得 |x-y| 的值最小。可以证明这样的 y 是唯一的。

输入描述:

一行，一个整数 x (1≤x≤1012)x\ (1\le x\le 10^{12})x (1≤x≤1012)，表示牛妹询问的数。

输出描述:

一行，一个整数 y，表示离 x 最近的完全平方数 y。

#include <iostream>
#include <cmath>
#define int long long
using namespace std;

signed main()
{
    int n;
    cin>>n;
    int x = sqrt(n);
    int a = x*x,b = (x+1)*(x+1);
    cout<<(n-a<b-n?a:b)<<endl;
    return 0;
}

dd当上了宣传委员，开始组织迎新晚会，已知班里有nnn个同学，每个同学有且仅有一个擅长的声部，把同学们分成恰好mmm组，为了不搞砸节目，每一组里的同学都必须擅长同一个声部，当然，不同组同学擅长同一个声部的情况是可以出现的，毕竟一个声部也可以分成好几个part进行表演，但是他不希望出现任何一组的人过多，否则可能会导致场地分配不协调，也就是说，她希望人数最多的小组的人尽可能少，除此之外，对组内人员分配没有其他要求，她希望你告诉她，这个值是多少，如果无法顺利安排，请输出-1

输入描述:

第一行两个数个数n,m(1≤m≤n≤100000)表示人数
接下来一行n个数,a[i](1≤a[i]≤n)表示第i个学生的擅长声部

输出描述:

输出一个数，表示人数最多的小组的人数

//暴力做法

#include <bits/stdc++.h>

using namespace std;
int n,m;
unordered_map<int,int>hx;

bool check(int x)
{
    int g = 0;
    for(auto&[a,b]:hx)
    {
        g += b/x + (b%x==0?0:1);
    }
    return g<=m;
}
int main()
{
    cin>>n>>m;
    int h = 0;
    for(int i = 0;i<n;++i)
    {
        int x;
        cin>>x;
        h = max(h,++hx[x]);
    }
    if(m<hx.size())
    {
        cout<<-1;
    }
    else{
        for(int i = 1;i<=h;++i)
        {
            if(check(i))
            {
                cout<<i;
                break;
            }
        }
    }
    return 0;
}

//二分做法

#include <bits/stdc++.h>

using namespace std;
int n,m;
unordered_map<int,int>hx;

bool check(int x)
{
    int g = 0;
    for(auto&[a,b]:hx)
    {
        g += b/x + (b%x==0?0:1);
    }
    return g<=m;
}
int main()
{
    cin>>n>>m;
    int h = 0;
    for(int i = 0;i<n;++i)
    {
        int x;
        cin>>x;
        h = max(h,++hx[x]);
    }
    if(m<hx.size())
    {
        cout<<-1;
    }
    else{
        int l = 1,r = h;
        while(l<r)
        {
            int mid = l+r>>1;
            if(check(mid))r = mid;
            else l = mid+1;
        }
        cout<<l;
    }
    return 0;
}

拓扑排序

给定一个包含�n个点�m条边的有向无环图，求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序，输出−1−1。

输入描述：

第一行输入两个整数�,�n,m ( 1≤�,�≤2⋅1051≤n,m≤2⋅105)，表示点的个数和边的条数。
接下来的�m行，每行输入两个整数��,��u**i,v**i (1≤�,�≤�1≤u,v≤n)，表示��u**i到��v**i之间有一条有向边。

输出描述：

若图存在拓扑序，输出一行�n个整数，表示拓扑序。否则输出−1−1。

#include <bits/stdc++.h>

using namespace std;
int n, m;
const int N = 2e5 + 10;
vector<vector<int> >edges(N);
int in[N];
queue<int>q;
vector<int>ans;

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        in[v]++;
    }
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        ans.push_back(t);
        for (int& x : edges[t]) {
            if (--in[x] == 0) {
                q.push(x);
            }
        }
    }
    if (ans.size() == n) {
        for (int i = 0; i < n - 1; i++) {
            cout << ans[i] << " ";
        }
        cout << ans[n - 1]; // 测评会考虑最后⼀个元素的空格
    } else {
        cout << -1 << endl;
    }
    return 0;
}