;;;ppp账户设置 - 黑猫OJ

This person is lazy and didn't join any contests or homework.😕~~

]

• [ l;'] >

| popo | popo| oop | | --pop- | -pop-- | --pop | | opop| opop | popo | 点我有惊喜

海底高铁

题目描述

该铁路经过 $N$ 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第 $i$ 段铁路连接了城市 $i$ 和城市 $i+1(1\leq i<N)$。如果搭乘的比较远，需要购买多张车票。第 $i$ 段铁路购买纸质单程票需要 $A_i$ 博艾元。

虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第 $i$ 段铁路，需要花 $C_i$ 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣 $B_i(B_i<A_i)$ 元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第 $i$ 段铁路的 IC 卡，无法乘坐别的铁路的车。

Uim 现在需要出差，要去 $M$ 个城市，从城市 $P_1$ 出发分别按照 $P_1,P_2,P_3,\cdots,P_M$ 的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。

现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。

输入格式

第一行两个整数，$N,M$。

接下来一行，$M$ 个数字，表示 $P_i$。

接下来 $N-1$ 行，表示第 $i$ 段铁路的 $A_i,B_i,C_i$。

输出格式

一个整数，表示最少花费

样例 #1

样例输入 #1

9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10

样例输出 #1

6394

提示

$2$ 到 $3$ 以及 $8$ 到 $9$ 买票，其余买卡。

对于 $30\%$ 数据 $M=2$。

对于另外 $30\%$ 数据 $N\leq1000，M\leq1000$。

对于 $100\%$ 的数据 $M,N\leq 10^5，A_i,B_i,C_i\le10^5$。

[NOIP2011 普及组] 统计单词数

题目描述

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例 1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例 2）。

输入格式

共 $2$ 行。

第 $1$ 行为一个字符串，其中只含字母，表示给定单词；

第 $2$ 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

输出格式

一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 $0$ 开始）；如果单词在文章中没有出现，则直接输出一个整数 $-1$。

注意：空格占一个字母位

样例 #1

样例输入 #1

To
to be or not to be is a question

样例输出 #1

2 0

样例 #2

样例输入 #2

to
Did the Ottoman Empire lose its power at that time

样例输出 #2

-1

提示

数据范围

$1\leq$ 第一行单词长度 $\leq10$。

$1\leq$ 文章长度 $\leq10^6$。

noip2011 普及组第 2 题

代码解析：

本题解法采用了栈的逻辑结构及数组的数据结构解题，h[]数组按顺序存储每列方块的高度；stk[]数组以模拟栈的方式存储未经处理的列的编号，依旧按照先进后出的规则，一旦开始处理stk里的元素，就会最后一项开始处理。

而如何利用这个性质解决题目才是解题的关键，总体分为堆栈、出栈两个过程：

$1）$

堆栈：当新的一列高度大于等于前一项时，执行堆栈操作，每一个存进stk的元素（列的编号）也因此符合一个规律：stk的第i项对应的高度，即h[stk[i]]小于等于第i+1项的高度，这一性质是用于之后计算面积时宽度的确定；

$2）$

出栈：当新的一列高度小于前一项时，就可以开始处理栈中的数据了，因为目前的一列是第一次比前一行低，而栈中的每一列高度都大于等于栈中前一项的列数的高度，所以对于栈中所有列的对应高度，其宽度向右一定能取到第i-1列； 而又因为栈中的每一列高度都小于等于栈中前一项的那一列的高度，所以对于任意一列stk[tp]的高度，其最左只能取到stk[tp-1]这一项对应的列数的右边一列，所以最终宽度确定为i-1-stk[tp-1]，对于这一结论，小于的情况自不用说，如果stk中相邻2列的高度相等，那么在计算更前一项时自然会得出正确的结果。 考虑到其中某一行的高度可能继续向后延伸，当stk的第tp项的高度小于等于最新一行高度时也会立刻停止，从第tp+1项继续堆栈。

另外一些小细节，因为处理数据时永远只能从前一列开始处理，因此循环范围额外取到了第n+1列，并限制了第n+1次是不会输入数据的； 而h+i是一个指针，指向h数组的最初物理地址向后i （元素的数据类型所占字节数）的位置，与h[i]并无区别