牛客练习赛64

A 怪盗-1412

Solution

wa了一发爆int 没开ll像极了一个**
贪心:

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

void solve(){
    ll n,m,k;
    cin>>n>>m>>k;
    if(n<2||m<1||k<1){cout<<0<<'\n';return;}
    ll v=n/2;
    ll u=n-v;
    cout<<u*v*m*k<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B Dis2

Solution

比赛的时候想了个的DFS，看到别人基本都是外层循环遍历当前节点，内层循环遍历当前节点的子节点，对每个节点来说他的贡献为他子节点的度-1，-1是要减掉和自己相连的度。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 2e5 + 5;

vector<int> G[N];
int cnt[N];
int n;

void dfs(int x,int fa,int pa){
    if(pa>0) cnt[pa]++,cnt[x]++;
    for(auto c:G[x]){
        if(c==fa) continue;
        if(G[x].size()>2) cnt[c]+=G[x].size()-2;
        dfs(c,x,fa);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(G[i].size()==1) {dfs(i,-1,-1);break;}
    }
    for(int i=1;i<=n;i++){
        cout<<cnt[i]<<'\n';
    }
    return 0;
}

C 序列卷积之和

Solution

先写个暴力找规律

容易发现右边从上到下是1 2 3 4，从右向左是每次加上最右边的数。
然后找到规律之后直接计算即可，问题是如何将降下来，前缀和优化即可。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int n;
ll a[N],pre[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]+=(pre[i-1]+i*a[i]%mod)%mod;
    }
    ll ans=0;
    for(int i=n;i>=1;i--)
        ans=(ans+pre[i]*(n-i+1)%mod*a[i]%mod)%mod;
    cout<<ans<<'\n';
    return 0;
}