题目链接

该死的调休，这几天基本都是满课，要么就是两三场比赛打满，根本补不完题，马上周末又是一堆比赛。最近CF不知道在抽什么风，动不动就要验我是不是机器人，然后转圈圈，再返回一个 “Oops！”。提交界面是打不开的，评测结果是 in queue 的，题目是卡时间的，人是忙里偷闲的，rating分是蹭蹭往下掉的。题解尽量肝，肝不出来就先丢 to do list 了。

这场做了4道就润了，有早八不敢熬了。后面的题基本都是看这个题解补的。

这场总体来说还是比较简单的，但是考点比较新奇。D大概是个滑动窗口思想，然后相邻窗口进行递推。E是个差分优化的暴力。F是个博弈，或者够强可以直接guess结论。G是个dp，但是这个dp值需要存储所有可能的约数，最后优化成对所有约数进行暴力验证。H是个状压dp，不太好想，写起来也挺暴力的。

---

A. Yogurt Sale

题意：

在 "Vosmiorochka "商店，一份酸奶的价格是 $a$ 布尔，但现在有促销活动，可以用 $b$ 布尔购买两份酸奶。

马克西姆需要购买的酸奶数量正好是 $n$ 。在购买两份酸奶时，他可以选择以正常价格或促销价格购买。

马克西姆购买 $n$ 份酸奶至少需要花费多少布尔？

思路：

如果买两份酸奶的时候促销价格更便宜，那就促销价格买，否则就用正常价格。可能剩下一个，正常价格买。

code：

#include <iostream>
#include <cstdio>
using namespace std;

int T,n,a,b;

int main(){
	cin>>T;
	while(T--){
		cin>>n>>a>>b;
		if(2*a>b)cout<<n/2*b+n%2*a<<endl;
		else cout<<n*a<<endl;
	}
	return 0;
}

---

B. Progressive Square

题意：

大小为 $n$ 的累进正方形是一个 $n\times n$ 矩阵。马克西姆选择三个整数 $a_{1,1}$ 、 $c$ 和 $d$ ，并根据以下规则构造一个累进正方形：

$$a_{i+1,j}=a_{i,j}+c$$

$$a_{i,j+1}=a_{i,j}+d$$

例如，如果 $n=3$、 $a_{1,1}=1$ 、 $c=2$ 和 $d=3$ ，那么累进正方形如下：

$$\left(\begin{array}{ccc}1& 4& 7\\ & & \\ 3& 6& 9\\ & & \\ 5& 8& 11\end{array}\right)$$

上个月，马克西姆构建了一个累进正方形，并记住了 $n$ 、 $c$ 和 $d$ 的值。最近，他发现了 $n^2$ 个整数，并想确认这些整数确实是个特定累进正方形的元素。

可以证明，对于 $n$ 、 $a_{1,1}$ 、 $c$ 和 $d$ 中的任何值，都存在一个满足所有规则的渐进正方形。

思路：

这个题的 $n$ 很小，而且 $c,d$ 居然告诉你了。

正着去验证 $n\ast n$ 个元素是累进正方形的元素似乎比较困难，但是发现累进正方形左上角的元素一定是最小的，因此我们可以直接找到 $a_{1,1}$ 的值，再加上 $c,d$ 知道，我们直接就知道了累进正方形是什么，排序后每个元素一一验证一下就行。

code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int T,n,c,d;

int main(){
	cin>>T;
	while(T--){
		cin>>n>>c>>d;
		vector<int> a(n*n),b;
		for(int i=0,t;i<n*n;i++){
			cin>>t;
			a[i]=t;
		}
		sort(a.begin(),a.end());
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				b.push_back(a[0]+i*c+j*d);
		sort(b.begin(),b.end());
		
		bool flag=false;
		for(int i=0;i<n*n;i++)
			if(a[i]!=b[i]){
				flag=true;
				break;
			}
		puts((flag)?"NO":"YES");
	}
	return 0;
}

---

C. Inhabitant of the Deep Sea

题意：

$n$ 艘飞船出发探索海洋深处。这些飞船的编号从 $1$ 到 $n$ ，依次递增；第 $i$ 艘飞船的耐久度为 $a_i$ 。

克拉肯按照特定的顺序攻击了这些飞船 $k$ 次。首先，它攻击第一艘飞船，然后是最后一艘，接着又是第一艘，依此类推。

克拉肯的每次攻击都会使飞船的耐久度降低 $1$ 。当船只的耐久度下降到 $0$ 时，它就会沉没，不再受到攻击(因此船只不再是第一艘或最后一艘，克拉肯只攻击尚未沉没的船只)。如果所有的船只都沉没了，克拉肯也就没有什么可攻击的了，于是它就游走了。

例如，如果 $n=4$ 、 $k=5$ 和 $a=[1,2,4,3]$ ，就会发生以下情况：

1. 卡拉基攻击第一艘飞船，它的耐久度变为零，现在为 $a=[2,4,3]$ ；
2. 卡拉基攻击最后一艘飞船，现在为 $a=[2,4,2]$ ；
3. 克拉肯攻击第一艘飞船，现在为 $a=[1,4,2]$ ；
4. 克拉肯号攻击最后一艘船，现在是 $a=[1,4,1]$ ；
5. 克拉肯攻击第一艘飞船，其耐久度变为零，现在为 $a=[4,1]$ 。

克拉肯攻击后有多少艘船被击沉？

思路：

朴素的思路是直接模拟这个过程，但是 $k\le 10^{15}$，会T。

考虑到如果他总的攻击次数不能击穿所有飞船（也就是 $k$ 比所有飞船总的耐久值都高），那么中间一定会剩下一些飞船，而两边受到的伤害其实是差不多的（前面受到 $\lceil \frac{k}{2}\rceil$ 伤害，后面受到 $\lfloor \frac{k}{2}\rfloor$ 伤害）。

所以我们可以把这种割裂的攻击方式转化成比较集中的攻击方式。我们把打一点伤害就换边的方式换成前面打 $\lceil \frac{k}{2}\rceil$ 伤害，后面打 $\lfloor \frac{k}{2}\rfloor$ 伤害的方式就可以了，这样一次可以直接判断能不能打掉一个飞船，时间复杂度为 $O(n)$。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;

int T,n;
ll k;
int a[maxn];

int main(){
	cin>>T;
	while(T--){
		cin>>n>>k;
		ll tot=0,pre=(k+1)/2,suf=k/2;
		for(int i=1
上一篇：C语言 函数——代码风格

下一篇：Canal---＞准备MySql主数据库----＞安装canal