自闭场，不想多说，能做的就2个签到和H了，难度2.0就是字典树上后缀自动机，知识储备限制了我的想象
H-Harder Gcd Problem
先挂个线性筛把范围内素数都筛一下，然后直接lowerbound找到第一个小于n的素数位置（实际上至少要小于等于n/2，我懒，直接lowerbound到n了），然后从大往小依次处理
对于每一个素数，让(j=(n/p[i])*p[i])（即找到最后一个j使得jp[i]<=n），然后把j向1枚举，每两个jp[i]组成一对答案，但对于j为奇数的情况，2*p[i]得先暂时保留
最后再遍历没被匹配的数，这时刚刚2*p[i]中带有2的因子，因此他们也能够相互匹配，这样再把它们两两匹配
我的处理是先让1*p[i]处于待匹配状态，若j为偶数，则2也能被匹配；若j为奇数，则2只能进入待匹配状态，而不会被匹配
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-12;
const int maxn = 4e5 + 10;
const int inf = 1e9;
ll mod = 1e9 + 7;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();
return f * x;
}
int v[maxn], p[maxn], ecnt, vis[maxn], cnt = 0;
void Euler_sieve(int n)
{
ecnt = 0;
for (int i = 2; i <= n; i++) {
if (v[i] == 0) { v[i] = i; p[++ecnt] = i; }
for (int j = 1; j <= ecnt; j++)
{
if (p[j] > v[i] || p[j] > n / i)break;
v[i * p[j]] = p[j];
}
}
}
struct an {
int a, b;
}ans[maxn];
int main()
{
fastio;
int t;
cin >> t;
Euler_sieve(3e5 + 5);
while(t--)
{
memset(vis, 0, sizeof(vis));
int n;
cin >> n;
cnt = 0;
int P = lower_bound(p + 1, p + 1 + ecnt, n) - p - 1;
int tmp = -1;
for (int i = P; i >= 1; i--)
{
tmp = p[i];
for (int j = n / p[i] * p[i]; j > p[i]; j -= p[i])
{
if (!vis[j])
{
if (tmp == -1)
tmp = j;
else
{
ans[++cnt] = { tmp,j };
vis[tmp] = vis[j] = 1;
tmp = -1;
}
}
}
}
tmp = -1;
for (int i = 2; i <= n; i += 2)
{
if (!vis[i])
if (tmp == -1)
tmp = i;
else
{
ans[++cnt] = { tmp,i };
vis[tmp] = vis[i] = 1;
tmp = -1;
}
}
cout << cnt << endl;
for (int i = 1; i <= cnt; i++)
cout << ans[i].a << " " << ans[i].b << endl;
}
return 0;
}
D-Dividing Strings
阴间字符串,模拟+思维难度感觉很大
首先需要知道的是：函数传入大字符串会T，建议直接取地址，具体差多少时间，见图：
剩下的就是做法了，打的时候想dp想半天没整出来，结果是模拟，我直接爬
由样例可得到的结论：
拆成长度为1的n个数，ans肯定<=9，因此枚举长度只有两种（1、拆成长度相同的串；2、拆成长度为d和d-1的串；3否则不能使ans<=9）
对于长度相同的串，直接找到最大值和最小值比较就行了
对于长度相差1的串：当且仅当长度为d的串为100000000x，长度为d-1的串为99999999y时相减<=9（反证法：出现其他串时MAX和MIN都可能改变，相减必大于9）
当d==2时，需要特判1x和y，让MAX=1x，MIN=y(我的代码好像不需要处理这个就能ac,个人写法可能有影响)
一定要记得把有前导零的串给筛掉（指相同长度的串匹配）
以下是代码（感谢ac代码帮模拟手残人找出错误）
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
double pi = acos(-1);
const double eps = 1e-12;
const int maxn = 1e5 + 10;
const int inf = 1e9;
string s;
int ans;
int pre[maxn];
int dif(string &a, string &b)
{
int len = a.length();
int res = 0;
for (int i = 0; i < len; i++)
{
res = res * 10 + a[i] - b[i];
if (res >= 9)return 9;
}
return res;
}
void div1(string &s,int d)//一定要取地址，不然无限TLE，下同
{
string MAX = "0", MIN = "z";
string tmp;
int len = s.length();
if (d > len / 2)return;
int i = 0;
while (i < len)
{
tmp = s.substr(i, d);
if (tmp[0] == '0' && d > 1)return;//筛掉前导零
MAX = max(tmp, MAX);//stl自带的字典序比较，我直接觉得牛逼
MIN = min(tmp, MIN);
i += d;
}
ans = min(ans, dif(MAX, MIN));
}
void div2(string &s, int d)
{
int len = s.length();
int i = 0, MAX = -1, MIN = 10;
if (d == 1)return;
if (len - d < d - 1)return;
while (i < len)//必然只能是长度相差1的1xxxxxxxy和9999999z，出现其他数的话1xxx就可能不是最大，9999..不是最小
{
if (s[i] == '1')
{
if (i + d > len)return;
if (pre[i + d - 1] - pre[i + 1])return;
MAX = max(MAX, s[i + d - 1] - '0');
i += d;
}
else
{
if (i + d - 1 > len)return;
if (pre[i + d - 2] - pre[i] != (d - 2) * 9)
return;
MIN = min(MIN, s[i + d - 2] - '0');
i += d - 1;
}
}
//cout << MAX << " " << MIN << endl;
if (MAX == -1 || MIN == 10)return;
ans = min(ans, 10 - MIN + MAX);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
ans = 9;
cin >> s;
int len = s.length();
pre[0] = 0;
for (int i = 1; i <= len; i++)
pre[i] = pre[i - 1] + s[i - 1] - '0';
for (int i = 1; i <= len / 2 + 1; i++)
{
if (len % i == 0)
div1(s, i);
div2(s, i);
// cout << ans << endl;
}
printf("%d
", ans);
}
return 0;
}