10
17
2016
1

UOJ Easy Round #7 题解

毛爷爷已经发过了:链接

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

开考后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;
}
Category: 比赛 | Tags: OI uoj | Read Count: 909
AP SSC fa 1 Question 说:
Sep 09, 2022 09:10:54 PM

Formative Assessment means not only an examination, it includes various aspects such as Examination in completed lessons, Reflections, Project work done on the allotted topic and Self also Prepared notes etc. AP SSC fa 1 Question Paper Candidates of Telugu Medium, English Medium & Urdu Medium of the AP State can download the AP 10th Class FA 4 Model Paper 2023 Pdf with answers for the regular exams conducted by the Directorate of Government Examinations, Andhra Pradesh.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com