当前位置: 首页 > news >正文

CSP-S 31

10.14

看大家得分跟信心赛似的,就我一个唐诗写了一场暴力 \(\ldots\)

开场t1没切出来就开始慌了,之后就想着多打暴力拿部分分,导致t2得出的性质没有推广,t3,t4暴力都没写出来(这俩得出性质/部分性质后比暴力好写多了)\(\ldots\)

t1

看到题就想二分,结果根本就分不出来 \(\ldots\)

发现我好像对于在线查询有种别样的执着,每次都不会离线和预处理 \(\ldots\)

观察到值域很小,空间可接受,于是直接一个 \(O(nV)\) 巨大预处理,之后单次询问是 \(O(\log(n)\log(V))\) ,所以总复杂度为 \(O(nV+q\log(n)\log(V))\)(其实还有单log做法)。

预处理:对于每个 \(x\) ,记录所有 \(x|a_i=x\)\(i\) ,查询时二分查找即可。

code

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int n, q;
int a[N], b[N];
vector<int> f[1024];inline long long solve(int l, int r, int x)
{long long ans = 0;int now = l;while (now <= r){// cerr << "&\n";if (f[x].size() == 0 || f[x][f[x].size() - 1] < now)break;// cerr << "!\n";int id = *lower_bound(f[x].begin(), f[x].end(), now);if (id > r)break;// int nxt = f[x][id];ans += b[id], x -= a[id];now = id + 1;// cerr << "id=" << id << " now=" << now << "\n";}// cerr << "$ans=" << ans << "\n";return ans;
}signed main()
{
#ifndef ANSfreopen("expedition.in", "r", stdin);freopen("expedition.out", "w", stdout);
#elsefreopen("ex_expedition1.in", "r", stdin);freopen("1.out", "w", stdout);
#endifios::sync_with_stdio(0);cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i){cin >> a[i];for (int val = a[i]; val <= 1023; ++val){if ((val | a[i]) == val)f[val].emplace_back(i);}}for (int i = 1; i <= n; ++i)cin >> b[i];cin >> q;int l, r, x;long long ans = 0;while (q--){cin >> l >> r >> x;ans ^= solve(l, r, x);}cout << ans;return 0;
}

t2

树的性质是好观察的,层数之差为奇数答案为 1 ,否则答案为 2 。

其实继续思考(或观察大阳历)就能发现答案只有 \(-1,0,1,2\) 但是我当时甚至都没有多看那两个非树的大阳历一眼 \(\ldots\)

继续推广可知,当两点间距离为奇数时,答案为 1 ,否则为 2 (在同一连通块内)。

考虑加边:满3加边,若存在奇环,则块内任意两点都可通过环改变这两点路径的奇偶性(画图可知)。

因此重点为判奇环。

奇偶染色即可。

具体看代码

code

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, n, m, q, cnt;
vector<int> e[N];
bool flag[N], gd[N];
int col[N], belong[N];void dfs(int x, int pre)
{belong[x] = cnt;if (col[x] && col[x] != pre)gd[cnt] = 1;elsecol[x] = pre;flag[x] = 1;for (auto y : e[x]){if (col[y] && col[y] == pre)gd[cnt] = 1;if (flag[y])continue;dfs(y, ((pre - 1) ^ 1) + 1);}
}signed main()
{freopen("teleport.in", "r", stdin);freopen("teleport.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> T;cin >> n >> m;for (int i = 1, u, v; i <= m; ++i){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}for (int i = 1; i <= n; ++i){if (!flag[i])++cnt, dfs(i, 1);}// for (int i = 1; i <= n; ++i)//     cerr << col[i] << "\n";// cerr << gd[1] << "\n";cin >> q;int s, t;while (q--){cin >> s >> t;if (s == t){cout << 0 << "\n";continue;}if (belong[s] != belong[t]){cout << -1 << "\n";continue;}if (gd[belong[s]]){cout << 1 << "\n";continue;}if (col[s] != col[t])cout << 1 << "\n";elsecout << 2 << "\n";}return 0;
}

t3

这题我觉得简单思考就解决了,但我当时一心暴力。

限制转化为形如 xxyzxy

之后暴力枚举 x,y,z 即可。

60pts

考虑到对于 z 只要求与 x,y 不同即可,根本不用枚举。

于是\(O(nk^2)\) ,通过。

code

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 114514;
string s;
int n, ans;inline int sum(int x)
{if (x >= mod)return x - mod;return x;
}inline void solve(char x, char y)
{int len1 = 0, len2 = 0, len3 = 0, len4 = 0, len5 = 0, len6 = 0;for (int i = 1; i <= n; ++i){if (s[i] == x){len5 += len4, len2 += len1, ++len1;len5 = sum(len5), len2 = sum(len2), len1 = sum(len1);}else if (s[i] == y){len6 += len5, len3 += len2;len6 = sum(len6), len3 = sum(len3);}else{len4 += len3;len4 = sum(len4);}}ans += len6;ans = sum(ans);
}signed main()
{freopen("anc.in", "r", stdin);freopen("anc.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> s;n = s.size();s = " " + s;for (int i = 1; i <= 26; ++i)for (int j = 1; j <= 26; ++j){if (i == j)continue;solve((char)i + 'a' - 1, (char)j + 'a' - 1);}cout << (ans + mod) % mod;return 0;
}
http://www.hskmm.com/?act=detail&tid=35316

相关文章:

  • 后缀树
  • ES原理、zookeeper、kafka
  • CF1606E Arena 题解(动态规划)
  • 服务器CPU市场概况2025
  • CSP-S 24
  • 读书笔记:深入理解java虚拟机
  • CSP-S 19
  • CSP-S 20
  • Flutter应用设置插件 - 轻松打开iOS和Android系统设置
  • CSP-S 22
  • Project. 2025.11化学小组pre
  • MySQLDay1
  • 蛋白表达标签:重组蛋白研究的精妙引擎
  • 106.腾讯地图位置服务再出错
  • 心理咨询系统
  • Adaptive Learning Rate(自适应学习率) - -一叶知秋
  • Luogu P10034 「Cfz Round 3」Circle 题解 [ 蓝 ] [ 背包 DP ] [ 质数筛 ] [ 图论 ] [ 构造 ]
  • 2025.10.20模拟赛
  • SQLite简单使用
  • 新学期每日总结(第12天)
  • 2025.10.20总结 - A
  • CF2107E Ain and Apple Tree
  • 傻瓜式处理kauditd0病毒程序记录
  • win10 升级 win11 后时间更新失败
  • 2025,为什么公众号编辑器排版决定阅读完成率?——一次从流程到结果的深评
  • 软件工程学习日志2025.10.20
  • P14254 分割(树上计数问题) 题解
  • P14262 [ROI 2015 Day1] 自动好友
  • 软件工程第二次团队作业
  • 超越技术范畴:低代码如何重塑企业数字文化