A.操作序列

题意：见题面

题解：纯模拟题，注意map.lower_bound(key)恰好是我们所需要的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
map<int,int>mp;
int main()
{
    int n,t,c;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&t);
        if(getchar()=='\n')
        {
            if(t==-1)
            {
                if(mp.empty())puts("skipped");
                else
                {
                    printf("%d\n",mp.begin()->second);
                    mp.erase(mp.begin());
                }
            }
            else
            {
                if(mp.count(t))
                    printf("%d\n",mp[t]);
                else
                    puts("0");
            }
        } 
        else
        {
            scanf("%d",&c);
            auto it = mp.lower_bound(t-30);
            if(it==mp.end()||it->first>t+30)
                mp[t]+=c;
        }
    }
    return 0;
}

B.树上子链

题意：给定权值，求一棵树的直径

题解：很常规的一道题目了，树形dp即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
ll p[maxn], dp[maxn], res = -INF;
vector<int> G[maxn];
void dfs(int u, int f)
{
    dp[u] = p[u];
    for (auto v : G[u])
    {
        if (v == f)
            continue;
        dfs(v, u);
        res = max(res, dp[u] + dp[v]);
        dp[u] = max(dp[u], dp[v] + p[u]);
    }
    res = max(res, dp[u]);
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &p[i]);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld\n", res);
    return 0;
}

C.交换游戏

题意：见题面

题解：一道搜索题，dfs+记忆化搜索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
map<int, int> vis;
int dfs(int x)
{
    if (!x || vis[x])
        return vis[x];
    for (int i = 0; i < 12; i++)
        if (x & 1 << i)
            vis[x]++;
    for (int i = 0; i < 10; i++)
        if (x >> i + 1 & 1 && (x >> i & 1) ^ (x >> i + 2 & 1))
            vis[x] = min(vis[x], dfs(x ^ 7 << i));
    return vis[x];
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
    {
        char s[15];
        scanf("%s", s);
        int x = 0;
        for (int i = 0; i < 12; i++)
            if (s[i] == 'o')
                x += 1 << i;
        printf("%d\n", dfs(x));
    }
    return 0;
}

D.收集纸片

题意：一个点是起点也是终点，中间需要经过n个点，问最少走多少路。

题解：发现n只有10，枚举所有顺序即可，可以用字典序排序来做。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
pair<int,int>p[20];
int s[20];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,n1;
        scanf("%d%d",&n,&m);
        scanf("%d%d",&p[0].first,&p[0].second);
        scanf("%d",&n1);
        for(int i=1;i<=n1;i++)
            scanf("%d%d",&p[i].first,&p[i].second);
        for(int i=1;i<=n1;i++)
            s[i]=i;
        p[n1+1].first=p[0].first;
        p[n1+1].second=p[0].second;
        int res = INF;
        do{
            int tmp=0;
            for(int i=1;i<=n1+1;i++)
                tmp+=abs(p[s[i]].first-p[s[i-1]].first)+abs(p[s[i]].second-p[s[i-1]].second);
            res = min(res,tmp);
        }while(next_permutation(s+1,s+n1+1));
        printf("The shortest path has length %d\n",res);
    }
    return 0;
}

E.方块涂色

题意：见题面

题解：将涂色的行列分别移到最上边和最左边，求右下角的面积即可。或者直接容斥定理

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int main()
{
    ll n,m,r,c;
    while(scanf("%lld%lld%lld%lld",&n,&m,&r,&c)!=EOF)
        printf("%lld\n",(n-r)*(m-c));
    return 0;
}

F.累乘数字

题意：见题面

题解：乘d次100就打2d个0即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int main()
{
    int n,d;
    while(scanf("%d%d",&n,&d)!=EOF)
    {
        printf("%d",n);
        for(int i=0;i<d;i++)
            printf("00");
        puts("");
    }
    return 0;
}

G.仓库选址

题意：在图中选一个点使全图加权距离最小。

题解：可以分别求出x和y的贡献，对于每个点的贡献就是x的贡献和加上y的贡献和，取最小即可。或者可以二位前缀和来维护每一个点的贡献。这题的数据挺水的，暴力也能过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
int x[maxn], y[maxn];
ll sumx[maxn], sumy[maxn];
int a[maxn][maxn];
void init()
{
    memset(x, 0, sizeof(x));
    memset(y, 0, sizeof(y));
    memset(sumx, 0, sizeof(sumx));
    memset(sumy, 0, sizeof(sumy));
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &m, &n);
        init();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                scanf("%d", &a[i][j]);
                x[i] += a[i][j];
                y[j] += a[i][j];
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                sumx[i] += 1ll * abs(i - j) * x[j];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                sumy[i] += 1ll * abs(i - j) * y[j];
        ll res = INFL;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                res = min(res, sumx[i] + sumy[j]);
        printf("%lld\n", res);
    }
    return 0;
}

H.货物种类

题意：见题面

题解：对于不带修改的单点求和，差分算是一种比较好写的做法了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
map<int, int> b[maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int l, r, d;
        scanf("%d%d%d", &l, &r, &d);
        b[l][d]++;
        b[r + 1][d]--;
    }
    map<int, int> now;
    int res, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (auto it : b[i])
        {
            now[it.first] += it.second;
            if (now[it.first] == 0)
                now.erase(it.first);
        }
        if (now.size() > cnt)
        {
            cnt = now.size();
            res = i;
        }
    }
    printf("%d\n", res);
    return 0;
}

I.工具人

J.计算A+B

题意：见题面

题解：是一道水题，但是用C写码量挺大的，用Python写就很简单

t = int(input())
for i in range(t):
    n = input().split("+")
    if len(n) != 2 or n[0] == '' or n[1] == '':
        print("skipped")
    else:
        print(int(n[0]) + int(n[1]))

官方题解