首页 > 代码库 > CH Round #59 - OrzCC杯NOIP模拟赛day1
CH Round #59 - OrzCC杯NOIP模拟赛day1
第一题:队爷的新书
题意简述:给定n个闭区间,求出一个数p使它与包含它的区间数的积最大,输出这个积。
分析:使用一个差分数组g,每个区间[l,r],l位置加1,r+1的位置减1,从前往后统计,得到对于每个p包含它的区间个数,相乘看是否最大。由于数据较大,需要离散化。
program book;var a,f,g:array[0..200001]of qword; l,r:array[0..100001]of longint; n,i,m:longint; sum,ans:qword;procedure qsort(l,h:longint);var i,j,t:longint; m:qword;begin i:=l; j:=h; m:=a[(i+j) div 2]; repeatwhile a[i]<m do inc(i);while m<a[j] do dec(j);if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t;inc(i); dec(j); end; until i>j; if i<h then qsort(i,h); if j>l then qsort(l,j); end;function make(x:longint):longint;var l,r,mid,ans:longint;begin l:=1;r:=m; while l<=r do begin mid:=(l+r) div 2; if f[mid]<=x then begin ans:=mid; l:=mid+1; end else begin r:=mid-1; end; end; exit(ans);end;procedure fry;var i:longint;begin qsort(1,2*n); a[0]:=-1; for i:=1 to 2*n do if a[i]<>a[i-1] then begin inc(m); f[m]:=a[i]; end; for i:=1 to n do begin l[i]:=make(l[i]); r[i]:=make(r[i]); end;end;begin assign(input,‘book.in‘);reset(input);assign(output,‘book.out‘);rewrite(output); readln(n); m:=0; for i:=1 to n do begin readln(l[i],r[i]); a[i*2-1]:=l[i]; a[i*2]:=r[i]; end; fry; for i:=1 to n do begin inc(g[l[i]]); dec(g[r[i]+1]); end; for i:=1 to m do begin inc(sum,g[i]); if sum*f[i]>ans then ans:=sum*f[i]; end; writeln(ans); close(input); close(output);end.
第三题:队爷的讲学计划
题意简述:一个有向图中,队爷从1点出发在图上行走,每条边都要一个花费,如果他走到某个点i,则该店对应强连通分量中的边权全部变为1,前往经过这些边只要花费1的代价且只需要交1次钱(由于你第一次到达i的时候交了钱,所依回到i的那个边不需要交钱),求队爷能走过的最多的点数,和在满足点数最多情况下最少花费。
分析:由于要求经过的点最多,显然对于每个强连通分量,队爷肯定要前往其包含的所有点,这样显然最优。
所以我们将每个强连通分量各自缩为一个点,这个点对应的点数(题目中的城市数)为分量包含的总点数,由于每条路只交一次钱,故代价为点数-1。
这样我们得到一个DAG,在图上跑SPFA求出最长路并同时求出对应最小花费即可。
另外看清题目没有要求终点,则终点可以是每个点。
CH Round #59 - OrzCC杯NOIP模拟赛day1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。