A. Maximum Cake Tastiness
直接排序输出前两个元素的和。
可以证明一定存在序列最大值，能够在其左右两侧找到序列次大值并通过一次reverse操作将次大值换到最大值旁边。所以找到最大值次大值相加即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
inline void solve(){
int n = 0; std::cin >> n;
for(int i = 1; i <= n; i++) std::cin >> a[i];
std::sort(a + 1, a + 1 + n, [&](int a, int b){ return a > b; });
std::cout << a[1] + a[2] << '\n';
}
signed main(){
int t = 0; std::cin >> t;
while(t--) solve();
return 0;
}
B. Prefix Removals
打一个std::map记录每个字符出现的次数。从前往后判断，直到当前字符在后面不再出现。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N], vis[N];
inline void solve(){
std::string s; cin >> s;
memset(vis, 0, sizeof vis);
for(int i = 0; i < s.size(); i++) vis[s[i]]++;
for(int i = 0; i < s.size(); i++){
if(vis[s[i]] == 1){
for(int j = i; j < s.size(); j++) cout << s[j];
cout << endl;
return;
}
else vis[s[i]] -= 1;
}
}
signed main(){
int t = 0; std::cin >> t;
while(t--) solve();
return 0;
}
C. Alice and the Cake
先求出总体的体积，然后开一个优先队列暴力拆解，然后每次判断能否拆解。能拆解就继续拆。如果拆到最后拆不出给定的情况，则输出NO。
显然，对于一个数字
n
n
n，最多拆解
log
?
(
n
)
\log(n)
log(n)次。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
#define YES std::cout << "YES" << '\n'
#define NO std::cout << "NO" << '\n'
std::priority_queue<int, vector<int>, greater<int>> pq;
std::map<int, int> mp;
inline void solve(){
mp.clear();
while(pq.size()) pq.pop();
int n = 0, sum = 0; std::cin >> n;
for(int i = 1; i <= n; i++) std::cin >> a[i], sum += a[i], mp[a[i]]++;
pq.emplace(sum);
while(pq.size()){
int now = pq.top(); pq.pop();
auto fnd = mp.find(now);
if(fnd == mp.end() || fnd -> second == 0){
if(now == 1){ NO; return; }
else { pq.emplace(now >> 1); pq.emplace(now - (now >> 1)); }
}
else fnd -> second -= 1;
}
YES;
}
signed main(){
int t = 0; std::cin >> t;
while(t--) solve();
return 0;
}
D. Potion Brewing Class
牛逼
一共有
n
n
n种药水，现在给你
n
?
1
n - 1
n?1个药水的配比，要求你求出至少要多少瓶药水。
由于题目保证答案一定存在，那么可以认为
n
?
1
n - 1
n?1个药水配比一定构成树形结构。如果构成多个连通块，由于连通块间总配比无法确定而会导致答案不存在。
那么首先建出树的结构，然后从根节点开始对所有的分母分解质因数，然后计算出每个质因子所需的个数。然后从根节点开始更新答案即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int MOD = 998244353;
const int maxn = 1e6 + 10;
int prime[maxn];
int vis[maxn], inv[maxn];
int a[N], cnt = 0;
#define YES std::cout << "YES" << '\n'
#define NO std::cout << "NO" << '\n'
void get() {
inv[1] = 1;
for(int i = 2; i <= 200010; i++){
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}
for (int i = 2; i <= 200000; i++){
if (!a[i]){
prime[++cnt] = i;
a[i] = i;
}
for (int j = 1; j <= cnt && i * prime[j] <= 200000; j++){
a[i * prime[j]] = prime[j];
if (i % prime[j] == 0) break;
}
}
}
struct edge{ int v, x, y; };
std::vector<edge> g[N];
int binpow(int x, int y, int mod = MOD, int res = 1){
for (; y; y >>= 1, (x *= x) %= mod) if (y & 1) (res *= x) %= mod;
return res;
}
inline void solve(){
int n = 0, ans = 0; std::cin >> n;
for(int i = 1; i <= n; i++) { vis[i] = 0; g[i].clear(); }
for(int id = 1; id <= n - 1; id++){
int i, j, x, y; std::cin >> i >> j >> x >> y;
int d = __gcd(x, y);
x /= d, y /= d;
g[i].emplace_back(edge{j, x, y});
g[j].emplace_back(edge{i, y, x});
}
std::function<void(int, int)> dfs1 = [&](int now, int fa){
for(auto nxt : g[now]){
int to = nxt.v, nx = nxt.x, ny = nxt.y;
if(to == fa) continue;
while(nx > 1){
if(vis[a[nx]] > 0) vis[a[nx]]--;
nx /= a[nx];
}
while(ny > 1){
vis[a[ny]]++;
ny /= a[ny];
}
dfs1(to, now);
nx = nxt.x, ny = nxt.y;
while(nx > 1){
vis[a[nx]]++;
nx /= a[nx];
}
while(ny > 1){
vis[a[ny]]--;
ny /= a[ny];
}
}
};
std::function<void(int, int, int)> dfs2 = [&](int u, int fa, int res){
ans = (ans + res) % MOD;
for(auto nxt : g[u]){
int to = nxt.v, nx = nxt.x, ny = nxt.y;
if(to == fa) continue;
dfs2(to, u, (res * inv[nx] % MOD * ny) % MOD);
}
};
dfs1(1, -1);
int tmp = 1;
for(int i = 1; i <= n; i++){
if(vis[i]) tmp = (tmp * binpow(i, vis[i])) % MOD;
}
dfs2(1, -1, tmp);
std::cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
get();
int t = 0; std::cin >> t;
while(t--) solve();
return 0;
}
|