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

CSP-S 20

9.11

今天是挂分的好日子~~~

101=0+10+91

t1 追逐游戏 (chase)

倍增+k祖先

算了不想写了.......

第2次没保存然后死机丢失了...

不难理解也不难实现,细节手模即可。

t1 就这样吧,看代码。

code

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, q;
vector<int> e[N];
int fa[N][20], dep[N];void dfs1(int x, int f)
{fa[x][0] = f;dep[x] = dep[f] + 1;for (int i = 1; i <= 19; ++i)fa[x][i] = fa[fa[x][i - 1]][i - 1];for (auto y : e[x])if (y != f)dfs1(y, x);
}int LCA(int x, int y)
{if (dep[x] < dep[y])swap(x, y);for (int i = 19; ~i; --i)if (dep[fa[x][i]] >= dep[y])x = fa[x][i];if (x == y)return x;for (int i = 19; ~i; --i)if (fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];return fa[x][0];
}inline int get_dis(int x, int y)
{int lca = LCA(x, y);return dep[x] + dep[y] - 2 * dep[lca];
}inline int jump_k(int x, int k)
{for (int i = 19; ~i; --i) //~i --> i>=0!!!!!!!if (k & (1 << i))x = fa[x][i];return x;
}inline void solve(int x, int y)
{int dis = get_dis(x, y);int k = (dis + 1) >> 1;cout << k << ' ';if (dep[x] < dep[y])swap(x, y), k = dis - k;cout << jump_k(x, k) << "\n";
}signed main()
{freopen("chase.in", "r", stdin);freopen("chase.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> q;for (int i = 1, u, v; i < n; ++i){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs1(1, 0);int s1, t, s2;while (q--){cin >> s1 >> t >> s2;int dis1 = get_dis(s1, t);int dis2 = get_dis(s2, t);if (dis1 < dis2)cout << dis2 << ' ' << t << "\n";elsesolve(s1, s2);}return 0;
}

t2 统计

赛时用memset挂了20pts...

正解巧妙。

类似异或哈希做法。

具体的:

对于 \(1\)\(m-1\) 中每个数随机一个哈希值,令 \(v_m=-\sum_{i=1}^{m-1}v_i\)

这样做可使满足要求的区间 \(l,r\)\(sum_r-sum_{l-1}\) 为0.

考虑快速统计答案:

\(sum\) 升序排列,之后快速统计。

“快速统计”部分看代码理解(语文功底太差导致的)。

code

点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int T;
int n, m;
int a[N], sum[N], v[N];mt19937_64 myrand(time(0));signed main()
{freopen("st.in", "r", stdin);freopen("st.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> T;while (T--){cin >> n >> m;for (int i = 0; i <= n; ++i)sum[i] = 0, v[i] = 0;for (int i = 1; i < m; ++i)v[i] = myrand(), v[m] -= v[i];for (int i = 1; i <= n; ++i)cin >> a[i], sum[i] = sum[i - 1] + v[a[i]];sort(sum, sum + 1 + n); // 注意必须手动保证sum[0]为0!!!int cnt = 1, ans = 0;for (int i = 1; i <= n; ++i){if (sum[i] != sum[i - 1])cnt = 0;ans += cnt++;}cout << ans << "\n";}return 0;
}

t3 软件工程

抽象东西假贪心有 96pts!!?

假做法:

code

点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e9 + 7;
int n, k;
bool flag[N];
struct node
{int l, r, id;
} a[N], b[N];inline bool cmp1(node a, node b) { return a.l < b.l; }
inline bool cmp2(node a, node b) { return a.l > b.l; }signed main()
{freopen("se.in", "r", stdin);freopen("se.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;for (int i = 1; i <= n; ++i){cin >> a[i].l >> a[i].r;a[i].id = i;b[i].l = a[i].r - a[i].l, b[i].r = i;}int ans = 0;if (k >= n){for (int i = 1; i <= n; ++i)ans += a[i].r - a[i].l;cout << ans << "\n";return 0;}sort(a + 1, a + 1 + n, cmp1);sort(b + 1, b + 1 + n, cmp2);for (int i = 1; i <= k - 1; ++i)ans += b[i].l, flag[b[i].r] = 1;int l = 0, r = inf;for (int i = 1; i <= n; ++i){if (flag[a[i].id])continue;l = max(l, a[i].l), r = min(r, a[i].r);}if (l < r)ans += r - l;memset(flag, 0, sizeof(flag));//下面几乎一样的部分你可以理解成针对hack的特判int maxn = 0, dat1 = 0, dat2 = 0;// for (int i = 1; i <= n; ++i)//     cerr << a[i].l << ' ' << a[i].r << "\n";for (int i = 1; i < n; ++i){if (min(a[i].r, a[i + 1].r) - a[i + 1].l > maxn)maxn = min(a[i].r, a[i + 1].r) - a[i + 1].l, dat1 = a[i].id, dat2 = a[i + 1].id;}int ans2 = maxn;// cerr << dat1 << ' ' << dat2 << "\n";flag[dat1] = flag[dat2] = 1;for (int i = 1; i <= min(k - 2, n); ++i){if (flag[i])continue;ans2 += b[i].l, flag[b[i].r] = 1;}l = 0, r = 1e9;for (int i = 1; i <= n; ++i){if (flag[a[i].id])continue;l = max(l, a[i].l), r = min(r, a[i].r);}// cerr << l << ' ' << r << "\n";// cerr << ans2 << "\n";if (l < r)ans2 += r - l;cout << max(ans,ans2) << '\n';return 0;
}

至于真的:

t4 命运的X

看看题解说的:
1

http://www.hskmm.com/?act=detail&tid=35308

相关文章:

  • 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] 自动好友
  • 软件工程第二次团队作业
  • 超越技术范畴:低代码如何重塑企业数字文化
  • 歌手与模特儿
  • 20251019
  • 十六天
  • 计算机毕业设计 基于EChants的海洋气象数据可视化平台设计与建立 Python 大数据毕业设计 Hadoop毕业设计选题【附源码+文档报告+安装调试】
  • https://www.luogu.com.cn/problem/CF1635E
  • ZR 2025 NOIP 二十连测 Day 5
  • SpringBoot整合Redis教程
  • [VIM] reverse multiple lines in VIM