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;
}
Postscript
G题就那么几个人过一看就不可做，弃了弃了
标签：Educational,Rated,const,int,Codeforces,CODE,include,RI,define From： https://www.cnblogs.com/cjjsb/p/17364238.html