1 WayJasy

尚未进行身份认证

叁肆伍叁,伍肆伍物

等级
TA的排名 7w+

Codeforces Round #592 (Div. 2) D. Paint the Tree

传送门题意:给出一棵树,每一个节点染成某种颜色需要花费aaa,每个节点和它直接相连的节点需要染成的颜色互不相同,问染完整棵树的最小花费。思路:由于颜色只有3种,画一画图会发现,如果每个节点的度数超过2,那么一定无解。也就是说给出的树是一条树链。那么颜色只有3种,一共有6种染色状态,先dfs出树链,然后直接暴力枚举所有状态、#include<iostream>#inc...

2019-10-16 15:27:11

2017四川省赛 Dynamic Graph (bitset)

传送门题意:给定nnn个点,mmm条边的有向图,初始每个点颜色是白色,qqq次操作,每次操作将某个节点的颜色取反(白变黑,黑边白),每次操作求出二元组(u,v)(u,v)(u,v),从uuu到vvv的路径上无白色顶点的路径数。思路:暴力修改点,每次修改后dfsdfsdfs一遍求路径,dp[u]dp[u]dp[u]表示以uuu为初始点的路径数转移:dp[u]+=dp[v]dp[u]...

2019-10-05 21:14:12

codeforces 593div3D 线段树

传送门题意:给定一个字符串修改某个位置的字符查询区间不同的字符种类数思路:对每一种字符建一棵线段树,维护区间该种字符的个数。然后就是裸的单点更新区间查询。#include<iostream>#include<algorithm>#include<cstdio>#include<stdio.h>#include<str...

2019-10-02 20:18:09

codeforces 585 div2C

传送门题意:给出长度为nnn的两个字符串,构造一个次数最少的交换二元组(x,y)(x,y)(x,y),表示交换s1[x]s1[x]s1[x]和s2[y]s2[y]s2[y],最后使得两个字符串相同思路:首先相同的字符就没必要去交换了。考虑上下字符不同的情况。上aaa,下bbb(下文称ab,baab,baab,ba同理)对于ababab如果有偶数组ababab,我们可以进行numab/2n...

2019-09-19 23:08:52

hdu5901 大素数筛

(记个模板题意:求1−n中质数个数(n<=1e11)求1-n中质数个数(n<=1e11)求1−n中质数个数(n<=1e11)出处Meisell−Lehmer算法,复杂度n23Meisell-Lehmer算法,复杂度n^{\frac{2}{3}}Meisell−Lehmer算法,复杂度n32​#include<cstdio>#includ...

2019-09-13 11:57:38

2019徐州网络赛 G题 (回文树 节点回文串不同的字符个数)

传送门题意:对于给定的字符串,求每个子回文串中不同的字符个数之和。思路:回文树。cnt[i]cnt[i]cnt[i]表示节点iii的回文串个数。sum[i]sum[i]sum[i]表示节点iii表示的回文串的不同字符个数。在构造回文树的时候判断当前插入的字符ccc在其匹配位置curcurcur处是否出现过,在继承curcurcur的答案的基础上进行更新。#incl...

2019-09-07 19:41:32

HDU4786 A - Fibonacci Tree (最大最小生成树)

VJ传送门题意:问你在一个无向图中是否存在一个生成树,权值为斐波拉契数。思路:生成树的权值范围必定在最小生成树和最大生成树的权值范围之间,因此用kruskal分别求出最大最小生成树权值后,然后二分判断是否是FIB数,或者用STL都可以。(有段时间没做题了,做做水题找下感觉)#include<iostream>#include<algorithm>#i...

2019-08-26 22:47:48

2019HDU多校九1002 (线段树求线段交点个数)

hdu6681题意:给你kkk条平行于x轴或y轴的射线,问这些射线把封闭区域n∗mn*mn∗m的矩形分成了几个封闭部分。思路:因为射线都是平行于坐标轴的,那么考虑线段树维护。离散化坐标后,按照xxx坐标从小到大排序。第一遍:如果当前点是竖着分割,那么分割的区间值加一,表示当前这段区间yyy坐标都有射线经过。如果当前点是横着分割的,那么直接单点查询当前点yyy坐标的值。(deb...

2019-08-19 22:50:42

Codeforces Round #580 (Div. 2)

传送门A:瞎搞,B:先记录把每个负数处理成−1-1−1,正数处理成+1+1+1对答案的贡献。然后分类讨论一下−1-1−1出现次数的奇偶性,然后加上0的贡献。C:简单构造。由于相邻nnn个数的和的差值绝对值<=1<=1<=1,并且任意一个和差值都<=1<=1<=1,那么先考虑:由于:{S1=a1+a2+...+anS2=...

2019-08-19 10:49:40

多项式乘法 (FFT模板)

FFT模板题记录一下FFTFFTFFT模板(内存记得开大点(最好四倍))下次改用手写复数类,#include<iostream>#include<algorithm>#include<cstdio>#include<stdio.h>#include<string.h>#include<queue>#incl...

2019-08-17 00:26:49

2019HDU多校第八场 Andy and Maze (colorr coding问题)

hdu6664题意:有nnn个房间,mmm条边,每条边连接两个房间u和vu和vu和v,从u到vu到vu到v花费ttt.每个房间有一颗宝石。现在要求在取得kkk个宝石的前提下使得花费最多。问最大花费(无法取得kkk颗宝石输出impossibleimpossibleimpossible)思路:又学到了新姿势(colorcoding问题)我们先随机对每个点进行染色(色号为0~k-1)...

2019-08-16 23:23:21

hdu 6611 K Subsequence(最大费用流)

hdu6611题意:从一个无序数组中选出kkk个非严格递增序列使得总和最大。思路:(出题人卡spfaspfaspfa费用流还是比较骚的。。)源点向每一个数建一条容量为1,花费为0的边。 将每个数拆成两个点保证只选中一次,点间建一条容量为1,费用为−a[i]-a[i]−a[i]的边,小的点向大的点连容量为1,花费为0的边,然后点向汇点建一条容量为1,费用为0的边。 还需要一个超级汇点,汇点...

2019-08-16 11:37:53

2019牛客多校九 J Symmetrical Painting(思维模拟)

传送门题意:给出nnn个长为1,以及下边界LLL和上边界RRR的矩形,每个矩形初始时涂上黑色。你可以将某些矩形区域涂上白色,涂完后求最大的矩形区域面积,满足存在一条平行于xxx轴的直线平方上下两部分矩形区域面积(即直线上下的黑色部分面积相同)思路:考虑枚举平分线,会发现对于一个矩形来说,平分线越靠近矩形中点,那么我们需要涂色的面积就越小(因为对称,画个图感受一下。),获得的黑色区域面积就...

2019-08-16 00:02:59

2019牛客多校九 B Quadratic equation(二次剩余)

传送门题意{(x+y)mod  p=bx∗ymod  p=c\begin{cases}(x+y)\modp=b\\x*y\modp=c\\\end{cases}{(x+y)modp=bx∗ymodp=c​求解x,yx,yx,y思路不考虑取模的情况下,原式可...

2019-08-15 21:25:28

2019HDU多校八 6665 Calabash and Landlord(离散化BFS)

hdu6665题意:求两个矩形在二维平面内组成的封闭区域的个数思路:暴力讨论赛中队友想暴力搞一下就被我否决了(情况太多有这时间还不如去开其他题?)考虑对矩形离散化到一个15∗1515*1515∗15的区域内,矩形的边界用特殊的符号表示,然后对这个区域进行bfsbfsbfs就完事了。#include<map>#include<set>#include<...

2019-08-14 19:15:22

Mail.Ru Cup 2018 Round 3 D. Decorate Apple Tree

传送门题意:问需要多少种颜色对一棵树的叶子节点进行染色,使得有k(1<=k<=n)个快乐节点k(1<=k<=n)个快乐节点k(1<=k<=n)个快乐节点快乐节点定义为如果该节点的所有叶子节点颜色均不同。(一开始看错题意以为是每个节点的颜色都要不一样正确理解题意后其实就是求每个节点有多少个叶子节点,叶子节点本身就算一个。...

2019-08-13 19:31:01

2019杭电多校第六场hdu6638 Snowy Smile (最大权值和矩形)

传送门题意:给出二维坐标轴上的n个点,每个点有整数权值。用一个矩形包含若干个点使得总权值和最大。给出二维坐标轴上的n个点,每个点有整数权值。用一个矩形包含若干个点使得总权值和最大。给出二维坐标轴上的n个点,每个点有整数权值。用一个矩形包含若干个点使得总权值和最大。思路(扯淡拖到现在才补这题。。。赛中尝试使用二维离散化前缀和(wawawa了并且找到了错误样例想法有误),又尝试了扫描...

2019-08-11 00:50:40

ZOJ 3209 (舞蹈链)

传送门题意:给出一个n∗mn*mn∗m的大矩形,以及ppp个小矩形,给出小矩形的左上角和右下角坐标。问最少选择多少个小矩形能覆盖大矩形。小矩形不能相交。思路:DLX的基本应用吧(精确覆盖问题)精确覆盖问题:给出一个010101矩阵,选出最少的行,使得每一列恰好有一个1.本题就可以抽象成精确覆盖问题:将ppp抽象成01矩阵的行,把n∗mn*mn∗m的矩阵的每一个格子抽象成新01...

2019-08-10 00:09:44

CF 1198 div1B

传送门题意:1: xy 把x位置的数更新为y2: x 把序列中小于x的数更改为x思路:线段树单点更新查询,维护一个lazy标记和区间Min, 每次查询pushdown更新Min#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2e5+5;usingll=long...

2019-08-06 13:51:38

HDU多校 第五场 6227 (equation)

传送门题意:对于∑1n∣aix+bi∣=C\sum_1^n|a_ix+b_i|=C∑1n​∣ai​x+bi​∣=C,求xxx的所有可行解(分数形式表示)。思路:分区间讨论。我们令∣aix+bi∣=0|a_ix+b_i|=0∣ai​x+bi​∣=0,那么就可以得到nnn个关于a,ba,ba,b的解xix_ixi​,(对每个绝对值编号1~i)按照xix_ixi​的大小(...

2019-08-06 00:29:21

查看更多

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