Codeforces Round #274 (Div.1)
VictorWonder
posted @ 2014年10月29日 19:33
in Codeforces
with tags
解题报告
, 1876 阅读
难得的下午场，肯定是要参加的了，在Claris大神的帮助下，最后竟然AC了四道题目，变成了紫名（感觉下一次要狂掉rating了）。
Problem 2A
考试的时候一看题意，直接枚举所有情况，复制粘贴再修修改改，感觉很顺手。
Problem 2B
一共只需要操作1000次，所以直接枚举每一次操作好了，每次操作找到最大和最小的山峰，然后一个加一，一个减一，很明显，最后肯定不存在山峰减了之后又加回来。
Problem 1A
开始时脑抽了，以为会有没有答案的情况。将所有考试按照时间顺序排序，然后判断一下考完第i门之后是第几天。
Problem 1B
这道题卡了我很久，主要是分类讨论太过于恶心，最后也果然是fst了，其实只要将各种情况都考虑到就行了。
主要有这么几种情况：
(1)能够直接找到x和y，那么输出0
(2)能够找到x或y中的一个，那么输出1
(3)能够找到x+y或者y-x，那么输出1
(4)什么都找不到就输出2
Problem 1C
DP题，在最后的两分钟终于做出来了，竟然没有fst，各种感动啊TAT。
f[i]表示目前在第i层，且从最开始一直到现在走到第i层一共有多少种走法，然后用前缀和以及滚动数组搞一下就行了。
Problem 1D
还是DP题，对于每一件物品，放在它上面的东西肯定是要被拿走的（否则就是没有意义的），所以我们只需要依次考虑有哪些物品需要放在第i个物品上就行了。
dp[i][S]表示最上面放置第i个物品且还有S的重量可以承受所获得的最大价值。
Problem 1E
我用的是离线的做法，先将所有的点加入到矩阵里面，再求出一个最大子正方形，然后删除每一个点，每次删除之后都更新一下最大子正方形的大小。
对于每个点我们都要维护其往左走遇到的第一个X和往右走遇到的第一个X，将点(x,y)拿走之后，对于1~n行第y个位置都更新往左和往右能到达的最大位置，接着再从1~x行判断从该行开始能否形成新的更大的子正方形。
代码：
2023年2月01日 20:16
Participating in the CodeForces Round #274 (Div.1) was an exhilarating experience. It took me some time to understand the questions, but with the help of Claris, I was able to successfully solve Lab grown diamonds four questions and become a purple name. Problem 2A was particularly simple; once I understood the meaning of the question, I was able to enumerate all the situations, copy and paste, and then modify them. Problem 2B only required 1000 operations and was easily solved by finding the largest and smallest peaks for each operation, and then adding or subtracting one.
2023年4月23日 19:34
crediblebh