概述
A.A Greeting from Qinhuangdao
题意：
给出 r r r 个红球， b b b 个篮球，求从全部的球里面，拿到两个红球的概率是多少。很基本的概率公式 p = C r 2 C b + r 2 = r ∗ ( r − 1 ) 2 ( r + b ) ∗ ( r + b − 1 ) 2 = r ∗ ( r − 1 ) ( r + b ) ∗ ( r + b − 1 ) p=frac{C_r^2}{C_{b+r}^2}=frac{frac{r*(r-1)}{2}}{frac{(r+b)*(r+b-1)}{2}}=frac{r*(r-1)}{(r+b)*(r+b-1)} p=Cb+r2Cr2=2(r+b)∗(r+b−1)2r∗(r−1)=(r+b)∗(r+b−1)r∗(r−1)。
找到最大公约数然后化简。
Code：
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
const int N = 2e5 + 50;
int n, m, k;
int main()
{
int t;
sd(t);
int cas = 1;
while (t--)
{
int x, y;
sdd(x, y);
n = x * (x - 1);
m = (x + y) * (x + y - 1);
k = gcd(n, m);
printf("Case #%d: %d/%dn", cas++, n / k, m / k);
}
return 0;
}
E.Exam Results
题意：
给出 n n n 个学生的考试分数可以为两个值 a , b a,b a,b， 每次选择一个一个值作为当前学生的分数，确定好每个学生的成绩后，选择所有学生成绩的后，找到成绩最大值，用最大值 ∗ p % *p% ∗p% ，成绩大于这个值的就为及格，计算及格人数的最大值。
把所有成绩从大到小排序，枚举每个成绩作为最值时可以找到多少学生的成绩及格的，每次加进去 n n n 个学生，如果不够 n n n 个学生说明枚举的不合适，每次找到当前成绩出现一次且大于及格线的统计数量，选取最大值。然后把加入的最大值减去。
Code：
const int N = 4e5 + 50;
int n, m, p;
struct node
{
int val, pos;
} a[N];
int b[N], c[N];//b数组统计能否找够n个人，c数组统计及格人数
bool cmp(node a, node b)
{
return a.val > b.val;
}
int main()
{
int t;
sd(t);
int cas = 1;
while (t--)
{
sdd(n, p);
rep(i, 0, n)
b[i] = c[i] = 0;
rep(i, 1, n)
{
sdd(a[2 * i - 1].val, a[2 * i].val);
a[2 * i - 1].pos = i, a[2 * i].pos = i;
}
sort(a + 1, a + 2 * n + 1, cmp);//分值从大到小排序
int cnt = 0, res = 0, pos1 = 0, pos2 = 0, ans = 0;
rep(i, 1, n + 1)//枚举每个数作为最大值
{
while ((pos1 + 1) <= 2 * n && cnt < n)
{
b[a[++pos1].pos]++;//前n个人每个位置出现的次数
if (b[a[pos1].pos] == 1)
cnt++;//出现一次记录
}
while ((pos2 + 1) <= 2 * n && a[pos2 + 1].val >= ((1ll * a[i].val * p % 100 == 0) ? (1ll * a[i].val * p / 100) : (1ll * a[i].val * p / 100 + 1)))
{
c[a[++pos2].pos]++;//及格的
if (c[a[pos2].pos] == 1)
res++;//出现一次记录
}
if (cnt == n)
ans = max(ans, res);
b[a[i].pos]--;//除去当前值
if (b[a[i].pos] == 0)
cnt--;
c[a[i].pos]--;
if (c[a[i].pos] == 0)
res--;
}
printf("Case #%d: %dn", cas++, ans);
}
return 0;
}
F.Friendly Group
题意：
给出了 n n n 个人和 m m m 条关系，每一个团体的价值为当前团体的关系数-人数，如果这个团体的关系数小于等于人数那么就是 0 0 0 ,也就相当于不选择。
可以使用并查集来考虑对于每个节点计算点数和边数的关系，符合边数-点数>0的就加上边数-点数，最后求总和。
Code：
const int N = 3e5 + 50;
int n, m, k;
int fa[N], cnte[N], cntv[N];
bool vis[N];
int x, y;
void init(int n)
{
rep(i, 0, n + 1)
{
fa[i] = i;
cnte[i] = 1;
cntv[i] = 0;
vis[i] = false;
}
}
int Find(int x)
{
if (fa[x] == x)
return x;
return fa[x] = Find(fa[x]);
}
void unio(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if (fx != fy)
{
fa[fx] = fy;
cntv[fy] += cntv[fx] + 1;
cnte[fy] += cnte[fx];
}
else
cntv[fy]++;
return;
}
int main()
{
int t;
sd(t);
int cas = 1;
while (t--)
{
sdd(n, m);
init(n);
int ans = 0;
rep(i, 1, m)
{
sdd(x, y);
unio(x, y);
}
rep(i, 1, n)
{
if (!vis[fa[i]])
{
if (cntv[fa[i]] - cnte[fa[i]] > 0)
ans += (cntv[fa[i]] - cnte[fa[i]]);
vis[fa[i]] = true;
}
}
printf("Case #%d: %dn", cas++, ans);
}
return 0;
}
G.Good Number
题意：
给出 n , k n,k n,k 代表有 1 − n 1-n 1−n 个数里找到满足 ⌊ k √ x ⌋ ⌊k √x⌋ ⌊k√x⌋ divides x x x . 这样的 x x x 有多少个，当 k k k 大于 30 30 30 的时候答案就是 n n n ，因为开 30 次方根就是 1 ，所有的数都可以整除 1 1 1 ，然后从 1 1 1 枚举 ⌊ k √ x ⌋ ⌊k √x⌋ ⌊k√x⌋ 的值到 ⌊ k √ x ⌋ k ⌊k √x⌋^k ⌊k√x⌋k 大于n时结束，这样每一段的长度计算出来，判断这一段有多少 ⌊ k √ x ⌋ ⌊k √x⌋ ⌊k√x⌋ 的倍数求和。
Code：
int ppow(int x, int n)
{
int res = 1;
while (n)
{
if (n & 1)
res *= x;
x = x * x;
n >>= 1;
}
return res;
}
const int N = 2e5 + 50;
int n, m, k;
int main()
{
int t;
sd(t);
int cas = 1;
while (t--)
{
sdd(n, k);
if (k > 30 || k == 1)
{
printf("Case #%d: %dn", cas++, n);
continue;
}
int l = 1, r = 1;
int ans = 0;
for (int i = 1; ppow(i, k) <= n; i++)
{
l = ppow(i, k);
r = min(n, ppow(i + 1, k));
int len = r - l;
if(len>0)
{
ans++;
len--;
}
ans += len / i;
//pdd(i, ans);
}
printf("Case #%d: %dn", cas++, ans);
}
return 0;
}
最后
以上就是忧郁猎豹为你收集整理的2020CCPC秦皇岛题解的全部内容，希望文章能够帮你解决2020CCPC秦皇岛题解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复