首页 > 其他分享 >ACM模拟赛10.3

ACM模拟赛10.3

时间:2022-10-07 13:22:08浏览次数:82  
标签:10 10.3 le 题意 矩阵 ACM LV 相连 模拟

ACM模拟赛10.3

第一场还算是正式的ACM模拟赛,毛子营的题目,10道题场上只会2道,害怕。

B Divide and Conquer

题意

\(n\) 个点 \(m\) 条边的无向图,你要找到一个点 \(x\) ,使得所有和这个点相连的点都两两相连,所有不和这个点相连的点都两两不相连。

保证有解。

\(1\le n\le 10^6,0\le m\le 10^6\) 。

题解

感觉很妙的一道题,想了很久。

考虑这个点 \(x\) 满足什么性质,不妨记与 \(x\) 相连的点集为 \(S\) ,不与 \(x\) 相连的点集为 \(T\) ,往点的度数方向去想,那么有 \(d_x=|S|\) ,并且 \(\forall i\in S, d_i\ge |S|\) , \(\forall i\in T,d_i\le |S|\) 。证明很简单, \(S\) 中的点至少要和 \(S\) 内的点以及 \(x\) 相连,而 \(T\) 中的点只能和 \(S\) 中的点相连。

另外,我们还可以发现,如果 \(x\) 满足条件,那么所有 \(d_y=d_x\) 的 \(y\) 也会满足条件。分情况讨论即可:如果 \(y\in S\) ,那么 \(y\) 恰好与 \(S\) 和 \(x\) 相连,与 \(T\) 不相连,所以 \(y\) 满足;如果 \(y\in T\) ,那么 \(y\) 恰好与 \(S\) 中每个点都相连,且它不与 \(T\) 中其它点以及 \(x\) 相连,所以 \(y\) 也满足。

到了这里 \(O((n+m)\sqrt m)\) 的做法就很显然了,直接枚举度数可能的值然后暴力判断,我们场上写了这个做法然后过了。

后来发现一种更优美的做法,仍然是之前的性质,如果 \(x\) 满足条件,那么它必然和 \(\{y|d_y>d_x\}\) 相连,与部分 \(\{y|d_y=d_x\}\) 相连,与 \(\{y|d_y<d_x\}\) 不相连。这个的一个必要条件是 \(|\{y|d_y>d_x\}|<d_x<|\{y|d_y\ge d_x\}|\) 。而且我们可以发现,这样满足条件的度数是唯一的,而题目中保证有解,所以只需要扫一遍即可找到答案。(当然,不保证有解也可以先这样找到度数再判断即可)

复杂度 \(O(n+m)\) 。

C Spatial Thinking

题意

场上题意是真看不懂,感谢室友让我知道这题是要干啥。。。

将一个 \(n\) 维空间内的棱长为 \(1\) 的单位立方体任意切分成 \(n!\) 个单纯形(由你决定如何切分),要求单纯形每个顶点都在立方体上,再给定 \(m\) 个点,你需要判断每个点在哪个单纯形内(如果在交界处任意输出一个)。

\(2\le n\le 8,0\le m\le 10^5\) 。

题解

切分方法就是选取一个 \(n\) 的排列,然后从 \((0,0,\dots,0)\) 开始,依次将这些位置从 \(0\) 改成 \(1\) 。

找在哪个单纯形内就直接按照大小关系康托展开即可。

D Palindromes

题意

给定一个 \(m\) 行 \(n\) 列的字符矩阵,将其划分成尽量少的若干连续列,使得每个连续列至少有一行回文。

\(1\le m\le 10,1\le n\le 10^5\) 。

题解

额,这题我场上居然没切,果然降智到了极点。。。

[最小回文划分](回文树 - OI Wiki (oi-wiki.org))的模板,复杂度 \(O(mn\log n)\) 。

当作复习回文树喽。

E Travelling by River

题意

河流上有 \(n\) 个港口和 \(m\) 条航线,其中保证任意一条航线连接的两个点编号不超过 \(k\) 。

港口按照 \(1\sim n\) 的顺序从下游排列到上游,某人计划依次经过 \(q\) 个港口并列出了列表,但是它发现路线太长了,于是按照以下策略保留要依次经过的港口:从左到右考虑列表中每个港口,第一个港口必去,下一个港口不被删除当且仅当它不与前一个港口相同并且可以由前一个港口不回头走到。

给出最终的行走路线。

\(2\le n\le 2\cdot 10^5,0\le m\le 2\cdot 10^5,1\le k\le 200,1\le q\le 2\cdot 10^5\) 。

题解

直接分治,从中间 \(k\) 个港口切开,如果要左右互到,则必然经过中间这些港口,于是压位记录每个点是否能不回头到达这中间 \(k\) 个港口,然后递归考虑。

容易发现时间复杂度为 \(O((nk\log n+qk)/64)\) 。

H Beautiful Pairs

题意

\(n\) 次询问每次询问给定 \(l,r\) 问 \([l,r]\) 内有多少数对 \((a,b)\) 满足 \(b|(a^2-1)\) 且 \(a|(b^2-1)\) 。

\(1\le n\le 10^5,1\le l\le r\le 10^{18}\) 。

题解

口胡的,没写,场上和队友一起找规律找了很久,最后找到了来不及写了。

考虑构造一个这样的矩阵 \(A\) ,满足 \(A_{i,1}=1,A_{i,2}=i+1,A_{i,j}=(i+1)*A_{i,j-1}-A_{i,j-2}\) 。

这样数对 \((a,b)\) (不妨假设 \(a<b\) )满足条件当且仅当存在 \(i,j\) 使得 \(A_{i,j}=a,A_{i,j+1}=b\) 。

求矩阵中某个元素可以用矩阵快速幂,前 \(k\) 行二分找答案,后面在 \(\log_k V\) 列里面二分找答案,复杂度大概是 \(O(n(k\log V+\log_kV\log^2V))\) 。

I Binary Matrices

题意

给定下列代码:

calc (n, x, p, q) {
  ans = 0;
  do n times {
    x = x * p + q;
    lhs = x;
    x = x * p + q;
    rhs = x;
    ans = sum(ans, multiply(hls, rhs));
  }
  return ans;
}

其中 \(x,p,q\) 的类型都是 unsigned long long ,加法和乘法都是自然溢出。

sum(a, b) 函数将两个值转化为 \(8\times 8\) 的二进制矩阵然后相加再转化回值传回。

multiply(a, b) 函数将两个值转化为 \(8\times 8\) 的二进制矩阵然后相乘再转化回值传回。

注意:矩阵中的值相加为不进位二进制加法。

calc (n, x, p, q) 的返回值。

\(1\le n\le 10^7,0\le x,p,q\le 10^{18}\) 。

时限 2s 。

题解

就恁卡常。

矩阵相加就是异或。

矩阵相乘先拆分成行和列,这样矩阵乘法的时候就可以通过与运算统计 \(1\) 的数量实现,运算次数 \(8\times 8\) 。

拆分成行简单,拆分成列就先矩阵转置,预处理一行转置成一列即可,运算次数 \(3\times 8\) 。

卡卡常勉强飘过。

J Quake

题意

LV 在打一个 Boss ,该游戏为回合制游戏,每个回合 LV 有 \(p\%\) 的概率击败 Boss ,而 Boss 有 \(1-(p\%)\) 的概率打败 LV ,如果 LV 打败 Boss \(n\) 次他就赢了,如果 Boss 打败 LV \(m\) 次 LV 就输了,并且 LV 输后游戏立即重启,双方打败次数归零,当然 LV 也可以选择在游戏任一回合结束后立即重启游戏,次数归零,问 LV 至少赢一次期望需要多少回合。

\(1\le n,m\le 10^3,0<p<100\) 。

题解

最水的一道题。

设 \(f(a,b)\) 表示 LV 已打败 \(a\) 次而 Boss 已打败 \(b\) 次后 LV 获胜的期望步数,那么有:

\[f(a,b)=\min(p\%\cdot f(a+1,b)+(1-p\%)\cdot f(a,b+1)+1,f(0,0)) \]

二分 \(f(0,0)\) ,看看求出的 \(f(0,0)\) 会不会比二分的更小即可。

时间复杂度 \(O(nm\log V)\) ,其中 \(V\) 为精度。

标签:10,10.3,le,题意,矩阵,ACM,LV,相连,模拟
From: https://www.cnblogs.com/lsq147/p/16759570.html

相关文章

  • 46th 2022/10/7 模拟赛总结33
    这次算是一个高光时刻吧rank2,不错的排名需要肯定但是,还是有所惰性,虽然今天可以理解,因为左眼有点肿?本次其实个人认为,rank2超级好拿,T1老老实实打了二分优化拿80,然后趁着......
  • 2022.10.3线段树复习笔记(未完待续)
    线段树原理及存储:如图,1即为根节点,存储着[1,5]的整个区间和,‘1’为左边界,‘5’为右边界,所以此节点表示的是[1,5]这个区间。线段树的每个节点向下二分,左儿子的编号为此节......
  • 10.6 模拟赛总结
    10.6模拟赛总结T1光大意:给定四个方块的需要的亮度值,有光的散射,每个方块对于另外三个有影响,问四个亮度值之和最小为多少。$n\le1500$思路:一眼看出是二分答案的判定性......
  • 10.6 noi(p) 模拟赛
    \(\rmNOIP\)模拟赛\(\rmDate:10.6\)去掉T1可以当省选练习题了(当然T4放T1)\(T1\)哈希即可,也有贪心的做法,但是自然溢出被卡了\(T2\)如果是一条链,那么这个操作......
  • JZOJ 7685. 【2022.10.06冲剌NOIP2022模拟】奇怪的函数(function)
    \(\text{Solution}\)观察到关于\(x\)的函数在\(n\)个操作之后一定是这样的:一段水平直线加上一段斜率为\(1\)的直线再加上一段水平直线于是线段树维护这个分段函数......
  • java--equals和模拟用户登录卫语句
    1.什么是卫语句卫语句就是把复杂的条件表达式拆分成多个条件表达式,减少嵌套。嵌套了好几层的if-then-else语句,转换为多个if语句,实现它的逻辑,这多条的if语句就是卫语句......
  • 玩转华为ENSP模拟器系列 | 两个网关之间通过IKE方式协商IPSec VPN隧道(采用预共享密钥
    素材来源:华为防火墙配置指南一边学习一边整理试验笔记,并与大家分享,侵权即删,谢谢支持!附上汇总贴:​​玩转华为ENSP模拟器系列|合集_COCOgsta的博客-CSDN博客_华为模拟器实验......
  • ts+vite3+vue3+mock+qs实现本地模拟数据功能
    第一步:安装qs因为项目中用到了ts,所以还需要安装:第二步:安装mock第三步:创建Vue页面:Category.vue<template><button@click="getById">getById</button><button......
  • 使用mock.js来模拟后台数据的方案
    如何在项目中引入mockjs,从而实现脱离后端数据,前端做假数据来独立开发业务逻辑。一.安装依赖npmimockjs--save-dev二.使用mock按照业务模块建立一个文件来写模拟......
  • 44th 2022/10/5 模拟赛总结31
    这次不好,大危本次打得可以说一塌糊涂,主要是比赛时,轻视题目,做得飞快,但是忽略了很多细节甚至是题目如T2,生成树的概念和子树弄混,炸裂,一个图的生成树要经过所有节点如T3,忽......