10.31日模拟赛总结

文章目录

  • 考试时间及策略
  • 考试结果
  • 考试反思
  • 题解
      • A.进步科学
      • B.吉吉没急
      • C.老杰克哒
      • D.季积晓淆

考试时间及策略

没啥好说的,因为好像都不会。所以全场感觉都在罚坐,很痛苦。

考试结果

30 + 0 + 50 + 5 = 85

考试反思

T1:T1是个神奇状压,感觉确实想不到。还是记住这个技巧吧。
T2:也是一道很难的题,会不了一点。
T3:只会 50pts 贪心的,没想出来暴力DP。如果能想出来暴力DP应该能想到正解吧。
T4:好像是FTT,会不了一点。

题解

A.进步科学

在这里插入图片描述

分析:
      正常状压感觉没有什么阶段,我们设 d p i , m a s k dp_{i,mask} dpi,mask 表示第 i i i 秒所有树上的节点的状态为 m a s k mask mask 是否可行。
      然后转移我们考虑若 d p i , m a s k = 1 dp_{i, mask} = 1 dpi,mask=1,那么我们让导致这个状态的操作整体后移1s,并且枚举第一秒操作哪个节点或者不操作节点。这样的好处是第 i + 1 i + 1 i+1 秒 可以直接继承第 i i i 秒的状态,不用再考虑前 i i i 秒的操作会不会在 第 i + 1 i + 1 i+1 秒产生影响。
      我们设 j u m p i , j jump_{i, j} jumpi,j 表示如果扭动了第 i i i 个点,在扭动 j j j 秒后每个点的状态(最开始都是 0 0 0)。我们可以预处理出来 j u m p jump jump 数组,然后转移 就是如果第一秒扭动了点 u u u,那么 d p i , m a s k → d p i + 1 , m a s k ⊕ j u m p u , i dp_{i, mask} \to dp_{i+1, mask \oplus jump_{u, i} } dpi,maskdpi+1,maskjumpu,i。最后如果某一时刻询问的状态为 1 1 1 就直接输出就好了。可以想到最多 n n n 秒就一定能得到答案。

CODE:

#include<bits/stdc++.h>// 设dp[i][mask] 表示i时刻状态为mask是否可行 
using namespace std;// 我们考虑 i -> i + 1 的时候, 把操作往后平移一个单位,然后在第一时刻操作一个数。
const int N = 17;
bool dp[N][1 << 16]; 
int jump[N][N], fa[N], n, k, mask;
int main(){freopen("decoration.in", "r", stdin);freopen("decoration.out", "w", stdout); scanf("%d", &n);for(int i = 2; i <= n; i++){scanf("%d", &fa[i]); }for(int i = 1; i <= n; i++){scanf("%d", &k);if(k) mask |= (1 << (i - 1));}for(int i = 1; i <= n; i++){int now = i; k = 0;jump[i][0] = (1 << (i - 1));for(int j = 1; j <= n; j++){if(fa[now]) jump[i][j] = (jump[i][j - 1] | (1 << (fa[now] - 1))), now = fa[now];else jump[i][j] = jump[i][j - 1];}}dp[0][0] = 1;for(int i = 0; i <= n; i++){//最多n秒就可以了 for(int j = 0; j < (1 << n); j++){if(dp[i][j]){dp[i + 1][j] |= dp[i][j];//第一秒啥也不干 for(int k = 1; k <= n; k++){dp[i + 1][j ^ jump[k][i]] |= dp[i][j];  // 第一秒选择了k,剩下的平移,那么可以抵消 }}}if(dp[i][mask]){printf("%d\n", i);break;}}return 0;
}

B.吉吉没急

在这里插入图片描述

分析:
      很神奇的一道题。
      我们首先把最后确定没学会算法的人当成一个限制。也就是说,我们考虑通过这些人来给其他人加一个限制。
      具体来说,我们设 h i h_{i} hi 表示每个人 允许最早在什么时间学会算法。如果 x x x 最后没有学会,那么 h i = I N F h_i = INF hi=INF。我们跑一边 dijkstra ,设当前在堆头的点编号为 u u u,与它连边的点是 v v v,边的出现时间范围时 [ l , r ] [l,r] [l,r]。若 h u > r h_u > r hu>r,说明如果 v v v 这个人想要学会算法,最早得在 l + 1 l + 1 l+1 时刻,因为我们至少要拿出 1 s 1s 1s 使得这个时刻 v v v 还没学会算法, u u u 此时和他吃饭。而 l + 1 l + 1 l+1 相当与是这个限制的极限。我们将 h v h_v hv 赋值成 m a x ( h v , l + 1 ) max(h_v, l + 1) max(hv,l+1),如果更新了放入堆中。如果 h u ≤ r h_u \leq r hur,也就意味着 h u h_u hu 允许在 r r r 之前学会算法,所以 h v h_v hv 什么时候学会都无所谓,我们只需要让边在某一个合适的时刻出现就好了。
      跑完一边 dijkstra 后,我们检验一下 h 1 h_1 h1 是否大于 0 0 0。如果 h 1 h_1 h1 大于 0 0 0,那么一定无解,因为这意味着 1 1 1 号点不允许一开始就学会算法,与条件是冲突的。
      否则,我们设 d i d_i di 表示每个点在满足 h i h_i hi 的限制下(也就是 d i d_{i} di 要大于等于 h i h_i hi)最早能够什么时候学会算法。因为每一个点越早学会算法,才越有可能教会其他最后确定学会的人。开始时 d 1 = 0 d_1 = 0 d1=0,其他的点设成 I N F INF INF,最后我们只需要检验所有确定学会的人 x x x 他的 d x d_x dx 是否等于 I N F INF INF 就好了。如果有一个等于,那么无解,否则有解。
      相当于 h h h 数组用来检验能否满足让确定学不会的人能够学不会, d d d 数组用来保证确定学会的人可以学会。

CODE:

#include<bits/stdc++.h>// 首先根据不能学会算法的人求出每一个人学会算法的最早时间 
using namespace std;// 然后在大于等于这个最早时间的前提下,每个人学会算法的时间应该尽可能早,这样能保证传递给后面的人 
const int N = 2e5 + 10;
int read(){int x = 0, f = 1; char c = getchar();while(!isdigit(c)){if(c == '-') f = -1, c = getchar();}while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
struct edge{int v, last, l, r;
}E[N * 2];
struct state1{int x, val;bool operator < (const state1 &a)const{return a.val > val;}
};
struct state2{int x, val;bool operator < (const state2 &a)const{return a.val < val;}
};
priority_queue< state1 > q1;
priority_queue< state2 > q2; 
const int INF = 1e9;
int head[N], n, m, u, v, l, r, d[N], h[N], tot, flag[N];
void add(int u, int v, int l, int r){E[++tot].v = v; E[tot].last = head[u];E[tot].l = l;E[tot].r = r;head[u] = tot;
}
bool vis[N];
void dijkstra1(){memset(vis, 0, sizeof vis);while(!q1.empty()){state1 u = q1.top(); q1.pop();int x = u.x, val = u.val;if(vis[x]) continue;vis[x] = 1;for(int i = head[x]; i; i = E[i].last){int v = E[i].v, l = E[i].l, r = E[i].r;if(h[x] > r){if(h[v] < l + 1){h[v] = l + 1;q1.push((state1){v, h[v]}); }}}}
}
void dijkstra2(){memset(vis, 0, sizeof vis);while(!q2.empty()){state2 u = q2.top(); q2.pop();int x = u.x, val = u.val;if(vis[x]) continue;vis[x] = 1;for(int i = head[x]; i; i = E[i].last){int v = E[i].v, l = E[i].l, r = E[i].r;if(d[x] > r) continue;if(h[v] <= r){if(max(d[x], max(h[v], l)) < d[v]){d[v] = max(d[x], max(h[v], l));q2.push((state2){v, d[v]});}}}}
}
int main(){freopen("lunch.in", "r", stdin);freopen("lunch.out", "w", stdout);n = read(), m = read();for(int i = 1; i <= m; i++){u = read(), v = read(), l = read(), r = read();add(u, v, l, r);add(v, u, l, r);}for(int i = 1; i <= n; i++){flag[i] = read();}for(int i = 1; i <= n; i++){if(flag[i] == -1) h[i] = INF, q1.push(state1{i, h[i]});}dijkstra1();for(int i = 1; i <= n; i++){if(h[1] > 0){printf("Impossible\n");return 0;}}memset(d, 0x3f, sizeof d);d[1] = 0;q2.push((state2){1, 0});dijkstra2();for(int i = 1; i <= n; i++){if(flag[i] == 1 && d[i] == 0x3f3f3f3f){printf("Impossible\n");return 0;}}printf("JJXSM\n");return 0;
}

C.老杰克哒

在这里插入图片描述

分析:
      首先我们把区间内划分成若干 1 1 1 的连续段,那么对于一段,最多花费 2 2 2 的代价把它消除:我们可以现在后面加1,然后进位后在前面减1。并且一段至少需要花费1的代价。
      基于上面的想法,我们可以考虑从后往前扫段,如果当前段长度大于1,那么就让它进位,否则就直接删掉。注意:进位后可能会与前面组成1段。所以这样做时肯定优的。贪心可以得到 50pts。
      但是这样做没有什么优化的空间。我们考虑dp。
      设 d p i , 0 / 1 dp_{i, 0/1} dpi,0/1 表示从开头到 i i i,字符串变成先一段连续的 0 0 0,然后一段连续的 0 / 1 0/1 0/1 的最小代价。考虑转移:

      如果第 i i i 位是 0 0 0

      d p i , 0 ← d p i − 1 , 0 dp_{i, 0} \leftarrow dp_{i-1, 0} dpi,0dpi1,0 d p i , 0 ← d p i − 1 , 1 + 2 dp_{i,0} \leftarrow dp_{i-1, 1} + 2 dpi0dpi1,1+2
      d p i , 1 ← d p i − 1 , 0 + 1 dp_{i, 1} \leftarrow dp_{i - 1, 0} + 1 dpi,1dpi1,0+1 d p i , 1 ← d p i − 1 , 1 + 1 dp_{i, 1} \leftarrow dp_{i - 1, 1} + 1 dpi,1dpi1,1+1

      解释一下上面的转移, d p i , 0 dp_{i, 0} dpi,0 可以由 d p i − 1 , 0 dp_{i - 1, 0} dpi1,0 转移而来,代表什么也不操作, d p i , 0 dp_{i, 0} dpi,0 d p i − 1 , 1 + 2 dp_{i - 1, 1} + 2 dpi1,1+2 转移过来,代表我们可以通过加1减1两次操作把前面的一段1给消除完,这样多的花费是2。 d p i , 1 dp_{i, 1} dpi,1 的转移同理。

      如果第 i i i 位是 1 1 1

      d p i , 0 ← d p i − 1 , 0 + 1 dp_{i, 0} \leftarrow dp_{i - 1, 0} + 1 dpi,0dpi1,0+1 d p i , 0 ← d p i − 1 , 1 + 2 dp_{i, 0} \leftarrow dp_{i - 1, 1} + 2 dpi,0dpi1,1+2
      d p i , 1 ← d p i − 1 , 0 dp_{i, 1} \leftarrow dp_{i - 1, 0} dpi,1dpi1,0 d p i , 1 ← d p i − 1 , 1 dp_{i, 1} \leftarrow dp_{i - 1, 1} dpi,1dpi1,1
      这转移和上面的是同理的。

      那么对每一次询问,我们设左端点是 s t st st,实际上就是按照 S s t S_{st} Sst 的类型给 d p s t , 0 / 1 dp_{st, 0/1} dpst,0/1 一个初值,然后 O ( n ) O(n) O(n)转移。

      我们发现转移是取 m i n min min,并且这个转移方式只跟当前为字符是 0 0 0 还是 1 1 1 有关。并且和矩阵乘法很想。我们对应 0 0 0 1 1 1,直接构造两种矩阵,然后用线段树维护区间内矩阵的乘积,加速转移就好了。

CODE:

#include<bits/stdc++.h>// 每一次转移可以看做是乘一个矩阵 
using namespace std;// 用线段树维护矩阵的乘积
const int N = 3e5 + 10;
struct matrix{int mt[2][2];friend matrix operator * (matrix a, matrix b){matrix c; memset(c.mt, 0x3f, sizeof c.mt);for(int i = 0; i <= 1; i++)for(int j = 0; j <= 1; j++)for(int k = 0; k <= 1; k++)c.mt[i][j] = min(c.mt[i][j], a.mt[i][k] + b.mt[k][j]);return c;}
};
matrix m1, m2;
struct SeqmentTree{int l, r; matrix mt;#define l(x) t[x].l#define r(x) t[x].r#define mt(x) t[x].mt
}t[N * 4]; 
int n, m, opt, x, y;
char str[N];
int read(){int x = 0, f = 1; char c = getchar();while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
void build(int p, int l, int r){l(p) = l, r(p) = r;if(l == r) return ;int mid = (l + r >> 1);build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);
}
void update(int p){mt(p) = mt(p << 1) * mt(p << 1 | 1);}
void ins(int p, int pos, matrix c){if(l(p) == r(p)){mt(p) = c;return ;}int mid = (l(p) + r(p) >> 1);if(pos <= mid) ins(p << 1, pos, c);else ins(p << 1 | 1, pos, c);update(p);
}
matrix ask(int p, int l, int r){if(l <= l(p) && r >= r(p)) return mt(p);int mid = (l(p) + r(p) >> 1);if(r <= mid) return ask(p << 1, l, r);else if(l > mid) return ask(p << 1 | 1, l, r);else return ask(p << 1, l, r) * ask(p << 1 | 1, l, r);
}
int query(int l, int r){matrix res;if(str[l] == '1') res.mt[0][0] = 1, res.mt[0][1] = 0;else res.mt[0][0] = 0, res.mt[0][1] = 1;if(l == r) return res.mt[0][0];matrix tmp = ask(1, l + 1, r);res = res * tmp;return res.mt[0][0];
}
int main(){freopen("string.in", "r", stdin);freopen("string.out", "w", stdout);n = read(); scanf("%s", str + 1);int len = strlen(str + 1);m1.mt[0][0] = 0; m1.mt[0][1] = 1; m1.mt[1][0] = 2; m1.mt[1][1] = 1;m2.mt[0][0] = 1; m2.mt[0][1] = 0; m2.mt[1][0] = 2; m2.mt[1][1] = 0;build(1, 1, n);for(int i = 1; i <= len; i++){if(str[i] == '0') ins(1, i, m1);else ins(1, i, m2);}m = read();for(int i = 1; i <= m; i++){opt = read(), x = read(), y = read();if(opt == 1) printf("%d\n", query(x, y));else{if(y == 0) ins(1, x, m1);else ins(1, x, m2);str[x] = (y + '0');}}return 0;
}

D.季积晓淆

在这里插入图片描述

分析:
会不了一点

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/177162.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【java学习—十一】泛型(1)

文章目录 1. 为什么要有泛型Generic2. 泛型怎么用2.1. 泛型类2.2. 泛型接口2.3. 泛型方法 3. 泛型通配符3.1. 通配符3.2. 有限制的通配符 1. 为什么要有泛型Generic 泛型&#xff0c;JDK1.5新加入的&#xff0c;解决数据类型的安全性问题&#xff0c;其主要原理是在类声明时通过…

通过Google搜索广告传送的携带木马的PyCharm软件版本

导语 最近&#xff0c;一起新的恶意广告活动被发现&#xff0c;利用被入侵的网站通过Google搜索结果推广虚假版本的PyCharm软件。这个活动利用了动态搜索广告&#xff0c;将广告链接指向被黑客篡改的网页&#xff0c;用户点击链接后下载的并不是PyCharm软件&#xff0c;而是多种…

矢量图形编辑软件illustrator 2023 mac中文软件特点

illustrator 2023 mac是一款矢量图形编辑软件&#xff0c;用于创建和编辑排版、图标、标志、插图和其他类型的矢量图形。 illustrator 2023 mac软件特点 矢量图形&#xff1a;illustrator创建的图形是矢量图形&#xff0c;可以无限放大而不失真&#xff0c;这与像素图形编辑软…

leetcode:1446. 连续字符(python3解法)

难度&#xff1a;简单 给你一个字符串 s &#xff0c;字符串的「能量」定义为&#xff1a;只包含一种字符的最长非空子字符串的长度。 请你返回字符串 s 的 能量。 示例 1&#xff1a; 输入&#xff1a;s "leetcode" 输出&#xff1a;2 解释&#xff1a;子字符串 &q…

Spire.doc读取模板文档,并在书签处插入内容

在书签位置插入文字 //加载模板文档 Document document new Document(Server.MapPath("~/File/评价结果.doc")); //创建书签导航器 BookmarksNavigator bn new BookmarksNavigator(document); //添加一个section到文档 Section newSec document.AddSection(); …

Java设计模式之命令模式

目录 定义 结构 案例 优点 缺点 使用场景 JDK源码解析 Thread中start与run方法的区别 定义 将一个请求封装为一个对象&#xff0c;使发出请求的责任和执行请求的责任分割开。这样两者之间通过命令对象进行沟通&#xff0c;这样方便将命令对象进行存储、传递、调用、增…

字体文件名称成中的Bold, Light,Italic,Regular, Medium是什么意思?

解释 字体文件名&#xff1a; IntelOneMono-Bold.ttf其中IntelOneMono字体名称 Bold 字体的样式 .ttf字体后缀 样式英文 中文Bold粗体BoldItalic粗体斜体Italic斜体Light细体LightItalic斜细体Medium中等MediumItalic中等斜体Regular标准以下来自鸿蒙字体以下来自鸿蒙字体TC…

大坝水库安全监测终端MCU,智能化管理的新篇章!

我国目前拥有超过9.8万座水库大坝&#xff0c;其中超过95%为土石坝&#xff0c;这些大坝主要是在上世纪80年代以前建造的。这些水库大坝在保障防洪、发电、供水、灌溉等方面发挥了巨大的作用&#xff0c;但是同时也存在一定的安全风险&#xff0c;比如坝体结构破损、坝基渗漏、…

基于 Center 的 3D 目标检测和跟踪

论文地址&#xff1a;https://arxiv.org/abs/2006.11275 论文代码&#xff1a;https://github.com/tianweiy/CenterPoint 3D 目标通常表示为点云中的 3D Boxes。 CenterPoint 在第一阶段&#xff0c;使用关键点检测器检测对象的中心&#xff0c;然后回归到其他属性&#xff0…

接入文心一言实战(一):API申请与测试

大家好&#xff0c;我是豆小匠。 这期来介绍申请百度文心一言API的步骤。 第一步 注册百度智能云账号 网址&#xff1a;https://login.bce.baidu.com/new-reg?tplbceplat&fromportal 第二步&#xff1a;申请预置模型 网址&#xff1a;https://console.bce.baidu.com/qi…

在虚拟机centos7中部署docker+jenkins最新稳定版

在虚拟机centos7中部署dockerjenkins最新稳定版 查看端口是否被占用 lsof -i:80 查看运行中容器 docker ps 查看所有容器 docker ps -a 删除容器 docker rm 镜像/容器名称 强制删除 docker rmi -f 镜像名 查看当前目录 pwd 查看当前目录下所有文件名称 ls 赋予权限 chown 777 …

unity中meta文件GUID异常问题

错误信息&#xff1a; The .meta file Assets/Scripts/Editor/ConvertConfigToBinary/TxtConverter.cs.meta does not have a valid GUID and its corresponding Asset file will be ignored. If this file is not malformed, please add a GUID, or delete the .meta file and…

【C语法学习】6 - gets()函数

文章目录 1 函数原型2 参数3 返回值4 读取机制5 示例 1 函数原型 gets()&#xff1a;从标准输入流stdin读取一个字符串存储到str指向的内存空间&#xff0c;函数原型如下&#xff1a; char *gets(char *str)2 参数 gets()函数的参数只有一个str&#xff1a; str是一个指向c…

智力测试情商测试小程序源码/带流量主提升智力微信小程序源码

智力测试情商测试小程序源码&#xff0c;这是一个考验智力&#xff0c;心理上面的一个测试游戏&#xff0c;支持多种测试方法。 比如有: 智商测试丨情商测试 | 性格测试丨爱情测试 | 抑郁症测试丨焦虑症测试 | 心理压力测试丨生活满意度测试&#xff0c;通过不同的测试&#xf…

win10pycharm和anaconda安装和环境配置教程

windows10 64位操作系统下系统运行环境安装配置说明 下载和安装Anaconda&#xff0c;链接https://www.anaconda.com/download 下载完后&#xff0c;双击exe文件 将anaconda自动弹出的窗口全部关掉即可&#xff0c;然后配置高级系统变量 根据自己的路径&#xff0c;配置…

如何在Linux命令行界面愉快进行性能测试?

本人在做性能测试的过程中&#xff0c;遇到一个问题&#xff0c;测试机选了一台Linux服务器&#xff0c;只有命令行界面。执行测试用例不是非常的灵活&#xff0c;有时候我需要改一两个参数添加一些日志&#xff0c;都需要重新打包部署&#xff0c;虽然自动化构建比较方便&…

vscode debug skills

1) VSCode 调试 C/C 代码时&#xff0c;如何显示动态分配的指针数组。 创建一个动态分配的一维数组: int n 10; int *array (int *)malloc(n*sizeof(int)); memset(array, 1, n*sizeof(int)); 如果直接 Debug 时查看 array 指针&#xff0c;并不能看到数组所有的值。 查看…

从用户角度出发,如何优化大数据可视化体验|北京蓝蓝UI设计公司

作者&#xff1a;蓝蓝设计-鹤鹤 大数据已经成为人们探索世界的新工具。但是&#xff0c;对于普通用户而言&#xff0c;大数据往往比较抽象和难以理解&#xff0c;因此&#xff0c;大数据可视化作为一种非常有效的工具工具被广泛应用。然而&#xff0c;在实际应用中&#xff0c…

【Java笔试强训】Day8(WY20 两种排序方法、HJ108 求最小公倍数)

WY20 两种排序方法 链接&#xff1a;两种排序方法 题目&#xff1a; 考拉有n个字符串字符串&#xff0c;任意两个字符串长度都是不同的。考拉最近学习到有两种字符串的排序方法&#xff1a; 1.根据字符串的字典序排序。例如&#xff1a; “car” < “carriage” < “c…

pycharm安装教程-pycharm安装详细步骤(Mac版)

之前跟大家讲了怎么安装Python&#xff0c;这期跟大家介绍个很好用的编程工具–pycharm。 PyCharm是一种Python IDE&#xff0c;带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具&#xff0c;比如调试、语法高亮、Project管理、代码跳转、智能提示、自动完成、单…