2020 CCPC-Wannafly Winter Camp Day1 总结
程序员文章站
2022-07-12 15:06:54
...
部分题目列表:
题号 | 题目 | 算法 |
---|---|---|
B题 | 密码学 | 签到题,字符串处理 |
H题 | 最大公约数 | 数学、gcd、大数 |
F题 | 乘法 | 较为巧妙的使用二分 |
A题 | 期望逆序对 | - |
C题 | 染色图 | - |
I题 | K小数查询 | 在线线段树套权值线段树 |
B题 密码学
签到题,就是一个字符串的计算,可耻的WA了一发是因为忘记了解码要倒着去解( 从 到 )
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int a[maxn], b[maxn];
string str[maxn];
int s[maxn][105];
void dde(int k)
{
for (int i = 0; i < str[k].size(); i++) {
if (str[k][i] > 'Z')
s[k][i] = str[k][i] - 'a';
else
s[k][i] = str[k][i] - 'A' + 26;
}
}
int main(void)
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
scanf("%d%d", &a[i], &b[i]);
for (int i = 1; i <= n; i++)
cin >> str[i];
for (int i = m - 1; i >= 0; i--) {
int x = a[i], y = b[i];
string aa = str[x], bb = str[y];
while (str[x].size() < str[y].size())
str[x] = str[x] + str[x];
for (int j = 0; j < str[y].size(); j++) {
dde(x), dde(y);
int kkk = s[y][j] - s[x][j];
kkk = (kkk + 52) % 52;
if (kkk < 26)
bb[j] = kkk + 'a';
else
bb[j] = kkk - 26 + 'A';
}
str[x] = aa;
str[y] = bb;
}
for (int i = 1; i <= n; i++)
cout << str[i] << endl;
return 0;
}
H题 最大公约数
Java大数走起
题干:有三个人 ,其中 和 共享了一个神秘的数字 ,已知 , 现在 和 说:“ 的值等于 ”。
不太信任 ,于是想向 确认一下 是否真的等于 。 虽然不想直接把 的值告诉 ,但是 允许 给出一个正整数 (注意 可以大于 ),然后 会回答 。
现在给出 ,你需要帮助 决定这样的 的取值,使得 一定可以通过 的回答来判断 有没有撒谎。如果这样的 有多个,你需要输出最小的那个。
输入第一行是一个整数 。
对于每组数据,输入一行两个整数 。
对于每组数据,输出一行一个整数,表示答案。如果满足条件的 不存在,则输出 −1。
// package Main;
import java.util.*;
import java.math.*;
public class Main {
static BigInteger arr[] = new BigInteger[505];
static BigInteger m(int a) {
return new BigInteger(a + "");
}
static boolean isP(int x) {
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
static void init() {
arr[1] = BigInteger.ONE;
for (int i = 2; i <= 500; i++) {
if (isP(i))
arr[i] = arr[i - 1].divide(arr[i - 1].gcd(m(i))).multiply(m(i));
else
arr[i] = arr[i - 1];
}
}
public static void main(String[] args) {
init();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- != 0) {
int n = sc.nextInt();
int k = sc.nextInt();
BigInteger ans = arr[n / k].multiply(m(k));
System.out.println(ans);
}
}
}
F题 乘法
题意:给出一个长度为 的数列和一个长度为 的数列, 可以构造得到一个 的矩阵 ,其中 , 给出整数 ,你需要求出 中第 大的数的值。(, )
思路:二分的找,需要额外注意当数为负数和零时候的情况
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int maxn = 1e5 + 5;
ll ef = 1e12;
ll n, m, k;
vector<ll> a, b;
ll update_a(ll x, ll mid, ll l, ll r)
{
if (l == r)
return l;
int m = (l + r + 1) >> 1;
if (x * b[m] <= mid)
return update_a(x, mid, m, r);
else
return update_a(x, mid, l, m - 1);
}
ll update_b(ll x, ll mid, ll l, ll r)
{
if (l == r)
return l;
int m = (l + r) >> 1;
if (x * b[m] <= mid)
return update_b(x, mid, l, m);
else
return update_b(x, mid, m + 1, r);
}
ll Binary_Search(ll l, ll r)
{
if (l == r)
return l;
ll mid = (l + r) >> 1;
ll ans = 0;
for (int i = 0; i < a.size(); i++) {
if (a[i] < 0)
ans += m - update_b(a[i], mid, 0, b.size());
else
ans += update_a(a[i], mid, -1, b.size() - 1) + 1;
}
if (ans >= k)
return Binary_Search(l, mid);
else
return Binary_Search(mid + 1, r);
}
int main(void)
{
IO;
cin >> n >> m >> k;
k = n * m - k + 1;
ll tmp;
for (int i = 0; i < n; i++) {
cin >> tmp;
a.push_back(tmp);
}
for (int i = 0; i < m; i++) {
cin >> tmp;
b.push_back(tmp);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
cout << Binary_Search(-ef, ef) << endl;
return 0;
}
A题 期望逆序对
题意:生成一个每个数是从 中生成的整数, 中不存在相同的数字,求逆序对个数的期望的最小值, 数组范围至.
输出一行一个整数,表示答案对 998244353 取模后的值。假设答案的最简分数表示是 , 你需要输出一个整数 满足
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 5050;
struct section {
int l, r;
void read() {
scanf("%d%d", &l, &r);
}
bool operator < (const section& s1) {
return l + r < s1.l + s1.r;
}
}a[maxn];
int n, b[maxn];
int quick(int x, int y)
{
int z = 1;
while (y) {
if (y & 1)
z = 1ll * z * x % mod;
y >>= 1;
x = 1ll * x * x % mod;
}
return z;
}
int cal(section x, section y)
{
int l = max(x.l, y.l);
if (l > x.r)
return 0;
int r = min(x.r, y.r);
int ans = 1ll * (l - y.l + r - y.l) * (r - l + 1) / 2 % mod;
ans = (ans + 1ll * (x.r - r) * (y.r - y.l + 1)) % mod;
return ans;
}
int main(void)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
a[i].read();
sort(a + 1, a + n + 1);
int ans = 0;
for (int i = 1; i <= n; i++)
b[i] = quick(a[i].r - a[i].l + 1, mod - 2);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
ans = (ans + 1ll * b[i] * b[j] % mod * cal(a[i], a[j])) % mod;
printf("%d\n", ans);
return 0;
}
C题 染色图
—待补—
I题 K小数查询
树套树之线段树套权值线段树,在线维护
—待补—
推荐阅读
-
2020 CCPC Wannafly Winter Camp Day1 A,B,E~I题解
-
2020 CCPC Wannafly Winter Camp Day1 F 乘法 (二分)
-
2020 CCPC Wannafly Winter Camp Day2 Div.1&2(A 托米的字符串)
-
2020 CCPC Wannafly Winter Camp Day1H
-
2020 CCPC Wannafly Winter Camp Day1 H 最大公约数(唯一分解定理)
-
2020 CCPC Wannafly Winter Camp Day1 F 乘法(二分)
-
CCPC-Wannafly Winter Camp Day2 H
-
2020 CCPC Wannafly Winter Camp Day1 B 密码学( 模拟)
-
2020 CCPC Wannafly Winter Camp Day1 Div.1&2(A题 期望逆序对)(找规律)
-
2020 CCPC-Wannafly Winter Camp