给你两个正整数序列 \(a_1, \ldots, a_n\) 和 \(b_1, \ldots, b_m\) 。求每个 \(j = 1, \ldots, m\) 的最大公约数 \(a_1 + b_j, \ldots, a_n + b_j\) 。
输入
第一行包含两个整数 \(n\) 和 \(m\) ( \(1 \leq n, m \leq 2 \cdot 10^5\) )。
第二行包含 \(n\) 个整数 \(a_1, \ldots, a_n\) ( \(1 \leq a_i \leq 10^{18})\) .
第三行包含 \(m\) 个整数 \(b_1, \ldots, b_m\) ( \(1 \leq b_j \leq 10^{18})\) 。
输出
打印 \(m\) 个整数。其中的 \(j\) -th 应该等于 GCD \((a_1 + b_j, \ldots, a_n + b_j)\) .
题解
根据 GCD 的基本性质,我们知道 \(GCD(x, y) = GCD(x - y, y)\) 。多个参数也是如此: \(GCD(x, y, z, \ldots) = GCD(x - y, y, z, \ldots)\) .我们将其用于 \(GCD(a_1 + b_j, \ldots, a_n + b_j)\) 并从所有其他参数中减去 \(a_1 + b_j\) : \(GCD(a_1 + b_j, \ldots, a_n + b_j) = GCD(a_1 + b_j, a_2 - a_1, \ldots, a_n - a_1)\) .
如果我们找到 \(G = GCD(a_2 - a_1, \ldots, a_n - a_1)\) ,那么任何答案都可以找到 \(GCD(a_1 + b_j, G)\) 。需要注意的是,我们必须假设空集的 GCD 是 \(0\) ,而对于任意 \(x\) 都是 \(GCD(x, 0) = x\) ,因为 \(0\) 是唯一能被任何其他数整除的数。
AC code:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
inline i64 gcd(i64 x, i64 y)
{
return y == 0 ? x: gcd(y, x % y);
}
int main()
{
i64 n, m;
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n >> m;
vector<i64> a(n + 1), b(m + 1), c(n + 1);
for (int i = 1; i <= n; i++)
{
std::cin >> a[i];
}
for (int j = 1; j <= m; j++)
std::cin >> b[j];
i64 x = 0;
for (int i = 1; i <= n; i++)
{
x = gcd(x, a[i]-a[1]);
}
for (int i = 1; i <= m; i++)
{
i64 t = gcd(x, a[1] + b[i]);
std::cout << abs(t) << (i == m ? '\n' : ' ');
}
return 0;
}
-
反思 gcd求最大公约数具有内部可随意减的性质,可以利用这个性质来完成转化,但是如果是随意减的话得出的gcd 可能是最大公约数的相反数!!!
宏定义的妙用
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include<time.h>
#endif
using i64 = long long;
i64 M,D;
int main()
{
#ifndef ONLINE_JUDGE
time_t a=clock();
#endif
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(0);
std::cin.tie(0);
#endif
std::cin>>M>>D;
#ifndef ONLINE_JUDGE
std::cout<<clock()-a<<"ms\n";
#endif
return 0;
}
LCM Challenge
题面翻译
找到3个不超过n的正整数(可以相同),使得它们的lcm(最小公倍数)最大。输出最大的lcm
题目描述
Some days ago, I learned the concept of LCM (least common multiple). I've played with it for several times and I want to make a big number with it.
But I also don't want to use many numbers, so I'll choose three positive integers (they don't have to be distinct) which are not greater than $ n $ . Can you help me to find the maximum possible least common multiple of these three integers?
输入格式
The first line contains an integer $ n $ ( $ 1<=n<=10^{6} $ ) — the $ n $ mentioned in the statement.
输出格式
Print a single integer — the maximum possible LCM of three not necessarily distinct positive integers that are not greater than $ n $ .
样例 #1
样例输入 #1
9
样例输出 #1
504
样例 #2
样例输入 #2
7
样例输出 #2
210
提示
The least common multiple of some positive integers is the least positive integer which is multiple for each of them.
The result may become very large, 32-bit integer won't be enough. So using 64-bit integers is recommended.
For the last example, we can chose numbers $ 7 $ , $ 6 $ , $ 5 $ and the LCM of them is $ 7·6·5=210 $ . It is the maximum value we can get.
- 这题是一道思维题,结合了一部分基本数论知识,如果 \(n\) 为奇数则三个数互质,否则它们的最小公倍数的就是他们三个数的乘积除以最小公倍数 \(2\) ,所以这里如果n是偶数的话,如果\(gcd(n,n-3)==1\),选择\(n \cdot (n-1) \cdot (n-3)\) ,否则就选择\((n-1)\cdot(n-2)\cdot(n-3)\)
【模板】字符串哈希
题目描述
如题,给定 \(N\) 个字符串(第 \(i\) 个字符串长度为 \(M_i\),字符串内包含数字、大小写字母,大小写敏感),请求出 \(N\) 个字符串中共有多少个不同的字符串。
友情提醒:如果真的想好好练习哈希的话,请自觉。
输入格式
第一行包含一个整数 \(N\),为字符串的个数。
接下来 \(N\) 行每行包含一个字符串,为所提供的字符串。
输出格式
输出包含一行,包含一个整数,为不同的字符串个数。
样例 #1
样例输入 #1
5
abc
aaaa
abc
abcc
12345
样例输出 #1
4
提示
对于 \(30\%\) 的数据:\(N\leq 10\),\(M_i≈6\),\(Mmax\leq 15\)。
对于 \(70\%\) 的数据:\(N\leq 1000\),\(M_i≈100\),\(Mmax\leq 150\)。
对于 \(100\%\) 的数据:\(N\leq 10000\),\(M_i≈1000\),\(Mmax\leq 1500\)。
样例说明:
样例中第一个字符串(abc)和第三个字符串(abc)是一样的,所以所提供字符串的集合为{aaaa,abc,abcc,12345},故共计4个不同的字符串。
Tip:
感兴趣的话,你们可以先看一看以下三题:
BZOJ3097:http://www.lydsy.com/JudgeOnline/problem.php?id=3097
BZOJ3098:http://www.lydsy.com/JudgeOnline/problem.php?id=3098
BZOJ3099:http://www.lydsy.com/JudgeOnline/problem.php?id=3099
如果你仔细研究过了(或者至少仔细看过AC人数的话),我想你一定会明白字符串哈希的正确姿势的_
- 字符串哈希,模数尽量选取大质数:
using u128 = unsigned long long;
u128 base = 131;
const u128 maxn = 100009;
const u128 N = 212370440130137957ll;
const u128 num = 233;
const u128 num2 = 100000007;
然后选取合适的哈希函数可以减少冲突的次数!!!
- 同时在比较一个数组中相同元素个数的时候可以选择先根据\(hash\) 值排序,然后再通过判断附近的字符串是否与自己相同
毕竟如果键值都不同也不会到一起去
AC code:
#include <bits/stdc++.h>
using namespace std;
using u128 = unsigned long long;
u128 base = 131;
const u128 maxn = 100009;
const u128 N = 212370440130137957ll;
const u128 num = 233;
const u128 num2 = 100000007;
u128 check[maxn];
u128 _hash(const char *s)
{
int l = strlen(s);
u128 ans = 0;
for (int i = 0; i < l; i++)
{
ans = (ans * base + s[i]) % N;
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0),cout.tie(0);
string a;
int n;
std::cin >> n;
int count=n;
for (int i = 1; i <= n; i++)
{
cin >> a;
const char *ans = a.c_str();
u128 a2 = _hash(ans) % num%maxn;
bool OK = false;
u128 a1 =_hash(ans);
while (check[a2])
{
if(check[a2]==a1)
{
OK=true;
break;
}
a2 = (a2 + num2) % maxn;
}
if(OK)
{
count--;
}
else
check[a2] += a1;
}
cout<<count<<endl;
return 0;
}
A.利诺瓦和王国
-
每次测试时限:2 秒
-
每次测试的内存限制:256 兆字节
-
输入:标准输入
-
输出:标准输出
写轻小说是莉诺娃生命中最重要的事情。昨晚,莉诺娃梦见了一个梦幻般的王国。她一醒来就开始为这个王国写轻小说,当然,她是这个王国的女王。
王国里有 \(n\) 座城市和 \(n-1\) 条双向道路连接着成对的城市。从任何一座城市出发,都可以通过一些道路到达其他城市。城市的编号从 \(1\) 到 \(n\) ,城市 \(1\) 是王国的首都。因此,王国是树状结构。
作为女王,莉诺娃计划选择****的 \(k\) 个城市发展工业,而其他城市则发展旅游业。首都也可以是工业城市或旅游城市。
每年在首都举行一次会议。每个工业城市派出一名特使参加会议。所有特使都将遵循从出发城市到首都的最短路径(这是唯一的)。
旅游城市的旅行是愉快的。对于每个特使来说,他的快乐程度等于他所走路径上的**旅游城市的数量。
为了成为受人爱戴的女王,莉诺娃希望选择 \(k\) 座城市,使所有使节的幸福总和最大。你能为她计算出最大的总和吗?
输入
第一行包含两个整数 \(n\) 和 \(k\) ( \(2\le n\le 2 \cdot 10^5\) , \(1\le k< n\) )--分别是城市数量和工业城市数量。
接下来的每行 \(n-1\) 包含两个整数 \(u\) 和 \(v\) ( \(1\le u,v\le n\) ),表示有一条道路连接城市 \(u\) 和城市 \(v\) 。
可以保证,从任何一个城市出发,都可以通过公路到达其他任何城市。
**第一行包含两个整数 \(n\) 和 \(k\) ( \(2\le n\le 2 \cdot 10^5\) , \(1\le k< n\) )--分别是城市和工业城市的数量。接下来的每一行 \(n-1\) 包含两个整数 \(u\) 和 \(v\) ( \(1\le u,v\le n\) ),表示有一条道路连接城市 \(u\) 和城市 \(v\) 。可以保证,从任何一个城市出发,都可以通过公路到达其他任何城市。
AC code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> _next;
vector<int> dis;
vector<pair<int, int>> num;
const int MAXN = INT_MAX;
void dfs(int x, int step)
{
dis[x] = step;
for (int i = 0; i < _next[x].size(); i++)
{
if (step + 1 < dis[_next[x][i]])
{
dfs(_next[x][i], step + 1);
}
}
}
vector<bool> vis;
int dfs2(int x)
{
int ans = 0;
for (int i = 0; i < _next[x].size(); i++)
{
auto &p = _next[x][i];
if (!vis[p])
{
vis[p] = 1;
ans += dfs2(p) + 1;
}
}
return num[x].second = ans;
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n, k;
std::cin >> n >> k;
dis.assign(n + 1, MAXN), num.assign(n + 1, pair(0, 0)), vis.assign(n + 1, 0);
for (int i = 1; i <= n; i++)
num[i].first = i;
_next.assign(n + 1, vector<int>());
for (int i = 1; i < n; i++)
{
int u, v;
std::cin >> u >> v;
_next[u].push_back(v);
_next[v].push_back(u);
}
dfs(1, 0);
vis[1] = 1;
dfs2(1);
sort(num.begin() + 1, num.begin() + n + 1, [&](pair<int, int> p1, pair<int, int> p2)
{
return dis[p1.first]-p1.second>dis[p2.first]-p2.second;
});
long long sum = 0;
for (int i = 1; i <= k; i++)
{
sum += dis[num[i].first];
sum -= num[i].second;
}
cout << sum << '\n';
return 0;
}
/*
4 1
1 2
2 3
1 4
3 1
1 2
1 3
5 3
1 2
1 3
2 4
2 5
*/
- 主要是图的遍历的过程中的一些思维和细节的问题!!!我没看题解WA了 \(6\) 发过了哈哈哈
「CROI · R2」01-string
题目描述
给定两个长度为 \(n\) 的 \(01\) 串 \(S,T\),你可以对串 \(S\) 执行无限次操作,每次都可以从以下操作中任选一个执行:
-
选择两个正整数 \(l,r(1\le l\le r\le n)\),将 \(S_l\dots S_r \ 01\) 反转。
-
选择两个正整数 \(l,r(1\le l\le r\le n)\),将 $S_l\dots S_r $ 全部改为 \(0\)。
-
选择两个正整数 \(l,r(1\le l\le r\le n)\),将 $S_l\dots S_r $ 全部改为 \(1\)。
你需要回答最少使用几次操作才能把 \(S\) 变成 \(T\)。
输入格式
本题采用多组数据测试。
第一行一个正整数 \(T\),表示数据组数。
对于每组数据:
第一行一个 \(01\) 串,表示串 \(S\)。
第二行一个 \(01\) 串,表示串 \(T\)。
输出格式
一共 \(T\) 行,第 \(i\) 行一个整数,表示第 \(i\) 组数据的答案。
样例 #1
样例输入 #1
3
00000
11111
10101
01010
11100101
11110000
样例输出 #1
1
1
2
提示
【样例解释】
以下提供样例三组数据的合法方案之一:
对于第一组数据,选取 \(l=1,r=5\),将 \(S_l\dots S_r\) 全部变成 \(1\)。
对于第二组数据,选取 \(l=1,r=5\),将 \(S_l\dots S_r \ 01\) 反转。
对于第三组数据,先选取 \(l=4,r=8\),将 \(S_l\dots S_r\) \(01\) 反转,再选取 \(l=5,r=8\),将 \(S_l\dots S_r\) 全部变成 \(0\)。
【数据范围】
本题采用捆绑测试。
- Sub 0(10 points):\(n\le 5\)。
- Sub 1(10 points):\(n\le 18\)。
- Sub 2(30 points):\(n\le 2000\)。
- Sub 3(50 points):无特殊限制。
对于所有的数据,\(1\le T \le 10\),\(1\le n\le 5\times 10^5\)。
- 对于我来说算是非常复杂而且考验我的思维的题目,难度对我来说非常高,但是它的学习价值真的特别高,对于我的逻辑思维能力是一个很大的挑战,我深入理解了一下题解的思维,然后在WA了无数发,以及参考题解的情况下,勉强理解了解题思路。
#include <bits/stdc++.h>
using namespace std;
string a, b;
#define int long long
long long M = 0x7ffffff;
void solve()
{
std::cin >> a >> b;
int _ = a.size();
vector<vector<int>> dp(6, vector<int>(_ + 5, 0x7ffffff));
dp[0][0] = 0, dp[1][0] = 1, dp[2][0] = 1, dp[3][0] = 1, dp[4][0] = 2, dp[5][0] = 2;
/**
* 0 不操作
* 1 覆盖成0
* 2 覆盖成1
* 3 反转
* 4 覆盖1 反转得 0
* 5 覆盖0 翻转得 1
*/
auto make = [&](int j, int i)
{
dp[j][i] = M;
};
for (int i = 1; i <= _; i++)
{
if (b[i - 1] == a[i - 1])
{
if (a[i - 1] == '1')
{
dp[0][i] = min(dp[0][i], dp[0][i - 1]);
dp[0][i] = min(dp[0][i], dp[1][i - 1]);
dp[0][i] = min(dp[0][i], dp[2][i - 1]);
dp[0][i] = min(dp[0][i], dp[3][i - 1]);
dp[0][i] = min(dp[0][i], dp[4][i - 1]);
dp[0][i] = min(dp[0][i], dp[5][i - 1]);
dp[2][i] = min(dp[2][i], dp[0][i - 1] + 1);
dp[2][i] = min(dp[2][i], dp[1][i - 1] + 1);
dp[2][i] = min(dp[2][i], dp[2][i - 1]);
dp[2][i] = min(dp[2][i], dp[3][i - 1] + 1);
dp[2][i] = min(dp[2][i], dp[4][i - 1]);
dp[2][i] = min(dp[2][i], dp[5][i - 1] + 1);
dp[5][i] = min(dp[5][i], dp[0][i - 1] + 2);
dp[5][i] = min(dp[5][i], dp[1][i - 1] + 1);
dp[5][i] = min(dp[5][i], dp[2][i - 1] + 2);
dp[5][i] = min(dp[5][i], dp[3][i - 1] + 1);
dp[5][i] = min(dp[5][i], dp[4][i - 1] + 1);
dp[5][i] = min(dp[5][i], dp[5][i - 1]);
make(1, i), make(3, i), make(4, i);
}
else
{
dp[0][i] = min(dp[0][i], dp[0][i - 1]);
dp[0][i] = min(dp[0][i], dp[1][i - 1]);
dp[0][i] = min(dp[0][i], dp[2][i - 1]);
dp[0][i] = min(dp[0][i], dp[3][i - 1]);
dp[0][i] = min(dp[0][i], dp[4][i - 1]);
dp[0][i] = min(dp[0][i], dp[5][i - 1]);
dp[1][i] = min(dp[1][i], dp[0][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[1][i - 1]);
dp[1][i] = min(dp[1][i], dp[2][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[3][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[4][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[5][i - 1]);
dp[4][i] = min(dp[4][i], dp[0][i - 1] + 2);
dp[4][i] = min(dp[4][i], dp[1][i - 1] + 2);
dp[4][i] = min(dp[4][i], dp[2][i - 1] + 1);
dp[4][i] = min(dp[4][i], dp[3][i - 1] + 1);
dp[4][i] = min(dp[4][i], dp[4][i - 1]);
dp[4][i] = min(dp[4][i], dp[5][i - 1] + 1);
make(2, i), make(3, i), make(5, i);
}
}
else
{
if (a[i - 1] == '1')
{
dp[1][i] = min(dp[1][i], dp[0][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[1][i - 1]);
dp[1][i] = min(dp[1][i], dp[2][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[3][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[4][i - 1] + 1);
dp[1][i] = min(dp[1][i], dp[5][i - 1]);
dp[3][i] = min(dp[3][i], dp[0][i - 1] + 1);
dp[3][i] = min(dp[3][i], dp[1][i - 1] + 1);
dp[3][i] = min(dp[3][i], dp[2][i - 1] + 1);
dp[3][i] = min(dp[3][i], dp[3][i - 1]);
dp[3][i] = min(dp[3][i], dp[4][i - 1]);
dp[3][i] = min(dp[3][i], dp[5][i - 1]);
dp[4][i] = min(dp[4][i], dp[0][i - 1] + 2);
dp[4][i] = min(dp[4][i], dp[1][i - 1] + 2);
dp[4][i] = min(dp[4][i], dp[2][i - 1] + 1);
dp[4][i] = min(dp[4][i], dp[3][i - 1] + 1);
dp[4][i] = min(dp[4][i], dp[4][i - 1]);
dp[4][i] = min(dp[4][i], dp[5][i - 1] + 1);
make(0, i), make(2, i), make(5, i);
}
else
{
dp[2][i] = min(dp[2][i], dp[0][i - 1] + 1);
dp[2][i] = min(dp[2][i], dp[1][i - 1] + 1);
dp[2][i] = min(dp[2][i], dp[2][i - 1]);
dp[2][i] = min(dp[2][i], dp[3][i - 1] + 1);
dp[2][i] = min(dp[2][i], dp[4][i - 1]);
dp[2][i] = min(dp[2][i], dp[5][i - 1] + 1);
dp[3][i] = min(dp[3][i], dp[0][i - 1] + 1);
dp[3][i] = min(dp[3][i], dp[1][i - 1] + 1);
dp[3][i] = min(dp[3][i], dp[2][i - 1] + 1);
dp[3][i] = min(dp[3][i], dp[3][i - 1]);
dp[3][i] = min(dp[3][i], dp[4][i - 1]);
dp[3][i] = min(dp[3][i], dp[5][i - 1]);
dp[5][i] = min(dp[5][i], dp[0][i - 1] + 2);
dp[5][i] = min(dp[5][i], dp[1][i - 1] + 1);
dp[5][i] = min(dp[5][i], dp[2][i - 1] + 2);
dp[5][i] = min(dp[5][i], dp[3][i - 1] + 1);
dp[5][i] = min(dp[5][i], dp[4][i - 1] + 1);
dp[5][i] = min(dp[5][i], dp[5][i - 1]);
make(0, i), make(1, i), make(4, i);
}
}
}
int min_ = LONG_LONG_MAX;
for (int i = 0; i < 6; i++)
{
min_ = std::min(min_, dp[i][_]);
}
std::cout << min_ << '\n';
}
signed main()
{
// std::ios::sync_with_stdio(0);
// std::cin.tie(0), cout.tie(0);
int t;
std::cin >> t;
while (t--)
solve();
return 0;
}
- 这里放一篇大佬的题解,真的好简洁好优雅,