零岛

回朕车以复路兮,及行迷之未远

2020 ICPC 上海赛区题解

按过题人数由多到少补题

D. Walker

题意

一段区间$[0,n]$,两个人一个从$p_1$出发以$v_1$的速度行走,另一个从$p_2$出发以$v_2$的速度行走,求两个人一起覆盖这段区间的最短时间。

思路

分4种情况

  1. 其中一个人走完全程
  2. 两个人对着走
  3. 两个人先向中间走,再折返
  4. 先向两边走再到中间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
const double eps=1e-7;
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--)
{
double n,p1,v1,p2,v2;
cin>>n>>p1>>v1>>p2>>v2;
if(p1>p2)
{
swap(p1,p2);
swap(v1,v2);
}
double l=0,r=min({(n+min(n-p1,p1))/v1,(n+min(n-p2,p2))/v2,max((n-p1)/v1,p2/v2)});//1走完全程,2走完全程,对穿
double ans=r;
while(r-l>eps)
{
double mid=(l+r)/2;
auto f=[](double p,double v,double t){
double d=v*t;//p点出发,t时间行走距离
if(d<p)//并不能走完
return (double)0;
return max(max(p,d-2*p+p),p+(d-p)/2);//先向两侧走,先向中间走最大覆盖区间
};
double s1=f(p1,v1,mid)+f(n-p2,v2,mid);
double s2=f(n-p1,v1,mid)+f(p2,v2,mid);
if(s1>=n||s2>=n)
ans=min(ans,mid),r=mid;
else
l=mid;
}
cout<<setiosflags(ios::fixed)<<setprecision(9)<<ans<<endl;
}
return 0;
}

M.Sky Garden

很久没打了,明显手生,AB一共WA了四发,CD切的很快,E毫无思路。

接下来一是应该复习算法并且能裸写,减少对模板的依赖;二是加强对div1C左右难度题目的训练。

阅读全文 »

文法:$G=(V,T,G,S)$,非终结符号$V$,终结符号$T$,产生式集$G$,开始符号集$S$.

句型:由文法开始符号可以经过若干步推导得到的文法符号串$\alpha$。
$$
\forall \alpha \in (V \cup T)^* \and S \xrightarrow{*} \alpha
$$
句子:由文法开始符号可以经过若干步推导得到的终结符号串$\omega$。

句型和句子区别:句子不含语法变量,句型可能含有语法变量。

语言:句子的集合。

BNF范式:一种书写产生式的格式。

阅读全文 »

先把AC的代码放上来吧,题解慢慢补。
很期待人退出第二季呢

赛后总结

赛中一人写了4题,有很大水分。
F作为签到题也是一个结论,虽然并没有猜出来但是也水过了。
J题是伽马函数,(虽然看着像二项式展开),计算了前几项OEIS也水过了,估计现场赛会推给队友吧。
I题是HDOJ3551一般图最大匹配的简化版?我用最大流水过了,出题人说最大流做法是错误的。
H是拉格朗日插值?我用费用流+map水过了……

阅读全文 »
0%