牛客-模拟

模拟

1

c++ 最大堆最小堆

c++STL默认的priority_queue是将优先级最大的放在队列最前面。

如何实现最小堆

priority_queue<int> pq; // 
pq.push( -1 * v1) ; //
pq.push( -1 * v2) ; //
pq.push( -1 * v3) ; // 分别是插入v1, v2, v3变量的相反数，那么pq其实也就变相成为了最小堆，只是每次从pq取值后，要再次乘以-1即可

struct Node {
    int value;
    int idx;
    Node (int v, int i): value(v), idx(i) {}
//  friend bool operator < (const struct Node &n1, const struct Node &n2) ;
    friend bool operator > (const struct Node &n1, const struct Node &n2) ;
}; 

inline bool operator > (const struct Node &n1, const struct Node &n2) {
    return n1.value > n2.value;
}

priority_queue<Node, vector<Node>, greater<Node> > pq; // 此时greater会调用 > 方法来确认Node的顺序，此时pq是最小堆

A-操作序列_牛客小白月赛22 (nowcoder.com)

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

typedef long long ll;
const int MAXN = 1e5+50;
int T, N;
int m, n;
map<ll,ll>ma;
int main()
{
    int N;
    for(int i = 1;i <= N;i++)
    {
        cin >> m;
        char c;
        c = getchar();
        if(c == '\n')
        {
            if(m == -1)
            {
                if(ma.empty())
                {
                    printf("skipped\n");
                }
                else {
                    printf("%lld\n",ma.begin()->second);
                    ma.erase(ma.begin());
                }
            }
            else {
                if(ma.count(m)) printf("%lld\n",ma[m]);
                else printf("0\n");
            }
        }
        else {
            cin >> n;
            auto pos = ma.lower_bound(m-30);
            if(pos->first > 1ll*(m+30) || pos == ma.end())
                ma[m] += n;
        }
    }
    return 0;
}

4

B-扫雷_牛客小白月赛17 (nowcoder.com)

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

typedef long long ll;
const int MAXN = 1e5+50;
char saolei[1005][1005];
int ans [1005][1005];
int main()
{
    int m, n;
    cin >> m >> n;
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin >> saolei[i][j];
        }
    }
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(saolei[i][j] != '*')
            {
                if(saolei[i-1][j] == '*') ans[i][j]++;
                if(saolei[i+1][j] == '*') ans[i][j]++;
                if(saolei[i][j-1] == '*') ans[i][j]++;
                if(saolei[i][j+1] == '*') ans[i][j]++;
                if(saolei[i-1][j-1] == '*') ans[i][j]++;
                if(saolei[i-1][j+1] == '*') ans[i][j]++;
                if(saolei[i+1][j-1] == '*') ans[i][j]++;
                if(saolei[i+1][j+1] == '*') ans[i][j]++;
            }
        }
    }
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++){
            if(saolei[i][j] == '*') printf("*");
            else printf("%d",ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

5

C-Forsaken给学生分组_牛客小白月赛18 (nowcoder.com)

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

typedef long long ll;
const int MAXN = 1e5+50;
ll a[100005];
int main()
{
    int n, k;
    ll ans = 0;
    cin >> n >> k;
    for(int i = 1;i <= n;i++) cin >> a[i];
    sort(a+1,a+n+1);
    for(int i = 1;i <= k;i++)
    {
        ans += (a[n+1-i]-a[i]);
    }
    cout << ans << endl;
    return 0;
}

6

分解质因数

J-Rinne Loves Math_牛客小白月赛11 (nowcoder.com)

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

typedef long long ll;
const int MAXN = 1e5+50;
ll a[100005];

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        map<int,int>m;
        int n;
        int a = 1, b = 1;
        cin >> n;
        if(n < 0) {printf("-1\n"); continue;}
        else if(n == 0) printf("0 0\n");
        for(int i = 2;i <= sqrt(n);i++)
        {
            while(n % i == 0) {
                m[i]++;
                n /= i;
            }
        }
        m[n]++;
        for(auto it:m)
        {
            if(it.second % 2 == 0) a *= pow(it.first,it.second/2);
            else {a *= pow(it.first,it.second/2); b *= it.first;}
        }
        printf("%d %d\n",a,b);
    }
    return 0;
}