2020牛客NOIP赛前集训营-普及组（第三场）

比赛地址：https://ac.nowcoder.com/acm/contest/7608

A:
把字符串、编号和价值存放在一个结构体中，用cmp给a数组排序
二维vector b保存着以a~z结尾的价值最大的字符串，可以用O(1)的时间完成查询
总算法时间复杂度O（nlogn）

#include <bits/stdc++.h>
using namespace std;
struct abc
{
    string s;
    int jia,id;
};
bool cmp(abc f1,abc f2)
{
    if(f1.jia==f2.jia)
    {
        return f1.id<f2.id;
    }
    return f1.jia>f2.jia;
}
int main()
{
    int n,m;
    cin>>n>>m;
    abc a[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].s>>a[i].jia;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    vector<vector<abc> > b;
    for(int i=0;i<=26;i++)
    {
        b.push_back({});
    }
    for(int i=1;i<=n;i++)
    {
        b[a[i].s[a[i].s.size()-1]-'a'].push_back(a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        char p;
        int k;
        cin>>p>>k;
        if(b[p-'a'].size()<k)
        {
            cout<<"Orz YYR tql"<<endl;
        }
        else
        {
            cout<<b[p-'a'][k-1].s<<endl;
        }
    }
    return 0;
}

B:
先算出i和j有多少种最大公约数的可能，因为n<=1000，所以可以把算出的gcd放入a数组中
再计算a数组的每个值和k有多少种可能的gcd，直接相乘即可
总时间复杂度O（n^2）

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
int main()
{
    int n;
    cin>>n;
    int a[n+1];
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[gcd(i,j)]++;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int k=1;k<=n;k++)
        {
            ans+=gcd(i,k)*a[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

以下为本人笔记:
https://ac.nowcoder.com/discuss/547031?type=101&order=0&pos=9&page=1&channel=-1&source_id=1