Codeforces 1230 #Codeforces

1230C.py

n, m = map(int, input().split())
G = [[] for i in range(n)]
ans = 0

for i in range(m):
    u, v = map(int, input().split())
    G[u - 1].append(v - 1)
    G[v - 1].append(u - 1)

minus = 2333
if n <= 6:
    ans = m
else:
    for i in range(7):
        for j in range(i + 1, 7):
            cnt = 0
            for q in range(7):
                if q in G[i] and q in G[j]:
                    cnt += 1
            minus = min(minus, cnt)
    ans = m - minus
print(ans)

1230D.py

def is_subset(a, b):
    return (~a & b) == 0

n = int(input())
a = map(int, input().split())
b = map(int, input().split())
vis = [False] * (n + 1)
st = list(zip(a, b))
st.sort()
st.reverse()
st.append((-1, -1))

ans = 0
for i in range(n):
    if st[i][0] != st[i + 1][0]:
        continue
    for j in range(i, n):
        if is_subset(st[i][0], st[j][0]):
            vis[j] = True
for i in range(n):
    ans += vis[i] * st[i][1]
print(ans)

1230E.cpp

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const ll inf=0x3f3f3f3f3f3f3f3f;

ll gcd(ll a, ll b){
    ll tmp = 0;
    while(b != 0){tmp = b, b = a % b, a = tmp;}
    return a;
}

const int maxn = 1e5 + 1000;
const int mod = 1e9 + 7;
int n;
ll val[maxn];
vector<int> G[maxn];
ll ans = 0;

void dfs(int u, int fa, map<ll, int> mp){
    map<ll, int> nw_map;
    for(pair<ll, int> pi:mp){
        ll v = gcd(val[u], pi.first);
        ans = (ans + v * pi.second % mod) % mod;
        nw_map[v] = nw_map[v] + pi.second;
    }
    ans = (ans + val[u]) % mod;
    nw_map[val[u]] += 1;
    for(int v:G[u]){
        if(v == fa) continue;
        dfs(v, u, nw_map);
    }
}

void solve(){
    int u, v;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> val[i];
    for(int i=1;i<n;i++){
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, 0, map<ll, int>());
    cout << ans << '\n';
}

signed main(){
    Android;
    solve();
}

1230F.cpp

//做法易懂，但证明复杂度较难
#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;
vector<int> G[maxn];
ll indegree[maxn]={0}, outdegree[maxn]={0};
int n, m, q;

void solve(){
    ll u, v, ans = 0;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        if(u < v) swap(u, v);
        indegree[v]++, outdegree[u]++;
        G[v].push_back(u);
    }
    for(int i=1; i<=n; i++) ans += indegree[i] * outdegree[i];
    cout << ans << '\n';

    cin >> q;
    for(int i=0;i<q;i++){
        cin >> u;
        ans -= 1ll * indegree[u] * outdegree[u];
        for(int v:G[u]){
            G[v].push_back(u);
            ans -= indegree[v] * outdegree[v];
            indegree[v]++, outdegree[v]--;
            ans += indegree[v] * outdegree[v];
        }
        indegree[u] = 0, outdegree[u] += G[u].size();
        G[u].clear();

        cout << ans << '\n';
    }

}

signed main(){
    Android;
    solve();
}

Thanks for faithful secretary