2 consult_

尚未进行身份认证

我要认证

本科在读

等级
TA的排名 7w+

P3178 [HAOI2015]树上操作 (树链剖分板子)

P3178 [HAOI2015]树上操作 题目描述: 有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 :询问某个节点 x 到根的路径中所有点的点权和。 树链剖分 模板来源 :https://www.bilibili.com/video/BV1xE411j7WF?from=search&seid=7017680147370733

2020-09-30 20:54:15

Invoker(2019ccpc秦皇岛)

Invoker费了九牛二虎之力搞出来了,记录一下。道路很曲折,代码写完了才发现一开始无脑屏蔽掉了出现数次的unordered,常识地以为是ordered 。由于连招是无序的,并且三个连招只有六种排列组合,所以我们把每个连招可能的组合排列出来就可以转移状态了dp[i][j] 表示:到第 i 位 选择 第 j 种连招所获得的最小代价。所以每个 dp[i][j] 要从 第 i-1 位的 0 - 6 种 连招转移过来。最后就是两个连招相邻连招的节约计算;#include<bits/stdc++.

2020-09-22 17:46:05

AtCoder Beginner Contest 176

链接D - Wizard in Maze题意: 在一个 H * W 的网格地图中,问从给定起点到终点要使用的最少魔法次数。行走规则:1、当相邻的位置为空地时可以直接走到下一个点而不使用魔法。2、否则使用一次魔法后可以把自己传送到以当前位置为中心的 5 * 5 的方阵的任一个空地位置。思路: 直接两个bfs嵌套搜索一下就????。#include<bits/stdc++.h>using namespace std;#define F first#define S secondt

2020-09-16 10:56:56

C. Binary String Reconstruction (Round 94 字符串构造)

链接题意: 给出一个01字符串w 和 正整数 x,可以通过以下规则构造出 s :1、当 w[i-x] 存在 且 w[i-x] ==‘1’ 时 s[i] = ‘1’;2、当 w[i+x]存在 且 w[i+x] ==‘1’ 时 s[i] = ‘1’;否则 s[i] = ‘0’;给出 s 串,求 w 串。若存在则输出 w ,否则输出 -1;思路: 对于s[i]=‘0’,则若 w[i-x] 存在则 w[i-x] 必为‘0’,若 w[i+x] 存在则 w[i+x] 必为‘0’。所以此时 w 串满足了

2020-09-04 11:22:23

Codeforces Round #666 (Div. 2) (A-D)

题目链接A - Juggling Letters直接统计每个字母个数,检查是否都是 n 的倍数即可#include<bits/stdc++.h>using namespace std;int vis[100];int main(){ int T; cin>>T; while(T--){ int n; cin>>n; memset(vis,0,sizeof vis); string s; for(int i=0;i<n;i++){

2020-09-02 19:10:32

Codeforces Round #665 (Div. 2) (A-D)

题目A - Distance and Axis选一点 B ,使得∣OA−AB∣|OA-AB|∣OA−AB∣为 K 时 A 需要挪动多少单位。那么当OA <= k 时,使AB=0,需要挪动k-OA。当OA>k 时 B 点必须在OA内,此时 OA 分解为a、b之和,那么当OA为奇数时k=∣a−b∣k=|a-b|k=∣a−b∣ 为奇数,当OA为偶数时k=∣a−b∣k=|a-b|k=∣a−b∣ 为偶数。所以根据 k 的奇偶性改变OA的奇偶性即可。#include<iostream>u

2020-08-22 15:05:27

D - Segment Intersections (Round 92 div2 模拟 枚举)

D - Segment Intersections * 题意: 分别给出 n 个区间 [al1,ar1],[al2,ar2],…,[aln,arn][al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n][al1​,ar1​],[al2​,ar2​],…,[aln​,arn​] 其初始值均为 [l1,r1][l_1,r_1][l1​,r1​] 和 [bl1,br1],[bl2,br2],…,[bln,brn][bl_1, br_1], [bl_2, br_2],

2020-08-20 19:45:58

B - Array Walk (Round 92 div2 贪心 枚举)

B - Array Walk 题意: 给定一个长度为 n 的数组,从位置1开始可以向右累加 k 次,且可以向左累加 z 次,但不能连续两次及以上向左累加,求最大累加和。思路: 贪心的考虑,在往右累加的过程中,若需要循环节的存在,则一定只要最大的一个循环节,所以我们在枚举最终停止位置时,同时记录最大的循环节,然后计算停止在每个位置能得到的最大累加和,再取最大即可。Code1:#include<bits/stdc++.h>using namespace std;#define IO

2020-08-20 18:36:43

C - Good String (Round 92 div2 枚举)

C - Good String 题意: 给定一个只包含0-9的字符串,要求删去最少的字符使得剩下的子序列是good,当且仅当 t2t3…tn−1tnt1t_2 t_3 \dots t_{n - 1} t_n t_1t2​t3​…tn−1​tn​t1​ 和 tnt1t2t3…tn−1t_n t_1 t_2 t_3 \dots t_{n - 1}tn​t1​t2​t3​…tn−1​ 相同。思路: 可以证明要么两位不同的数循环出现,或者数字都一样两种情况才满足good的条件,所以直接枚举两位数字循环,选取最长

2020-08-20 17:46:25

D. Colored Rectangles (Round 93 div2 DP)

D. Colored Rectangles 题意: 给三种颜色并且成对出现木条,长度分别为 ai、bi、cia_i、b_i、c_iai​、bi​、ci​,问所有组成的矩形的面积的和最大为多少。(每个矩形必须有两种颜色,每种颜色木条数不超过 200)思路: 首先只贪心的选是不对的,因为我们要的是所有矩形的面积和最大,所以每次选择不能只选择最长的两对边,还要看每种颜色木条的数量。所以我们只能暴力DP出所有情况找出最大值。O(n3)dp[i][j][k]dp[i][j][k]dp[i][j][k] ,代表分

2020-08-17 22:45:13

C - Good Subarrays (Round 93 div 2 思维)

C - Good Subarrays 题意: 给个长度为 n 的数组,选取一个区间,使得其区间和等于区间的长度,问有多少这种区间。思路: 暴力直接O(n2) 的去找肯定超时,所以我们做个转化,将所有元素减一,那么所有区间和等于0的区间都是满足条件的区间。所以我们可以在维护前缀和时,记录下每个前缀和出现的次数,当两个前缀和相等,那么其之间的区间和必为0。然后累加计数即可。Code:#include<bits/stdc++.h>using namespace std;typedef

2020-08-17 22:31:09

牛牛的01游戏 (string)

牛牛的01游戏题目描述牛牛最近迷上了小游戏,于是他也想对他的01字符串进行一些操作,01字符串上的0和0相邻时会变成1,而1和1相邻时会在字符串上消失,而0和1相邻时什么都不会发生,牛牛现在把初始的字符串给你,你能告诉牛牛这个字符串最后会变成什么样吗。备注:1≤∣str∣≤1061\leq |str|\leq10^61≤∣str∣≤106,字符串上的合并消失应优先与左边进行,例如000,中间的0优先与左边的0合并变为10,消失同理思路: 直接用string充当栈,也可用stack 。Code:

2020-08-14 19:31:52

D. Boboniu Chats with Du (664 div2 贪心 枚举)

D. Boboniu Chats with Du 题意: 给 n 个快乐值,你可以按任何顺序在群里说出快乐值为 kik_iki​ 的话,当 m<kim<k_im<ki​ 时,你会获得 d 天的禁言(不包括当天),n 天后你的快乐值的和最大是多少。思路: 很明显的贪心,但是不是太好想。首先我们把大于 m 的与小于等于 m 的数分开存到 a、ba、ba、b 数组中,然后分别从大到小排序。所以如果我们说快乐值大于 m 的话,那么每次肯定说最大的 ai,当说 num 次 ai 时要耗费t

2020-08-13 21:19:37

C. Boboniu and Bit Operations (664 div2 位运算/dp)

C. Boboniu and Bit Operations 题意: 给出两个非负整数的数组a,b,长度分别为n,m。设对于 i,ji,ji,j 有 ci=aic_i =a_ici​=ai​&bjb_jbj​ ,求c1∣c2∣c3……∣cnc_1|c_2|c_3……|c_nc1​∣c2​∣c3​……∣cn​ 的最小值。1≤n,m≤2001\le n,m\le 2001≤n,m≤200,0≤ai<290\le a_i < 2^90≤ai​<29,0≤bi<290

2020-08-13 20:43:47

C. Pinkie Pie Eats Patty-cakes (662 div2 构造)

C. Pinkie Pie Eats Patty-cakes题意: 有 n 个已知种类的蛋糕,求如何吃掉这 n 个蛋糕使得,相同种类的蛋糕之间的蛋糕距离最大,求最大吃法中的相同蛋糕的最小距离(两个相同蛋糕之间的距离为其之间的蛋糕数)。思路: 所以,如何构造才能使得相同蛋糕之间的距离最大呢,我们把种类最多的蛋糕数设为 k 个 ,显然分开放后会产生k-1个间隔,所以我们把剩下的蛋糕分别填充这k-1个间隙,然后找个最小的距离即可。注意 :k 可能会出现多个。Code1:隔板思想。#include&l

2020-08-12 22:12:22

B. Applejack and Storages (662 div2 思维 模拟)

B. Applejack and Storages**题意: 初始给定n个长度已知的木板,然后q次操作,每次加入或减少一个长度为x的木板(保证减少前存在长度为 x 的木板),每次操作后询问:是否可以利用现在的木板组成一个正方形和一个长方形(可为正方形)。思路: 显然可以很暴力去做,每次操作后寻找出现次数前三大的数,然后分类讨论是否能组成,但是复杂度太大。由于四条形同的木板组成一个正方形,两条形同的木板组成一对边,所以,我们只统计 2≤k≤42\le k \le42≤k≤4 和 k=4k=4k=4

2020-08-12 21:36:47

D. 505 (663 div2 枚举)

D. 505 题意: 给一个 n 行 m 列的01矩阵,其中 n≤mn \le mn≤m ,每次操作可以把某个元素取反,求最小的操作次数使得,这个矩阵中的每一个偶数大小的子方阵里的 1 都为奇数个。若不管多少操作都满足不了条件,就输出-1。思路: 服了,题都读不懂了QAQ。。所以,当 4≤n4\le n4≤n 时,问题是无解的,因为当存在 4 * 4 的方阵时,若其四个角的2 * 2 的方阵里的 1 为奇数个,那么4 * 4 里的就为偶数了。所以,分类讨论n=1,n=2,n=3,暴力枚举第一列后,

2020-08-11 17:40:02

C. Cyclic Permutations(663 div 2 排列组合)

C. Cyclic Permutations 题意: 给一个 n 的全排列,然后构建一个图,节点为每个数的下标,数组中的每个数可以与右边第一个大于它的数,左边第一个大于它的数连接无向边,问在 n 的全排列中有多少排列构成的图中存在简单环。思路: 一开始题意还读错了,,以为是包含 n 的简单环有多少。。现在想想有点扯。所以当一个数左右两边存在大于这个数的数,必定能构成一个简单环,例如:对于i,j,k,当i>j,k>j对于i,j,k,当i>j,k>j对于i,j,k,当i>j

2020-08-11 17:13:38

E1. Weights Division (easy version) (div3)(贪心)

E1. Weights Division (easy version) 题意: 给一颗以1为根的树,每次操作可以把一条边的边权除以2下取整,问要使根节点到所有叶子节点的路径长度和小于给定的S,求最小的操作次数。 思路: 由于从根到叶子的路径中有很多的边是重复经过了多次的,所以在贪心的时候要从整体考虑贪心,并且我们每次找的是,把这条边整除2后与之前的边的差值尽量大的边,这个差值除了w - w / 2 之外我们还要乘上这条边经过的次数,才能每次找到最优的边。Code:#include<bits/

2020-08-10 16:30:17

D. Binary String To Subsequences (div3) (字符串思维)

D. Binary String To Subsequences题意: 给一个01串,要求拆分成尽量少的子序列,每个子序列满足01交替,例如:101010或者010101,输出子序列个数 及原串中每个字符所属的子序列编号。思路: 由于字符串长度2e5,所以考虑 O(n) 或者 O(nlogn) 的做法。我们考虑如何使得子序列最少:在遍历时当前位为1时,那么如果之前有以0结尾的子序列,那直接接上去,并且此子序列的末尾状态也改变了,否则重新另开一个子序列。那么就可以用两个队列,动态的维护是否有以 0

2020-08-10 16:01:30

查看更多

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