Codeforces Round #548 (Div. 2)

A. Even Substrings

题意：给你一串数字，问有多少区间满足以偶数结尾（水题）

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef  long long ll;
 
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    ll tot=0;
    ll ans=0;
    for(int i=0;i<n;i++){
        if((s[i]-‘0‘)%2==0){
            tot++;
            ans+=tot;
        }
        else tot++;
    }
    cout<<ans<<endl;
    return 0;
}

B. Chocolates

题意：n种类型的巧克力，每种有ai个，问你最多能买多少块，要满足前一种不买或者前一种买的比当前的少；

从后面往前维护，遍历一遍就行了，自己当时做的时候一直从前面往后维护，一直T……；

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef  long long ll;
ll a[maxn];
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll res=a[n];
    ll ans=a[n];
    for(int i=n-1;i>=1;i--){
        res=max(0LL,min(a[i],res-1));
        ans+=res;
    }
    cout<<ans<<endl;
    return 0;
}

C. Edgy Trees

题意：给你一颗树，问从某个节点走到某个节点至少经过一个黑边的有多少种；

自己：算出总的可能减去都没有经过黑边的种类，然而不会维护边的颜色。。。就卡了

看了学长的~用了两个vec，一个v来维护树，一个v用来维护边的颜色，~~

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
typedef  long long ll;
vector<int>g[maxn],id[maxn];
bool vis[maxn];
ll a[maxn],cnt;
void dfs(int u){
    vis[u]=true;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        int w=id[u][i];
        if(vis[v]||w)continue;
        dfs(v);
        vis[v]=true;
        a[cnt]++;
    }
}
ll ksm(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1){
            ans=(ans*x)%mod;
        }
        x=x*x%mod;
        y/=2;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(v);
        g[v].push_back(u);
        id[u].push_back(w);
        id[v].push_back(w);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt++;
            dfs(i);
            vis[i]=true;
            if(a[cnt])a[cnt]++;
            else cnt--;
        }
    }
    ll ans=0,res,sum=0;
    for(int i=1;i<=cnt;i++){
        ans=(ans+ksm(a[i],m))%mod;
        sum+=a[i];
    }
    res=ksm(n,m)%mod;
    res=(res-ans-(n-sum)+mod)%mod;
    cout<<res<<endl;




    return 0;
}

D。待补