T1
1161. 【普及组模拟赛】作弊(cheat) (File IO): input:cheat.in output:cheat.out
时间限制:
1000 ms 空间限制:
262144 KB 具体限制
Goto ProblemSet
题目描述
凭着奶牛的聪明，他很快就把语数英X四科赶了上来（听说还是半斤八两），但是，可能由于他太聪明了，导致基础科一直搞不好，所以每次考试，他都想作弊，而且他又找回了一些朋友，于是他就试一下作弊的滋味了。他是怎么作弊的呢？奶牛的朋友太强悍了，他生怕被老师发现，又害怕被其他同学偷去，于是他每次递给奶牛都是一段只含有a,b,c,d的字符串，那么答案是什么呢？“答案就是该字符串内最长的回文串。”哈哈哈，奶牛瞬间就发现了这个秘密，可是，奶牛的朋友是个**狂，他每次递给奶牛的都是一些非常长的字符串，奶牛在短时间内没发找到答案，所以奶牛又找到了你，帮他找出字符串内最大的回文串。
输入
第一行：一个数字N，表示字符串的长度。 第2行，一段长度为N的字符串
输出
第一行，一个数字M，表示回文串的长度。 第二行，一段长度为M的回文串，如果有多个解，则输出在原串里最靠前的一个。
样例输入
10
abcdcdcbaa
样例输出
9
abcdcdcba
数据范围限制
提示
【注意】 回文串: 从左往右写和从右往左写都是一样的一段字符串。 对于20%的数据，N<=100 对于100%的数据，N<=10000 因为基础课全部是选择题, 所以奶牛找出回文串之后就按顺序天下去了。第1题答案a,第2题b…… 奶牛的朋友是谁？有时是JBY，有时是TFF，有时是HBL……
T2
1162. 【普及组模拟赛】最大杂置(set) (File IO): input:set.in output:set.out
时间限制:
1000 ms 空间限制:
262144 KB 具体限制
Goto ProblemSet
题目描述
令S为n个元素的集合，则S有2^n-1个子集（除去空集）。现在要你从这2^n-1个子集中选出最多的子集，使这些子集能构成一个杂置。 杂置是指任意两个集合没有包含或被包含的关系。例如对于有3个元素的集合{a,b,c}。 {a,b}，{a,c}，{b,c}可以构成一个杂置，而{a},{b},{a,b}则不能构成一个杂置。
输入
第一行一个t表示包括t组数据，接下来t行每行一个n。
输出
对于每组数据输出最大杂置包含的集合数。结果模12345678。
样例输入
3
1
2
3
样例输出
1
2
3
数据范围限制
提示
【数据范围】 30%的数据t<=10。 100%的数据t<=3000，n<=3000。
T3
1163. 【普及组模拟赛】投影(skyline) (File IO): input:skyline.in output:skyline.out
时间限制:
1000 ms 空间限制:
262144 KB 具体限制
Goto ProblemSet
题目描述
一天你对着眼前的景物拍了一张照，这个相机很特别，有建筑物的地方显示“X”，没有建筑物的地方显示为“.”,假设每个建筑都是块状的，照片长W(1<=W<=1,000,000),用N(1<=N<=50,000)对平面坐标(x,y)( 1 <= x <= W, 0 <= y <= 500,000)描述照片中建筑物高度发生变化的位置,你的任务是计算出最少需要多少个建筑才能形成该照片。 如下图： 在输入中被描述为: (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1).这幅图片最少需要6个建筑，下面是用6个建筑形成该照片的例子：
输入
第一行: 两个空格隔开的整数N,W; 第2到N+1行:两个空格隔开的整数x和y，表示发生改变的点的坐标。输入中x是严格递增的而且第1个x一定是1。
输出
输出最少需要多少建筑才能形成该照片。
样例输入
10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1
样例输出
6
数据范围限制
如题
T4
1164. 【普及组模拟赛】除草(ontherun) (File IO): input:ontherun.in output:ontherun.out
时间限制:
1000 ms 空间限制:
262144 KB 具体限制
Goto ProblemSet
题目描述
一条笔直的路边有N(1 <= N <= 1,000)个草丛，草丛位置互不相同，我们用一个整数表示每个草丛的位置。现在你从某个位置L(1<=L<=1,000^2)出发去除掉所有的草丛，为达到目的你可以来回改变方向去移动，假设你以每秒1个单位距离的速度移动，并且能在到达草丛的瞬间把草除掉。 要求计算草丛被清除的时刻总和的最小值。
输入
第1行:两个空格隔开的整数N和L. 第2到N+1行: 每行一个整数表示草丛的位置P(1 <= P <= 1,000,000).
输出
输出一个整数表示最小清除时刻总和。
样例输入
4 10
1
9
11
19
样例输出
44
数据范围限制
如题
提示
样例说明: 11-10=1 11-9=2 然后加上前面的时间得2+1 9-1=8然后加上前面的时间得8+2+1 19-1=18然后加上前面的时间得18+8+2+1 Ans:=1+(2+1)+( 8+2+1)+( 18+8+2+1)=44
2016.8.16
考试思路：
T1
这题比较简单，就是在字符串第1到n个位置里枚举i就是某个子串的中点，然后向两边走，判断是否一样，特殊情况就是比如像abba这样子的字串，那就需把头赋为现在的i，尾赋为i+1，同样也是向两边走，判断是否一样，每次枚举中点则判断是否要更新ans，如要，则把头和尾也更新，最后输出ans和头到尾形成的字串，就可以了。
T2
就是找规律而已，可以利用杨辉三角，对于每个n，形成了层数为max(n)+1的杨辉三角之后，输出每个f[n+1,(n+1) div 2+1]，就可以了。
T3
比赛时不时很懂题，于是弃了。
T4
一开始看题时觉得应该是d动态规划，可是想了半个多小时的动态转移方程错了，所以只好模拟一下，就是用一个循环表示要走n次，然后每次找出离现在这个点最近的一个点，可以用个r变量表示，然后标记走过了，下次就不能再走了，然后js变量累加从一开始一共走了多远，每次js+p[r]，答案ans就加上js，就可以了。
正确思路：
T1
同上。
T2
同上。
T3
其实这题并不是太难，第一列输入的x其实没有用，只有y才有用，一开始每个改变的点用bz数组标记为false，循环i从1到n，如果bz[i]=false，则说明这里还没被覆盖过，所以ans加一，然后循环j从i+1到n，枚举i后面的点，如果a[i]>a[j]就是说明有一个地方断开凹了下去，所以后面的是不能被现在的这个覆盖的，则break，如果a[i]=a[j]，就是说明i和j这两个位置可以被同时覆盖，所以bz[j]:=true，到j这个位置时就不用判断了。
T4
确实是动态规划，f[i,j,1]表示铲除掉i到j这段路之间的草，停留在i的最少时间总和，f[i,j,2]则表示铲除掉i到j这段路之间的草，停留在j的最少时间总和，所以可推出动态转移方程，在动态规划之前，a数组先要从小到大排个序，使动态规划简单化，进而可以得出程序核心部分，如下：
for i:=1 to n do
<span style="white-space:pre"> </span>for j:=1 to n do
begin
f[i,j,1]:=abs(l-a[i])*n;
f[i,j,2]:=f[i,j,1]; //初始化
end;
for i:=n downto 1 do
<span style="white-space:pre"> </span>for j:=i+1 to n do
begin
f[i,j,1]:=min(f[i+1,j,1]+(a[i+1]-a[i])*(n-j+i),
f[i+1,j,2]+(a[j]-a[i])*(n-j+i));
f[i,j,2]:=min(f[i,j-1,1]+(a[j]-a[i])*(n-j+i),
f[i,j-1,2]+(a[j]-a[j-1])*(n-j+i)); //因为已经排过序，所以f[i,j,1]和f[i,j,2]
end; 可以从各自的前一个和后一个加上a[i]*这段路要重复多少次
write(min(f[1,n,1],f[1,n,2])); //因为我们不知道最后停留在哪个点会更优
转载请注明原文地址: https://ju.6miu.com/read-1311899.html
