牛客周赛round84

一塌糊涂

https://ac.nowcoder.com/acm/contest/103152

还是太菜了

A

简单

#include<bits/stdc++.h>
using namespace std;

int a[3];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int res=0;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<3-1;i++) res+=abs(a[i+1]-a[i]);
    if(res==0) cout<<"Yes\n";
    else cout<<"No\n";
    
    return 0;
}

B

贪心。重新排序，要么从小到大，要么从大到小。两种排法或者元素相同一种排法。最小值就是，最大元素减最小元素的差值

#include<bits/stdc++.h>
using namespace std;


const int INF=1e9;
int n;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin>>n;
    int mx=-INF,mn=INF;
    int x;
    for(int i=1;i<=n;i++) {
        cin>>x;
        mx=max(mx,x);
        mn=min(mn,x);
    }
    
    mx-=mn;
    cout<<(1+(mx>0))<<" "<<mx<<endl;
    
    return 0;
}

C

很简单，暴力。遍历字符串，内层字串长度，依次算；

#include<bits/stdc++.h>
using namespace std;


string s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,t;cin>>n>>t;
    cin>>s;
    int res=0;
    for(int i=0;i<n-t+1;i++)
    {
        for(int j=i;j<i+t-1;j++){
           res+=abs(s[j]-s[j+1]);
        }

    }
    cout<<res;
    return 0;
}

D

C的强化版，数据变大。用前缀和来优化。

#include<bits/stdc++.h>
using namespace std;


string s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,k;cin>>n>>k;
    cin>>s;
    s=" "+s;
    vector<int> sum(n+1);
    for(int i=2;i<=n;i++){
        sum[i]=sum[i-1]+abs(s[i]-s[i-1]);
    }
    
    long long ans=0;
    for(int i=k;i<=n;i++){
        ans+=(sum[i]-sum[i-k+1]);
    }
    cout<<ans<<endl;

    return 0;
}

E

• 树上前缀和
• 树的创建与表示
• dfs
• lambda表达式

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n;
    cin>>n;
    vector<int> v(n+1,0);
    vector<vector<int>> g(n+1,vector<int>());
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    auto dfs1 = [&](auto&&self,int fa,int node)->void{
        if(g[node].size()==1&&fa!=-1){
            v[node]=0;
            return ;
        }
        for(auto son:g[node]){
            if(son==fa)continue;
            self(self,node,son);
            v[node]+=abs(node-son)+v[son];
        }
    };
    int ans=9e18;
    auto dfs2 = [&](auto&&self,int fa,int node)->void{
        if(g[node].size()==1&&fa!=-1){
            return ;
        }
        for(auto son:g[node]){
            if(son==fa)continue;
            int d1=v[son];
            int d2=v[1]-v[son]-abs(son-node);
            ans=min(ans,abs(d1-d2));
            self(self,node,son);
        }
    };
    dfs1(dfs1,-1,1);
    dfs2(dfs2,-1,1);
    cout<<ans;
}

F

状态压缩DP，不会······

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 20;
int a[N], n, dp[N][1 << 20], f[N];

void init()
{
    int ans = 1;
    f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans * i) % mod;
        f[i] = ans;
    }
}

int qmi(int x, int y)
{
    int cnt = 1;
    while (y)
    {
        if (y & 1) cnt = (cnt * x) % mod;
        y >>= 1;
        x = (x * x) % mod;
    }
    return cnt;
}


signed main()
{
    cin >> n;
    init();
    for (int i = 0; i < n; i++)  cin >> a[i];
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            int cnt = 0, tmp = i;
            if (i >> j & 1)
            {
                while (tmp)
                {
                    if (tmp & 1) cnt++;
                    tmp >>= 1;
                }
                for (int k = 0; k < n; k++)
                {
                    if ((i >> k) & 1) continue;
                    dp[k][i | (1 << k)] += (dp[j][i] + abs(a[j] - a[k]) * f[cnt - 1] % mod) % mod;
                    dp[k][i | (1 << k)] %= mod;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans = (ans + dp[i][(1 << n) - 1]) % mod;
    }
    cout << (ans * (qmi(f[n], mod - 2))) % mod << "\n";
    return 0;
}

G

加权逆序对?不会······

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b%2)ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    int ans=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        ans+=a[i]*(i-1)-sum;
        ans=(ans%mod+mod)%mod;
        sum+=a[i];
        sum%=mod;
    }
    ans=ans*2%mod;
    //ans*=ksm(n,mod-2)%mod;
    cout<<ans*ksm(n,mod-2)%mod;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}