“蔚来杯“2022牛客暑期多校训练营1，签到题GADI

题号 标题 已通过代码 通过率 团队的状态
A Villages: Landlines 点击查看 1673/4177 通过
B Spirit Circle Observation 点击查看 39/299 未通过
C Grab the Seat! 点击查看 88/392 未通过
D Mocha and Railgun 点击查看 1589/8517 通过
E LTCS 点击查看 43/324 未通过
F Cut 点击查看 21/154 未通过
G Lexicographical Maximum 点击查看 1834/4971 通过
H Fly 点击查看 56/405 未通过
I Chiitoitsu 点击查看 648/1134 通过
J Serval and Essay 点击查看 160/1331 未通过
K Villages: Landcircles 点击查看 1/45 未通过

G.Lexicographical Maximum

题意：

• 官方

思路：

• 官方

#include
using namespace std;

int main(){
    string s;  cin>>s;
    if(s.size()==1){
        cout<<s<<"\n";
        return 0;
    }
    int ok = 1;
    for(int i = 0; i < s.size()-1; i++){
        if(s[i]!='9')ok = 0;
    }
    if(ok==0){
        cout<<string(s.size()-1,'9');
    }else{
        cout<<s<<"\n";
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

A.Villages: Landlines

题意：

• 官方
  

思路：

• 能源站可以没有代价无限建，所以我们假设每个地方都有一个能源站好啦
• 然后电线的话，把没有连上的能源站连上，最小的代价。
• 题目等价于将n个x±r的区间联通的最小代价。
• 记得要开longlong

#include
using namespace std;
typedef long long LL;
const LL maxn = 2e5+10;
struct node{ LL l, r;}a[maxn];
bool cmp(node x, node y){
    return x.l!=y.l? x.l<y.l : x.r<y.r;
}
int main(){
    LL n;  cin>>n;
    for(LL i = 1; i <= n; i++){
        LL x, r;  cin>>x>>r;
        // cin>>a[i].l>>a[i].r;
        a[i].l = x-r;
        a[i].r = x+r;
    }
    sort(a+1,a+n+1,cmp);
    LL sum = 0, last = a[1].r;
    for(LL i = 2; i <= n; i++){
        if(a[i].l>last){
            // cout<
            sum += a[i].l-last;
        }
        last = max(last, a[i].r);
    }
    cout<<sum<<"\n";
    return 0;
}


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

D.Mocha and Railgun

题意：

• 官方

思路：

• 对于P点和线段2d而言，不难想到两种特殊情况，要么就是2d和圆心连线PO垂直，要么就是重合。
• 算一下不难发现垂直弧长是最小，重合是弧长最大。
• 然后根据弦长公式等可以推出弧长。

#include
using namespace std;

int main(){
    int T;  cin>>T;
    while(T--){
        double r;  cin>>r;
        double x, y, d;  cin>>x>>y>>d;
        // printf("%.10lf\n", 2*r*asin(d/r));
        double bb = acos((sqrt(x*x+y*y)+d)/r);
        double aa = acos((sqrt(x*x+y*y)-d)/r);
        // cout<
        printf("%.10lf\n", r*(aa-bb));
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

I.Chiitoitsu

题意：

• 官方
  
  思路：
• 官方std是期望dp，但是不难想到打表做法。
• 因为初始手牌只有13张，所以肯定是0对+13张，1对+11张，2对+9张，3对+7张，4对+5张，5对+3张，6对+1张这几种情况。一共也只有7种情况罢了。而且样例给出了数据最大最难算的0+13的情况和小数据5+3供验证打表正确性。
• 所以直接dfs打表，即可得到答案。
  13:927105416
  11:745749140
  9：707741534
  7：882102328
  5：781250051
  3：100000041
  1：31

//打表
#include
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL pows(LL a, LL x) { if(x==0)return 1; LL t = pows(a, x>>1); if(x%2==0)return t*t%mod; return t*t%mod*a%mod; }
LL pows(LL a, LL x, LL p) { if(x==0)return 1; LL t = pows(a, x>>1, p); if(x%2==0)return t*t%p; return t*t%p*a%p; }
LL exgcd(LL a, LL b, LL &x, LL &y){ if(!b){ x = 1, y = 0; return a; }else{LL r = exgcd(b, a%b, x, y); LL t = x; x = y; y = t-a/b*y; return r; }}
void exgcd(LL a, LL b, LL &d, LL &x,  LL & y, LL MOD) { if (b==0) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x, MOD); y -= x * (a / b); } }
LL inv(LL a, LL MOD) { LL d=0, x=0, y=0; exgcd(a, MOD,  d,  x, y, MOD); return d == 1 ? (x + MOD) % MOD : -1; }

LL sum=0;
void dfs(int d,int p,int r,LL w){//轮数,单牌,牌库,概率
    if(p<=0){
        sum=(sum+w*(d-1)%mod)%mod;
        return ;
    }
    dfs(d+1,p-2,r-1,w*p%mod*3%mod*inv(r,mod)%mod);//摸到对子，单牌-2，牌库-1, 概率*=p*3/牌库(每种牌p当前牌库里肯定还有3张)
    if(r>p*3) dfs(d+1,p,r-1,(w*(r-p*3)%mod*inv(r,mod)%mod)%mod);//摸到单牌，单牌不变，牌库-1，概率*=(牌库-p*3)/牌库
}

int main(){
    dfs(1,3,34*4-13,1);//开局3张单牌(相同牌开局最多出现两张！所以单牌，牌库里肯定还有3张)
    cout<<sum<<"\n";
    return 0;
}


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

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL mod = 1e9+7;
int getid(string s){ //1-34
    if(s[1]=='m')return s[0]-'0';
    if(s[1]=='p')return s[0]-'0'+9;
    if(s[1]=='s')return s[0]-'0'+18;
    if(s[1]=='z')return s[0]-'0'+27;
    return 0;
}
int now[50], all[50];

int main(){
    IOS;
    int T;  cin>>T;
    for(int _w = 1; _w <= T; _w++){
        cout<<"Case #"<<_w<<": ";
        string s;  cin>>s;
        memset(now,0,sizeof(now));
        for(int i = 0; i < (int)s.size(); i+=2){
            int id = getid(s.substr(i,2));
            now[id]++;
            all[id] = (all[id]+4-1)%4;
            if(now[id]==2)now[id] = 0;
        }
        // //开局单牌数量
        int cnt = 0;
        for(int i = 1; i <= 34; i++){
            if(now[i]!=0)cnt++;
        }
        if(cnt==1)cout<<"31\n";
        else if(cnt==3)cout<<"100000041\n";
        else if(cnt==5)cout<<"781250051\n";
        else if(cnt==7)cout<<"882102328\n";
        else if(cnt==9)cout<<"707741534\n";
        else if(cnt==11)cout<<"745749140\n";
        else if(cnt==13)cout<<"927105416\n";
    }
    return 0;
}


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