2023杭电多校4
C - Simple Set Problem
题目描述：
一共T组输入，每组输入有K个集合，从K个集合中选取K个数，也就是每个集合选取一个数，问这些数字中的最大值减去这些数字中的最小值的最小的值。
解题思路：
利用双指针，对于每一个右端点，存一段至少包含所有集合的点各一个的区间，然后就可以用区间极差来算整体的极差。这道题目非常恶心，非常卡时间，需要用快读和快写来优化一下，另外记得提交到GCC的编译器。
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <algorithm>
#include <climits>
#include <iostream>
#include <cstdio>
using namespace std;
#define endl '\n'
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
void write(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
void solved()
{
int n = read();
vector<array<int, 2>> arr;
int ans = 2e9;
for (int i = 1; i <= n; i++)
{
int k = read();
while (k--)
{
int v = read();
arr.push_back({v,i});
}
}
sort(arr.begin(), arr.end());
vector<int> vis(n + 1, 0);
int nums = 0;
int j = 0;
for (int i = 0; i < arr.size(); i++)
{
array<int, 2> now = arr[i];
if (!vis[now[1]]++)
{
++nums;
}
if (nums == n)
{
while (vis[arr[j][1]] > 1)
{
--vis[arr[j++][1]];
}
ans = min(ans, (arr[i][0] - arr[j][0]));
}
}
write(ans);
printf("\n");
}
int main()
{
int T = read();
while (T--)
{
solved();
}
return 0;
}
G - Guess
题目描述：
给定两个式子，一个是U(x)，如果x有平方因子，那么他就是0，如果他有k个质因子，那么他就是(-1)^k，要求我们计算一个S(n)=∑d|nμ(nd)ln(d)。
解题思路：
这是一道打表找规律的题目，并且需要一点板子。首先从打表中找出规律，如果输入的数是一个质数的k次，那么答案就是这个质数，其中k大于等于1，如果这个数是1的话当然就是1。那么快速判断一个超级大的数字是否为质数呢，我们就需要套一个板子的代码，这就是米勒-拉宾素性检验(MillerRabbin)算法，然后如果这个数不是质数，因为他最大是1e18，我们无法预处理出这么多的质数，至少要下降到1e6，所以要先判断一下开根号的结果是不是满足题意。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e6 + 10;
const int mod = 998244353;
int isPrime[N];
vector<int> prime;
int Quick_Multiply(int a, int b, int c)
{
long long ans = 0, res = a;
while (b)
{
if (b & 1)
ans = (ans + res) % c;
res = (res + res) % c;
b >>= 1;
}
return (int)ans;
}
int Quick_Power(int a, int b, int c)
{
int ans = 1, res = a;
while (b)
{
if (b & 1)
ans = Quick_Multiply(ans, res, c);
res = Quick_Multiply(res, res, c);
b >>= 1;
}
return ans;
}
bool Miller_Rabin(int x)
{
if (x == 2)
return true;
if (x < 2 || !(x & 1))
return false;
int s = 0, t = x - 1;
while (!(t & 1))
{
s++;
t >>= 1;
}
for (int i = 0; i < 10 && prime[i] < x; ++i)
{
int a = prime[i];
int b = Quick_Power(a, t, x);
for (int j = 1; j <= s; ++j)
{
int k = Quick_Multiply(b, b, x);
if (k == 1 && b != 1 && b != x - 1)
return false;
b = k;
}
if (b != 1)
return false;
}
return true;
}
void sieve()
{
for (int i = 2; i < N; i++)
{
isPrime[i] = 1;
}
for (int i = 2; i < N; i++)
{
if (isPrime[i])
{
prime.push_back(i);
}
for (int &it : prime)
{
if (i * it >= N)
{
break;
}
isPrime[i * it] = 0;
if (i % it == 0)
{
break;
}
}
}
}
bool isPerfectSquare(int v)
{
int k = sqrt(v);
return (k * k == v);
}
signed main()
{
close;
int T;
cin >> T;
sieve();
for (int i = 1; i <= T; i++)
{
if (i > 1)
{
cout << " ";
}
int v;
cin >> v;
if (Miller_Rabin(v) || v == 1)
{
cout << v % mod;
continue;
}
if (isPerfectSquare(v) && Miller_Rabin((int)sqrt(v)))
{
cout << (int)sqrt(v) % mod;
continue;
}
int flag = 0;
int originalV = v;
for (auto j : prime)
{
if (j * j > v)
break;
while (v % j == 0)
{
v /= j;
}
if (v == 1)
{
cout << j % mod;
flag = 1;
break;
}
v = originalV;
}
if (!flag)
{
cout << 1;
}
}
cout << endl;
}
J - Kong Ming Qi
题目描述：
一个(n+2)(m+2)的棋盘上有(n)*(m)个棋子，棋子可以跳跃另外一个棋子，当且仅当他们相邻，且该棋子跳跃到的地方没有棋子，问最后棋盘上最少有几颗棋子。
解题思路：
这题需要模拟很多种情况，模拟完就做出来了。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
signed main()
{
close;
int T;
cin >> T;
for (int i = 1; i <= T; i++)
{
int n, m;
cin >> n >> m;
if (n == 1 || m == 1)
{
int k = max(n, m);
cout << k - k / 2 << endl;
continue;
}
if (n % 3 == 0 || m % 3 == 0)
{
cout << 2 << endl;
continue;
}
cout << 1 << endl;
}
}
L - a-b Problem
题目描述：
有T组输入，每组输入有n个对，每个值由a和b组成，A要最大化A，B要最大化B，问最后SUMA-SUMB的值是多少。
解题思路：
直接求一个a+b，然后对他进行排序，从高到低拿即可。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e5 + 10;
struct ss
{
int sum;
int a;
int b;
};
ss input[N];
signed main()
{
close;
int T;
cin >> T;
for (int i = 1; i <= T; i++)
{
int n;
cin >> n;
for (int j = 1; j <= n; j++)
{
cin >> input[j].a >> input[j].b;
input[j].sum = input[j].a + input[j].b;
}
sort(input + 1, input + 1 + n, [&](const ss &left, const ss &right)
{ return left.sum > right.sum; });
int sumA = 0;
int sumB = 0;
for (int j = 1; j <= n; j++)
{
if (j & 1)
{
sumA += input[j].a;
}
else
{
sumB += input[j].b;
}
}
cout << sumA - sumB << endl;
}
}