ciel_s-CSDN博客

原创 poj 1364 King （差分约束 spfa）

题目链接接触了差分约束系统，其实就是最短路。这个题目题意理解起来有点麻烦，不过其实是很简单的模板题。注意的点：用spfa时，因为图可能不是联通的，所以要加一个花费为0的超级源点。题目给点限制条件是大于小于，但是差分约束系统是有等号的，对于整数来说只要加一减一就可以。记录模板#include <iostream>#include <cstdio>#include <cstring>#in

2017-09-13 22:51:42 272

原创 hdu 6170 Two strings （dp）

题目链接刚开始想用模拟的方法去做，但是*的处理比较麻烦就很难写。后来用dfs 的方法去写结果会超时…… 比赛结束之后看题解说是dp，然后就去往这个方向思考，然后发现dp确实能做= =用dp[i][j]表示b[i]和a[j]是否匹配。 if b[i]==a[j]||b[i]==’.’ dp[i][j]=dp[i-1][j-1] ;if b[i]==’*’ 此时b[i-1]可以出现0次或1次或更多

2017-08-23 16:07:12 260

原创 hdu 6153 A Secret (KMP)

题目链接因为要求字符串的所有后缀和另一个串的匹配，和kmp中匹配时求next数组有相似之处。可以把先把他们做一个转置的处理，再跑一遍kmp。同时用一个num数组来记录前缀长度为i时的匹配次数。但是我们这时求得的num并不是最终答案，要得到正确的num还需要一个累加的过程。即num[next[i]]+=num[i]。然后就可以求得答案了。#include <iostream>#include <

2017-08-21 19:50:45 321

原创 hdu 6143 Killer Names （组合数，递推）

链接今天下午多校赛的痛苦经历……下午的时候在选出一些数字放入n有多少种方式计算时，只想着怎么用排列组合的方式计算出来，然后发现计算量简直爆炸……然后就gg…… 后来的发现递推这种方法。首先假如用x个字母去填n，那所有的情况就是x^n，然后分别减去只用了1、2…到x-1种字母的情况，就是x个字母全用上的组合方式。处理出来这些之后，答案就是第一个单词用1~m-1种，第二个字母用1~m-i种方案的组

2017-08-17 22:07:47 291

原创 2017江苏省赛jscpc赛后总结

刚刚打完的省赛，拿到了队伍的第一块牌，还是有点开心的。然而比赛过程全靠队友carry，自己实在是好废啊orzzz刚开始的时候d和i题都做的很快，两题之后我们竟然在金牌区，当时确实是有一点点小激动的，之后的一段时间榜上都没有开新题，我们就把所有的题差不多都读了一下，想贪心一发b结果发现思路有点问题，这个时候榜单刷出了h和e。 h感觉像图论的题目，看起来可以做，就一直在想h，和tt讨论了一下都没有

2017-05-15 19:42:32 749

迟来的女生赛总结，还是写一下吧第一题水题是我敲的，本来先拿到试题看了之后想了想觉得没问题就直接敲了，结果发现样例没过。。学妹看了看说我少考虑情况了，确实……然后发现自己之前的还要大改，第一次交上去的时候已经过去了不少时间，读题要认真QAQ 然后就是第二题的dp了，现在回过头来看我当时的dp思路整个就是偏掉了，所以状态怎么都转移不好，导致写的很长的代码，调了半天虽然过了样例，交上去始终wa，后来举了

2017-05-14 23:21:10 508 1

原创 hdu 6024 Building Shops (dp)

题意：有n个教室，从左到右建若干糖果屋，要求每个教室的本身或者左边至少有一个糖果屋，如果在这个点建糖果屋，花费为每个点的c，如果不建，花费为这个点到左边最近的糖果屋距离。求最小花费。很明显是一道dp的题目，然而在比赛的时候却没有做出来，而且思路是完全偏了……所以挣扎了很长时间也没做出来，还是觉得自己好菜啊……dp状态的定义其实是关键……如果状态定义对了，转移方程就很好想了，但是比赛的时候不知道为什么

2017-05-08 20:02:53 455

原创 hdu 6030 （矩阵快速幂）

题意：给你一串珠子，要求任意素数区间段内红色大于蓝色，问有多少种方案。赛后补题…… 我们首先可以发现只要考虑2和3就可以了，因为其他任意区间都可以拆成2和3的组合，所以只要2和3满足就一定可以。然后我们写一下就可以发现规律，如果新加一颗红色，那只要之前的满足就一定可以满足，如果新加一颗蓝色，只有红红蓝这种情况下才可以，所以就有递推式F(x)=F(x-1)+F(x-3) 2 3 4对应的情况我

2017-05-08 16:25:41 979

原创 hdu 6026 Deleting Edges（最短路）

题意：给你一个图，然后删去一些边（可以不删）使其变成一棵树，要求每条边到0点的距离最短。女生赛题目第4题，当时觉得很简单，只要跑一遍dijkstra，然后统计对于每个顶点最短路相同时的路径个数，最后乘一下就好。结果敲了一遍交上去wa了……百思不得其解，最后也没想出来是哪里的问题。结束之后把打印的代码给学长看，结果上来就被一通骂= =“你连dijkstra的原理都没搞懂吧……” 恩……确实是

2017-05-08 16:18:03 815

原创 hdu 4857 逃生（拓扑排序）

题目链接题目大意就是：给你一些先后关系，然后输出它们的拓扑序，但是和普通的不一样的地方，输出使编号小的数字尽量靠前的拓扑序，而不一定是字典序。例如： 4—>2 5—>1—>3正常情况下字典序最小的拓扑序应该是：4 2 5 1 3 这种规则下，则应该是： 5 1 4 2 3解法：自己其实是没有想到看题解的QAQ 在当前入度为0的点中，我们先输出哪个并不能完全取决于这个点的大小，而是

2017-04-25 00:17:30 353

原创 hdu 6006 Engineer Assignment（状压dp）

题目链接Problem DescriptionIn Google, there are many experts of different areas. For example, MapReduce experts, Bigtable experts, SQL experts, etc. Directors need to properly assign experts to various pro

2017-04-24 15:48:53 1218

原创 zoj 3777 Problem Arrangement（状压dp）

题目链接The 11th Zhejiang Provincial Collegiate Programming Contest is coming! As a problem setter, Edward is going to arrange the order of the problems. As we know, the arrangement will have a great effec

2017-04-16 22:53:13 388

原创 2017WHU校赛OL Werewolf （基环外向树）

题目链接题目大意：有n个玩家，编号1~n，已知狼人不会投狼人，其他人可能投任何人，给你一局投票的情况，判断最多有多少狼人。比赛时没有什么思路，题解说是基环外向树，第一次听到这个名词感觉十分高端，搜了一下才发现这个东西就是一颗普通的树再加上一条边，那么一定会在这个树里形成一个环，外向树是说其他链的方向指向外，内向树则是指向内。对于n个玩家，每个人投一票，构成的关系便有n条边，这些点不一定是相互连通的，

2017-04-12 22:00:01 453

原创 hdu 3549 Flow Problem（最大流模板题）

题目链接最大流的模板题，今天写了一个dinic的模板想测试一下，结果T到天荒地老，一度怀疑人生，到最后发现竟然是数组开小了。。。双向边数组要开两倍啊。。。我这个智障……记录模板 Dinic + 链式前向星存图#include <iostream>#include <queue>#include <cstdio>#include <cstring>#include <string>usi

2017-04-12 21:31:08 423

原创 poj 2387 Til the Cows Come Home （最短路）

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get ba

2017-04-04 21:20:22 279

原创 poj 1251 Jungle Roads（最小生成树）

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so

2017-04-04 21:15:18 287

原创 poj 2836 Rectangular Covering （状压dp）

n points are given on the Cartesian plane. Now you have to use some rectangles whose sides are parallel to the axes to cover them. Every point must be covered. And a point can be covered by several rec

2017-04-04 20:49:57 245

原创 poj 3254 Corn Fields（状压dp）

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, s

2017-04-04 20:20:47 199

原创 poj 2441 Arrange the Bulls（状压dp）

Farmer Johnson’s Bulls love playing basketball very much. But none of them would like to play basketball with the other bulls because they believe that the others are all very weak. Farmer Johnson has

2017-04-04 20:11:39 334

原创 poj 2686 Traveling by Stagecoach （状压dp）

DescriptionOnce upon a time, there was a traveler. He plans to travel using stagecoaches (horse wagons). His starting point and destination are fixed, but he cannot determine his route. Your job in thi

2017-04-04 19:51:45 334

原创 hdu 4734 F(x) 数位dp

题目链接Problem DescriptionFor a decimal number x with n digits (AnAn-1An-2 … A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + … + A2 * 2 + A1 * 1. Now you are given two numbers A and B, ple

2017-03-26 21:35:48 359

原创 Codeforces 786A Berzerk（博弈）

题目链接很明显的博弈题目，但是昨天打比赛的时候就是一直想不出来，一直在纠结这个loop的情况到底要怎么定义，感觉到深深的挫败感，自己之前专门看了一段时间博弈也没有任何用处= =太菜了今天看了一下题解，发现思路其实还是很简单的，对于每个点都有两种状态，a推到这里和b推到这里，我们可以知道，对于1这个位置，无论哪个人在面临这样的局面时，都是必败态，我们从这个点出发，如果这个点是必败态（0），那么对于所有

2017-03-24 21:15:11 921 1

原创 hdu 2089 不要62 （数位dp入门）

题目链接Problem Description杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如： 62315 73418 88914 都属于不吉利号码。但是，61152虽然含有6

2017-03-19 20:43:55 320

原创 zoj 3537 Cake （凸包最优三角剖分）

题目链接这道题目是一道最优三角剖分的题目，其实也是一种区间dp里的一种应用，思路也很简单。这道题目还需要先是不是凸包，这里其实主要想记录一下凸包模板==#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const dou

2017-03-19 18:53:05 408

原创 zoj 3469 Food Delivery（区间dp）

题目链接When we are focusing on solving problems, we usually prefer to stay in front of computers rather than go out for lunch. At this time, we may call for food delivery.Suppose there are N people living

2017-03-13 20:31:18 282

原创 hdu 2476 String painter（区间dp）

Problem DescriptionThere are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change

2017-03-11 18:47:19 202

原创 CodeForces - 149D Coloring Brackets（区间dp）

题目链接这是一道区间dp的题目……怎么说呢，让我认识到我之前对区间dp的理解太浅显和模式化了，总觉得就是枚举每个区间段就可以了， ==确实是我刷的题还太少。这道题目也是对于这些颜色该怎么处理无从下手，看完题解才觉得好巧妙。dp[rl[r][prel][prer]，用这个数组来表示每个区间的状态，prel prer即代表这个区间外的紧挨的两个括号的颜色，有三种状态0 1 2，0为不染色，1为红色，

2017-03-10 18:15:25 240

原创 hdu 4283 You Are the One（区间dp）

题目链接Problem Description　　The TV shows such as You Are the One has been very popular. In order to meet the need of boys who are still single, TJUT hold the show itself. The show is hold in the Small hal

2017-03-10 17:55:43 215

原创博弈题目小结

闲聊最近一周基本上都在看博弈，也看了几篇大家所说的经典的论文，今天稍微总结一下博弈中常见的题目类型。还有，入门的时候真的很推荐去看张一飞的那篇论文，有很详细的引入过程，我之前一直不是很理解为什么nim游戏就能和异或扯上关系……看完这篇论文后才有些理解。Nim Gamenim游戏真的是很经典的游戏，很多种游戏都是由它延伸变形而来。规则如下：n堆石子,双方轮流从任意一堆石子中取出至少一个,不能取的人

2017-03-06 20:35:34 963

原创 hdu 3094 A tree game （博弈树的删边问题）

题目链接Problem DescriptionAlice and Bob want to play an interesting game on a tree. Given is a tree on N vertices, The vertices are numbered from 1 to N. vertex 1 represents the root. There are N-1 edges

2017-03-05 22:52:58 443

原创 poj 3710 Christmas Game（博弈无向图删边游戏）

题目链接贾志豪的论文里提到的经典题目，关于树的删边，没有环的情况下，有一个结论：每个节点的sg值的所有的子节点sg值加一的异或，叶子结点的sg值为0。而这道题目中的树经过了特殊处理会有环的存在，但是保证环只会有一个点和树相连。这里要用到The Fusion Principle（融合定理）：将图中任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加新边；所有连到原来环上的边全都改成与新点相连。

2017-03-05 22:46:12 396

原创 hdu 5745 La Vie en rose（bitset优化dp）

题目链接去年多校赛的一道题目，今天下午拿来训练的时候做的，刚开始题意卡了半天，根本没有看懂，后来才发现那个下标的大小决定了我们题目理解的是否正确== 总之大意就是，有一串长字符s，短字符p，p中相邻的字母可以进行交换但不能重复交换，问以s的每个字符开头是否能匹配p或者p的变形。理解题意后发现这道题的思路还是相当简单的，就是一个很普通的dp，但是问题是数据规模，正常的dp时间复杂度为o(m*n)，5

2017-03-05 00:04:15 479

原创 poj 2315 Football Game （博弈 nim k game）

题目链接DescriptionAlice and Bob both love football very much, and both of them are vanguards. They are both good at football control. One day after a football match, they play an interesting game, in whic

2017-03-03 21:29:26 623

原创 uva 1378 A Funny Stone Game（博弈论）

题目链接这是看王晓珂的论文里遇到的第一个例题，之前看了很久都没看懂……题目大意就是有n堆石子，每次从第i堆里取出一颗石子并向i之后的堆j k（j可以等于k）各放入一颗石子，最后不能操作者输。这个题目思路里很重要的一句话就是，可以把每一颗石子当成一堆石子来看，如果是第p堆，那它所代表的这堆石子个数为n-1-p。这句话一直没有理解，现在有点懂了吧。对于这个游戏，最终状态是每个石子堆的sg函数异或结果，那

2017-03-03 00:09:34 648

原创 poj 1947 Rebuilding Roads （树形背包）

DescriptionThe cows have reconstructed Farmer John’s farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn’t have time to rebuild any extra roads, so

2017-02-26 22:56:28 282

原创 hdu 1011 Starship Troopers （树形背包）

Problem DescriptionYou, the leader of Starship Troopers, are sent to destroy a base of the bugs. The base is built underground. It is actually a huge cavern, which consists of many rooms connected with

2017-02-24 15:25:55 221

原创 hdu 4003 Find Metal Mineral（树形dp+分组背包）

Problem DescriptionHumans have discovered a kind of new metal mineral on Mars which are distributed in point‐like with paths connecting each of them which formed a tree. Now Humans launches k robots on

2017-02-23 19:08:14 274

原创 poj 2486 Apple Tree （树形dp）

DescriptionWshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There are N nodes in the tree. Each node has an amount of apples. Wshxzt starts her happy trip at o

2017-02-22 23:08:04 237

原创 poj 2152 Fire（树形dp）

DescriptionCountry Z has N cities, which are numbered from 1 to N. Cities are connected by highways, and there is exact one path between two different cities. Recently country Z often caught fire, so t

2017-02-22 01:49:26 384

原创 poj 1741 Tree （树的分治）

TreeTime Limit: 1000MS Memory Limit: 30000K Total Submissions: 20776 Accepted: 6803DescriptionGive a tree with n vertices,each edge has a length(positive integer less than 1001). Define

2017-02-20 17:03:08 320

空空如也

关于安卓开发中高德地图的定位问题，amaplocationlistener出现问题