hdu 4782 | 2013 Asia Chengdu Regional Contest B (模拟)

http://acm.hdu.edu.cn/showproblem.php?pid=4782

题意:

将格式混乱的html代码输出成标准格式。

思路:

模拟。

说下细节:

  • 遇到open tag,先打印,后dep++
  • 遇到close tag,先dep–,再打印
  • 遇到空标签,直接在当前深度打印
  • 遇到空白字符时,只有当前面出现了text以及后面也出现了text的时候才打印。也就是说第一个string和最后一个string都是紧邻标签的。

最坑的一点是…虽然题目给了数据组数,但是在</html>所在行的同一行,可能出现下一组的开始<html>

最坑的一点是…虽然题目给了数据组数,但是在</html>所在行的同一行,可能出现下一组的开始<html>

最坑的一点是…虽然题目给了数据组数,但是在</html>所在行的同一行,可能出现下一组的开始<html>

说好的多组数据呢…

 

 

codeforces #413 A. Carrot Cakes (模拟)

题目链接

题意:初始有一个锅,每t分钟可以做好k个饼,现在需要N个饼。还可以另外建一个锅,花费d时间,建好以后两个锅可以并行烙饼。问是否应该建锅?(以期减少烙饼时间)

思路:求出两种情况下的总时间,比较一下。

只有一个锅的情况很好求。

两个锅的情况比较麻烦,不如模拟时间流逝?

反正最多也就1E6的时间。。。模拟一下。。。稳。。

 

 

hihocoder 1197 Give My Text Back (模拟)

#1197 : Give My Text Back

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

To prepare for the English exam Little Ho collected many digital reading materials. Unfortunately the materials are messed up by a malware.

It is known that the original text contains only English letters (a-zA-Z), spaces, commas, periods and newlines, conforming to the following format:

1. Each sentence contains at least one word, begins with a letter and ends with a period.

2. In a sentence the only capitalized letter is the first letter.

3. In a sentence the words are separated by a single space or a comma and a space.

4. The sentences are separated by a single space or a single newline.

It is also known the malware changes the text in the following ways:

1. Changing the cases of letters.

2. Adding spaces between words and punctuations.

Given the messed text, can you help Little Ho restore the original text?

输入

A string containing no more than 8192 English letters (a-zA-Z), spaces, commas, periods and newlines which is the messed text.

输出

The original text.

样例输入
样例输出

比较容易忽视的几个细节是:
连续的空格或者换行符只能有一个;

一个句子是某一行最后一个句子的时候,’.’后没有空格

比较难处理的是,’.’或者’,’前面的空格.

我的做法是,先不处理,最后倒序处理.

 

hdu 2522 A simple problem (模拟,求小数循环节)

题目链接

题意:求一个小数的循环节…

思路:其实直接模拟就好…

模拟竖式计算…

这里用到一个小技巧。

由于多组数据,每次都memset一个bool会很慢,导致超时。

我们可以用一个人int数组来代替每次重置的bool数组,

 

2017 小米 软件工程师 校招 笔试题 (模拟)

题意:一串电话号码,每个数字+8取各位后,把每个数字写成对应的大写英文,从”ZERO”和“NINE”,然后打乱字母的顺序。现在给出打乱的字母顺序,问可能的字典序最小的电话号码是是多少(可能有前导0)

思路:分析0..9 每个数字的英文组成。。。然后大概类似解方程。。可以根据字母的个数确定每个数字的个数。。。

然后-8。。。存一下排个序就好了。。。1A

 

hdu 5835 || ccpc 2016 网络赛 1004 Danganronpa (模拟)

hdu 5835 题目链接
题意:n种礼物,每种a[i]个。现在有无穷个小朋友排成一排,分给每个人一个“普通”的礼物,一个“昂贵”的礼物(哪个普通哪个昂贵是自己定的,或者说,任意的) 要求是相邻的小朋友的普通的礼物不能是同一种。现在问最多能给多少小朋友分礼物。。。

思路:容易知道,因为昂贵的礼物是没有限制的。。所以没什么用。。考虑礼物总数sum..那么最多只可能分给sum/2个小朋友。。。然后再两个指针模拟一下。。记得特判n=1的情况。1A

 

 

whust 2016 #1 D Zhenya moves from the dormitory (贪心,模拟)

题目链接
傻逼模拟。。读完题就ac了。。。

whust 2016 warm up E||codeforces 689 A. Mike and Cellphone (模拟)

cf689A

思路:一个老式的电话键盘。。。。给出一个拨号的移动路径。。。问这个路径是否唯一。

思路:如果唯一就说明。。。不能平移。。。否则不唯一。。

平移可以上下左右。。所以先写4个常亮数组。。。标记平移后的结果。。。设置不合法位就可以了。。。

 

 

BZOJ 1689: [Usaco2005 Open] Muddy roads 泥泞的路 (模拟)

1689: [Usaco2005 Open] Muddy roads 泥泞的路

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 311  Solved: 227
[Submit][Status][Discuss]

Description

Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools. Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely. Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools.

    牧场里下了一场暴雨,泥泞道路上出现了许多水坑,约翰想用一批长度为L的木板将这些水坑盖住.    牧场里的道路可以看成一根数轴,每个水坑可以用数轴上的两个坐标表示,如(3,6)表示从3到6有一个长度为3的水坑.所有的水坑都是不重叠的,(3,6)和(6,9)可以出现在同一个输入数据中,因为它们是两个连续的水坑,但不重叠.
    请你帮助约翰计算最少要用多少块木板才能将所有水坑盖住

Input

* Line 1: Two space-separated integers: N and L * Lines 2..N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the start and end points of a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap.

    第1行有二个用空格隔开的整数N和L.其中1≤N≤10000,表示水坑总数.L为木板长度.
接下来的N行每行有二个用整数si和ei(0≤si<ei≤109),表示一个水坑的两个坐标.

Output

* Line 1: The miminum number of planks FJ needs to use.

    一个整数,表示约翰盖住所有水坑最少要用多少块长为L的木板.

Sample Input

3 3
1 6
13 17
8 12

Sample Output

5

HINT

Source

 

注意区间是左开右闭。

 

bzoj1603: [Usaco2008 Oct]打谷机 (纱布题)

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 774  Solved: 593
[Submit][Status][Discuss]

Description

Farmer John有一个过时的打谷机(收割小麦),它需要带子来带动。发动机驱动轮1总是顺时针旋转的,用来带动转轮2,转轮2来带动转轮3,等等。一共有n(2<=n<=1000)个转轮(n-1条带子)。上面的图解描述了转轮的两种连接方式,第一种方式使得两个轮子旋转的方向相同,第二种则相反。 给出一串带子的信息: *Si—驱动轮 *Di—被动轮 *Ci—连接的类型(0=直接连接,1=交叉连接) 不幸的是,列出的信息是随即的。 作为样例,考虑上面的图解,n=4,转轮1是驱动轮,可以得知最后转轮4是逆时针旋转的。

Input

*第一行:一个数n *第二行到第n行:每一行有三个被空格隔开的数:Si,Di,Ci

Output

*第一行:一个单独的数,表示第n个转轮的方向,0表示顺时针,1表示逆时针。

Sample Input

4
2 3 0
3 4 1
1 2 0

Sample Output

1
思路:傻逼模拟题。。。。排下序。

hdu 5611 || BC #69 div2 1002 Baby Ming and phone number

http://acm.hdu.edu.cn/showproblem.php?pid=5611
题意:给出n个电话号码(长度为11的字符串),满足特殊条件的价格为a,否则为b.特殊条件为最后5位数字一样,最后5位严格递增或者严格递减,最后8位是一个1980年1月一日到2016年12月31日的合法日期。问最后的价值。

 

思路:直接搞….结果死在cin了。。。原来3E6的cin就会TLE。。。。。q神说1E5有的也会tle…..

所以方案是,能不用cin就不要用cin…

如果要读string的话。。。一个解决办法是把数据流同步关掉(是叫这个名字吗。。)

std::ios::sync_with_stdio(false); 会快很多。。。

还有一个办法是先用scanf读 char[] 然后再转化? 没试过==
哦哦还要注意要判闰年。
还有要开long long

 

 

 

 

 

 

cf 611 A||codeforces goodbye 2015 C. New Year and Domino

http://codeforces.com/contest/611/problem/C
题意:给出一个n*m的地图,.表示可以空,#表示墙。一个东西需要占两个相邻的格子,问给定一个矩形,放一个东西的方案数。
思路:q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下,每次标记到后一个点。然后二维的前缀和。然后每次询问的时候,去掉最上边和最左边两条边界上对应的多加的点。

codeforces 31 C. Schedule

http://codeforces.com/problemset/problem/31/C
题意:给出n个借用教室的时间安排,可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。
思路:首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。

如果没有任何冲突,那么答案为n,直接输出一遍就好。

以l为第一关键字,r为第二关键字升序sort下。

如果有一个冲突,那么要看是否有包含关系,如果有,需要去掉大的这个,方案数为1.如果只是相交,那么可以去掉任意一个。方案数为2.

如果有两个冲突,我要看这两个冲突涉及到几个时间安排,如果涉及到4个或者时间安排,那么不可能全部解决,die掉。

如果这两个冲突涉及到三个时间安排,也就是说中间的和两段的相交,那么可以取消中间的这个时间安排来解决冲突。方案数为1.

需要注意的是输出的时候要按照原来的顺序。。所以存的时候记得存一下id.因为排序以后会打乱原有。输出之前还要sort下。 忘了这个。。WA#22/。因为按照id未必是从小到大输出的。

 

 

codeforces 1 B. Spreadsheets

http://codeforces.com/problemset/problem/1/B
题意:给出了两种表格的表示方法。要求互相转化。
思路:直接模拟即可。注意和一般的进制转化不同的是,26进制对应的是1到26而不是0到25,所以要记得处理下借位。

codeforces 158 B. Taxi

http://codeforces.com/problemset/problem/158/B
题意:n组人,每组有si个(1<=si<=4),每辆车能装4个人。问最少需要多少辆车装下所有人并且保证同一组的人在一辆车里。
思路:统计人数分别为1,2,3,4的人数。对于4的直接加到答案。贪心的思路是:优先用人数少的去填人数多的。