Educational Codeforces Round 103 (Rated for Div. 2)

比赛地址

A（水题）

题目：
给出\(n\)和\(k\)询问，若\(k\)能整除\(n\)个数累加和，问这\(n\)个数中最大值最小化时值为多少

解析：
由题目条件知\(n\ge 1\)，如果\(n\le k\)，则每个元素至少为1，那么这样情况下平均分配能让最大值最小化，同理\(n>k\)时，则使得\(n\le dk\)，且\(dk\%n<k\)也就是让这个\(dk\)越小越好

注：\(\lceil\frac{a}{b}\rceil=\lfloor\frac{a+b-1}{b}\rfloor\)

#include<bits/stdc++.h>
using namespace std;
/*===========================================*/
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n, k;
		scanf("%d%d", &n, &k);
		k *= (n + k - 1) / k;
		printf("%d\n", (k + n - 1) / n);
	}
}

B（贪心）

题目链接
⭐

题目：
给出\(p\)数组，公式\(k_i=\frac{p[i]}{\sum_{j=0}^{i-1}p[j]}\)，要求\(k_i\)均小于等于指定数值\(k\%\)，现在如果要满足这个要求，可能需要对数组\(p\)部分元素进行增加，则总增加量最小是多少

解析：
不难发现对于当前\(i\)来说，增加自己或者增加\(j(j>0)\)，是充满不确定性的，因为这样的操作可能会使得\(k_i>k\%\)，所以如果增加值全部汇聚在\(p_0\)是最好的（\(k_0\)与题目要求无关），那么只需要找到使得每个元素符合要求的最小增加量即可

#include<bits/stdc++.h>
#define rep(i,a,b) for(int  i=a;i<b;++i)
typedef long long LL;
using namespace std;
/*===========================================*/

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		LL sum, t;
		LL ret = 0;
		int n, k;
		scanf("%d%d", &n, &k);
		scanf("%lld", &sum);
		rep(i, 1, n)
		{
			scanf("%lld", &t);
			if (100 * t > k * sum)
			{
				LL tmp = (100 * t + k - 1) / k;
				ret += tmp - sum;
				sum = tmp;
			}
			sum += t;
		}
		printf("%lld\n", ret);
	}
}

C（思维）

题目链接
⭐⭐⭐

题目：
给出\(n\)条链长度为\(c[i]\)和\(a,b\)数组，数组表示第\(i\)条链的“1”端连接至第\(i-1\)条链的\(a[i]\)处，“\(c[i]\)”端连接至第\(i-1\)条链的\(b[i]\)处，假设每个连接的长度为单位长度，求这个图中的最大环

解析：

由于两两链之间只能靠\(a[i],b[i]\)决定的边相连，所以这个最大环的求解是一个线性递推的过程
假设当前下标为\(i\)，可以将环的构造抽象为为2种可能性：①以第\(i-1\)条链为圈的边界 ②不以第\(i-1\)条链为圈的边界，两种情况下所得到的最大值加上当前\(c[i]\)链长度（即将环封闭），更新最大值即可
对于①的情况，则为\(2+|a[i]-b[i]|\)
对于②的情况，为避免点的重复经过，此时新增的长度为\(2+(c[i-1]-\max(a[i],b[i]))（距离右端点）+(\min(a[i],b[i])-1)（距离左端点）\)

注意：

处于第\(1\)条链时，只能以第\(0\)条链为边界，所以只能考虑①的情况
注意开\(long\ long\)

#include<bits/stdc++.h>
#define rep(i,a,b) for(int  i=a;i<b;++i)
typedef long long LL;
using namespace std;
/*===========================================*/

const int maxn = 1e5 + 5;
int a[maxn], b[maxn], c[maxn];
LL ret, now;


int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		scanf("%d", &n);
		rep(i, 0, n)
			scanf("%d", &c[i]);
		rep(i, 0, n)
			scanf("%d", &a[i]);
		rep(i, 0, n)
			scanf("%d", &b[i]);
		now = ret = 0;
		rep(i, 1, n)
		{
			if (i != 1)
			{
				if (a[i] == b[i])
					now = 2;
				else
					now += 2LL + min(a[i], b[i]) - 1 + c[i - 1] - max(a[i], b[i]);
			}
			now = max(now, 2LL + abs(a[i] - b[i]));
			ret = max(ret, now + c[i] - 1);
		}
		printf("%lld\n", ret);
	}
}

D（思维）

题目链接
⭐⭐

题目：
给出一个字符串，如果第\(i\)个字符为\(L\)则代表存在通路\(i-1\rightarrow i\)，\(R\)代表存在通路\(i-1\leftarrow i\)，且每使用一次道路，所有道路方向反向，那么求出起始点在第\(i\)点能够途径点数的最大值

解析：

假设从\(i\)点出发，可以向某个方向前进，那么，在朝那个方向前进后，由于道路的转向可以使得按照原线路返回，且由于一来一回肯定使用了偶数次道路，那么回到起始点时，道路状态与初始时相同，那么即求从\(i\)点向左向右能行进的最大距离之和
而行进距离则就是看左右两边各有多少个交替的\(RL\)序列，求左边的序列长度可以正序遍历字符串，右边的序列长度可以倒序遍历字符串

#include<bits/stdc++.h>
#define rep(i,a,b) for(int  i=a;i<b;++i)
#define rep1(i,a,b) for(int  i=a;i<=b;++i)
#define rrep(i,a,b) for(int i=b-1;i>=a;--i)
#define rrep1(i,a,b) for(int i=b;i>=a;--i)
using namespace std;
/*===========================================*/

const int maxn = 3e5 + 5;
char s[maxn];
int l[maxn], r[maxn];

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		scanf("%d%s", &n, s + 1);
		l[0] = r[n] = 0;
		int cnt = 0;
		rep1(i, 1, n)
		{
			if (s[i] != s[i - 1])
				++cnt;
			else
				cnt = 1;
			if (s[i] == 'L')
				l[i] = cnt;
			else
				l[i] = 0;
		}
		cnt = 0;
		rrep1(i, 1, n)
		{
			if (s[i] != s[i + 1])
				++cnt;
			else
				cnt = 1;
			if (s[i] == 'R')
				r[i - 1] = cnt;
			else
				r[i - 1] = 0;
		}
		rep1(i, 0, n)
			printf("%d ", l[i] + r[i] + 1);
		printf("\n");
	}
}

E（状压+拓扑序）