- 博客(39)
- 收藏
- 关注
RSS订阅原创 bzoj2878 [NOI2012] 迷失游乐园 期望+基环树dp
题目描述放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有n个景点、m条道路的无向连通图，且该图中至多有一个环（即m只可能等于n或者n-1）。小Z现在所在的大门也正好是一个景点。小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小Z会一直游玩...
2018-05-25 16:49:04
533
原创 [NOIp2016] 蚯蚓
题目描述本题中，我们将用符号 \lfloor c \rfloor⌊c⌋ 表示对c向下取整，例如： \lfloor 3.0 \rfloor= \lfloor 3.1 \rfloor=\lfloor 3.9 \rfloor=3⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3 。蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有n只蚯蚓（n为正整数)。...
2018-04-29 18:13:57
416
原创 SNOI2018 暴力记
DAY-1：下午中考体考，早上就没去机房，十点才起的床，中午考试前和班里同学谈笑风生了一会，结果都奶我进队，之后体考也凉凉的，50m起跑慢了，1000m没安排好时间，实心球离满分差的贼远，最后47分滚粗，班里绝大多数人都49。DAY0：省选前一天，敲了一天模板，还打了三道SA题，已经为我省选翻车做好了铺垫。晚上机房人几乎都走完了，我一天也没打几个模板，感觉真的要凉了，就再也没管了颓圮去了，打了五局...
2018-04-23 17:39:35
3221
1
原创 bzoj5017 [Snoi2017]炸弹 O(n)递推
5017: [Snoi2017]炸弹Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 320 Solved: 118[Submit][Status][Discuss]Description在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi，爆炸半径是 Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置 Xj 满足： Xi−Ri≤Xj≤Xi+Ri,那么，该...
2018-04-17 20:50:06
880
1
原创 bzoj5248 [2018多省省队联测]一双木棋
5248: [2018多省省队联测]一双木棋Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 155 Solved: 132[Submit][Status][Discuss]Description菲菲和牛牛在一块n行m列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。落子的规则是...
2018-04-09 22:36:49
575
原创 codeforces 895d string mark
D. String Marktime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAt the Byteland State University marks are strings of the same length. Mark x is con...
2018-02-27 16:46:11
333
原创 codeforces895c Square Subsets
C. Square Subsetstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPetya was late for the lesson too. The teacher gave him an additional task. For s...
2018-02-27 16:40:18
442
原创 codeforces900D Unusual Sequences
D. Unusual Sequencestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputCount the number of distinct sequences a1, a2, ..., an (1 ≤ ai) consisting of p...
2018-02-27 16:33:35
304
原创 codeforces920G List Of Integers
G. List Of Integerstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet's denote as L(x, p) an infinite sequence of integers y such that gcd(p, y) ...
2018-02-27 16:01:26
331
原创 codeforces 908E New Year and Entity Enumeration
E. New Year and Entity Enumerationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an integer m.Let M = 2m - 1.You are also given a s...
2018-02-27 15:52:54
353
原创 codeforces 932e Team Work
E. Team Worktime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou have a team of N people. For a particular task, you can pick any non-empty subset ...
2018-02-27 15:43:32
323
原创 codeforces 938e Max History
E. Max Historytime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a of length n. We define fa the following way:Initially fa = ...
2018-02-27 15:35:37
379
原创 codeforces 486d Valid Sets
D. Valid Setstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputAs you know, an undirected connected graph with n nodes and n - 1 edges is called a tr...
2018-02-27 15:25:47
236
原创 codeforces 850b Arpa and a list of numbers
B. Arpa and a list of numberstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputArpa has found a list containing n numbers. He calls a list bad if an...
2018-02-27 15:15:51
183
原创 codeforces789D Weird journey
D. Weird journeytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLittle boy Igor wants to become a traveller. At first, he decided to visit all the...
2018-02-27 14:56:21
768
原创 codeforces 893e Counting Arrays
E. Counting Arraystime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given two positive integer numbers x and y. An array F is called an y-fa...
2018-02-27 11:46:48
410
原创 codeforces888G Xor-MST
G. Xor-MSTtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a complete undirected graph with n vertices. A number ai is assigned to ea...
2018-02-27 11:37:45
332
原创 codeforces 888D Almost Identity Permutations
D. Almost Identity Permutationstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA permutation p of size n is an array such that every integer from ...
2018-02-27 11:27:47
425
原创 codeforces859E Desk Disorder
E. Desk Disordertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA new set of desks just arrived, and it's about time! Things were getting quite cr...
2018-02-27 11:22:46
357
原创 codeforces869c The Intriguing Obsession
C. The Intriguing Obsessiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output— This is not playing but duty as allies of justice, Nii-chan!— Not alli...
2018-02-27 11:11:14
284
原创 codeforces 852F Product transformation
F. Product transformationtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputConsider an array A with N elements, all being the same integer a.Define ...
2018-02-27 11:02:35
244
原创 codeforces 886E&&889C Maximum Element
E. Maximum Elementtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOne day Petya was solving a very interesting problem. But although he used many ...
2018-02-27 10:55:10
644
原创 codeforces 856c Eleventh Birthday
C. Eleventh Birthdaytime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputIt is Borya's eleventh birthday, and he has got a great present: n cards with ...
2018-02-26 11:08:49
533
原创 codeforces 914c Travelling Salesman and Special Numbers
C. Travelling Salesman and Special Numberstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe Travelling Salesman spends a lot of time travelling s...
2018-02-22 11:13:15
440
原创 codeforces 52B Right Triangles
B. Right Trianglestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a n × m field consisting only of periods ('.') and asterisks ('*')...
2018-02-22 11:07:49
725
原创 codeforces 870E Points, Lines and Ready-made Titles
E. Points, Lines and Ready-made Titlestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given n distinct points on a plane with integral coo...
2018-02-22 09:11:20
304
原创 snoi多校模拟赛 t3 z
C Z星球(z.pas/c/cpp)TL:2S ML:512MB【Description】Z星球的居民有独特的命名方式。在Z星球上，子女的名字都由父亲的名字扩展而成。所谓扩展，就是在父亲的名字前面和后面各添加一些字母，也可以不添加。例如父亲的名字是ac，那么他的儿子的名字可以是kacshi，他的孙子的名字可以是kacshidashabi。现在Z星球的领袖手中有一份Z星球所有男性居民的姓名表，共N...
2018-01-19 18:05:32
327
原创 snoi多校模拟赛 1.18 t2 clique
B最大团(clique.pas/c/cpp)TL:3S ML:512MB【Description】给定二维坐标上的N个点，如果两个点之间的距离大于K，则他们不能同时被选取。求最大团的大小。也即，选出最多点，使得这些点两两之间的距离不大于K。【Input】多组测试，第一行一个整数T，表示数据的组数。之后T组数据，每组数据第一行两个非负整数N, K。之后N行，每行两个整数，表示点的坐标。【Outpu...
2018-01-19 00:46:52
327
原创 snoi多校模拟赛 1.18 t3 home
C 回家(home.pas/c/cpp)TL:3S ML:512MB【Description】 Alice和Bob是一对好兄妹。有一天放学后，他们打算回家。但是，他们还想在路上多玩一会。现在他们有一张地图，地图上标注了小镇的所有的N个地点，以及这些地点之间的道路（道路是无向的），共M条。在这N个地点中，有K个地点他们希望一定经过。同时，他们不希望在外面玩太久，所以他们要求经过的点总数...
2018-01-18 22:51:31
342
原创 snoi多校模拟赛 1.18 t1 query
A 查询(query.pas/c/cpp)TL:5S ML:512MB【Description】给定一个含有N个非负整数的序列，请写一个程序，支持以下两个操作：1、Q l r 表示求l至r这一段所有数的和，结果对329701061取模2、C l r 表示将l至r这一段中的每一个数变为其立方。【Input】第一行一个整数N。接下来N行，每行一个整数a[i]，表示初始序列。接下来一个整数Q，表...
2018-01-18 18:12:49
212
原创 bzoj2002 弹飞绵羊
2002: [Hnoi2010]Bounce 弹飞绵羊Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 12641 Solved: 6433[Submit][Status][Discuss]Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地...
2018-01-17 22:40:17
244
原创 snoi多校模拟赛 1.17 t1 path
A 路径规划(path.pas/c/cpp)TL:1S ML:128MB【Description】kAc在数轴上有N片西瓜地。第 i片的坐标是X[i](注意 X并没有排序)。任意两片西瓜地坐标不同。有一天他要给这N片西瓜地浇水。初始他在X[1]的位置。他必须按1..N 的顺序浇水，也就是说，必须先去X[1]，再去X[2]...最后到X[n](他可以沿着坐标轴正方向或者负方向走)。给西瓜地浇水不需...
2018-01-17 17:48:50
276
原创 bzoj4195 noi2015 程序自动分析
惨案？noi现场惊现noipd2t1难度题?4195: [Noi2015]程序自动分析Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 2312 Solved: 1110[Submit][Status][Discuss]Description 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x...
2018-01-17 00:15:40
237
原创 snoi多校模拟赛 1.16 t2
原题：bzoj29002900: 好玩的数字游戏Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 99 Solved: 59[Submit][Status][Discuss]DescriptionTK在虐题的同时，也喜欢玩游戏。现在，有这样的一个游戏，规则是这样的：先随机给出一个数字N，然后你在操场上把1到N的所有数字写成一排，就像这样：123456...
2018-01-16 21:32:10
422
原创 snoi多校模拟赛1.16 t1 光之大陆
原题：bzoj28732873: 光之大陆Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 70 Solved: 33[Submit][Status][Discuss]Description在光之大陆的土地上，各种势力盘根错节。来自光之峡谷的精灵，来自黑暗森林的亡灵，来自古老东方的人类共同生活在一起。善于打造装置的矮人，善于发明的侏儒，隐匿于山林的巨...
2018-01-16 21:19:08
382
原创 snoi多校模拟赛1.15 t3 string
这道题应该是三道里面最良心的一道题了吧。代码量和思维难度都比较小。解法：用trie，先把每个串的长度扩到1000（500*2），然后对于每个点访问时cnt++，最后在所有cnt>1的点中找深度最深的那个，即为答案证明：为什么扩到1000就一定正确呢？懒癌晚期。。。代码：#include <stdio.h>#include <string.h>#include &l...
2018-01-15 18:50:11
215
原创 snoi多校模拟赛1.15 t1 travel
解法：树形dp，dp[k][j][i]表示模k意义下以i为终点长度为i的路径是否存在。转移：因为每次最多走一条边，所以只需要枚举k转移即可，方程见代码，很容易想到。边界条件就是能直接到的点的dp距离值=1。代码中为了简化，使用了三个数组，循环使用，来表示当前点状态，后续状态，总状态。这样就能使写代码快很多，还有就是注意，后续状态转移完之后，还要再枚举一次，得到完整的后续状态，不然会WA！ps：从标...
2018-01-15 16:02:36
218
原创 bzoj1500 noi2005 维修数列
1500: [NOI2005]维修数列Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 15855 Solved: 5269[Submit][Status][Discuss]DescriptionInput输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。...
2018-01-14 22:25:28
364
原创 bzoj4326 noip 2015 运输计划
4326: NOIP2015 运输计划Time Limit: 30 Sec Memory Limit: 128 MBSubmit: 1841 Solved: 1173[Submit][Status][Discuss]Description公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球...
2018-01-06 00:46:05
268
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人