1 Zc_Ethan

尚未进行身份认证

我要认证

一个优秀的OI选手,都是从WA山T海走出来的

等级
TA的排名 12w+

洛谷君のNOIP。のCSP信心赛B题题解(动规,思维,次大)

T2题目大意给定一个矩阵(n∗mn*mn∗m),则你可以求从左上走到右下路径上的权值累加和的最大值(要求只能向右或下走)。此时你可以将其中的任意一个元素改成0,求改动哪一个元素,可以使最大值最小。并输出这个最小的最大值。题解这题的难点就是在你可以将一个格子变成0,那么不妨我们来思考如何求不变成0的最大值。那就是一道方格取数的问题,dpdpdp的入门题。设dp[i][j]dp[i][j]dp[i][j]表示从(1,1)→(i,j)(1,1)\to(i,j)(1,1)→(i,j)的路径权值的最大值,

2020-10-05 21:27:47

洛谷君のNOIP。のCSP信心赛A题题解(记忆化搜索,分治)

T1题目大意给定一个nnn和kkk,然后求按照一定的要求,在nnn个座位的圆桌上最多坐的人的数量。要求:1、第一个人选择一号位  \qquad\,\, 2、接下来每个人会坐在离最近的人尽可能远的位置  \qquad\,\, 3、每个人离最近的人之间的空位子数量不得小于kkk题解对于10%10\%10%由于k=0k=0k=0,可以直接输出nnn。不知道各位的想法如何,我十分敏感地想到了毕导的这个视频,当场就喊出来了。这实在是太像了。于是我就顺着毕导的思路做这道题:答案是在kkk确定的前提

2020-10-04 23:16:25

2020初赛重点题解析及解题技巧-part1 选择

Before All本文题目链接全部采用洛谷的初赛题集,如果无法正常打开,请根据描述自行上网搜索。打开后按照原文进行查找,文中给出格式"NOIPNOIPNOIP年份-题号"。当然,你不想开直接看文章也不拦着你。选择题第一台计算机是ENIACENIACENIAC,诞生于美国宾夕法尼亚大学,使用电子管,此后发展出晶体管,集成电路,超大集成电路。重要人物,图灵→\to→人工智能之父,冯诺依曼→\to→计算机之父,香农→\to→信息论创始人。存取速度:CPU内部(寄存器)>>>Ca

2020-09-25 21:56:59

所有正整数的和是多少?

背景介绍最近看B站看到有这样一个题。1+2+3+4+⋯+∞=?1+2+3+4+\dots +\infty=?1+2+3+4+⋯+∞=?这不是很简单吗?没有上限,那么肯定还是∞\infty∞喽。诶,和我想的一样。但是数学题是不能用直觉来做的,需要深入思考。解题方法首先设3个数:S1=1−1+1−1+1…S_1=1-1+1-1+1\dotsS1​=1−1+1−1+1…S2=1−2+3−4+5…S_2=1-2+3-4+5\dotsS2​=1−2+3−4+5…S=1+2+3+4+5…S=1+2+3

2020-08-27 13:48:05

2020牛客暑期多校训练营Identical Trees(树形dp,KM算法)

Identical Trees题目描述样例input:30 1 13 3 0output:2题目大意给定同构两棵树(即形状一样,保证有解),现在你可以将第一棵树中的任意一个节点编号改成任意一个数。现问最少需要多少次操作才能将第一棵树改成与第二棵树相同。相同的要求是对于每个节点其父节点相同,但是对于一个节点其子节点的顺序可以不一样。分析这题比赛的时候乱做搞了一个树形dpdpdp,然后WAWAWA得不成样子,蒙了半天。当然这题确实是树形dpdpdp,因为我们可以只考虑一棵树的子树,

2020-08-12 17:01:38

2020牛客暑期多校训练营Groundhog Playing Scissors(计算几何,线段交,暴力)

Groundhog Playing Scissors题目描述样例input:43 3-3 3-3 -33 -352 -1 2 1output:0.6098题目大意在坐标系中给出一个凸多边形,并可以绕原点旋转。现有一条线段,要求凸多边形旋转某个度数后,线段不能够将凸多边形截成两半(如果线段不够长就无法做到)的概率。分析很多dalao都是用三分做的,比较麻烦。这题有更加简洁的方式。可以考虑精度误差。由于题目只需要我们保留4位小数,在时间充足的情况下,完全可以枚举。枚举多边形

2020-08-11 18:54:44

2020牛客暑期多校训练营Decrement on the Tree(图论,set)

Decrement on the Tree题目描述样例input:5 31 2 31 3 42 4 53 5 61 102 103 10output:8121010题目大意给你一棵树,现在你可以选择其中的一条链,将其边上的权值都减一。并且每条边的权值不能为负数。要求最少要删除多少次(每次只能减一),才能使得整棵树的权值都是0。(只需要输出答案,而不是修改)并且,在给出答案之后,会有qqq次修改,将某一条边的权值改成另一个,这时你要再一次输出答案。分析首先看到题目有

2020-08-11 14:03:29

2020牛客暑期多校训练营Hearthstone Battlegrounds(贪心,模拟)

Hearthstone Battlegrounds题目描述样例input:31 0 1 01 0 1 01 0 0 10 1 1 01 0 0 11 0 1 0output:YesYesNo题目大意炉石传说玩过吗?没玩过就不要做了。看不懂的。给定4种类型的人鱼:K1:K1:K1:带有剧毒,圣盾,亡语。K2:K2:K2:带有剧毒,圣盾。K3:K3:K3:带有剧毒,亡语。K4:K4:K4:带有剧毒。...

2020-08-10 22:02:56

2020牛客暑期多校训练营Tournament(构造)

Tournament题目描述样例input:234output:1 21 32 31 21 31 42 32 43 4题目大意有nnn支队伍两两之间比赛一场,则进行n(n−2)2\frac{n(n-2)}{2}2n(n−2)​场。现每支队伍会从他们要比赛的第一天开始直到他们的比赛的最后一场为止,即安排中他们队伍最后出现的那天为止,都会待在比赛场地里。现你可以安排比赛顺序,要求如何安排会使得所有队伍待在场地里的时间总合最小。分析首先想到的是:for(i  from

2020-08-10 20:31:19

2020牛客暑期多校训练营Groundhog and Gaming Time(数学期望,线段树,逆元)

Groundhog and Gaming Time题目描述样例input:62 21 21 41 53 53 6output:405536771题目大意给定nnn个区间(Li,Ri)(L_i,R_i)(Li​,Ri​),每个区间有12\frac{1}{2}21​的概率取到,假设取了mmm个,求:E(∣(L1,R1)∩(L2,R2)∩(L3,R3)...∩(Lm,Rm)∣2)E(|(L_1,R_1)\cap(L_2,R_2)\cap(L_3,R_3)...\cap(L_m,R_

2020-08-09 23:20:28

2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)

Groundhog and Apple Tree题目描述样例input:154 2 1 5 71 2 41 3 54 2 95 2 3output:23题目大意给定一棵树,每条边有权值,点上也有权值。现有一个初始Hp=0Hp=0Hp=0的人,如果经过边,那么HpHpHp减去边权,如果经过点,那么会加上点权。为了保证任何时刻Hp≥0Hp\ge 0Hp≥0,他可以随时休息1分钟,然后增加1HpHpHp。如果每个点的点权只能加一次,每条边只能经过两次,那么如果这个人从1号结点开始,遍

2020-08-09 21:03:42

2020牛客暑期多校训练营The Escape Plan of Groundhog(暴力,前缀和)

The Escape Plan of Groundhog题目描述样例input:4 41 1 1 11 0 1 11 1 0 11 1 1 1output:3input:5 51 0 1 1 11 0 1 0 11 1 0 1 11 0 0 1 11 1 1 1 1output:3题目大意给定一个01矩阵,要求在里面找到一个子矩阵,满足:1、这个矩阵的周围的一圈是1。2、这个矩除了周围一圈,中间01数量之差最多为1。3、这个矩阵至少为2*2。求会有多少矩阵

2020-08-09 17:53:52

2020牛客暑期多校训练营Groundhog Chasing Death(质因数分解,费马小定理,模拟)

Groundhog Chasing Death题目描述样例input:1 2 1 2 8 4output:2048input:1 2 3 4 120 180output:235140177题目大意给定a,b,c,d,x,ya,b,c,d,x,ya,b,c,d,x,y,求:∏i=ab∏j=cdgcd⁡(xi,yj)\mathop{\prod}\limits_{i=a}^{b}\mathop{\prod}\limits_{j=c}^{d}\gcd(x^i,y^j)i=a∏b​j=c∏

2020-08-09 08:57:35

2020牛客暑期多校训练营Groundhog and 2-Power Representation(高精度,递归)

Groundhog and 2-Power Representation题目描述样例input:2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)output:1315题目大意给定一个计算式,定义2(a)=2a2(a)=2^a2(a)=2a。计算结果。分析分析数据范围,赤裸裸的高精度。但是题目又更恶心了一点,它把幂换成了括号,因此需要括号匹配之后递归求解。我要学PYTHON接下来是DNdalaoDNdalaoDNdalao给的更好的思路

2020-08-08 20:36:03

2020牛客暑期多校训练营The Flee Plan of Groundhog(树形DP)

The Flee Plan of Groundhog题目描述样例input:7 21 22 55 75 63 63 4output:1题目大意土拨鼠和OrangeOrangeOrange同住在一棵树上。现在,土拨鼠去看望OrangeOrangeOrange,他从1号结点出发,OrangeOrangeOrange住在nnn号结点。土拨鼠速度为1m/s1m/s1m/s,ttt秒之后,OrangeOrangeOrange发现自己发烧了,为了传染给土拨鼠,他以2m/s2m/s2m/s的

2020-08-08 19:55:29

2020牛客暑期多校训练营Groundhog Looking Dowdy(滑动窗口,贪心)

Groundhog Looking Dowdy题目描述样例input:4 31 32 8 61 23 1 7 5output:2题目大意有nnn天,每天土拨鼠有一些衣服可以穿。其中mmm天他要出去见AppleAppleApple,因此他希望穿一些更特别的衣服。每件衣服都有一个dowdinessdowdinessdowdiness不时髦度。现在土拨鼠希望对于任意的mmm天每天找到一件衣服使得选出的这些衣服中dowdinessdowdinessdowdiness的最大值和最小值的差的最

2020-08-08 19:18:04

2020牛客暑期多校训练营Tokens on the Tree(树形DP,树链剖分)

Tokens on the Tree题目描述输入描述:输出描述:示例1输入251 2 3 3101 2 3 4 3 6 3 8 2输出71989说明题目大意给定一棵树,这棵树上有黑白两种颜色,白色和黑色节点各构成了一坨连通块,其中一个节点可以将其颜色转移到它所在的连通块的外面一圈。再定义一个函数f(u,v)f(u,v)f(u,v),如果一个连通块通过变换能使得这个块的两端互换位置,那么称这两个形态为同种形态。现要求对于所有的u+v≤nu+v\le nu+v≤n,nn

2020-08-06 23:23:59

2020牛客暑期多校训练营A National Pandemic(树链剖分)

A National Pandemic题目描述输入描述:输出描述:示例1输入15 61 21 32 42 51 1 53 42 11 2 73 33 1输出396题目大意有一个国家,它的城市分布可以表现为一棵树。其中爆发了疫情,我们定义f(n)f(n)f(n)表示nnn号城市的疫情严重性。有以下3种操作:1、蔓延,给定一个x,wx,wx,w。对于所有城市yyy,其严重程度会加上w−dist(x,y)w-dist(x,y)w−dist(x,y),其中dis

2020-08-06 15:22:18

2020牛客暑期多校训练营Cinema(状压DP,离散化)

Cinema题目描述输入描述:输出描述:示例1输入33 34 51 5输出(MD原因,截图)题目大意给定一个n,mn,mn,m,现有n∗mn*mn∗m大小的电影院。由于疫情,一个位置如果有人,那么上下左右都不能坐人了。现在要求,在整个电影院坐到无法再坐时,最少有多少人能入座。分析看数据猜算法。m≤15m\le 15m≤15,果断状压。再看题目,嗯每行的状态只和上一行有关,太棒了就是状压。接下来看看怎么状压吧。首先肯定是定义状态怎么表示。不妨0表示没有人,1表示有人。

2020-08-04 23:01:30

2020牛客暑期多校训练营Enigmatic Partition(数学,二阶隔项差分)

Enigmatic Partition题目描述输入描述:The first line contains the number of test cases T (1 \le T \le 10,0001≤T≤10,000).In each of the following T lines there are two integers l and r (1 \le l \le r \le 100,0001≤l≤r≤100,000).输出描述:For each test case, output one

2020-08-04 15:09:28

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取