Preface

补题

A~D都能秒出，E没看出性质被薄纱了，F感觉是个丁真题随便讨论下就过了

后面看了下F的标算是个倍增，感觉Tutorial对性质挖掘的还不够的说

A. Garland

SB题，设出现次数最多的颜色个数为\(cm\)，若\(cm\le 2\)则答案为\(4\)；若\(cm=3\)则答案为\(6\)，若\(cm=4\)则无解

import java.util.*;
public class hl666 {
    public static void main(String args[]) {
        Scanner In=new Scanner(System.in);
        for (int t=In.nextInt();t>0;--t) {
            int x=In.nextInt();
            int[] c=new int[10];
            ++c[x%10]; ++c[x/10%10]; ++c[x/100%10]; ++c[x/1000];
            int cur=0;
            for (int i=0;i<10;++i) cur=Math.max(cur,c[i]);
            if (cur==4) {
                System.out.println("-1");
            } else if (cur==3) {
                System.out.println("6");
            } else {
                System.out.println("4");
            }
        }
    }
}

B. Points on Plane

SB题，画个图看下就发现答案一定是一层层间隔着取

然后稍微找下规律就会发现当答案为\(k\)时最多可以涵盖\((k+1)^2\)个点，因此直接开个根号就行了

import java.util.*;
public class hl666 {
    public static void main(String args[]) {
        Scanner In=new Scanner(System.in);
        for (int t=In.nextInt();t>0;--t) {
            long n=In.nextLong();
            long x=(long)Math.sqrt(n);
            if (x*x<n) ++x;
            System.out.println(x-1);
        }
    }
}

C. Sum on Subarrays

构造趣题，这题刚好在周四那场耻辱之战之前写的，然后就在吹嘘那构造题精通，结果后面原形毕露了捏

不过这题本身还是很trivial的，考虑先连着填充\(t\)个\(1\)，然后剩下的位置都填\(-1000\)，此时区间和为正数的区间个数显然就是\(\frac{t(t+1)}{2}\)

找出最大的且满足\(\frac{t(t+1)}{2}\le k\)的\(t\)，然后考虑剩下的部分怎么处理，一个很naive的想法就是在后面继续找，然后如果不行有剩下的就在中间继续找

但这样一看就不是很优美而且有些情况根本构造不出来的说，我们考虑对原来的构造方法稍作修改

我们把前面\(t\)个位置中的某个位置改成\(1000\)，然后把后面那一段\(-1000\)开头的那个改成\(-500\)，因此此时的序列形如

\[1,1,\cdots,1000,1,1,\cdots,1,-500,-1000,-1000,\cdots \]

我们发现设\(1000\)的下标为\(r\)，则此时多出的和为正数的区间个数恰好为\(r\)

而当\(t\)加一时\(\frac{t(t+1)}{2}\)的值恰好增加\(t+1\)，而\(t\)本身可以额外加上\(t\)的贡献，因此一定可以涵盖所有情况

这样就很优美了的说

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=35;
int t,n,k,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&k),i=1;i*(i+1)/2<=k;++i);
		for (--i,j=1;j<=i;++j) a[j]=1; a[k-i*(i+1)/2]=1000;
		for (a[i+1]=-500,j=i+2;j<=n;++j) a[j]=-1000;
		for (j=1;j<=n;++j) printf("%d%c",a[j]," \n"[j==n]);
	}
	return 0;
}

D. Binary String Sorting

这种题目刚开始都没什么好想的，上来就是一个DP，后面发现好像是个丁真结论题，不过无伤大雅

01串构成的LIS显然就是一段0再加上一段1，然后很经典的可以设计状态\(f_{i,p=0/1,q=0/1}\)表示以\(i\)结尾，结尾的两个字符为\(p,q\)且前\(i\)个字符构成的01串为LIS的最小代价

转移的话都很trivial，不过从\(p=1,q=1\)的状态接上一个\(0\)的情况就一定是删去\(0\)，因为否则我们一定要用至少两次的交换操作，这显然不是最优的

代码非常的好写

#include<cstdio>
#include<iostream>
#include<cstring>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=300005,S=1e12,INF=1e18;
int t,n,f[N][2][2],tmp; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,p,q; for (scanf("%s",s+1),n=strlen(s+1),i=0;i<=n;++i)
		for (p=0;p<2;++p) for (q=0;q<2;++q) f[i][p][q]=INF;
		for (f[0][0][0]=0,i=0;i<n;++i) for (p=0;p<2;++p) for (q=0;q<2;++q)
		if (p<=q&&(tmp=f[i][p][q])!=INF)
		{
			f[i+1][p][q]=min(f[i+1][p][q],tmp+S+1);
			if (s[i+1]=='0')
			{
				if (p==0&&q==0) f[i+1][0][0]=min(f[i+1][0][0],tmp);
				if (p==0&&q==1) f[i+1][0][1]=min(f[i+1][0][1],tmp+S);
			} else f[i+1][q][1]=min(f[i+1][q][1],tmp);
		}
		int ans=INF; for (p=0;p<2;++p) for (q=0;q<2;++q)
		ans=min(ans,f[n][p][q]); printf("%lld\n",ans);
	}
	return 0;
}

后面一想发现由于这两个贡献都是\(10^{12}\)加上一个极小数的情形，因此只要在最小化总操作次数的情况下尽量多的用交换操作即可

可以直接枚举LIS中0/1的分界点，然后预处理下前缀后缀的贡献即可，代码就没写了，也是很好写的

E. Two Tanks

妙题，被思博题薄纱了，考虑到了根据总水量来一起考虑但没观察到关键性质（话说但凡认真看看样例输出可能都找到性质了）

下面讲的主要学习自知乎dalao的博客，里面有些图片看着可以帮助理解

首先考虑枚举总水量\(s\)，设此时第一个桶初始时可取值区间\([L,R]\)，观察或者转化题意后可以证明对应的答案一定是如下形式：

\[l,l,\cdots,l,l+1,l+2,\cdots,r-1,r,r,\cdots r \]

这里证明过程就看上面的链接吧，这里不再赘述，只能说是巧妙

然后现在问题就是怎么找出分界点\(l,r\)的值了，一种trivial的想法就是二分，不过这样复杂度会有点卡

更巧妙的方法是直接从临界的情况，第一个桶剩\(L/R\)时倒推出原来的取值点，只能说是被brainf**k了

总复杂度\(O(n\times (a+b))\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int n,a,b,v[10005],ans[N][N],sum;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d%d",&n,&a,&b),i=1;i<=n;++i)
	scanf("%d",&v[i]),sum+=v[i]; for (i=0;i<=a+b;++i)
	{
		int L=max(0,i-b),R=min(a,i),l=L,r=R;
		auto fix=[&](CI x)
		{
			if (x<L) return L; if (x>R) return R; return x;
		};
		for (j=n;j;--j) l=max(l+v[j],L),r=min(r+v[j],R);
		int ansl=l,ansr=r; for (j=1;j<=n;++j)
		ansl=fix(ansl-v[j]),ansr=fix(ansr-v[j]);
		for (j=L;j<=R;++j) if (j<l) ans[j][i-j]=ansl;
		else if (j>r) ans[j][i-j]=ansr; else ans[j][i-j]=j-sum;
	}
	for (i=0;i<=a;++i) for (j=0;j<=b;++j) printf("%d%c",ans[i][j]," \n"[j==b]);
	return 0;
}

F. Traveling in Berland

思博题，刚开始rush了个找性质的做法然后挂了，后面想了半天发现是没特判所有的\(b_i\)都为\(2\)的情况，白白想了好久苦路西

首先注意到\(b_i\)的取值只有\(\{1,2\}\)，而且我们最后加的油的总量一定是\(\sum_{i=1}^n a_i\)

因此我们转化下题意，令\(sum=2\times \sum_{i=1}^n a_i\)，即假设刚开始加的全是单价为\(2\)的油，然后考虑最大化加单价为\(1\)的油的数量

基于一个贪心的想法我们很容易想到，对于每个\(b_i=1\)的点，除非它最后能一步走到终点（这种情况后面单独讨论），否则我们一定在此时把油箱加满

而对于\(b_i=2\)的点，显然只要保证此时油量能让其走到下一条边即可

因此基于这个思路，我们发现我们可以找出所有\(b_i=1\)的点\(i\)前面的那个\(b_j=1\)的点\(j\)，设它们的距离为\(d\)，则在点\(i\)处一般情况下要加的油量就是\(\min(d,k)\)

我们预处理出每个\(b_i=1\)的点的预期减去的值，显然大部分情况下它们的贡献都是不变的，因此把和记为\(ret\)

然后考虑起点\(st\)的不同带来的细微影响，稍加讨论发现：

对于\(st\)之前的最近的\(b_{pre}=1\)的点\(pre\)，要特别考虑\(pre\)的贡献，因为不能粗暴地加满了，如果可以直接到终点就把油加到刚刚好即可
对于\(st\)之后的最近的\(b_{nxt}=1\)的点\(nxt\)，要考虑\(st\)到\(nxt\)的贡献要在原来的基础上略作修改，而且还要分\(b_{st}\)的取值的不同有所调整，这个画图手玩一下就很好理解

然后这题就做完了，如果预处理每个点的\(pre\)和\(nxt\)复杂度就是\(O(n)\)的，不过前面写的时候脑子有点问题写了个二分，反正不影响的说

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,k,a[N],b[N],pos1[N],cnt; long long pfx[N],pre[N],sum,ret;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),sum=ret=cnt=0,i=1;i<=n;++i)
		scanf("%d",&a[i]),pfx[i]=pfx[i-1]+a[i],sum+=2LL*a[i];
		for (i=1;i<=n;++i) if (scanf("%d",&b[i]),b[i]==1) pos1[++cnt]=i;
		if (!cnt)
		{
			for (i=1;i<=n;++i) printf("%lld%c",sum," \n"[i==n]); continue;
		}
		auto find_pre=[&](CI x)
		{
			return pos1[lower_bound(pos1+1,pos1+cnt+1,x)-pos1-1];
		};
		auto find_nxt=[&](CI x)
		{
			return pos1[lower_bound(pos1+1,pos1+cnt+1,x)-pos1];
		};
		auto dist=[&](CI x,CI y)
		{
			if (x<y) return pfx[y-1]-pfx[x-1]; return pfx[n]-pfx[x-1]+pfx[y-1];
		};
		for (pos1[0]=pos1[cnt],pos1[cnt+1]=pos1[1],i=1;i<=n;++i)
		if (b[i]==1) ret+=min(pre[i]=dist(find_pre(i),i),1LL*k);
		for (i=1;i<=n;++i)
		{
			long long cur=sum-ret+max(0LL,k-dist(find_pre(i),i));
			if (b[i]==1) cur-=max(0LL,k-pre[i]); else cur-=max(0LL,k-pre[find_nxt(i)]);
			printf("%lld%c",cur," \n"[i==n]);
		}
	}
	return 0;
}