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

2020CSP-J2比赛记录题解

题目请看洛谷

备注:这次比赛我是没打的


T1

先把数转成二进制,逐位计算,并判断是否可完整正确拆分

贴一下代码
#include <bits/stdc++.h>
using namespace std;
#define fre(c) freopen(c".in","r",stdin);freopen(c".out","w",stdout);
#define ll long long
#define endl "\n"
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define cst const
cst ll N = 1e3 + 5;
ll n, a[N], cnt, now = 1;
ll read() {char c;ll sum = 0, f = 1;c = getchar();while (!isdigit(c)) {if (c == '-')f *= -1;c = getchar();}while (isdigit(c)) {sum = sum * 10 + (c - '0');c = getchar();}return sum * f;
}
int main() {
//	ios
//	fre("")n = read();if (n % 2 == 1) {cout << -1;return 0;}now = 1;while (now <= n) now *= 2;while (n > 0) {	if (now <= n) {	a[cnt ++] = now; n -= now; } now /= 2; }for (int i = 0; i < cnt; i ++) { if (i > 0) {cout << " ";} cout << a[i]; }return 0;
}

赛时:-point

赛后:100point


T2

以前看过思路

用个桶存,无脑sort也可以拿分,存储分数线低的位置,听说还可以用对顶堆

贴一下代码
#include <bits/stdc++.h>
using namespace std;
#define fre(c) freopen(c".in","r",stdin);freopen(c".out","w",stdout);
#define ll long long
#define endl "\n"
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define cst const
cst ll N = 1e3 + 5;
ll n, w, x, a[N], sum;
ll read() {char c;ll sum = 0, f = 1;c = getchar();while (!isdigit(c)) {if (c == '-')f *= -1;c = getchar();}while (isdigit(c)) {sum = sum * 10 + (c - '0');c = getchar();}return sum * f;
}
int main() {
//	ios
//	fre("")n = read();w = read();for (ll i = 1; i <= n; i ++) {x = read();a[x] ++;sum = 0;for (ll j = 600; j >= 0; j --) {sum += a[j];if (sum >= max(1LL, i * w / 100)) {cout << j << " ";break ;}}}return 0;
}

赛时:-point

赛后:100point


T3

先用转成栈,接着变成树形结构

贴一下标程
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 1000005;char s[N];
int a[N];
int son[N][2], ck;
int flag[N], c[N];
int n, q;
int dfs(int u, int g) {a[u] ^= g;if (u <= n) {return a[u];}int x = dfs(son[u][0], g ^ flag[son[u][0]]);int y = dfs(son[u][1], g ^ flag[son[u][1]]);if (a[u] == 2) {if (x == 0) c[son[u][1]] = 1;if (y == 0) c[son[u][0]] = 1;return x & y;} else {if (x == 1) c[son[u][1]] = 1;if (y == 1) c[son[u][0]] = 1;return x | y;}
}
void dfs2(int u) {if (u <= n) return;c[son[u][0]] |= c[u];c[son[u][1]] |= c[u];dfs2(son[u][0]);dfs2(son[u][1]);
}
int main() {// freopen("expr.in", "r", stdin);// freopen("expr.out", "w", stdout);gets(s);scanf("%d", &n);ck = n;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}stack<int> b;for (int i = 0; s[i]; i += 2) {if (s[i] == 'x') {int x = 0;i++;while (s[i] != ' ') {x = x * 10 + s[i] - '0';i++;}i--;b.push(x);} else if (s[i] == '&') {int x = b.top();b.pop();int y = b.top();b.pop();b.push(++ck);a[ck] = 2;son[ck][0] = x;son[ck][1] = y;} else if (s[i] == '|') {int x = b.top();b.pop();int y = b.top();b.pop();b.push(++ck);a[ck] = 3;son[ck][0] = x;son[ck][1] = y;} else if(s[i] == '!'){flag[b.top()] ^= 1;}}int ans = dfs(ck, flag[ck]);dfs2(ck);scanf("%d", &q);while (q--) {int x;scanf("%d", &x);printf("%d\n", c[x] ? ans : !ans);}return 0;
}

赛时:-point

赛后:-point

T4

记忆化搜索,分析来时路

贴一下代码
#include <bits/stdc++.h>
using namespace std;
#define fre(c) freopen(c".in","r",stdin);freopen(c".out","w",stdout);
#define ll long long
#define endl "\n"
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define cst const
cst ll N = 1e3 + 5;
ll n, m, a[N][N], dp[N][N];
inline ll read() {char c;ll sum = 0, f = 1;c = getchar();while (!isdigit(c)) {if (c == '-')f *= -1;c = getchar();}while (isdigit(c)) {sum = sum * 10 + (c - '0');c = getchar();}return sum * f;
}
int main() {
//	ios
//	#ifdef debug
//		fre("D")
//	#endifn = read();m = read();for (ll i = 1; i <= n; i ++) {for (ll j = 1; j <= m; j ++) {a[i][j] = read();}}for (ll i = 1; i <= n; i ++) {dp[i][1] = dp[i - 1][1] + a[i][1];}for (ll j = 2; j <= m; j ++) {vector<ll> left(n + 2), right(n + 2);left[1] = dp[1][j - 1] + a[1][j];for (ll i = 2; i <= n; i ++) {left[i] = max(left[i - 1], dp[i][j - 1]) + a[i][j];}right[n] = dp[n][j - 1] + a[n][j];for (ll i = n - 1; i >= 1; i --) {right[i] = max(right[i + 1], dp[i][j - 1]) + a[i][j];}for (ll i = 1; i <= n; i ++) {dp[i][j] = max(left[i], right[i]);}}cout << dp[n][m];return 0;
}

赛时:-point

赛后:100point


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

相关文章:

  • Binder.getCallingPid()和Binder.getCallingUid()漏洞分析
  • 让博客园设置支持PlantUml画图
  • 光谱相机的未来趋势 - 详解
  • Hall定理学习笔记
  • Vue3快速上手 - Ref
  • 象棋图片转FEN字符串详细教程
  • 面向对象抽象,接口多态综合-动物模拟系统
  • MinGW-即时入门-全-
  • 自然语言处理在风险识别中的应用
  • cat
  • qt everywhere souce code编译 - 实践
  • 2023 CCPC final G
  • 2025 年高可靠性测试设备/HALT/HASS/Halt/Hass/厂家制造商推荐榜:聚焦高效质量解决方案,助力企业产品升级
  • 八字手链人物传记计划——旭
  • 20232309 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 亚马逊发布基于Linux的Vega OS电视系统,禁止侧载应用
  • .net9.0 JWT AUTH2.0 添加身份认证授权
  • 扣子系列教程
  • 解决vscode中用npm报错
  • MATLAB复杂曲线曲面造型及导函数实现
  • 2025 年最新月嫂培训机构推荐榜单:短期 / 精英 / 金牌 / 高端月嫂培训及就业推荐,精选优质机构
  • OOP-实验一
  • 达梦使用jemalloc内存分配器
  • 2025 年深圳/龙岗/龙华/罗湖/南山/旧房翻新/出租房/二手房/老房/装修公司推荐:聚焦品质与服务,助您轻松焕新家
  • 2025 年中频炉厂商最新推荐排行榜权威发布,深度剖析应达电气等优质企业核心优势及选购要点节能/智能/自动化成套/高效率/智能感应加热中频炉厂家推荐
  • 2025 年气体/实验室/调压/气路/减压阀厂家推荐榜:聚焦安全与专业,助力各行业精准选品
  • 摸鱼混子回归 - ZERO
  • vue3实现抓拍并上传
  • 2025 年国内润滑油厂商最新推荐榜:聚焦优质品牌实力,助力企业精准选品润滑油净化/过滤/回用/液压油润滑油过滤厂商推荐
  • 纯前端实现项目过期