A

签到.

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c;
int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    while(n--) {
        cin>>a>>b>>c;
        ans=0;
        ans+=(a-100)/50;
        if(b >= 34 && b <= 40) ans+=1;
        if(c >= 34 && c <= 40) ans+=1;
        if(b == 45) ans+=2;
        if(c == 45) ans+=2;
        cout<<ans<<"\n";
    }
    return 0;
}

B

签到×2.

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int x,y,h[310][310];
int ans;
int tx[4]={1,-1,0,0},ty[4]={0,0,1,-1};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) {
        cin>>x>>y;
        h[x][y]=1;
    }
    ans=4*k;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(h[i][j]) {
                for(int t=0;t<4;t++) {
                    if(h[i+tx[t]][j+ty[t]]) ans--;
                }
                h[i][j]=0;
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

C

D

E & F

贪心。考虑怎样操作才能一次消除最多的宝石。手玩两个例子后发现，我们可以从后向前枚举，记录下枚举过的宝石的颜色种类数。当我们枚举到一个宝石时正好发现了所有颜色，即再向左枚举时不会再出现新颜色，根据定义，这个宝石就是我们能够进行操作的宝石的极左点。我们对它进行一次操作，消除这个宝石往右的所有宝石。接着继续重复上述操作。具体实现可以使用set记录已枚举过的宝石。

注意在枚举过程中，如果有某种颜色的宝石被消除完了，那么下轮枚举时颜色的总数应该相应减少。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,t;
int c[N];
set<int> s,u;
int num[N];
void solve() {
    int sum=s.size();
    int cnt=0;
    int ans=0;
    u.clear();
    for(int i=n;i>=1;i--) {
        num[c[i]]--;
        if(!u.count(c[i])) {
            u.insert(c[i]); 
            cnt++;
        }
        if(cnt == sum) {
            ans++; cnt=0;
            for(auto it=u.begin();it!=u.end();it++) {
                int x=*it;
                if(!num[x]) sum--;
            }
            u.clear();
        }
    }
    cout<<ans<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        s.clear();
        cin>>n;
        for(int i=1;i<=n;i++) num[i]=0;
        for(int i=1;i<=n;i++) cin>>c[i],s.insert(c[i]),num[c[i]]++;
        solve();
    }
    return 0;
}

G

H

I

手玩样例发现一个结论：任意两点间最短路最多只会经过一条边。证明略。所以我们只需要分别统计出每条边对答案的贡献即可。

具体的话，我们先将a数组从小到大排序，从最大的边开始有 $ ans=4* \overset{n-1}{\underset{i=1}{\sum i\ast}}a_{i+1} $

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10;
int t,n;
int a[N];
void solve() {
    sort(a+1,a+n+1);
    LL ans=0;
    for(LL i=1;i<n;i++) {
        ans+=1ll*i*a[i+1];
    }
    cout<<ans*4<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        solve();
    }
    return 0;
}

J

上一题的结论乍一看好像在这题不适用了，所以我们需要把结论修改一下。将a数组排序后，对于任意两点 $ a_{i} $，$ a_{j} $间的最短路，它只会有如下两种形态：

1.只包含将两点直接相连的边，贡献为 $min\{a_{i},a_{j} \}$

2.只包含 $ a_{i} $ 到 $ a_{1} $ 和 $ a_{1} $ 到 $ a_{j} $ 两条边，贡献为 $ 2*a_{1} $

证明不难，略。因为第二种情况里的贡献是定值，所以我们仿照上一题的流程，比较每条边与 $ 2*a_{1} $ 的大小并计算贡献即可。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10;
int t,n;
int a[N];
void solve() {
    sort(a+1,a+n+1);
    LL ans=0;
    int p=upper_bound(a+1,a+n+1,2*a[1])-a;
    for(int i=1;i<n;i++) {
        if(i < p) ans+=1ll*a[i]*(n-i);
        else ans+=2ll*a[1]*(n-i);
    }
    cout<<ans*4<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        solve();
    }
    return 0;
}

K

L

M