# Codeforces Round #722 (Div. 2)

A. Eshag Loves Big Arrays

Soulution:

Code:

int t, n;
map<int, int> mp;

int main(){
__;
cin >> t;
while(t --){
cin >> n;
int x;
mp.clear();
for(int i = 1; i <= n; i ++)    cin >> x, mp[x] ++;
if(mp.size() == 1)  puts("0");
else{
int f = 0;
int ans = 0;
for(auto i : mp){
if(f){
ans += i.se;
}
f = 1;
}
printf("%d\n", ans);
}

}
return 0;
}


B. Sifid and Strange Subsequences

Soulution:

Code:

int t, n;
ll a[N];

int main(){
__;
cin >> t;
while(t --){
cin >> n;
for(int i = 1; i <= n; i ++)    cin >> a[i];
if(n == 1){
puts("1");
continue;
}
sort(a + 1, a + n + 1);
int p = 0;
ll ans = 0, res = 3e9;
for(int i = 1; i <= n; i ++){
if(a[i] <= 0){
p = i;
ans ++;
if(i >= 2) {
res = min(res, abs(a[i] - a[i - 1]));
}
}
}
if(p == 0)  ans = 1;
else{
p ++;
if(p <= n){
if(res >= a[p]){
ans ++;
}
}
}
printf("%lld\n", ans);
}
return 0;
}


C. Parsa's Humongous Tree

Soulution:

Code:

int n, t;
int l[N], r[N];
ll f[N][2];
vector<int> G[N];

void dfs(int u, int fa){
for(int i = 0; i < G[u].size(); i ++){
int v = G[u][i];
if(v == fa) continue;
dfs(v, u);
f[u][0] += max(f[v][0] + abs(l[u] - l[v]), f[v][1] + abs(l[u] - r[v]));
f[u][1] += max(f[v][0] + abs(r[u] - l[v]), f[v][1] + abs(r[u] - r[v]));
}
}

int main(){
__;
cin >> t;
while(t --){
cin >> n;
for(int i = 1; i <= n; i ++){
G[i].clear();
f[i][0] = 0;
f[i][1] = 0;
}
for(int i = 1; i <= n; i ++){
cin >> l[i] >> r[i];
}
for(int i = 1; i < n; i ++){
int u, v;
cin >> u >> v;
G[u].pb(v);
G[v].pb(u);
}
dfs(1, 0);
printf("%lld\n", max(f[1][0], f[1][1]));
}
return 0;
}


D. Kavi on Pairing Duty

Soulution:
f[i]n=i 的可行解数量

1.包含情况：

2.相等情况： 只有在线段长度为 n 的因子时才存在方案

f_i=\sum_{j=1}^{n-1}{f_j+}\pi \left( i \right), 其中\pi \left( i \right)表示i的因子个数

Code:

int n;
ll f[N], D[N];

int main(){
__;
for(int i = 1; i < N; i ++){
for(int j = i; j < N; j += i){
D[j] ++;
}
}
f[1] = 1, f[2] = 3;
ll res = f[1] + f[2];
cin >> n;
for(int i = 3; i <= n; i ++){
f[i] = (res + D[i]) % mod;
res = (res + f[i]) % mod;
}
printf("%lld\n", f[n]);
return 0;
}