3 余西子

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 2w+

P3690 【模板】Link Cut Tree (动态树)

给定 n 个点以及每个点的权值,要你处理接下来的 m 个操作。操作有四种,操作从 0 到 3 编号。点从 1 到 n 编号。0 x y 代表询问从 x 到 y 的路径上的点的权值的 xor 和。保证 x 到 y 是联通的。1 x y 代表连接 x 到y,若 x 到 y 已经联通则无需连接。2 x y 代表删除边 (x,y),不保证边 (x,y) 存在。3 x y 代表将点 x 上的权值变成 y。#include <bits/stdc++.h>#define rep(i, a, b

2020-08-14 16:00:50

Android Studio无法连接上蓝叠模拟器问题

本文是自己在安装安卓环境时一直无法成功运行的原因,仅供参考。在按照网上大部分人提供的安装流程走下来之后,我碰到了最后装模拟器的问题,关于模拟器,很多人推荐的是Genymotion模拟器,那本人由于经济实力原因还是选择了之前就有用过的蓝叠模拟器。在成功adb connect 127.0.0.1:5555之后,首次运行安装过程中还是无法运行,出现Session’app’:Installation did not secceed.The application could not be installed的问

2020-07-29 13:18:17

[COCI2015]BNE 最大全1子矩阵

题意你有一个1000*1000的矩阵,现在定义一个矩阵 $A_{x,y} $ 是酷的当且仅当 a1,1+ax,y<=ax,1+a1,ya_{1,1}+a_{x,y}<= a_{x,1}+a_{1,y}a1,1​+ax,y​<=ax,1​+a1,y​ 且 x>1,y>1x>1,y>1x>1,y>1 条件成立时。 而一个矩阵是非常酷的当且仅当它的所有子矩阵都是酷的。现在问你,非常酷的矩阵的最大的元素个数有多少。做法我们证明一下,假设有如下图,两边的矩

2020-07-10 20:15:57

图论总结

因为图论的知识点是真的杂,稍微写一点东西帮助记忆。后续会慢慢补充。一、最短路DijkstraFloydSPFAK短路差分约束系统二、最小生成树PrmieKruskal三、二分图定义设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。定理最小点覆盖数 = 最大匹配数 (这是 Konig 定理)最大独立集 = 顶点数 - 最大匹配数最小路径覆盖数 = 顶点数 – 最大匹配数3.1

2020-07-03 12:04:43

C. Johnny and Megans Necklace 欧拉回路

题目链接 https://codeforces.ml/contest/1361题意给你 nnn 段线段,每个线段的两端都有一个权值,现在要你将所有的线段相连成一个环,两个线段相连时会产生一个权值 val=log2(aval=log_2(aval=log2​(a xor b)b)b),即两个值能够相连必须在二进制的val位之后所有值相等,如果两个值相等,那么这个 valvalval 默认为20。这个环的值等于所有连接节点的最小值,要你求这个环的最大值。做法自己想还是一下子做不出来,参考了别人的做法敲

2020-06-30 11:14:22

Gym 102419H In-degree 费用流or最大匹配

题目链接: http://codeforces.com/gym/102419/problem/H题意:2000个点,2000条边,无重边无自环的无向图,现在要你把这些无向边变成有向边,使得每个点的入度为给你的数组 AAA ,如果为 −1-1−1 则任意入度即可。做法:两种做法,第一种是费用流做法, 1−n1-n1−n 表示点, 1−m1-m1−m 表示边,我们将边也看成点,从原点到所有点...

2020-03-30 15:24:44

Gym 101655D Delta Quadrant 树形dp

题目链接https://codeforces.com/gym/101655/attachments题意一棵有着 1e41e41e4 个结点的树,树的边上有权值,你现在可以任意选择从某一个起点开始,遍历 n−kn-kn−k (k<=20)(k<=20)(k<=20)个不同的结点并返回,问经过的路径长度最短为多少。做法看到 kkk 的个数其实心里就有点谱了,并且 nnn ...

2020-03-23 15:09:50

CF932 D. Tree 倍增

题目链接: https://codeforces.com/contest/932/problem/D题意4e5次操作,每次操作有两种不同内容111 fff www 表示新增加一个结点,以 fff 作为其父节点,新结点权值为 www222 uuu sumsumsum 表示以结点 uuu 为第一个元素找到一个序列,要求:① 序列中靠后的点必须是前面的点的父亲。② 序列所有结点的和不能...

2020-03-17 20:46:48

竞赛图 哈密顿图

竞赛图竞赛图是通过在无向完整图中为每个边缘分配方向而获得的有向图(有向图)。 也就是说,它是一个完整图形的方向,等价于一个有向图,其中每对不同的顶点通过单个有向边连接,即每对顶点之间都有一条边相连的有向图称为竞赛图。总的概括就是一个有向完全图。与哈密顿路径的关系任何有限数量n个顶点的竞赛图都包含一个哈密尔顿路径,即所有n个顶点上的直线路径。假设该语句适用于n,并考虑n + 1个顶点上的...

2020-02-27 16:07:59

Running Routes 区间dp

题目链接 https://open.kattis.com/problems/runningroutes题意给你一个正 nnn 边多边形,告诉你所有点和点之间是否可以连线,现在要你选出最多的连线,使得所有线之前两两不相交,问最多能选出多少条线。做法其实能感觉出来是区间 dpdpdp ,因为如果一个 888 边形,3和6连上后,7~2 和 4~5两个区间都是一个新的状态,但是emmm,原来自...

2020-02-07 19:00:44

UFPE Starters Final Try-Outs 2020 J.Jingle Bells 树形dp

题目链接 http://codeforces.com/gym/102448/problem/J题意你现在有一棵树,5种颜色 (1,2,3,4,5)(1,2,3,4,5)(1,2,3,4,5) ,树的边会有一种颜色或者没有被染色。现在要你给树染上颜色,让每一个顶点的所有边都带有不同的颜色,问你有多少中方案。做法树形 dpdpdp ,(赛上并没有时间想,挺神奇的一道我应该是做不出来的一道题)。...

2020-02-05 20:45:37

cf #616 (Div. 2) E. Prefix Enlightenment 拆点并查集

题目链接: http://codeforces.com/contest/1291/problem/E题意:你现在有一个 nnn 位的 010101 串 SSS ,和 kkk 个集合,每个集合里会有 1,2,3,4,.....,n{1,2,3,4,.....,n}1,2,3,4,.....,n 中的若干个数字,并且保证每个数字只会在最多两个集合中出现。当你某次选择某一个集合 xxx 时,串 S...

2020-02-03 20:05:22

617.E . XOR and Favorite Number 莫队+异或前缀和

题目链接: https://codeforces.com/contest/617/problem/E题意:长为 1e51e51e5 的数组 aaa ,和 1e51e51e5 个查询,每次查询要求出区间 [li,ri][l_i,r_i][li​,ri​] 中有多少 个子区间使得该区间内的异或和为 kkk。做法:因为我们要快速求得一个区间 [li,ri][l_i,r_i][li​,ri​] 中...

2019-11-20 15:16:57

605D A. Board Game set+树状数组思想

题目链接: https://codeforces.com/gym/260204/problem/A题意:你现在有 nnn 种魔法,每种魔法 iii 都有四个数值 a[i],b[i],c[i],d[i]a[i],b[i],c[i],d[i]a[i],b[i],c[i],d[i] , 现在你有初值 x=0,y=0x=0,y=0x=0,y=0 ,一个魔法 iii 能被使用当且仅当满足 a[i]&lt...

2019-11-20 14:06:08

D1. Constrained Tree 构造+dfs

题目链接:https://codeforces.com/contest/513/problem/D1

2019-11-13 18:30:20

Fabricating Sculptures dp+前缀和优化

题目链接: https://codeforces.com/gym/102428/problem/F题意:你现在有 mmm 个方块,要搭建一个以 sss 为底的一个模型,这个模型是不能储水的结构,即不存在一列,其左边和右边的俩均比它高,问你有多少种搭建的方法。做法:dp[i][j]dp[i][j]dp[i][j] 表示以 iii 为底的时候,还有 jjj 个方块时的方案数。这个时候 dp[i...

2019-11-18 10:17:43

Codeforces 549B. Looksery Party 构造

题目链接: http://codeforces.com/problemset/problem/549/B题意:你现在拥有一个 n∗nn*nn∗n 的 010101 数组 aaa ,和一个长为 nnn 的数组 bbb,现在要你选出一些行的集合 XXX,使得对于每一列 jjj 所有行的和 ∑a[i][j](i∈X)\sum a[i][j] (i\in X)∑a[i][j](i∈X) 不等于 bj...

2019-11-12 15:48:53

CF551D GukiZ and Binary Operations 矩阵快速幂

题目链接: http://codeforces.com/problemset/problem/551/D题意:你现在需要构造一个长为 nnn 的数组 aaa ,使得 (a1anda2)∣((a2anda3)∣...∣(an−1andan))=k(a_1and a_2)|((a_2and a_3)|...|(a_{n-1}and a_n))=k(a1​anda2​)∣((a2​anda3​)∣....

2019-11-12 14:54:00

E. Little Elephant and Tree dfs序+线段树

题目链接: http://codeforces.com/contest/258/problem/E题意:你现在做法:代码#include <bits/stdc++.h>#define lson rt<<1#define rson rt<<1|1#define mid (l+r)/2#define rep(i,a,b) for(int i = ...

2019-11-09 20:38:18

cf 246 E. Blood Cousins Return 二分+主席树

题目链接: http://codeforces.com/problemset/problem/246/E题意:你现在有一棵 1e51e51e5 个结点的树,每个结点有一个权值。你现在有 1e51e51e5 个询问,每个询问会有两个值 v,kv,kv,k ,询问的是结点 vvv 的往下第 kkk 代所有结点中有多少个不同的权值。做法:因为每一层的结点都已经固定了,所以我们可以按照层序遍历来...

2019-11-04 09:54:55

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。