|
|
A Maxmina
代码实现
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n, k;
cin >> n >> k;
vector<int> a(n);
for(auto &x : a) cin >> x;
if (a == vector<int>(n, 0)) cout << &#34;NO&#34; << &#39;\n&#39;;
else cout << &#34;YES&#34; << &#39;\n&#39;;
}
}
B Rebellion
#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5;
int a[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
set<int> s;
for(int i = 1; i <= n; i++){
cin >> a;
if (a == 0) s.insert(i);
}
int ans = 0;
for(int i = 1; i <= n; i++){
if (s.empty()) break;
if (a == 0){
s.erase(i);
}
else{
ans++;
s.erase(prev(s.end()));
}
}
cout << ans << &#39;\n&#39;;
}
}
C Permutation Operations
分析
这题一开始题给读错了,以为是每次操作给每个后缀加一,想了半天没想出来咋做,后来重新读题发现每次操作是加i...
首先通过操作我们一定可以把逆序对的数量变为0.我们发现只要对于每个a_i < a_{i-1}的位置,在i处操作直至a_i = a_{i - 1}就能删除所有逆序对,所以需要操作的地方一共最多只有n处,而这些位置差的和不会超过n,所以n次操作一定可以删除所有的逆序对,给这些位置排一下序贪心的去操作即可.
代码实现
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5;
int a[maxn];
pair<int, int> d[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a;
d = {a - a[i - 1], i};
}
sort(d + 1, d + n + 1);
for(int i = n; i >= 1; i--)
cout << d.second << &#34; \n&#34;[i == 1];
}
}
D Paths on the Tree
分析
显然每条路径一定尽可能地长比较好,所以每条路径一定是根到某个叶子结点.
我们可以发现对于每个结点,经过其的路径数最多只有两种取值,且一定为k, k + 1(差不超过1)的形式,简单用归纳法证明一下.
- 首先根节点的取值数量只有1种,为了方便证明我们也可以写成k, k + 1的形式.
- 若某个结点的的取值为k, k + 1(1) 如果其只有一个儿子,那么儿子的取值也是k, k + 1,不超过两种(2) 若其不止一个儿子,假设儿子数量为s.当k = 0(\bmod \ s)时,儿子的取值只有两种\frac{k}{s}, \frac{k}{s} + 1,当k \ne 0(\bmod \ s)时,儿子的取值也只有两种\lfloor \frac{k}{s} \rfloor, \lfloor \frac{k}{s} \rfloor + 1.所以如果父亲的取值是k, k + 1这样形式,其儿子的取值范围一定也是k, k + 1的形式,所以树中所有结点都满足取值最多只有两种,且差值不超过1.
然后我们就可以做树形DP,对于每个儿子求出其两种取值时DP值分别是多少,设儿子j取k/k+1时DP值为f_{j, 0/1},求完后我们可以把儿子按照f_{j,1} - f_{j,0}排序,优先让f_{j,1} - f_{j,0}比较大的儿子取值取到k+1即可.总复杂度为O(n\log{n}).
代码实现
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
using LL = long long;
using PLL = pair<LL, LL>;
const int maxn = 4e5 + 5;
vector<int> g[maxn];
int p[maxn], w[maxn];
LL f[maxn][2];
void dfs(int u, int p1, int p2){
f[0] = 1LL * p1 * w;
f[1] = 1LL * p2 * w;
if (g.empty()) return;
vector<PLL> v;
for(auto j : g){
dfs(j, p1 / g.size(), p1 / g.size() + 1);
v.push_back({f[j][0], f[j][1]});
f[0] += f[j][0];
f[1] += f[j][0];
}
sort(v.begin(), v.end(), [&](PLL &a, PLL &b){
return a.second - a.first > b.second - b.first;
});
{
int t = p1 - p1 / g.size() * g.size();
for(int i = 0; i < t; i++)
f[0] += v.second - v.first;
}
{
int t = p2 - p1 / g.size() * g.size();
for(int i = 0; i < t; i++)
f[1] += v.second - v.first;
}
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
g.clear();
for(int i = 2; i <= n; i++){
cin >> p;
g[p].push_back(i);
}
for(int i = 1; i <= n; i++) cin >> w;
dfs(1, k, k + 1);
cout << f[1][0] << &#39;\n&#39;;
}
}
本文使用 Zhihu On VSCode 创作并发布
|
|
发表于 2022-11-29 13:57:06