• 欢迎光临~

2022牛客多校(一)

开发技术 开发技术 2022-07-20 次浏览

A

线段覆盖,求未覆盖长度

左端点排序,然后扫一遍

2022牛客多校(一)2022牛客多校(一)
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define endl  "n"
 5 #define mp    make_pair
 6 #define pb    push_back
 7 #define st    first
 8 #define nd    second
 9 #define pii   pair<int, int>
10 
11 #define sz(x) (int((x).size())
12 #define rep(i, s, t) for (int i = (int)(s); i <= (int)(t); ++ i)
13 #define inc(i, s, t) for (int i = (int)(s); i <  (int)(t); ++ i)
14 
15 typedef long long ll;
16 typedef long double ld;
17 typedef unsigned long long ull;
18 
19 #ifdef LOCAL
20 ostream &operator<<(ostream &out, string str) {
21     for (char c : str)
22         out << c;
23     return out;
24 }
25 template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
26 template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) {
27     auto &[a, b, c] = p;
28     return out << "(" << a << ", " << b << ", " << c << ")";
29 }
30 template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
31     out << '{';
32     for (auto it = a.begin(); it != a.end(); it = next(it))
33         out << (it != a.begin() ? ", " : "") << *it;
34     return out << '}';
35 }
36 void dump() { cerr << "n"; }
37 template <class T, class... Ts> void dump(T a, Ts... x) {
38     cerr << a << ", ";
39     dump(x...);
40 }
41 #define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
42 #else
43 #define debug(...) ;
44 #endif
45 
46 const int N = 2e5 + 10;
47 #define int long long
48 struct Node {
49     int x, r;
50     bool operator < (const Node& rhs) const {
51         if (x == rhs.x) return x + r < rhs.x + rhs.r;
52         return x < rhs.x;
53     }
54 } a[N];
55 
56 int32_t main() {
57     int n; cin >> n;
58     rep(i, 1, n) cin >> a[i].x >> a[i].r;
59     sort(a + 1, a + n + 1);
60     ll ans = 0, id = 1;
61     rep(i, 2, n) {
62         debug(id);
63         debug(a[id].x, a[id].r);
64         if (a[id].x + a[id].r >= a[i].x - a[i].r) {
65             if (a[i].x + a[i].r > a[id].x + a[id].r)
66                 id = i;
67         } else {
68             ans += a[i].x - a[i].r - (a[id].x + a[id].r);
69             id = i;
70         }
71     }
72     cout << ans << endl;
73 }
View Code

 

D

结论题,考虑如何能得到最大圆弧

那么发现当旋转的线段所在的直线过圆心时,圆弧上的曲率最大

相同长度上的圆弧,曲率越大,圆弧越长

所以直接算出直线过原点的情况即可

2022牛客多校(一)2022牛客多校(一)
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 double r;
 4 double x,y,d;
 5 int main(){
 6     int T;scanf("%d",&T);
 7     while(T--){
 8         cin>>r>>x>>y>>d;
 9         double D=sqrt(x*x+y*y);
10         double a=asin((d+D)/r),b=asin((d-D)/r);
11         printf("%.12lfn",a*r+b*r);
12     }    
13     return 0;
14 }
View Code

 

G

签到题

题意就是给一堆区间把所有相交的区间合并,

找出合并后,所有区间后的空隙

2022牛客多校(一)2022牛客多校(一)
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define LOCAL
 4  
 5 #define endl  "n"
 6 #define mp    make_pair
 7 #define pb    push_back
 8 #define st    first
 9 #define nd    second
10 #define pii   pair<int, int>
11  
12 #define sz(x) (int((x).size())
13 #define rep(i, s, t) for (int i = int(s); i <= int(t); ++ i)
14 #define inc(i, s, t) for (int i = int(s); i <  int(t); ++ i)
15  
16 typedef long long ll;
17 typedef long double ld;
18 typedef unsigned long long ull;
19  
20 #ifdef LOCAL
21 ostream &operator<<(ostream &out, string str) {
22    for (char c : str)
23       out << c;
24    return out;
25 }
26 template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
27 template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) {
28    auto &[a, b, c] = p;
29    return out << "(" << a << ", " << b << ", " << c << ")";
30 }
31 template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
32    out << '{';
33    for (auto it = a.begin(); it != a.end(); it = next(it))
34       out << (it != a.begin() ? ", " : "") << *it;
35    return out << '}';
36 }
37 void dump() { cerr << "n"; }
38 template <class T, class... Ts> void dump(T a, Ts... x) {
39    cerr << a << ", ";
40    dump(x...);
41 }
42 #define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
43 #else
44 #define debug(...) ;
45 #endif
46  
47 int32_t main() {
48   string s;
49   cin >> s;
50   int n = s.length();
51   if (n == 1) cout << s;
52   else {
53     bool flag = true;
54     inc(i, 0, n - 1) if (s[i] != '9') flag = false;
55     if (flag) cout << s;
56     else {
57       inc(i, 0, n - 1) printf("9");
58     }
59   }
60 }
View Code

 

I

定义dp[i][j]为抽取i次牌后剩余j张单牌的概率

转移方程写为

1 dp[0][cnt]=1;
2 for(int i=1;i<=121;++i)
3     for(int j=1;j<=13;j+=2)
4         dp[i][j]=dp[i-1][j]*(124-i-3*j)*inv(124-i)+dp[i-1][j+2]*(3*j+6)*inv(124-i);

最终答案的求和

1 int ans=0;
2 for(int i=0;i<=121;++i)
3     ans=ans+i*dp[i-1][1]*3*inv(124-i);

 

J

启发式合并

题意是求出一个图中染色的最大点数

考虑通过边的关系将x和y进行合并,边是单向的,

有结论如果选择x能将y染色,那么选择x一定是更优的

根据这一特点建树,求出森林中最大size的树即可

2022牛客多校(一)2022牛客多校(一)
 1 set<int>to[N], from[N];
 2 int fa[N], sz[N];
 3 int findf(int x) {
 4     if (fa[x] == x)return x;
 5     return fa[x] = findf(fa[x]);
 6 }
 7 void _Merge(int x, int y) {
 8     x = findf(x), y = findf(y);
 9     if (x == y)return;
10     if (to[x].size() < to[y].size())
11         swap(x, y);
12     fa[y] = x;
13     sz[x] += sz[y];
14     vector<pair<int, int> >mg;
15     for (auto t : to[y]) {
16         to[x].insert(t);
17         from[t].erase(y);
18         from[t].insert(x);
19         if (from[t].size() == 1)
20             mg.push_back(make_pair(t, x));
21     }
22     for (auto [x, y] : mg)
23         _Merge(x, y);
24 }
25 
26 int main() {
27     int T = fast_IO::read();
28     for (int ti = 1; ti <= T; ++ti) {
29         int n = fast_IO::read();
30         for (int i = 1; i <= n; ++i)fa[i] = i, sz[i] = 1;
31         for (int i = 1; i <= n; ++i) {
32             int k = fast_IO::read();
33             for (int j = 1; j <= k; ++j) {
34                 int y = fast_IO::read();
35                 to[y].insert(i);
36                 from[i].insert(y);
37             }
38         }
39         for (int i = 1; i <= n; ++i)
40             if (from[i].size() == 1)
41                 _Merge(*from[i].begin(), i);
42         int ans = 0;
43         for (int i = 1; i <= n; ++i)
44             ans = max(ans, sz[i]);
45         printf("Case #%d: %dn", ti, ans);
46         for (int i = 1; i <= n; ++i)
47             to[i].clear(), from[i].clear();
48     }
49     return 0;
50 }
View Code

 

 

 

 

 

程序员灯塔
转载请注明原文链接:2022牛客多校(一)
喜欢 (0)