111qqz的小窝

老年咸鱼冲锋!

codeforces #425 B. Petya and Exam (暴力)

题目链接

题意:

给出由小写字母,’?’和’*’组成的字符串s,仅由小写字母组成的字符串t,问按照规则s能否变成t.

规则如下:首先给出定义的[好字母]的字符串,[好字母]之外的都是[坏字母],对于s中每个‘?’,规定其必须替换为一个[好字母]

对于s中的每个‘*’,规定其必须替换为0个或者多个坏字母。

思路:

显然带*的会比较难搞。所以只说带*的情况

我WA了好多次,原因是一开始读错题(或者题意不太清楚?),认为*只能最多替换一个[坏字母]

后来在这个思路上改,越改越复杂orz

仔细想一下,关键点有两个,一个是当前位置有三种情况{没有经过*,经过*且仍在*的作用域内,经过*且已经出了*的作用域}

如何知道*的作用域呢?由于*的替换是连续的,因此只要对比s和t的长度差就可以了。

对于不同的作用域,普通字母的判断位置是不同的,在经过*的作用域之后,普通字母(包括‘?’)记得加一个offset

所以第二个关键点就是,对于*的替换,一次判断完多个。

除此之外,注意下*可能为空的特殊情况,特判一下比较保险。

 

 

 

 

leetcode 437. Path Sum III

题目链接

题意:求一棵二叉树中,所有一段连续路径之和等于给定值的路径数目。

思路:想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。

 

bestcoder #88 || hdu 5908 Abelian Period(暴力)

题目链接

题意:一段数字串,如果一个数字k满足,将该串分成若干个长度为K的子串,这些子串两两满足每个字符出现的次数一样多,那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。

思路:

  • 首先我们发现,所有的阿贝尔周期一定是数字串长度(设为n)的因数。
  • 然后我们还发现。。。如果某个因子是阿贝尔周期,那么该因子的整数倍中恰好也是n的因子的也一定是阿贝尔周期,类似筛法。
  • 然后我们还发现。。。最小的阿贝尔周期一定比数字串中的元素个数大。。。

 

2016-10-02-00-07-21-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

然而其实后面两个不管也可以过吧。。。因为有点忘了n的约数个数的上界了。。。。

还是太保守了。。。

不过hack了四发哈哈哈。。。要是大号的话今天就紫了呜呜呜

2016-10-01-21-11-30-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

 

 

 

seerc 2014 A Banks (暴力)

题目链接

题意:n个数围成一圈,对于负数可以进行magic操作,也就是取反,但是会影响到左右相邻的,加上这个负数。问最少进行多少次magic操作,使得所有数都是非负。

思路:我们知道,如果一个负数想变成整数的话,只能通过magic 操作。唯一可能影响次数的就是顺序。

不过手动写了几个发现顺序好像无关紧要?

于是大胆猜测,写了发暴力2333。

 

codeforces #368 div 2 B. Bakery (暴力)

题目链接

题意:n个城市,m条双向路,要从k条中选择一个,使得到其他n-k个城市中的某个城市的距离最短。

思路:直接暴力 枚举。1A

 

codeforces #368 div 2 A. Brain’s Photos (暴力)

题目链接

。。。这题也能成hack题。。。。有毒啊。。然后我room里所有人都写对了。。。是我看这道题看得太早了?

whust 2016 warm up G ||codeforces 689C. Mike and Chocolate Thieves

cf689C

 

题意:给出一个m。。问恰好使得不超过某个n的a*b^3(a,b是正整数)的方案数为m的n是多少。。。

思路:暴力+二分。。。

 

 

 

poj 3368 Frequent values (暴力+rmq,分类讨论)

poj 3368 题目链接

题意:给出n个非减的数a[i],求区间[l,r]中出现次数最多的数的出现的次数。

思路:由于数列非减,那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i],表示从当前位置向左边延伸最多延伸几个相等的数。

f[i] = f[i-1] + 1 (iff a[i]==a[i-1])

然后查询的时候。

如果直接用ST算法查询rmq的话。。。

可能产生错误结果,原因是f[i]是从左边1到i这段连续区间里当前数出现的次数。

但是查询区间不一定是从1开始,所以查询区间内的第一段连续相等的数可能不完整。。。想了半天。。最后看了题解,发现是这部分暴力来搞。但是如果所有数列中所有数都相等,这样的复杂度就达到了o(1E10)?。。。2s应该过不了吧。。。但是所有题解都是这么写的。。。不是很懂。。。所谓的面向数据编程?

 

不过还是有启示的:分类讨论的思想。一道题未必用一种算法解。如果因为一小部分导致某算法不能用的话,不妨暴力搞之然后再用这个算法。

 

 

 

 

hdu 3183 A Magic Lamp ( 暴力)

hdu3183题目链接

 

题意:n位长的数字串(n<=1000),删掉m个(m<=n),使得剩下的数字串表示的数字最小。 忽略前导0.

思路:暴力搞就可以。要注意每位数字是有一定位置的范围的。比如当前是第i位数字,后面还要取n-m-i位数字,那么第i位数字最多只能取到第k位,k=m+i,因为这样才能保证后面还有n-m-i位数字。

 

BZOJ 1653: [Usaco2006 Feb]Backward Digit Sums(暴力)

 

1653: [Usaco2006 Feb]Backward Digit Sums

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 349  Solved: 258
[Submit][Status][Discuss]

Description

FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this: 3 1 2 4 4 3 6 7 9 16 Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities. Write a program to help FJ play the game and keep up with the cows.

Input

* Line 1: Two space-separated integers: N and the final sum.

Output

* Line 1: An ordering of the integers 1..N that leads to the given sum. If there are multiple solutions, choose the one that is lexicographically least, i.e., that puts smaller numbers first.

Sample Input


4 16

Sample Output


3 1 2 4
OUTPUT DETAILS:

There are other possible sequences, such as 3 2 1 4, but 3 1 2 4
is the lexicographically smallest.

思路:n很小。。一开始做得时候把公式推错了。。3+3算成了4.我的内心是崩溃的。。
其实直接暴力就好。可以用next_permutation来生成全排列,然后判断是否合法。

 

BZOJ 1622: [Usaco2008 Open]Word Power 名字的能量 (暴力)

1622: [Usaco2008 Open]Word Power 名字的能量

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 462  Solved: 228
[Submit][Status][Discuss]

Description

    约翰想要计算他那N(1≤N≤1000)只奶牛的名字的能量.每只奶牛的名字由不超过1000个字待构成,没有一个名字是空字体串,  约翰有一张“能量字符串表”,上面有M(1≤M≤100)个代表能量的字符串.每个字符串由不超过30个字体构成,同样不存在空字符串.一个奶牛的名字蕴含多少个能量字符串,这个名字就有多少能量.所谓“蕴含”,是指某个能量字符串的所有字符都在名字串中按顺序出现(不一定一个紧接着一个).
    所有的大写字母和小写字母都是等价的.比如,在贝茜的名字“Bessie”里,蕴含有“Be”
“sI”“EE”以及“Es”等等字符串,但不蕴含“lS”或“eB”.请帮约翰计算他的奶牛的名字的能量.

Input

    第1行输入两个整数N和M,之后N行每行输入一个奶牛的名字,之后M行每行输入一个能量字符串.

Output

    一共N行,每行一个整数,依次表示一个名字的能量.

Sample Input

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont

INPUT DETAILS:

There are 5 cows, and their names are “Bessie”, “Jonathan”,
“Montgomery”, “Alicia”, and “Angola”. The 3 good strings are “se”,
“nGo”, and “Ont”.

Sample Output

1
1
2
0
1

OUTPUT DETAILS:

“Bessie” contains “se”, “Jonathan” contains “Ont”, “Montgomery” contains
both “nGo” and “Ont”, Alicia contains none of the good strings, and
“Angola” contains “nGo”.

思路:复杂度1E8..5S的时限。。。暴力。。

bzoj 1599: [Usaco2008 Oct]笨重的石子 (暴力)

1599: [Usaco2008 Oct]笨重的石子

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 886  Solved: 614
[Submit][Status][Discuss]

Description

贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店,在那里,她购买了三个不同的骰子,这三个质量均匀的骰子,分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊,想要知道出现几率最大的和是多少。 问题给出三个骰子的面数,让你求出出现几率最大的和是多少。如果有很多种和出现的几率相同,那么就输出小的那一个。

Input

*第一行:三个由空格隔开的整数:s1,s2,s3

Output

*第一行:所要求的解

Sample Input

3 2 3

Sample Output

5

输出详解:

这里是所有可能的情况.

1 1 1 -> 3 1 2 1 -> 4 2 1 1 -> 4 2 2 1 -> 5 3 1 1 -> 5 3 2 1 -> 6

1 1 2 -> 4 1 2 2 -> 5 2 1 2 -> 5 2 2 2 -> 6 3 1 2 -> 6 3 2 2 -> 7

1 1 3 -> 5 1 2 3 -> 6 2 1 3 -> 6 2 2 3 -> 7 3 1 3 -> 7 3 2 3 -> 8

5和6出现的几率都是最大的,所以输出5.

暴力。。。

codeforces #346 div 2 C. Tanya and Toys (暴力乱搞)

题目链接
题意:有1E9个礼物,第i个礼物价钱是i,然后现在已经有n个不重复的礼物,a[i],m元钱,想尽可能多得买不同种类的礼物,还能买多少个。
思路:先不考虑已经买的,从1连续买到k,然后考虑子啊这个区间内已经买的,等于实际上没有花钱。
反正就是暴力搞啊搞啊。。我也不知道怎么搞。。
结果最后。。方案数为0的时候。。。最后一个答案我是单独输出的。。忘了判断了。。。所以会输出两个0.宝宝心里苦啊。。。。。。。。

codeforces 334 B. Eight Point Sets (暴力)

题目链接
题意:给出8个点,问能否构成一个8元素集合,使得x1

codeforces croc2016 A. Amity Assessment (暴力)

题目链接
题意:2×2的格子,有三个位置分别放”A“ “B” “C” ,一个位置为空。只有和空位相邻位置上的字母能移动到空位。没有其他移动规则。现在给出两个状态。问能否互相转化。
思路: 貌似可以dfs…?但是一共才2*2,可以直接暴力枚举。 手写一种变换最多能有12种。