4 Top_xiao

尚未进行身份认证

暂无相关简介

等级
TA的排名 3w+

Aizu - 1388 Problem K Counting Cycles

题目意思:给你一个n个点m条边的无向图, 求简单环(度数为2的连通子图)个数。 (n≤1e5,n−1≤m≤n+15,保证图联通)思路:看了 m 的范围, 就要想到要在树上做。最多有 16 条多余的边, 想到 状压。 二进制枚举。首先想一下如果 n 很小的话怎么做。二进制枚举每次要加的边, 然后判断加上这些边能不能构成一个简单环。这些边能不能构成一个简单环的条件是:所有点的度数为 ...

2020-04-13 14:37:51

利用github hexo 搭建个人博客。

Windos 10 系统按照 Node.js官方地址安装 git官方网站根据自己的电脑系统下载下来一路安装就好。安装git之后, 就可以换用 git bash 了, 在文件夹里面鼠标右键,找到 git bash 就可以了。以下所有的命令都会在 git bash 中完成 。安装 hexo新建一个文件夹,命名 blog, 就是自己的博客放在这个 blog 文件夹里面。查看...

2020-04-04 17:16:11

Java 学习(三)接口与继承

父类引用指向子类。如果父类是 static 那么调用的还是父类方法,如果不是 static 那就调用子类的方法。记住 static 就好了。子类引用指向子类那就调用子类的方法。...

2020-03-30 11:17:42

Java 学习(二) 懒汉,饿汉,单例模式

饿汉式单例模式GiantDragon 应该只有一只,通过私有化其构造方法,使得外部无法通过new 得到新的实例。GiantDragon 提供了一个public static的getInstance方法,外部调用者通过该方法获取12行定义的对象,而且每一次都是获取同一个对象。 从而达到单例的目的。这种单例模式又叫做饿汉式单例模式,无论如何都会创建一个实例懒汉式单例模式懒汉式单例模式与饿汉式...

2020-03-29 22:00:23

Java 学习(一) 数组

数组复制:System.arraycopy(src, srcPos, dest, destPos, length)src: 源数组srcPos: 从源数组复制数据的起始位置dest: 目标数组destPos: 复制到目标数组的起始位置length: 复制的长度定义一个数组:int a[] = new int[15]然后用 a.length 那么, length 就是 15;获取...

2020-03-29 20:15:41

bzoj 1040: [ZJOI2008]骑士(树形DP)

 Z国的骑士团是一个很有势力的组织,帮会中汇聚了来自各地的精英。他们劫富济贫,惩恶扬善,受到社会各界的赞扬。最近发生了一件可怕的事情,邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里,在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上,就像期待有一个真龙天子的降生,带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的,但是骑士们互相之间...

2018-09-16 21:27:57

Educational Codeforces Round 82 (Rated for Div. 2) E Erase Subsequences

题目链接题意:给定字符串 s 和 t ,问能否用至多两个 s 的非重叠子序列相加构造出 t思路:首先把 t 串分成两个小串, t1 和 t2然后 dp[i][j] 代表 t1 的 i 位置, t2 串的 j 位置, 匹配 s 串的最短长度。那么 if (i && dp[i-1][j] < n) dp[i][j] = min(dp[i][j], nx[dp[i-1]...

2020-02-23 23:23:48

2019 USP-ICMC K. Candies

链接题意:n 个数, 还有 L, R, 问有多少个本质不同的区间和在 L R 之间。思路:先考虑一个问题 , 长度为 n 的字符串, 求本质不同的子串有多少个。n * (n + 1 ) / 2 然后在减去 height[i] , 这种是求总的, 然后减去重复的。sa 代表排名为 i 的子串在的位置, 然后 height[i] 代表排名为 i 的子串和排名为 i - 1 的子串 重...

2020-02-22 22:40:19

SDU-ACM 2020 Winter Camp Day1

题目链接A Codeforces Round #457 (Div. 2) C. Jamie and Interesting Graph题意:给你 n, m, 让你构造一个图出来,n 个点, m 条边,每条边有权重。 没有重边,没有自环。且从 1 号点到 n 号点最短路的长度是素数。这个图组成的最小生成树的权重和也是素数。思路:先挑一个素数 x 出来, x 大于等于 n,然后我们先...

2020-02-10 23:41:13

Codeforces Round #355 (Div. 2)

linkD Vanya and Treasure题意:n*m的格子,一开始再(1,1)的位置,每个位置都有一个宝箱,每个宝箱都有一个编号,编号为x的宝箱可以被编号为x-1的宝箱里的钥匙打开,1号宝箱没有锁,问打开p号宝箱最少走多少步思路:很显然, 由于 x 只能打开 x+1 的, 所以我们很容易的就想到了暴力 dp, 但是如果 x 的个数, x + 1 的个数乘起来很大的话, 那么我们就...

2020-02-04 12:08:32

Educational Codeforces Round 81 (Rated for Div. 2)

题目链接D. Same GCDs题意:You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a+x,m).思路:gcd(a,m) = gcd(a+x, m)so if gcd(a, m) = kthen gcd(a,m) /...

2020-01-31 19:51:48

Educational Codeforces Round 80 (Rated for Div. 2) D. Minimax Problem

题目链接题目意思:n*m的数组, 选取两行,两行合并成一行,取对应位置上的最大值,然后再取这行的最小值。使这个最小值最大,问这两行的行号。每行的数字最多八个,思路:看到每行最多八个数, 就要想到二进制位优化。首先要二分出来最大的数 x ,对于这个数,我们进行check。然后对于每一行, 这一行中如果大于 x, 就设为1, 否则就设为 0, 这样每行就可以组成一个数 y 。vis[...

2020-01-26 20:03:28

Codeforces Round #605 (Div. 3) E. Nearest Opposite Parity

题目链接题意:N 个数, 每个数a[i], 从 i 这个位置 只可以走到 i + a[i], i - a[i], 前提是走到的位置在 1 - n 之间, 问从 i 这个位置最少走几步走到j,a[i] 和 a[j] 的奇偶不一样思路:我一开始的思路就是用记忆化搜索, f 数组代表当前位 i 的答案, 如果搜到了 j 这个位置 且 j 这个位置的 f[j] 有值, 那么就直接返回就可以了, 但...

2020-01-24 13:47:05

Educational Codeforces Round 78 (Rated for Div. 2) D. Segment Tree

题目链接题意:n 个点, 每个点有一个区间,任意两个区间的值都不一样, 值从 1 - 2*n, 如果两个区间有交,那么代表这两个点有边,问这n个点是不是一棵树思路:刚看完题就会有一个简单的思路:那就是先排序, 然后判断两个点的区间是不是交, 如果是交的话那么就用 并查集 并起来。简单的思路就是这样, 但是实现起来的时候,时间复杂度会很大,所以我们要想一种优化的方法,优化时间复杂度。...

2020-01-22 21:32:37

Codeforces Round #352 (Div. 2)

C. Recycling Bottles题意:在网格上有n个瓶子,现在有两个人A和B,他们有自己的起始位置,还有一个垃圾桶的位置,求捡完瓶子之后两个人走的最短距离是多少。捡瓶子的步骤是:先去捡瓶子,然后扔到垃圾桶。思路:我们先假设把所有的瓶子都捡了,记录一个答案 ans, 代表要走多少路,然后我们找出来从 A 的出发点走会减少多少距离, 从 B 的出发点走会减少多少距离。所以我们只需要...

2020-01-20 20:02:23

Hello 2020 D. New Year and Conference

题目链接题意:有 n 个事件,在 A 会议室开会的时间段是 abegin aend, 在 B 会议室开会的时间段是bbegin bend。 现在的要求是在 A 会议室中任意事件相交,那么在 B 会议室中这些事件也要相交, 同理,在 B 会议室中任意事件相交,那么在 A 会议室中这些事件也要相交, 如果满足条件 输出 YES , 否则输出 NO。思路:对于所有的事件, 我们按照在 A 会议室...

2020-01-20 15:58:22

Codeforces Round #613 (Div. 2) D. Dr. Evil Underscores

题意:给你一些数, 找一个数x, 使得与所有数的亦或最大的那个值 最小 x思路:亦或的话, 肯定是位数是从大到小来枚举, 如果所有的数中,当前位上的值是一样的,那么 x 在这个位上就一定是 0, 如果这个位既有0也有1, 那么就要分两种情况来考虑,填 1 会怎么样, 填 0 会怎么样,然后把数分成两拨,一波是当前位是1 的, 一波是当前位是0的。 然后不断递归下去。 所以dfs 转移的时候...

2020-01-18 18:25:31

Codeforces Round #612 (Div. 2) B. Numbers on Tree

题意:给你一棵树, 还原树上每个节点的价值, 首先树上的每个节点都有一个数,代表这个节点子树中有多少个节点的价值小于当前节点。思路:对于每一个节点,我们维护一个数组,然后数组中的值就是当前节点和当前节点子树的编号, 然后数组中的下标就代表每个节点的价值。dfs 回溯之后,我们就可以知道当前节点插入到数组的哪一个位置。对于怎么维护一个数组, 我们就可以用 vector 。vector 支...

2020-01-18 17:29:41

Codeforces Round #350 (Div. 2) F. Restore a Number

题意:小明写了一个大数字 n ,然后再这个数字后面又加了一个数字 k , k 是 n 的位数现在小明把完整的数字传给了小红, 但是在传输的过程中出现了意外,小红收到的数字的内容是打乱的, 现在知道的是小明还记得 大数字 n 的一部分,也就是他的字串,让你还原这个数字 n, 且让这个数字 n 尽可能的小。记住,不能又前导零, 一个单个的 零 是允许的。输入是小红收到的数还有小明记住的数思...

2020-01-14 11:39:40

dij + spfa + Tarjan

Dij#include<bits/stdc++.h>using namespace std;typedef pair<long long,int> P; //const int N = 2e5+100;int a[N],n,m,k,t;int Head[N],Next[N*2],To[N*2],cnt = 0,val[N*2];long long dis...

2020-01-13 15:52:04

查看更多

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