2021CCPC女生赛

已过A，D，G，K

剩下的题看情况补。

vp链接

中文题面，比较友好

A. 公交线路

B. 攻防演练

C. 连锁商店

D. 修建道路

题面：编号1~n，考虑修这一整条路的最大支付费用（区间[i,j]）的max{a_k}

范围:1<=n<=200000，且All 1<=a_i<=1e9

模拟

算数组这一项与下一项的最大值即可。

#include<bits/stdc++.h>
#define ll long long
const int mod = 1e9+7;
const int N = 200007;
int a[N];
 
using namespace std;
 
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
 
    ll ans=0;
 
    for(int i=0;i<n-1;i++)
    {
        ans+=max(a[i],a[i+1]);
    }
    cout<<ans<<endl;
 
    return 0;
}

E. 被遗忘的计划

F. 地图压缩

G. 3G网络

题面：n个建立3G网络基站的位置，每个基站能够实现以基站为圆心的半径为 r 的圆内区域的3G网络覆盖。

记成

$$C_{i,r}={(x,y)\in R^2|(x-x_i)^2+(y-y_i)^2\leq r^2}$$

此时我们需要计算

$$f(r)=\frac{S(C_{1,r}\bigcup C_{2,r} \bigcup\cdots C_{n,r})}{S(C_{1,r})+S(C_{2,r})+\cdots+S(C_{n,r})}$$

求当r→∞的时候f(r)的极限是什么，其中S表示平面点集的面积

数据范围 1<=n<=2000 -10000<=x,y<=10000 误差不超过1e-9

构造

实际上当r趋近于无穷的时候f(r)所给出来的式子是圆的面积了

#include<bits/stdc++.h>
#define ll long long
const int mod = 1e9+7;
const int N = 2e5+100;
int a[N],b[N];
 
using namespace std;
 
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>a[i]>>b[i];
    }
    printf("%.15lf",1.0/double(t));
    return 0;
}

H. 4G网络(无人AC，大概率不补)

I. 驾驶卡丁车

J. 最大权边独立集

K. 音乐游戏

题面：读取一行中有几个”-“字符。

范围 10<=n<=1000,其中一行字符串长度为6，首和尾都是’|’

模拟

签到题

#include<bits/stdc++.h>

using namespace std;
 
int main(){
    int t;
    scanf("%d",&t);
    getchar();
    int cnt=0;
    while(t--)
    {
        string s;
        getline(cin,s);
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='-') cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}