Lvat_s Blog

毛爷爷已经发过了:链接

我来写一些考试时的感受吧

开考后6min:

T1什么鬼？但是好像不难……

T2什么鬼？答案可以有误差？

T3什么鬼？我只会暴力

开考后10min:

T1没思路啊……弃疗比赛算了

开考后1hr46min:

啊！UOJ比赛不是CF，只要看了题目都计入排行榜！赶快写题不然Rating要掉了！

开考后2hr17min:

哎……T1为啥不是每次向右向下走一格呢？啊！原来走中间时间最短的越长越好而不是直接在当前走！

开考后2hr37min:

提交T1,赶快写T2暴力吧

开考后2hr52min:

T2暴力写完了赶快写T3暴力

开考后3hr3min:

啊！T3暴力刚写完！弃疗算了

最终得分100+50+0

-------------------------

以下为部分题解

A.短路

考虑每个环要么走一格要么走完全部，否则将多余的一步用于时间更少的环显然更优

略微推一下式子就发现可以线性扫描一遍解决

时间复杂度$O(n)$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;
const long long INF=99999999999999999ll;

int n;
long long a[N],ans,last,sho,lw;

int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<=n;i++)scanf("%lld",&a[i]);
last=4ll*a[n];
ans=(n*4ll+1)*a[n];
sho=a[n];lw=n;
for(int i=n-1;i>=0;i--){
	if(a[i]<sho){sho=a[i];lw=i;}
	last+=(sho+a[i])*2ll;
	ans=min(ans,last+i*4ll*a[i]-3*a[i]);
	//printf("Aw:%lld %lld\n",ans,last+i*4ll*a[i]-3*a[i]);
}
printf("%lld\n",ans);
return 0;
}

B.天路

订正时发现题目看错了……是与答案相差$5\%$而不是5！

那么每次乘一下1.05就不会出问题了……然后随便把小于枚举值的ans更新一下即可

复杂度我也不太会分析你萌看毛爷爷的解释吧

那个分治现在还不太会……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=100005,INF=1000005;

int n,a[N],ans[N],mx[N],mn[N],f1,f2,l1,l2;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline int Calc(int x){
mx[f1=l1=1]=1;
mn[f2=l2=1]=1;
int pos=1;
for(register int i=2;i<=n;i++){
	while(f1<=l1 && a[mx[l1]]<a[i])l1--;
	while(f2<=l2 && a[mn[l2]]>a[i])l2--;
	mx[++l1]=i;mn[++l2]=i;
	while(a[mx[f1]]-a[mn[f2]]>x){
		pos++;
		while(f1<=l1 && mx[f1]<pos)f1++;
		while(f2<=l2 && mn[f2]<pos)f2++;
	}
	ans[i-pos+1]=min(ans[i-pos+1],a[mx[f1]]-a[mn[f2]]);
}
}

inline void Solve(){
for(register int i=0;i<=INF*2;i=(int)(i*1.05)+1)Calc(int(i*1.05));
for(register int i=n-1;i>=2;i--)ans[i]=min(ans[i],ans[i+1]);
for(register int i=2;i<=n;i++)printf("%d\n",ans[i]);
}

int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]),ans[i]=1e9;
if(n<=1000){
	for(register int i=1;i<=n;i++){
		int mx=a[i],mn=a[i];
		for(register int j=i+1;j<=n;j++){
			mx=max(mx,a[j]);mn=min(mn,a[j]);
			ans[j-i+1]=min(ans[j-i+1],mx-mn);
		}
	}
	for(register int i=2;i<=n;i++)printf("%d\n",ans[i]);
}
else Solve();
return 0;
}