@toc

6-10题Acwing均有提交地址

第一题：跑步训练（模拟）

答案：3880

#include <iostream>

using namespace std;

int main()
{
    int res = 0;
    int sum = 10000;

    while(sum >= 600){
        res += 120; // 跑步 + 休息
        sum -= 300;
    }

    res += sum / 10; // 不够一个周期了，每s损耗体力

    cout << res;

    return 0;
}

第二题：合并检测（数学，均值不等式）

答案：10

第三题：分配口罩（搜索，dfs）

答案：2400

#include <iostream>

using namespace std;

int nums[] = {9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200,
4175600, 6309600, 5865200, 6604400, 4635000, 10663400, 8087200, 4554000};

int ans = 1e9;

void dfs(int u,int s1,int s2)
{
    if(u == 15){
        ans = min(ans,abs(s1 - s2));
        return;
    }
    dfs(u + 1,s1 + nums[u],s2);
    dfs(u + 1,s1,s2 + nums[u]);
}

int main()
{
    dfs(0,0,0);
    cout << ans;

    return 0;
}

写法2：二进制搜索

#include <iostream>

using namespace std;

int nums[] = {9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200,
4175600, 6309600, 5865200, 6604400, 4635000, 10663400, 8087200, 4554000};

int ans = 1e9;

void dfs()
{
    for(int i = 0;i < (1 << 15);i ++ )
    {
        int s1 = 0,s2 = 0;
        for(int k = 0;k < 15;k ++ )
            if((i >> k) & 1) s1 += nums[k];
            else s2 += nums[k];
        ans = min(ans,abs(s1 - s2));
    }
}

int main()
{
    dfs();
    cout << ans;

    return 0;
}

第四题：矩阵（动态规划）

答案1340

#include <iostream>

using namespace std;

int mod = 2020;
int f[2030][1020];

int main()
{

    f[0][0] = 1;
    for(int i = 1;i <= 2020;i ++ )
        for(int j = 1;j <= i;j ++ )
        {
            f[i][j] = (f[i][j] + f[i - 1][j - 1]) % mod;
            if(i - j <= j) f[i][j] = (f[i][j] + f[i - 1][j]) % mod; // f[i][j]合理才转移
            /*
                说明：j 是第一行放的数量，i - j则是第二行放的数量
                第二行的数量不能大于第一行的数量，因为 是从前i个中顺序选的
                举例：假如第二行的数量 大于 第一行的数量
                1
                2 3 
                那么 4 只能接在 3后面，这样的情况放不满矩阵
            */
        }

    cout << f[2020][1010] << endl;

    return 0;
}

第五题：完美平方数

第六题：解码（模拟）

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;

    string res;
    for(int i = 0;i < s.size();i ++ )
    {
        if(s[i] >= '0' && s[i] <= '9') continue;
        int cnt = 0;
        if(i + 1 < s.size() && s[i + 1] >= '0' && s[i + 1] <= '9') cnt = s[i + 1] - '0';
        if(cnt > 0){
            while(cnt -- ) res += s[i];
        }else res += s[i];
    }

    cout << res << endl;

    return 0;
}

第七题：走方格（动态规划）

#include <iostream>

using namespace std;

const int N = 32;

int n,m;
int f[N][N];

int main()
{
    cin >> n >> m;

    f[1][1] = 1;

    for(int i = 1;i <= n;i ++ )
        for(int j = 1;j <= m;j ++ )
        {
            if(i == 1 && j == 1) continue;
            if(i % 2 == 0 && j % 2 == 0) continue;
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }

    cout << f[n][m] << endl;

    return 0;
}

第八题：整数拼接（哈希表）

题解

/*

    (A[i] * A[j].size() + A[j]) % k == 0
   = (A[i] * A[j].size()) = -A[j] % k;

*/

#include <iostream>

using namespace std;

const int N = 100010;

typedef long long LL;

int n,k;
int a[N];
int s[11][N];

int get(int n)
{
    int res = 0;
    while(n) res ++, n/=10;
    return res;
}

int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i ++ ) cin >> a[i];

    for(int i = 0;i < n;i ++ )
    {
        LL t = a[i] % k;
        for(int j = 0;j < 11;j ++ ) // 10 ^ 9,总共有10位，开0-10的哈希表11个
        {
            s[j][t] ++;
            t = t * 10 % k;
        }
    }

    LL res = 0;
    for(int i = 0;i < n;i ++)
    {
        LL t = a[i] % k;
        int len = get(a[i]);
        res += s[len][(k - t) % k]; // (k - t) % k, 数学意义上的取模

        // 判重
        LL r = t;
        while(len --) r = r * 10 % k;
        if(r == (k - t) % k) res --;
    }

    cout << res << endl;

    return 0;
}

第九题：超级胶水（贪心）

题解

#include<iostream>

using namespace std;

int n,x;

int main()
{
    cin>>n;

    long long  sum=0,res=0;
    for(int i=0;i<n;i++){
        cin>>x;
        res += sum * x;
        sum += x;
    }

    cout<<res<<endl;
    return 0;
}

第十题：网络分析（带权并查集）

详细题解

#include <iostream>

using namespace std;

const int N = 10010;

int n,m;
int p[N],v[N],d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int main()
{
    cin >> n >> m;

    for(int i = 1;i <= n;i ++ ) p[i] = i;

    for(int i = 0;i < m;i ++ )
    {
        int t,a,b;
        cin >> t >> a >> b;
        if(t == 1){
            int pa = find(a), pb = find(b);
            if(pa != pb)
            {
                d[pa] += v[pa] - v[pb];
                p[pa] = pb;    
            }
        }else{
            int pa = find(a);
            v[pa] += b;
        }
    }

    for(int i = 1;i<= n;i ++) 
        cout << v[find(i)] + d[i] << ' ';

    return 0;
}