Codeforces Hello 2023

第一题

条件等价于最终的结果中必须存在子串 $RLRL$ ，所以只要原字符串中存在 $LRLR$ 或 $RLRL$ 则本题有解，若先搜索到 $LRLR$ 则输出其中 $LL$ 的下标+1 的值，若先搜索到 $RLRL$ 则输出 $00$，若字符串中只有 $LL$ 或 $RR$ 则输出 $-1-1$ 。

第二题

题意：给定一个数组长度 $nn$ ，求是否存在满足数组中各元素之和等于任意两相邻元素之和的数组，若存在则举例

注：$2\le n\le 10002\; \backslash leq\; n\; \backslash leq\; 1000$

若 $nn$ 为偶数，则必可构造出该数组：$[1,-1,1,-1,\mathrm{.}\mathrm{.}\mathrm{.}][1,\; -1,\; 1,\; -1,\; ...]$

若 $nn$ 为奇数，则分两种情况：

1. 若 $n=3n\; =\; 3$ ，则无解
2. 若 $nn$ 为其他任意奇数，则必可构造出数组：$[-(n\mathrm{/}2-1),n\mathrm{/}2,-(n\mathrm{/}2-1),n\mathrm{/}2,\mathrm{.}\mathrm{.}\mathrm{.}][-(n/2-1),\; n/2,-(n/2-1),\; n/2,...]$

第三题

题意：给定长度为 $nn$ 的数组 $aa$ ，给定 $mm$ ，有一操作可使数组 $aa$ 中某一元素取负，即 $a_i=-a_{i}a\_\{i\}\; =\; -a\_\{i\}$ ，求使 $a[1]+a[2]+\mathrm{.}\mathrm{.}\mathrm{.}+a[m]a[1]\; +\; a[2]\; +\; ...\; +\; a[m]$ 为最小前缀和的操作数

即对于给定的 $m(1\le m\le n)m(1\; \backslash leq\; m\; \backslash leq\; n)$ ，都有任何一个 $k(1\le k\le m)k(1\; \backslash leq\; k\; \backslash leq\; m)$ ，使 $a[1]+a[2]+a[3]+\mathrm{.}\mathrm{.}\mathrm{.}+a[k]\ge a[1]+a[2]+a[3]+\mathrm{.}\mathrm{.}\mathrm{.}+a[m]a[1]+a[2]+a[3]+...+a[k]\; \backslash geq\; a[1]+a[2]+a[3]+...+a[m]$

我们定义 $[L,R]=a[L]+a[L+1]+\mathrm{.}\mathrm{.}\mathrm{.}+a[R-1]+a[R][L,\; R]\; =\; a[L]\; +\; a[L\; +\; 1]\; +\; ...\; +\; a[R\; -\; 1]\; +\; a[R]$

分类讨论一下：

• $k\le mk\; \backslash leq\; m$ 时，
  • $a[1,k]\ge a[1,m]\Rightarrow a[1,k]+a[k+1,m]>=a[1,m]\Rightarrow a[k+1,m]\le 0a[1,\; k]\; \backslash geq\; a[1,\; m]\; \backslash Rightarrow\; a[1,\; k]\; +\; a[k\; +\; 1,\; m]\; >=\; a[1,\; m]\; \backslash Rightarrow\; a[k\; +\; 1,\; m]\; \backslash leq\; 0$
  • 可以得到，任意的 $i\in [2,m]i\; \backslash in\; [2,\; m]$ 都有 $a[i,m]\le 0a[i,\; m]\; \backslash leq\; 0$
• $k>mk\; >\; m$ 时，
  • $a[1,k]\ge a[1,m]\Rightarrow a[1,m]+a[m+1,k]\ge a[1,m]\Rightarrow a[m+1,k]\ge 0a[1,\; k]\; \backslash geq\; a[1,\; m]\; \backslash Rightarrow\; a[1,\; m]\; +\; a[m\; +\; 1,\; k]\; \backslash geq\; a[1,\; m]\; \backslash Rightarrow\; a[m\; +\; 1,\; k]\; \backslash geq\; 0$
  • 可以得到，任意的 $i\in [m+1,n]i\; \backslash in\; [m\; +\; 1,\; n]$ 都有 $a[m+1,i]\ge 0a[m\; +\; 1,\; i]\; \backslash geq\; 0$

所以我们贪心的考虑即可

代码：

LL T;
cin >> T;
while (T --)
{
	LL n, m;
	cin >> n >> m;
    
	multiset<LL> st;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	
	LL sum = 0, res = 0;
	for (int i = m;i >= 2;i --) // 倒序
	{
	    sum += a[i];
	    st.insert(a[i]);
	    while (sum > 0) // 贪心的把最大的数取负
	    {
	        LL t = *(prev(st.end()));
	        sum -= t;
	        sum += -1 * t;
	        st.erase(prev(st.end()));
	        res ++;
	    }
	}
	
	st.clear();
	sum = 0;
	for (int i = m + 1;i <= n;i ++)
	{
	    sum += a[i];
	    st.insert(a[i]);
	    while (sum < 0) // 贪心的把最小的数取负
	    {
	        LL t = *(st.begin());
	        sum -= t;
	        sum += -1 * t;
	        st.erase(st.begin());
	        res ++;
	    }
	}
	
	cout << res << endl;
}

第四题（未解决）

贪心+数据结构

补题网址：https://zhuanlan.zhihu.com/p/596398202