传送门：https://codeforces.com/contest/2019
B. All Pairs Segments
题意：
首先样例解释一下：
一共有：[1,2],[1,3],[1,5],[1,6],[1,7],[2,3],[2,5],[2,6],[2,7],[3,5],[3,6],[3,7],[5,6],[5,7],[6,7]
点 1，7 在5个线段中包含，点2,4,6在9个线段中包含，点3,5在11个线段中包含
所以查询 5 时，输出2，查询9时，输出3 ...
思路：
1 2 3 5 6 7 假设一共有 n 个数
在 i 的下标中 左边一共有 i - 1 个数 ，右边有 n - i + 1，相互组合有 ( i - 1 ) * ( n - i + 1 )的贡献
并且 i 可以和右边的数组合 ，一共有 n - i 个贡献
如果没有出现在数组中，比如说 4 ，左边可以有 i - 1 个数，右边有 ( n - i + 1 ) 可以组合，所以有
( i - 1 ) * ( n - i + 1 )
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n , q;cin >> n >> q;vector<int> a(n + 1);for( int i = 1; i <= n; i++) cin >> a[i];map<int,int> mp;for( int i = 1; i <= n; i++){mp[( i - 1 ) * ( n - i + 1 ) + n - i ]++;if( i > 1 )mp[(i - 1) * ( n - i + 1 )] += ( a[i] - a[i-1] - 1 );}while(q--){int x; cin >> x;cout << mp[x] << " ";}cout << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}C. Cards Partition
题意：
思路：
假设 mx 时 数组 a 的最大值，sum 是数组 a 的总和
假设牌的大小为 x ，所有牌的数量为 x * mx，但是还有一种可能 ( sum + x - 1 ) / x * x
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n , k ; cin >> n >> k;vector<int> a(n + 1);for( int i = 1; i <= n; i++) cin >> a[i];int sum = 0; int mx = 0;for( int i = 1 ; i <= n; i++){sum += a[i]; mx = max( mx , a[i] );}int ans = 1;for( int i = 1 ; i <= n; i++){int temp = max( mx * i , ( sum + i - 1 ) / i * i ) ;if( temp <= sum + k ) ans = max( ans , i );}cout << ans << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}E. Tree Pruning
题意：
思路：（拓扑排序）
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int h[N], e[2 * N], ne[2 * N], idx;
int Size[N];
queue<int> que;
int leaf[N];
vector<int> dep[N];
bool vis[N]; int sum;
int deg[N];
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
void dfs(int u, int fa, int depth)
{Size[u] = 1;dep[depth].push_back(u);for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (j == fa)continue;dfs(j, u , depth + 1 );Size[u] += Size[j];}if (Size[u] == 1) {leaf[u] = 1;}
}
void topsort()
{while (que.size()){int x = que.front();que.pop();if (vis[x]) continue;vis[x] = true;sum++;for (int i = h[x]; i != -1; i = ne[i]){int j = e[i];if (j == 1) continue;if (--deg[j] <= 1)que.push(j);}}
}
void solve()
{int n; cin >> n;sum = 0; idx = 0;while (que.size())que.pop();for (int i = 0; i <= n; i++){leaf[i] = Size[i] = deg[i] = 0;vis[i] = false;h[i] = -1;dep[i].clear();}for (int i = 0; i < n - 1; i++){int a, b; cin >> a >> b;add(a, b); add(b, a);deg[a]++; deg[b]++;}dfs(1, -1, 0);int ans = 2e18;for (int i = 1; i < n; i++){int res = 0;for (auto e : dep[i]){res += Size[e] - 1;}ans = min(ans, res + sum);for (auto e : dep[i]){if (leaf[e]){que.push(e);}}topsort();}cout << ans << endl;
}
signed main()
{int tt; cin >> tt;while (tt--)solve();return 0;
}
