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/%d\n", 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
];
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
]++;
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: %d\n", 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: %d\n", 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: %d\n", 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
;
}
printf("Case #%d: %d\n", cas
++, ans
);
}
return 0;
}
