2019CCPC-江西省赛【部分题解】
比赛只写出来了F，I，J，K。补题：G，C，H。
江西省赛
HDU - 6572：F - String
签到题
题意：给你一个字符串，让你找出能构成"avin"的概率。
思路：直接记录a，v，i，n出现的概率相乘即可。
坑点：约分
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 150;
char str[maxn], temp[4] = {'a', 'v', 'i', 'n'};
int num[maxn];
void solve() {
int n;
while (~scanf("%d", &n)) {
scanf("%s", &str);
memset(num, 0, sizeof(num));
for (int i = 0; i < n ;++i) {
num[str[i]]++;
}
int cnt = 1;
for (int i = 0; i < 4; ++i) {
cnt *= num[temp[i]];
}
if (!cnt) {
puts("0/1");
} else {
int x = cnt, y = n * n * n * n;
for (int i = 2; i <= cnt; ++i) {
if (x % i == 0 && y % i == 0) {
x /= i;
y /= i;
}
}
printf("%d/%d\n", x, y);
}
}
}
int main() {
solve();
return 0;
}
HDU - 6575：I - Budget
签到题
题意：给你一个3位小数的浮点数，所有预算将四舍五入到小数点后2位。例如1.003就是-0.003, 1.008就是0.002，给你n个浮点数，求出所有预算的和。
思路：可以用四舍五入函数保留小数点后两位，然后减去原来的数，但是自己不会，就用了个字符串存储，然后取小数点后三位，进行判断是否四舍五入。
坑点：小数相加减可能会出现-0.00的情况，利用eps处理即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 150;
char str[maxn], temp[4] = {'a', 'v', 'i', 'n'};
int num[maxn];
void solve() {
int n;
while (~scanf("%d", &n)) {
scanf("%s", &str);
memset(num, 0, sizeof(num));
for (int i = 0; i < n ;++i) {
num[str[i]]++;
}
int cnt = 1;
for (int i = 0; i < 4; ++i) {
cnt *= num[temp[i]];
}
if (!cnt) {
puts("0/1");
} else {
int x = cnt, y = n * n * n * n;
for (int i = 2; i <= cnt; ++i) {
if (x % i == 0 && y % i == 0) {
x /= i;
y /= i;
}
}
printf("%d/%d\n", x, y);
}
}
}
int main() {
solve();
return 0;
}
HDU - 6576：J - Worker
简单数论
题意：有n个仓库和m个工人。在i仓库的任何工人每天都可以处理a[i]订单。客户想知道是否有一种工人分配方法可以满足每个仓库每天处理相同数量的订单.
思路：算出n个仓库每天处理订单的最小公倍数。求出最小公倍数，这个最小公倍数可能是我们每个仓库要完成的订单量，然后求出每个仓库还需要分配多少个(b[i])工人的总和sum，看是否是m的倍数，如果不是，那么肯定不能分配，如果是，则肯定能分配，前面可能的含义：就是每个仓库分m/sum倍的b[i]个工人。这样才能使得m个分配完。
坑点：m的数据范围是1e18，题面表达不清楚。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1500;
int a[maxn];
void solve() {
int n;
ll m;
while (~scanf("%d%lld", &n, &m)) {
scanf("%d", &a[1]);
int t = a[1] / __gcd(1, a[1]);
for (int i = 2; i <= n; ++i) {
scanf("%d", &a[i]);
t = t * a[i] / __gcd(t, a[i]);
}
ll sum = 0;
for (int i = 1; i <= n; ++i) {
sum += t / a[i];
}
if (sum > m || m % sum) {
puts("No");
continue;
}
ll ans = t * m / sum;
puts("Yes");
for (int i = 1; i <= n; ++i) {
if (i < n) {
printf("%lld ", ans / a[i]);
} else {
printf("%lld\n", ans / a[i]);
}
}
}
}
int main() {
solve();
return 0;
}
HDU - 6577：K - Class
签到题
两个式子联立解方程即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
void solve() {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", (x * x - y * y) / 4);
}
int main() {
solve();
return 0;
}
HDU - 6573：G - Traffic
签到题
题意：你要在交叉路口拍照，然后有东西方向行驶的车和南北方向行驶的车，为了避免发生碰撞，南北方向的车会等待相同的时间。
思路：暴力枚举等多长时间，南北方向的所有车都能通过且不与东西方向的车相撞。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2500;
int dp[105][105];
void solve() {
int n, c, x;
while (~scanf("%d%d", &n, &c)) {
memset(dp, 0, sizeof(dp));
int ans = 0;
while (n--) {
scanf("%d", &x);
for (int i = 1; i <= c; ++i) {
dp[i][x] = dp[x][i] + 1;
if (i != x) {
ans = max(ans, dp[i][x]);
}
}
}
printf("%d\n", ans);
}
}
int main() {
solve();
return 0;
}
HDU - 6570：C - Wave
简单DP
题意：给出n个数字，找一个类似于abab…形式的子序列，求其最长的长度。
思路：dp(i,j)表示当前数字为j，前一个数字为i的序列长度。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
void solve() {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", (x * x - y * y) / 4);
}
int main() {
solve();
return 0;
}
HDU - 6574：H - Rng
逆元+数学
题意：给定一个n，然后让你随机生成两个区间，随机生成一个r∈[1,n]，在随机生成一个l∈[1,r],求两个区间相交的概率q/p % 1e9 + 7.
思路：随机生成一个r的概率为1/n,随机生成一个l的概率为1/(n - i + 1);
判断相交很难，可以用对立事件，1-两个区间不相交，下面来看怎么处理不相交。
我们让第一段区间的右端点小于第二段的左端点，这样第一段的左端点和第二段的右端点可以取值如下图, 第一段可以取值i，第二段可以取值n - i - 1.
枚举从1到n枚举i，这样个i边界就为n - 1，所以总和就为n * (n - 1)，真的是这样吗？其实不然，当i到中间位置是，前面的两个区间就枚举过了，所以要除以2，不相交的概率为n * (n - 1) / 2 / (n * n), 相交的概率用1减去化简得，(n + 1) / (2 * n), 最后用逆元来处理即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll fast_power(ll a, ll b) {
ll ans = 1;
while(b > 0) {
if (b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans % mod;
}
void solve() {
ll n;
while (~scanf("%lld", &n)) {
printf("%lld\n", (n + 1) * fast_power(2 * n, mod - 2) % mod);
}
}
int main() {
solve();
return 0;
}