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

CSP-S 22

9.16

原来史可以连着吃

挂了100

t1

简单贪心,不多解释。

没有大样例爆了

code

点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18;
int minn;
int T;
int cnt2, cnt3, cnt4;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> T;while (T--){cin >> cnt2 >> cnt3 >> cnt4;int ans = 0;if (cnt3 == cnt4 && cnt3 == 0){cout << cnt2 / 5 << "\n";continue;}if (cnt3 / 2 >= cnt4) // 3 3 4{ans += cnt4;cnt3 -= 2 * cnt4;if (cnt3 >= cnt2) // 2 2 3 3ans += cnt2 / 2;else{ans += cnt3 / 2;cnt2 -= cnt3 / 2 * 2;//注意 /2 后再*2 ,只有满2才减ans += cnt2 / 5; // 2 2 2 2 2}}else // 剩2,4{ans += cnt3 / 2;cnt4 -= cnt3 / 2;if (cnt2 > cnt4 / 2) // 2 4 4{ans += cnt4 / 2;cnt2 -= cnt4 / 2;if (cnt4 % 2 == 1)if (cnt2 >= 3)++ans, cnt2 -= 3;ans += cnt2 / 5;}elseans += cnt2;}cout << ans << "\n";}return 0;
}

t2

考虑分成链与点dp ,详见代码

code

点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10;
const int mod = 998244353;
int n, ans;
int a[N], dp[N];inline int km(int a, int b)
{int ans = 1;while (b){if (b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i)//将边看作有向cin >> a[i];sort(a + 1, a + 1 + n); // 排序并不影响结果,有序更好算dp[0] = 1;for (int i = 1; i <= n; ++i){for (int j = a[i - 1] + 1; j <= a[i]; ++j) for (int k = j; k; --k)dp[k] = (dp[k] + dp[k - 1]) % mod; // 倒序避免更新重 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]ans = (ans + dp[1]) % mod;ans = (ans - a[i]) % mod;for (int j = 1; j <= a[i]; ++j)dp[j - 1] = (dp[j - 1] + (j - 1) * j % mod * dp[j] % mod) % mod;}cout << ans * km(2, mod - 2) % mod << "\n";//正向与反向,/2return 0;
}

t3

不是哥们,wyx \(O(n^2log_n)\) 过了,我的就 T ??? (虽然正解 \(O(nlog_n)\)

正解为树型dp状物。

code

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k;
vector<int> e[N];
int dis[N], cnt, lim;void dfs(int x, int f)
{dis[x] = 1;for (auto y : e[x]){if (y == f)continue;dfs(y, x);dis[x] = min(dis[x], dis[y] + 1);}for (auto y : e[x]){if (y == f)continue;if (dis[x] + dis[y] <= 0)continue;dis[x] = max(dis[x], dis[y] + 1);}if (dis[x] > lim)dis[x] = -lim, ++cnt;
}inline bool check(int up)
{lim = up;cnt = 0;dfs(1, 0);if (dis[1] > 0)++cnt;return cnt <= k;
}inline int fen()
{int l = 1, r = n, ans = r;while(l<=r){int mid = (l + r) >> 1;if(check(mid))r = mid - 1, ans = mid;elsel = mid + 1;}return ans;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;for (int i = 1, u, v; i < n; ++i){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}int ans = fen();cout << ans;return 0;
}

t4

咕,太过神秘了。

累了,不想写了,凑合看。

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

相关文章:

  • 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
  • Vue 项目 AI 文档增量更新工具操作手册
  • 4060显卡也能玩转AI改图!Flux.1 Kontext Dev GGUF版本超详细入门教程 - 实践