Atcoder abc263

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
E(概率论),Ex(计算几何,二分)

https://atcoder.jp/contests/abc263/tasks

E - Sugoroku 3

n个格子,初始在1

1到n-1上面都有个骰子, 上面 [0..Ai] 等概率

在到N之前 每次移动 扔出的步数

求期望扔的次数

答案mod 998244353

范围

n 2e5

ai n-i 也就是不会超过n

2s

1024mb

我的思路

记 f(i) = 首次到i的期望次数

i -> j 的期望步数 = 1/(ai+1) + 2/(ai+1)^2 + 3/(ai+1)^3…

s = sum t/(ai+1)^t, t=1…

s/x = sum t/(x)^{t+1}, t=1…

s/x = -(sum 1/(x)^t)’, t=1…

s/x = -((1/x) 1/(1-1/x))’

s/x = -(1/(x-1))’

s/x = 1/(x-1)^2

s = x/(x-1)^2

s = x/(x-1)^2

s = (ai+1)/ai^2

f(i) = sum(f[j=0….i-1]+s[j], 若 j 能到i)

注意到 f[j]+s[j] 的贡献值与i无关, 只有是否贡献有关, 而是否贡献 还是连续的一段

所以用遍历记录贡献和 和失效处来算?

然而并不对, 样例都过不了

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

mint ans[200010];
mint rm[200010];

int main(){
  int n = read();
  mint c=0;
  rep(i,0,n-1){
    int ai=read();
    ans[i] = c;
    c-=rm[i];
    mint s = ans[i] + mint(ai+1)/(mint(ai)*ai);
    rm[i+ai] += s;
    c+=s;
  }
  printf("%d\n",c.val());
  return 0;
}

题解

dp[i] = i到n的期望步数

dp[i] = (sum dp[i…i+a[i]])/(a[i]+1) + 1

dp[i](1-1/(a[i]+1)) = (sum dp[i+1...i+a[i]])/(a[i]+1) + 1

dp[i] = ((sum dp[i+1...i+a[i]]) + a[i]+1)/a[i]

代码

https://atcoder.jp/contests/abc263/submissions/35594337

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=(int)n-1;i-->a;)
int read(){int r;scanf("%d",&r);return r;}

mint ans[200010];
mint suf[200010];
int a[200010];

int main(){
  int n = read();
  rep(i,0,n) a[i]=read();
  per(i,0,n){
    ans[i] = (suf[i+1]-suf[i+a[i]+1]+a[i]+1)/a[i];
    suf[i] = suf[i+1]+ans[i];
  }
  printf("%d\n",ans[0].val());
  return 0;
}

Ex - Intersection 2

2维平面, n条线, ai x + bi y + ci = 0, 保证两两不平行

考虑重复的交点,那么两两有交点

输出 到原点 第K近的交点的距离

范围

n 5e4

ai,bi,ci, [-1000,1000]

7s

1024mb

我的思路

先考虑交点计算

1
2
3
4
ai bi    -ci
aj bj * =-cj
      x
      y
1
2
x = (ai bi)^-1 * -ci
y   (aj bj)      -cj
1
2
x = -(bicj-bjci)/(biaj-bjai)
y = -(aicj-ajci)/(aibj-ajbi)

$dis = \frac{\sqrt{(b_ic_j-b_jc_i)^2+(a_ic_j-a_jc_i)^2}}{|b_ia_j-b_ja_i|}$

感觉i和j混在一起的并没法拆开

题解

二分 半径r,每次考虑有多少个交点 在半径r中

!!! 找 每条线 和 圆r的交线段

然后问题变成, 有很多端点在r上的线段,求交点个数

就没了, 似乎没啥精度需要注意? 只有除零需要注意

代码

https://atcoder.jp/contests/abc263/submissions/35595508

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
vector<tuple<int,int,int> > abc;
const double PI=acos(-1);

double xy2theta(double x,double y){ // (x,y) -> theta
  if(x>=0 && y>=0) return atan(y/x);
  if(x<0 && y>=0) return PI/2+atan(-x/y);
  if(x<0 && y<0) return PI+atan(y/x);
  return 3*PI/2+atan(-x/y);
}

pair<double,double> solve(double A,double B,double C){ // Ax^2+Bx+C=0
  return {(-B+sqrt(abs(B*B-4*A*C)))/(2*A),(-B-sqrt(abs(B*B-4*A*C)))/(2*A)};
}

ll cross(const vector<pair<int,int>>&ij){ // 线段相交数
  vector<int>fen(ij.size()*2);//fenwick
  auto query=[&](int x){
    int r=0;
    for(int i=x+1;i;i-=(i&-i)) r+=fen[i-1];
    return r;
  };
  auto add=[&](int x){
    for(int i=x+1;i<=(int)fen.size();i+=(i&-i)) fen[i-1]++;
  };

  ll r=0;
  for(auto [i,j]:ij){
    r+=query(j-1)-query(i); // pi < i < pj < j, 查询 [i+1,j-1]
    add(j);
  }
  return r;
}

int f(double radius){
  vector<pair<double,double>> lr;
  for(auto [a,b,c]:abc)if(abs(c)/sqrt(a*a+b*b) < radius){
    double x0,y0,x1,y1;
    if(a != 0){
      tie(y0,y1) = solve(a*a+b*b,2*b*c,c*c-a*a*radius*radius);
      x0 = -(b*y0+c)/a;
      x1 = -(b*y1+c)/a;
    }else{
      tie(x0,x1) = solve(a*a+b*b,2*a*c,c*c-b*b*radius*radius);
      y0 = -(a*x0+c)/b;
      y1 = -(a*x1+c)/b;
    }
    auto l = xy2theta(x0,y0);
    auto r = xy2theta(x1,y1);
    if(l>r)swap(l,r);
    lr.push_back({l,r});
  }
  vector<double> p;
  for(auto[l,r]:lr){
    p.push_back(l);
    p.push_back(r);
  }
  sort(begin(p),end(p));
  vector<pair<int,int> >ij;
  for(auto [l,r]:lr)ij.push_back({
      lower_bound(begin(p),end(p),l)-begin(p),
      lower_bound(begin(p),end(p),r)-begin(p)
  });
  sort(begin(ij),end(ij));
  return cross(ij);
}

int main(){
  int n = read();
  int k = read();
  rep(i,0,n)abc.push_back({read(),read(),read()});

  double l = 0;
  double r = 4e6;
  while(r-l>1e-6){
    double mid=(l+r)/2;
    (f(mid)<k?l:r)=mid;
  }
  printf("%.15lf\n",l);
  return 0;
}

总结

E

当时现场13min 过了4题,然后这个题卡了一直出不了, 我概率论菜啊

不懂啊,正着的时候, 期望转移步数为啥是不对的?

概率论完全不会, 卡蓝题, 后面F,G两个黄题倒是会做

Ex

我有想过二分, 但这样和圆切成线段 考虑! 完全没想到, 虽然以前做过本来就在圆上的线段,去考虑交的题

参考

官方题解