巅峰赛 #30 T1-T5 题解
2026-02-01 22:31:02
发布于：广东
15阅读
0回复
0点赞
不是今晚打的也不是昨晚打的。
速写这一块。
下次巅峰赛一定要快点出难一点的 T6 啊，这是我了解算法模板的唯一途径
T1
显然能翻转就翻转。这不需要证吧。
然后随便写一下就行了。
namespace cjdst{
void solve(){
int n;
std::string a;
std::cin >> n >> a;
a = " " + a + " ";
int cur = '0', ans = 0;
for(int i = 1; i <= n; i++){
if(a[i] != cur) ans++, cur = a[i];
}
std::cout << ans << '\n';
}
}
时间复杂度：。
T2
强烈谴责 ACGO 没标数据范围这一行为。
显然加到刚好大于就行了。这不需要证吧。
然后随便写一下就行了。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
ll cur = -0x3f3f3f3f3f3f3f3fll, ans = 0;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
if(a[i] <= cur) ans += (cur + 1 - a[i]), a[i] = cur + 1;
cur = a[i];
}
std::cout << ans << '\n';
}
}
时间复杂度：。
T3
叽里咕噜说什么呢。
先转化一下，将边权对 取模显然没有影响。然后求的就是这些路径的和为偶数。注意到一个 数列和为偶数，那异或和一定为 。
考虑强化问题。我们统计出所有路径异或之和，然后拿总路径数减去它即可。
注意到求路径异或和这个问题我刚好做过，是 A75099。具体可以参考这个题解。
然后稍微改改就出来了。
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
vector <pair <int, int>> v2[200005];
vector <int> v[200005];
int a[200005];
int cnt0[60], cnt1[60];
int n;
void dfs(int cur, int fa){
for(auto i:v2[cur]){
if(i.first == fa) continue;
a[i.first] = i.second;
a[i.first] ^= a[cur];
dfs(i.first, cur);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
int x, y, z;
cin >> x >> y >> z;
v2[x].push_back({y, abs(z) % 2});
v2[y].push_back({x, abs(z) % 2});
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 60; j++){
if(a[i] >> j & 1) ans += (__int128(cnt0[j]) << j), cnt1[j]++;
else ans += (__int128(cnt1[j]) << j), cnt0[j]++;
}
}
cout << 1ll * n * (n - 1) / 2 - ans << '\n';
return 0;
}
时间复杂度：，其中 。其实 可以直接取到 ，但我懒得改了。
T4
好题。
注意到先不下降再不上升可以拆成两段：不下降，不上升。
所以考虑建分层图。对于不下降部分，将点权小的连向点权大的；对于不上升部分，将点权大的连向点权小的；然后每个不下降部分的点都连向不上升部分的对应点。
然后跑不下降 不上升 最短路即可。
namespace cjdst{
void solve(){
int n, m, s, t;
std::cin >> n >> m >> s >> t;
std::vector <int> a(n + 5);
std::vector <std::vector <pii>> v(n * 2 + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
v[i].push_back({i + n, 0});
}
for(int i = 1; i <= m; i++){
int x, y, z;
std::cin >> x >> y >> z;
if(a[x] <= a[y]){
v[x].push_back({y, z});
v[y + n].push_back({x + n, z});
}
if(a[x] >= a[y]){
v[y].push_back({x, z});
v[x + n].push_back({y + n, z});
}
}
std::priority_queue <pll, std::vector <pll>, std::greater <pll>> q;
std::vector <ll> dis(n * 2 + 5, 0x3f3f3f3f3f3f3f3fll);
std::vector <int> vis(n * 2 + 5);
q.push({0, s});
while(!q.empty()){
auto head = q.top();
q.pop();
if(vis[head.second]) continue;
vis[head.second] = 1;
for(auto it:v[head.second]){
if(dis[it.first] > head.first + it.second){
dis[it.first] = head.first + it.second;
q.push({dis[it.first], it.first});
}
}
}
if(dis[t + n] == 0x3f3f3f3f3f3f3f3fll){
std::cout << "-1\n";
}else std::cout << dis[t + n] << '\n';
}
}
时间复杂度：。
T5
注意到只选一个即可使得 ，所以 。
然后发现第一个数只要不是 ，要想 ，那后面的必须是正数；第一个数是 那后面的选啥都行。
所以我们求出后缀的正数数量，然后分为 和非 处理。
namespace cjdst{
void solve(){
ll n, mod;
std::cin >> n >> mod;
std::vector <int> ksm(n + 5);
ksm[0] = 1;
for(int i = 1; i <= n; i++){
ksm[i] = ksm[i - 1] * 2 % mod;
}
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::vector <int> suf(n + 5);
for(int i = n; i; i--){
suf[i] = suf[i + 1] + (a[i] > 0);
}
ll ans = 0;
for(int i = 1; i <= n; i++){
if(a[i] != 0) ans += ksm[suf[i + 1]];
else ans += ksm[n - i];
ans %= mod;
}
std::cout << "0 " << ans << '\n';
}
}
时间复杂度：。
全部评论 6
其实 T1 贪心还有另一种实现方法：
n = int(input()) s = input() ans = 0 t = 0 for c in s: if (int(c) ^ t) == 1: ans += 1 t ^= 1 print(ans)t是当前位被反转的奇偶昨天 来自 北京
1
有帮助，赞一个