CF
最后20min过了两题代码量超小的题。。。
B. Fakes and Shidget
由题意，我们要求的是，在每一对 $(a,b),(c,d)$ 选择一个，求 $\max{\frac{\sum_{i=1}^n b_i}{\sum_{i=1}^na_i}}$。
直接01分数规划即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| const int N=2e5+5;
int n,a[N],b[N],c[N],d[N];
int main()
{
read(n);
fo(i,1,n)
read(a[i],b[i],c[i],d[i]);
db l=0,r=1e9,mid;
fo(i,1,100)
{
mid=(l+r)/2.;
db ans=0;
fo(i,1,n)
ans+=max(b[i]-a[i]*mid,d[i]-c[i]*mid);
if(ans>=0) l=mid;
else r=mid;
}
printf("%.10lf",mid);
return 0;
}
|
C. Cyclically Shifted Maze
meaningiess直接把这题秒了。。
D. Two Pirates - 2
清醒的人一定先拿走最大的那个。然后就不知道怎么做了。
可以发现，排好序后，选到某一堆的概率与其本身无关，因此可以使用DP。
设 $f_{n,i}$ 表示 $n$ 堆的时候，从小到大排名第 $i$ 被选到的概率。
分两种情况讨论即可。时间复杂度 $O(n^2)$。
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
| const int N=5005;
int n;
int a[N];
db f[N][N];
int main()
{
read(n);
fo(i,1,n) read(a[i]);
sort(a+1,a+n+1);
fo(i,1,n)
{
int opt=(n-i+1)&1;
if(opt)
{
fo(j,1,i)
f[i][j]=f[i-1][j];
f[i][i]=1;
}
else
{
fo(j,1,i)
f[i][j]=(f[i-1][j-1]*(j-1)+f[i-1][j]*(i-j))/i;
}
}
db sum=0,ans=0;
fo(i,1,n) sum+=a[i];
fo(i,1,n) ans+=f[n][i]*a[i];
printf("%.12lf %.12lf\n",ans,sum-ans);
return 0;
}
|
E. Powerless Mage
F. Exactly One Point
假设我们从后往前选择点。
若选择了点 $i$，则该点必须覆盖至少一条线段。设 $mx_i$ 表示所有 $l\le i$ 的线段的 $r$ 的最大值；$mn_i$ 表示所有 $l\geq i$ 的线段的 $r$ 的最小值。那么后面点的合法范围是 $[mx_i+1,mn_{i+1}]$。那么在里面随便选一个就可以了。
时间复杂度 $O(n\log n)$。
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
| const int N=1e6+5;
const int inf=1e9;
int mi[N],mx[N],l[N],r[N],n,is[N];
int fa[N];
int main()
{
read(n);
int m=n*4;
fo(i,0,m) mi[i]=inf;
fo(i,1,n)
{
read(l[i],r[i]);
l[i]++; r[i]++;
is[l[i]]++; is[r[i]+1]--;
mx[l[i]]=max(mx[l[i]],r[i]);
mi[l[i]]=min(mi[l[i]],r[i]);
}
fo(i,1,m) mx[i]=max(mx[i],mx[i-1]),is[i]+=is[i-1];
fd(i,m-1,1) mi[i]=min(mi[i],mi[i+1]);
VI ans;
set<int> s;
s.insert(m);
fd(i,m-1,1)
if(mx[i]+1<=mi[i+1])
{
auto it=s.upper_bound(mx[i]);
if(it!=s.end()&&(*it)<=mi[i+1])
fa[i]=*it,s.insert(i);
}
if(s.size()<=1) return puts("-1")&0;
if(*s.begin()>mi[1]) return puts("-1")&0;
int u=*s.begin();
for(;u;u=fa[u]) if(is[u]) ans.pb(u);
printf("%d\n",ans.size());
for(int x:ans) printf("%d ",x-1);
return 0;
}
|
G. Lexicographically Minimal Subsequence
贪心一个一个往后看是否能选。
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
| const int N=1e6+5;
int n,k;
char s[N];
int now[26];
vector<int> vec[26];
int main()
{
scanf("%s\n%d",s+1,&k);
n=strlen(s+1);
fo(i,1,n) vec[s[i]-'a'].pb(i);
fo(i,1,k)
{
int pos;
fo(j,0,25)
if(now[j]<vec[j].size())
{
if(n-vec[j][now[j]]>=k-i)
{
putchar(j+'a');
pos=vec[j][now[j]];
break;
}
}
fo(j,0,25)
for(;now[j]<vec[j].size()&&vec[j][now[j]]<=pos;now[j]++);
}
return 0;
}
|
H. Video Reviews - 2
考虑最后一个人 $a_n$，如果 $a_n<m$，那么一定不选。转换为 $(n-1,m-1)$ 的子问题。
如果 $a_n\geq m$，且 $n=m$，则这个一定会被选；如果 $n>m$，则这个可能被选，但实际上选前面的一定不会更差，因此这个一定不会选。
那么就可以直接从 $a_n$ 开始倒退至 $a_1$ 即可。
由于 $z_j$ 有逆元，同一段内可以由 $a_{i+1}$ 直接推出 $a_i$，不同段的边界处需要预处理顺推一遍进行计算。
时间复杂度 $O(n)$，空间复杂度 $O(m)$。
J. Lost Island
第三次见到这种题了。
我们记一个颜色的状态为 $(a_i,b_i)$。设某个人的颜色为 $i$。
若 $a_i=b_i>0$，则这人看到外面只有 $b_{i}-1$ 个，不合理。因此这个知道自己就是 $i$，将在第 $1$ 天自杀。
若 $a_i=b_i+1$，则这人假设自己不是 $i$，那么外面这些颜色 $i$ 的人看到的状态应为 $(a_i-1,b_i)$，将在第 $1$ 天自杀，但他们并没有，于是这人在第 $2$ 天知道自己是颜色 $i$。
以此类推，在 $x+1$ 天，某人假设自己不是 $i$，那么外面的人将在第 $x$ 天自杀，但是并没有，于是这人在 $x+1$ 这天自杀。
因此，对于 $b_i>0$，颜色为 $i$ 的人将在 $a_i-b_i+1$ 天自杀。
- 若不存在 $b_i=0$，则 $a_i-b_i+1$ 最大的那些人将在次大的 $a_j-b_j+1$ 之后一天自杀，因为其他人都死光了。
- 若只存在一个 $b_i=0$，则 $i$ 颜色的人在 $a_i-b_i+1$ 最大的下一天自杀。
- 若存在两个或以上 $b_i=0$，则所有 $b_i=0$ 的人将活下来。
时间复杂度 $O(n)$。
K. Bloodseeker
首先我们把这些怪分为两类：$h_i\geq t_i$ 和 $h_i<t_i$。
第一类是可以帮助我们回血的，第二类是要我们掉血的。
显然可以在恰当时间去打第一类从而充分运用其回血，一共能回 $\sum h_i-t_i$ 滴血。
对于第二类，假设有两个怪 $(h_i,t_i),(h_j,t_j)$，当且有 $k$ 滴血量。
先打 $i$ 需要满足： $m+h_i-t_i\geq t_j$。
先打 $j$ 需要满足：$m+h_j-t_j\geq t_i$。
其他不等式一样。因此我们直接按照 $h$ 从打到小依次消掉即可。
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
| struct node{ll x,y;};
inline int solve()
{
ll n,m,x,y;
ll now=0;
read(n,m);
vector<node> a;
fo(i,1,n)
{
read(x,y);
y=min(y,m);
if(x<=y) now+=y-x;
else a.pb({y,x-y});
}
now+=m;
sort(all(a),[&](auto x,auto y){return x.x>y.x;});
for(auto [x,y]:a)
{
if(x+y>now) return puts("NO")&0;
else now-=y;
}
puts("YES");
return 0;
}
int main()
{
CASET solve();
return 0;
}
|
L. Not the Longest Increasing Subsequence
值域也为 $k$，那么直接DP一下就好了。输出方案可以倒着推一遍。
M. Binary Search Tree
树形DP一波即可。opentrains卡我常数，使用 $O(n)$ 的方法才过了。