A

solution:

模拟题

按照题意模拟即可

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string s;
map<ll , ll > mp;
set<int> se;
set<int>::iterator it;
int main()
{
    int t;
    cin>>t;
    getchar();
    while(t--)
    {
        int flag = 0,sign = 0,flag2 = 0;
        int cnt = 0;
        getline(cin,s);
        int len = s.length();
        if(s[0] == '-'){
            if(se.size() == 0){
                printf("skipped\n");
            }else{
                it = se.begin();
                cout<<mp[*it]<<endl;
                mp[*it] = 0;
                se.erase(*it);
            }
            continue ;
        }

        for(int i=len-1;i>=0;i--){
            if(s[i] == ' '){
                flag = 1;
            }
        }

        if(flag == 0){
            int x = 0;
            for(int i=0;i<len;i++){
               x = x*10 + (s[i]-'0');
            }
            printf("%lld\n",mp[x]);
            continue ;
        }
        int x = 0,y = 0;
        for(int i=0;i<len;i++){
            if(s[i] == ' '){
                sign = 1;
                continue ;
            }
            if(sign == 0){
                x = x*10 + (s[i]-'0');
            }else{
                y = y*10 + (s[i]-'0');
            }
        }
        for(int i=max(0,x-30);i<=x+30;i++){
            if(mp[i] != 0){
                flag2 = 1;
                break ;
            }
        }
        if(flag2 == 1){
            continue ;
        }
        mp[x] += y;
        se.insert(x);
    }
    return 0;
}

B

solution:

简单的树上dp

树上dfs，记得初始化ans = -inf,没初始化为负数wa一发

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int n,x,y;
ll ans=-1e18,dp[maxn],a[maxn];
vector<int> v[maxn];
void dfs(int x,int fa)
{
    dp[x] = a[x];
    ans = max(ans , dp[x]);
    for(int i=0;i<v[x].size();i++){
        int nex = v[x][i];
        if(nex == fa)
            continue ;
        dfs(nex , x);
        ans = max(ans , dp[x] + dp[nex]);
        dp[x] = max(dp[x] , dp[nex] + a[x]);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        dp[i] = -1e18;
    }
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    printf("%lld\n",ans);
    return 0;
}

C

solution:

DFS

长度为12的字符串，考虑枚举可以更换的情况，直到无法更换，记录最大值即可

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
char s[20];
int ans = 12;
void dfs()
{
    for(int i=3;i<=12;i++){
        if(s[i-2] == '-' && s[i-1] == 'o' && s[i] == 'o'){
            s[i-2] = 'o',s[i-1] = '-',s[i] = '-';
            dfs();
            s[i-2] = '-',s[i-1] = 'o',s[i] = 'o';
        }
        if(s[i-2] == 'o' && s[i-1] == 'o' && s[i] == '-'){
            s[i-2] = '-',s[i-1] = '-',s[i] = 'o';
            dfs();
            s[i-2] = 'o',s[i-1] = 'o',s[i] = '-';
        }
    }
    int sum = 0;
    for(int i=1;i<=12;i++){
        if(s[i] == 'o')
            sum++;
    }
    ans = min(ans , sum);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans = 12;
        scanf("%s",s+1);
        dfs();
        printf("%d\n",ans);
    }
    return 0;
}

D

solution:

暴力枚举

一开始没考虑时间复杂度写的dfs超时了，改成next_permutation全排列就过了

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 13;
int a[maxn],b[maxn],c[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x,y,n,ans = 1e9;
        scanf("%d %d",&x,&y);
        scanf("%d %d",&a[0],&b[0]);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            c[i] = i;
            scanf("%d %d",&a[i],&b[i]);
        }
        c[0] = 0;
        do{
            int cnt = 0;
            for(int i=1;i<=n;i++){
                cnt += abs(a[c[i]] - a[c[i-1]]) + abs(b[c[i]] - b[c[i-1]]);
            }
            cnt += abs(a[c[0]] - a[c[n]]) + abs(b[c[0]] - b[c[n]]);
            ans = min(ans ,cnt);
        }while(next_permutation(c,c+1+n));
        printf("The shortest path has length %d\n",ans);
    }
    return 0;
}

E

solution:

签到题，输出n×m + r×m + (n - r)×c

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n , m, r,c;
    while(cin>>n>>m>>r>>c)
    {
        ll cnt1 = n*m;
        ll cnt2 = r*m + (n - r)*c;
        cout<<cnt1 - cnt2<<endl;
    }
    return 0;
}

F

solution:

签到题

乘几次就加几个00

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n ,d;
    while(cin>>n>>d){
        cout<<n;
        for(int i=1;i<=d;i++){
            cout<<"00";
        }
        cout<<endl;
    }
    return 0;
}

G

solution:

不明白这个题要干什么。。。n的四次方都过，假的吧

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[105][105];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,ans = 1e9+10;
        scanf("%d %d",&m,&n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int cnt = 0;
                for(int k=1;k<=n;k++){
                    for(int z=1;z<=m;z++){
                        cnt += (a[k][z]*(abs(k-i) + abs(z-j)));
                    }
                }
                ans = min(ans , cnt);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

H

solution:

差分数组/线段树

差分数组的做法挺简单的，就是只需要最后一次查询，我们可以从前往后遍历，维护当前位置一共存放了多少种不同的货物，类似前缀和

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
vector<int> add[maxn],del[maxn];
map<int , int > mp;

int main()
{
    int n,m,x,y,z;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&z);
        add[x].push_back(z);
        del[y+1].push_back(z);
    }
    int ans = 0,sum = 0,maxx = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<add[i].size();j++){
            mp[add[i][j]]++;
            if(mp[add[i][j]] == 1)
                sum++;
        }
        for(int j=0;j<del[i].size();j++){
            mp[del[i][j]]--;
            if(mp[del[i][j]] == 0)
                sum--;
        }
        if(sum > maxx){
            maxx = sum;
            ans = i;
        }
    }
    printf("%d\n",ans);

    return 0;
}

I

no solution，计算几何待补。。。

J

solution:

签到题

首先判断是不是a+b的类型，然后用大数相加即可，比赛因题面描述不清，前导0的样例已经移除了，这。。。

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string sum(string s1,string s2)
{
     if(s1.length()<s2.length())
     {
          string temp=s1;
          s1=s2;
          s2=temp;
     }
     for(int i=s1.length()-1,j=s2.length ()-1;i>=0;i--,j--)
     {
          s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0));
          if(s1[i]-'0'>=10)
          {
              s1[i]=char((s1[i]-'0')%10+'0');
              if(i)
                   s1[i-1]++;
              else
                   s1='1'+s1;
          }
     }
     return s1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        string s1,s2;
        int flag = 0;
        for(int i=0;i<s.length();i++){
            if(s[i] == '+'){
                flag = 1;
                continue ;
            }
            if(s[i] >= '0' && s[i] <= '9'){
                if(flag == 0){
                    s1 = s1 + s[i];
                }else{
                    s2 = s2 + s[i];
                }
                continue ;
            }
            flag = 2;
        }
        if(s1.length() == 0 || s2.length() == 0 || flag == 2){
            cout<<"skipped"<<endl;
            continue ;
        }
        string ans = sum(s1,s2);
        cout<<ans<<endl;
    }
    return 0;
}