2020 CCPC QHD

字数统计: 1.4k字   |   阅读时长≈ 7分

lgwnb​

A.Greeting from Qinhuangdao

题意：

给你$n$个红球，$m$个蓝球，求从这些球中取$2$个红球的概率，用$p/q$形式表示概率。

题解：

签到题，令$s=n+m$公式为$C_n^2/C_{s}^2$，化简为$\frac{n(n-1)}{s(s-1)}$，求下两个的$gcd$，约分一下即可，特判一下$n=1$的情况。

AC代码：

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
//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }


signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    int r,b;cin>>r>>b;
    int p=r*(r-1),q=(r+b)*(r+b-1);
    cout<<"Case #"<<_<<": ";
    if(!p)cout<<"0/1\n";
    else{
      int g=gcd(p,q);
      cout<<p/g<<'/'<<q/g<<endl;
    }
  }
  return 0;
}

E.Exam Results

题意：

现已知$n$个学生的成绩，思路清晰的时候是$a_i$，差的时候是$b_i$，令$x$为$n$个学生中最高的成绩，设及格线为$x*p\%$，问最多能及格的人数是多少。

题解：

首先我们以$a_i$为排序标准，大的在前面，用个树状数组把$a_i$的出现次数现记录下来，因为我们需要让最大值尽可能小的同时，及格的人数也尽可能的多，那么我们就从大到小遍历，每到一个$i$，查询完后，就把$a$和$b$调换，更新树状数组，同时更新最大值，因为最大值有可能在前面出现，所以要记录下最大值，用个$multiset$即可，最后储存数据的时候因为$a_i$有$1e9$这么大，我们需要离散化储存一下数据，每次查询的是小于及格线的人数，然后用$n$减去即可求出，然后和答案取个$max$即可。

AC代码:

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
//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
typedef long long ll;

int N;
int mp[400005],tr[400005];
void add(int x,int a){
  for(;x<=N;x+=x&-x){
    if(a!=-1||tr[x])tr[x]+=a;
  }
}
int query(int x){
  int ans=0;
  for(;x>=1;x-=x&-x)ans+=tr[x];
  return ans;
}
struct xy{
  int a,b;
  bool operator<(const xy&p)const{return a>p.a;}
}a[200005];
signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    multiset<int>st;
    int tot=0;
    int n,p;cin>>n>>p;
    _for(i,0,n){
      cin>>a[i].a>>a[i].b;
      mp[tot++]=a[i].a,mp[tot++]=a[i].b;
    }
    sort(a,a+n);
    sort(mp,mp+tot);
    N=unique(mp,mp+tot)-mp;
    _for(i,1,N+1)add(i,-1);
    _for(i,0,n)add(lower_bound(mp,mp+N,a[i].a)-mp+1,1),st.insert(a[i].a);
    int ans=INT_MIN;
    _for(i,0,n){
      int ma=*st.rbegin();
      ll x=1ll*ma*p/100+(1ll*ma*p%100!=0);
      x=lower_bound(mp,mp+N,x)-mp+1;
      if(x==1)ans=n;
      else ans=max(ans,n-query(x-1));
      add(lower_bound(mp,mp+N,a[i].a)-mp+1,-1);
      add(lower_bound(mp,mp+N,a[i].b)-mp+1,1);
      st.erase(st.find(a[i].a)),st.insert(a[i].b);
    }
    cout<<"Case #"<<_<<": "<<ans<<endl;
  }
  return 0;
}

F.Friendly Group

题意：

现在有$n$个人，需要将他们分配到一个组内，如果组内有$k$个人，则组的好感度减$k$，组内有$m$个朋友关系，则组的好感度加$m$。

题解：

我们可以把每个人看成一个点，关系看成一条边，最后会有若干个连通图，我们只取不为树的连通图。

AC代码：

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
//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define EB emplace_back
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'


int cd,ce;
const int N=3e5+5;
struct xy{
  int v,id;
};
vector<xy>e[N];
int vis[N],vm[1000005];
void dfs(int u){
  vis[u]=1;
  cd++;
  _sfor(v,e[u]){
    if(!vm[v.id])ce++,vm[v.id]=1;
    if(!vis[v.v])dfs(v.v);
  }
}
signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    int n,m;cin>>n>>m;
    _for(i,1,n+1)e[i].clear(),vis[i]=0;
    _for(i,0,m)vm[i]=0;
    int u,v;
    _for(i,0,m){
      cin>>u>>v;
      e[u].EB(xy{v,i}),e[v].EB(xy{u,i});
    }
    int ans=0;
    _for(i,1,n+1){
      ce=cd=0;
      if(!vis[i]){
        dfs(i);
      }
      if(ce>=cd)ans+=ce-cd;
    }
    cout<<"Case #"<<_<<": "<<ans<<endl;
  }
  return 0;
}

G.Good Number

题意：

给定一个数$n$，定义$\lfloor\sqrt[k]{x}\rfloor|x$的$x$为好的数字，问$n$以内有几个好的数字。

题解：

我们不难发现$k=1$的时候答案为$n$，$k<30$的时候直接数论分块爆搜一下，$k>=30$的时候$\lfloor\sqrt[k]{x}\rfloor=1$，答案也为$n$。

AC代码：

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
//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'


signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    int n,k;cin>>n>>k;
    cout<<"Case #"<<_<<": ";
    if(k==1)cout<<n<<endl;
    else if(k<30){
      int ans=0;
      int N=pow(n,1.0/k);
      _for(i,1,N){
        ans+=int((pow(i+1,k)-1))/i-int((pow(i,k)-1)/i);
      }
      ans+=n/N-int((pow(N,k)-1)/N);
      cout<<ans<<endl;
    }else cout<<n<<endl;
  }
  return 0;
}

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true