AtCoder Beginner Contest 137（A-D）

ABC签到，细讲CD题。

A：

意外的是发现了max的新用法，可以的。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int MAXN = 1e5 + 7;

int main()
{
    ios::sync_with_stdio(0);
    int a, b;
    cin>>a>>b;
    cout<<max({a+b, a-b, a*b})<<endl;

    return 0;
}

           

B：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 300 + 7;

int main()
{
    int k, x;
    cin>>k>>x;
    for(int i = x-k+1; i<= x+k-1;i++)
    {
        cout<<i;
        if(i != x+k-1)
            cout<<' ';
        else cout<<endl;
    }

    return 0;
}
           

C：

就是对每个字符串排序，然后再把所有字符串排序，两两相等就加1。这里我用的是vector套string。也可以用无序map，时间都差不多。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;

vector <string> ve;
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    string s;
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        cin>>s;
        sort(s.begin(), s.end());
        ve.push_back(s);
    }
    sort(ve.begin(),ve.end());
    int x = 1;
    for(int i = 1; i < n; i++)
    {
        if(ve[i] == ve[i-1])
        {
            ans += x;
            x++;
        }
        else x = 1;
    }
    cout<<ans<<endl;

    return 0;
}


           

下面是大佬写的无序map：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;

int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    unordered_map<string, ll> mp;
    ll ans = 0;
    for(int i = 0; i < n; i++) 
    {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        ans += mp[s];
        mp[s]++;
    }
    cout << ans << endl;
    return 0;
}
           

D：

说实话，当我知道这道题用优先队列的时候，我发现这也是一道签到了。比赛的时候一直在用贪心写，可能我太贪了。然后怎么贪都写不对，放弃了。最后的时候大佬说用优先队列存，一下就豁然了，可惜没有时间了。

然后周天说来补题的，结果上午睡大觉+下午睡大觉+晚上烧烤。。。

好吧今天周一了，我补！写了半天一直wa，都没信心了，是这个思想啊怎么就不对了。去看了看大佬的代码，好吧，直接遍历m多方便，我硬是写单循环给累死，不说了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int MAXN = 1e5 + 7;

struct node
{
    int x, y;
}stu[MAXN];

bool cmp(node a, node b)
{
    return a.x < b.x;
}
priority_queue <int> que;

int main()
{
    ios::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        cin>>stu[i].x>>stu[i].y;
    }
    sort(stu, stu+n, cmp);
    int pos = 0;
    for(int i = 1; i <= m; i++)
    {
        for(int j = pos; j < n; j++)
        {
            if(stu[j].x == i) que.push(stu[j].y);
            else
            {
                pos = j;
                break;
            }
        }
        if(que.size())
        {
            ans += que.top();
            que.pop();
        }
    }
    cout<<ans<<endl;

    return 0;
}