1 S atur

尚未进行身份认证

我要认证

要变成萤火虫

等级
TA的排名 2w+

L. Working Plan (优先队列 & 贪心思维 & 课表安排) ICPC Seoul 2018

思路:现有m个人和n天的课表,要求安排一个可行方案,满足第j天有d[j]个人工作,第i个人总共工作w[i]天。且每个人一开始工作就必须连续工作w天,然后至少休息h天才能工作。如果有可行解第一行输出"1",然后输出m行,每i行含w[i]/w个数,表示第i个人每次工作的开头那天;无解直接输出"-1"。从头按顺序开始安排每一天工作的任选,首选工作量最大的且可以工作(既没有在进行上一次工作,也休息了至少h天;且后w天都需要人工作)的人。这个时候就用一个优先队列来存m个人的当前工作量情况,且用一个队列过渡。.

2020-09-05 22:06:00

D. Go Latin (模拟 / 简单) ICPC Seoul 2018

思路: 就是那么个意思,就像英语单词的词性转换,模拟判断一下就好。代码实现:#include<bits/stdc++.h>#define endl '\n'#define null NULL#define ll long long#define int long long#define pii pair<int, int>#define lowbit(x) (x &(-x))#define ls(x) x<<1#define rs(x) (x.

2020-09-05 20:13:23

J. Easy Integration (逆元 & 分部积分) 2020牛客暑期多校训练营(第一场)

传送门思路:题意就是给你n,让求出下下列式子的结果:很明显这就是数学方面的问题啦,这么菜的我在数学方面就更菜,反正最后看题解博客得知结果就是 (n)! / (2n+1)!。代码实现:#include<bits/stdc++.h>//#define endl '\n'#define null NULL#define ll long long#define int long long#define pii pair<int, int>#define low

2020-09-05 16:58:44

F. Infinite String Comparision (字符串 & 字典序) 2020牛客暑期多校训练营(第一场)

传送门思路:一般的思路无非就是模拟判断一下,当然就需要考虑到s和t的长度已经对应字符的字典序大小问题。但是我看见一篇大佬博客写得妙啊!代码实现:#include<bits/stdc++.h>#define endl '\n'#define null NULL#define ll long long#define int long long#define pii pair<int, int>#define lowbit(x) (x &(-x))#

2020-09-05 16:38:28

Codeforces1401D Maximum Distributed Tree (树dfs & 贪心)

传送门题意: 给出一棵n个点的树,想让给每条边赋值,使得所有边权的乘积为k。因为k非常大,所有将k拆分成m个因子,换而言之就是n-1条边权的乘积得等于m个因子的乘积。定义f(x, y)为点x到点y的简单路径所经过的所有边的权值和,现问怎么安排边权,才能让所有简单路径的 f 值和 (即下图所示公式)最大,并得到该max值。思路:若m < n-1,那么剩下的边用1来填充。dfs找到每条边的经过次数,然后贪心一下将大的因子赋值给经过次数最多的边贡献就最多。至于经过次数的计算,可以将 u -

2020-09-02 23:22:02

Codeforces D Rarity and New Dress (二维dp & 菱形寻找)

传送门题意: 给出n*m的矩形,相同字符的表示同一种颜色,找出矩阵中有多少个斜正方形(如下图所示)。思路:设dp[i][j]表示(i,j)为止以上能最多得到的"斜正方形",答案就是所有位置的dp值之和。而对于位置(i,j),只需要考虑(i-1,j-1),(i-1,j),(i-1,j+1),(i-2,j)位置是否与其同色。若同色则(i,j)位置构成一个图形,直接dp[i][j]=1。反之就dp[i][j] = min(dp[i-1][j-1],dp[i-1][j+1],dp[i-2][j])+

2020-08-30 00:04:48

Codeforces E1. Weights Division (easy version) (树dfs & 边的利用次数)

传送门题意: 给定一棵以 1 号点为根的带权有根树。每次可选择一条边将其边权除以2(下取整),试问至少经过多少次选择,才能使得所有根节点到叶子节点的路径权值和不超过S?思路:利用有限队列每次选择权值最大的边处理,直到sum <= S。(我只想得到这么多了,莫得法太菜了呜呜呜。细节部分还一直处理不好,嗐。)看了大佬博客才知道,原来还得将经过次数和权值分别存取,如果直接存cnt*val会有错(这个在大佬2博客中有提到)。大佬1博客代码比较简洁清晰,大佬2博客思路比较详细。代码实现:#i

2020-08-29 22:47:42

Codeforces E. Tree Queries (树 & dfs & 特定路径判断)

传送门题意: 给你一个以 11 为根的有根树。每回询问 k 个节点v1 ,v2 ⋯vk。​求出是否有一条以根节点为一端的链使得询问的每个节点到此链的距离均≤1.只需输出可行性, 无需输出方案.思路:这棵树以 1 为根,那么,这条路径要么经过给定点,要么经过给定点的父亲,要么经过给定点的至少一个儿子。这时我们发现,经过以上三种点都必须经过给定点的父亲,于是我们就把题面转化为了:给定若干个点,求是否有一条从 1 开始的路径经过这些点。按照深度排序后依次判断后一个点是否在前一个点的子树内即可。

2020-08-23 00:26:20

Codeforces C. Uncle Bogdan and Country Happiness (树型递推)

传送门题意: 给出一颗根节点为 1 的树,对于每个节点 i,有 p[i] 个人的家在节点 i 上。一开始所有人都在根节点上,然后每个人会往家沿着最短路走。每个人出发时有一个心情,可能是好心情也可能是坏心情,在经过一条边时,心情可能由好变坏,但是不可能由坏变好。每个点有一个幸福检测器,最后的检测结果为:所有经过该节点的人中,好心情的人数减坏心情的人数。现在给出每个 h[i] ,问有没有可能最后每个节点的检测结果恰好为 h[i] 。思路:刚开始看完题就一头懵,有点点思路但还是太菜,码力不得行啊。

2020-08-22 21:26:12

Codeforces D. Maximum Distributed Tree (树dfs & 边的利用次数)(Round #665 Div.2)

传送门题意: 给出一棵n个点的树,想让给每条边赋值,使得所有边权的乘积为k。因为k非常大,所有将k拆分成m个因子,换而言之就是n-1条边权的乘积得等于m个因子的乘积。定义f(x, y)为点x到点y的简单路径所经过的所有边的权值和,现问怎么安排边权,才能让所有简单路径的 f 值和 (即下图所示公式)最大,并得到该max值。思路:比赛的时候相叉了,后面快结束了才行到 idea, 但对树的相关操作不熟就这么错过了上高分分的机会,呜呜太菜了~若m < n-1,那么剩下的边用1来填充。dfs找

2020-08-22 19:48:02

Codeforces A. Distance and Axis (思维 / 暴力) (Round #665 Div.2)

传送门题意: 在坐标轴OA上找到一个点B,使得| |OA| - |OB| | == k。若无法等于k,就将A向左后右移动一个单位,试问最少经过多少次操作可以找到符合条件的B点。思路:简单粗暴点,可直接先将B点放在原点位置。若 |OA| == k,那么可以直接选择原点(或二倍A点的位置)为B,操作数为0。若 |OA| < k,那么将A加到k即可。若 |OA| > k,就需要在OA间安插B点的操作数比较少,且若 n-k为奇数,还需要将A向右移动一步即可。代码实现:#inclu

2020-08-22 17:55:21

Codeforces B. Ternary Sequence (思维 / 贪心) (Round #665 Div.2)

传送门题意: 给出两个只由0,1,2组成的数组a,b;可通过一种计算规则得到相应的数组c:c[i] = a[i]*b[i] , a[i] > b[i]c[i] = 0 , a[i] == b[i]c[i] = -a[i]*b[i], a[i] < b[i]现可将a,b进行特定的排序,使得sum©得到最大值,并求出该max。思路:正贡献(+2)的情况,a[i] > b[i],那么就要认a中的2尽量多的对应b的1.无贡献的情况,a[i]

2020-08-22 17:34:35

Codeforces C. Mere Array (思维 / gcd) (Round #665 Div.2)

传送门就先不说了,咱先上代码,明早再来写思路吧。#include<bits/stdc++.h>#define endl '\n'#define null NULL#define ll long long#define int long long#define pii pair<int, int>#define lowbit(x) (x &(-x))#define ls(x) x<<1#define rs(x) (x<<1+1)#d

2020-08-22 01:18:17

Codeforces D. Secret Passwords (并查集 / 字符串分组)

传送门题意: 给定n个字符串。如果存在一个或多个字母同时在字符串a和b中出现, 这a和b就被分在同一组如果a和c在同一组 b和c在同一组, 则aa和bb也在同一组问所有的字符串最后被分成几组?思路:基本原理:利用并查集维护下字符集合。把每一个字母当成一个点,对于每一个给出的字符串,把字符串中的所有字母之间都连上边。这样,若两个字符串有公共的字母,他们就一定在一个连通块内,最后求出连通块个数就是答案。代码实现:#include<bits/stdc++.h>#defin

2020-08-22 01:06:09

Codeforces E. Tree Painting (树形dp & 换根)

传送门题意: 给定一棵有 n 个结点的无根树,所有结点都是白色的。第一次操作可以随意使一个结点染成黑色,之后每次操作可以使一个与黑色结点相邻的白色结点变成黑色。每次操作可以获得的权值为被染成黑色的白色结点所在的白色连通块的结点数量。求可以获得的最大权值。思路:最开始我以为选哪儿都一样,都是n到1的和,后面才知道是俺太菜了。只要确定第一个黑点后权值就确定了,所以这就是个选择根节点的树形dp题。但显然如果要每个节点都dfs求答案绝对超时,于是需要推算下换根公式预处理下。这里可以参考大佬博客,讲得

2020-08-21 22:26:41

P3379 【模板】最近公共祖先(LCA)

传送门思路:所谓LCA即两点的最近公共祖先,暴力的思维当然是一步一步往上爬寻找相交的第一个祖先,但这么暴力显然会超时。这个时候就可考虑以2的倍数来加速向上爬,且是从……32,16,8,4,2,1这样从大往小的选择跳跃步数(这样方便对大数悔棋)。大概操作即先爬最深的点x,让x与y位于同一深度时再开始一起往上爬。首先要记录各个点的深度和他们 2^i 级的的祖先,用数组d表示每个节点的深度,用 fa[i][j] 表示节点 i 的 2^j 级祖先。具体思路操作参考大佬博客,真的超详细,超nice!

2020-08-21 01:26:52

Codeforces E. 1-Trees and Queries (树 & LCA & 定长路径)

传送门题意: 给定一个含有n个节点的树(相邻两点间的距离为1),以及q个询问。每一个询问给出5个整数:x,y,a,b,k。指如果像树中的x节点和y节点之间加一条边,问是否存在一条路径从a到b长度为k的路径?(注:每一次询问添加的边不会互相干扰,即只在该次询问有效)思路:首先我们看a与b之间的连通性,有三种有意义的最短路径L:a -> b,即不需要x与y之间的边a和b也能连通,距离记录为dist_ab。a -> x -> y -> b,记作dist_axyb。a

2020-08-21 00:37:09

Codeofrces C. Omkar and Waterslide (模拟 / 暴力) (Global Round 10)

传送门题意: 给出一个序列a,每次可以选择一个非递减序列将每个元素+1,试问将整个元素变成非递减需要多少次操作?思路: 简单的模拟题,直接找到每次出现降低地方非递减序列中的min取操作数即可。代码实现:#include<bits/stdc++.h>//#define endl '\n'#define null NULL#define ll long long#define int long long#define pii pair<int, int>#defin

2020-08-19 23:46:39

Codeforces E Necklace Assembly (暴力 / 循环因子)

传送门题意: 店铺里有n颗珠子,现让你串一条最长的项链,满足将项链逆时针旋转 k 个位置后依然和原位置一样(被定义为k-beautiful项链)。思路:首先最小的答案是最大的字符个数,然后考虑项链中字符不全相等的情况。如果环转k的因子次是美的,那么k次也一定是美的,那么k也一定是美的。设某个字母有x个,x/循环节个数就是该字母能填充的循环节长。把所有字母填充的循环节长加起来,如果大于循环节长度就是符合的。代码实现:#include<bits/stdc++.h>#define

2020-08-19 23:30:20

Codeforces E. Polygon (思维 / 判断)

传送门题意: 对于一个n* n的一个全为0的初始矩阵,矩阵上方和左侧均有一排炮台,矩阵的下侧与右侧是边界。炮台可以发射子弹,子弹只能直线行走,且遇到边界后会停止,遇到一个停止的子弹也会停止,子弹停止后的坐标里面的值记为1。现给出一个结果矩阵,试问是否可以由初始矩阵(全为0)通过炮台打出来;能则输出“YES”,否则输出“NO”。思路: 很简单的思维题,显然对于边界上的炮弹是一定可以打到的,而对于中间的炮弹必须满足其下方或右侧有停留的炮弹即可。代码实现:#include<bits/stdc+

2020-08-19 21:43:05

查看更多

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