A – 2023 (abc335 A)
题目大意
给定一个字符串,将最后一位改成4
。
解题思路
模拟即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
s.back() = '4';
cout
B – Tetrahedral Number (abc335 B)
题目大意
给定(n),按字典序输出非负整数(i,j,k),使得 (i+j+kleq n)
解题思路
(n)只有 (21),直接 (O(n^3))枚举判断即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i
C – Loong Tracking (abc335 C)
题目大意
二维网格,贪吃蛇,移动,进行(q)次操作,分两种
- 指定贪吃蛇下一步移动的方向
- 指定(i),输出贪吃蛇的第 (i)个部位的坐标。
解题思路
每移动一次,只有头部到了新的坐标,其他部分的坐标都变成前一个。
如果我们把每个部分的坐标按顺序放在一个队列里,队尾是头部坐标,队头是尾部坐标,每次移动相当于一次出队和一次入队。
但stl
的队列queue
不支持随机访问,因此用vector
模拟这个队列即可。
出队其实没有必要操作,不断push_back
即可。问第(i)个部位坐标就从队尾倒着数即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector> pos(n);
for (int i = 0; i > dir{
{'U', {0, 1}}, {'D', {0, -1}}, {'L', {-1, 0}}, {'R', {1, 0}}};
while (q--) {
int op;
cin >> op;
if (op == 1) {
string s;
cin >> s;
auto [x, y] = pos.back();
auto [dx, dy] = dir[s[0]];
x += dx;
y += dy;
pos.push_back({x, y});
} else if (op == 2) {
int s;
cin >> s;
auto [x, y] = *(pos.end() - s);
cout
D – Loong and Takahashi (abc335 D)
题目大意
给定一个(n times n)的二维网格,(n)奇数,给每个格子一个数字(in [1, n^2 – 1]),要求每个数字仅使用一次,且相邻数字的格子相邻,且正中间的格子不能是数字,而是T
。
给出一种构造方法。
解题思路
按照样例的构造方式,一个螺旋回字构造即可。
每次一个螺旋回字构造就填充最外围的一圈,起点依次为((1,1) to (2,2) to (3,3)) ,最后恰好到正中间,因此能恰好填满。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int mid = n / 2;
vector> tu(n, vector(n, 0));
int num = 1;
array, 4> dir{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
int cur = 0;
int x = 0, y = 0;
while (x != mid || y != mid) {
tu[x][y] = num;
auto [dx, dy] = dir[cur];
int nx = x + dx, ny = y + dy;
while (nx = n || ny = n || tu[nx][ny] != 0) {
cur = (cur + 1) % 4;
auto [dx, dy] = dir[cur];
nx = x + dx, ny = y + dy;
}
++num;
x = nx, y = ny;
}
for (int i = 0; i
E – Non-Decreasing Colorful Path (abc335 E)
题目大意
给定一张无向图,点有点权。
找一条从(1to n)的路径,其点权不递减,且不同的数的个数最多。不存在则输出(0)。
解题思路
注意到这个路径要求点权是一个不严格递增的情况,这明显存在一个决策的方向性,即点权大的一定从点权小的求得答案,当点权小的答案都求完了,那么该点权大的答案也求完了,即固定了,知晓了。
因此就直接设(dp[i])表示到达点 (i)时的最大的答案(不同的数的个数最多),按照点权从小到大转移,若点权相同则按照答案从大到小转移。用优先队列维护转移顺序即可。往后转移。初始条件为(dp[1] = 1)
也可以根据点权构造边权,注意到图如果有环,其边权一定都是(0),缩环后变成一张DAG(有向无环图),直接拓扑 (DP)即可,其实跟上面是一样的。
神奇的代码
#include
using namespace std;
using LL = long long;
const int inf = 1e9;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector a(n);
for (auto& i : a)
cin >> i;
vector>> edge(n);
auto add = [&](int u, int v) {
if (a[u] > u >> v;
--u, --v;
add(u, v);
add(v, u);
}
vector dis(n, inf);
dis[0] = -1;
priority_queue> q;
q.push({-a[0], -dis[0], 0});
while (!q.empty()) {
auto [_, d, u] = q.top();
q.pop();
if (dis[u] != -d)
continue;
for (auto [v, w] : edge[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({-a[v], -dis[v], v});
}
}
}
debug(dis);
cout
F – Hop Sugoroku (abc335 F)
题目大意
给定一个(n)个数的数组(a), 你在(0)处。当你在 (i)处时,你可以移动到 (j = i+a_i times k 处,(k)为正整数,也可以不移动。
问你可以移动到的位置的集合数量。
解题思路
注意到每次移动一定是往右边移动,具有明显的决策方向性,可以设(dp[i])表示移动到第 (i)个位置时,移动位置的集合数量(即这个集合中的最大值为 (i)的集合数量)。
转移式则为(dp[i] = sum_{j % a_j == i % a_j} dp[j]),初始条件为 (dp[0] = 1)。
上述(dp)的复杂度为 (O(n^2)),考虑如何优化转移。
但思考下会发现上述转移最坏情况就是 (O(n)),当 (a_j)全部为(1)时 ,就要对每个(j)都累加。但因为是对每个 (j)都累加,事实上我们可以预先处理出前缀和,这样就可以 (O(1))。
考虑这个前缀和的形式是怎样的,我们对(a_j)的值进行了枚举,假设为 (x),那满足转移条件的 (j) 则为(j % x == i % x = y),我们要把这些 (j)的 (dp[j])累加,即 (sum[x][y] = sum_{j % x == y} dp[j]) ,这样(dp[i] = sum_{x=1}^{max a}sum[x][i % x])。
但因为(max a)是 (2e5),和(n)同一个数量级,上述转移 复杂度还是(O(n^2))。
但注意到如果(a_j)比较大时,满足条件的(j) 的数量是很少的,这种情况下我们可以暴力转移,这个转移是往后转移,即当前为(i),则 (dp[j] += dp[i](j = i + a_i times k))。
这期间就有个分界点,我们设分界点为(mid = sqrt{n})
- 当(a_i > mid)时,我们暴力更新后面的(dp[j]),这样的(j)的数量(即 (k)的数量)不超过(frac{n}{sqrt{n}} = sqrt{n})个。更新的复杂度是(O(n sqrt{n}))
- 当(a_i leq mid)时,由于转移的数量 (j)很多,我们就先不转移,先保存在 (sum)数组里(可以看成是懒标记),即 (sum[a_i][i % a_i] += dp[i])。更新的复杂度是(O(1))
这样,对于后续的一个(i)的 (dp[i])的值,注意到原始转移式是(dp[i] = sum_{j % a_j == i % a_j} dp[j]),我们已经把情况一(即(a_j > mid))的(dp[j])累加进 (dp[i])里了,还剩下(a_j leq mid)的没累加进来,因此此时再 (dp[i] += sum_{j = 1}^{mid}sum[j][i % j])即可。更新的复杂度是(O(n sqrt{n}))
最终的时间复杂度是(O(nsqrt{n}))。
注意到上述转移里,我们把(j)和 (a_j)是割裂开了,考虑 (a_j)的所有取值情况,然后分成两类分别处理。
这其实也是一类经典的(dp)优化方法,即根号分治(dp),即存在两种形式的转移,且在不同数量级下时间复杂度各有优势,然后结合起来, (sqrt{n})是一个经典的分界点
神奇的代码
#include
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int half = sqrt(n);
vector> sum(half, vector(half, 0));
vector a(n);
for (auto& i : a)
cin >> i;
vector dp(n);
dp[0] = 1;
for (int i = 0; i = mo)
dp[i] -= mo;
}
if (a[i] >= half) {
for (int j = i + a[i]; j = mo)
dp[j] -= mo;
}
} else {
sum[a[i]][i % a[i]] += dp[i];
if (sum[a[i]][i % a[i]] >= mo)
sum[a[i]][i % a[i]] -= mo;
}
}
int ans = 0;
for (auto& i : dp) {
ans += i;
if (ans >= mo)
ans -= mo;
}
cout
G – Discrete Logarithm Problems (abc335 G)
题目大意
给定一个数组(a)和一个质数(P),求 ((i,j))的数量,满足以下条件
- 存在 (k),使得 (a_i ^ k equiv a_j (mod P))
解题思路
这题难在需要有数论知识。
首先因为有质数(P),会存在一个原根 (g),使得 (g^0 sim g^{P-2})的值恰好取遍了 (1 sim P-1) ,由费马小定理知(g^{P-1} equiv g^0 equiv 1(mod P))就回到了起点。上述的幂是对(P)取模的。
因此(a_i)可以找到个 (x),使得 (g^x equiv a_i (mod P)),对应的(a_j)则对应(y)。
除此之外,关于阶的概念:一个数的阶是一个最小的正整数(m),使得 (a_i ^ m equiv 1 (mod P)) ,其实就是循环节的长度,一般记为(ord(a_i))。
然后是一个简单但深刻的定理:
- 如果存在(k),使得(a_i^k equiv a_j(mod P)),则有 (ord(a_j) | ord(a_i))
如何通俗点理解呢?考虑阶的定义,(g^{xm} equiv 1 equiv g^0(mod P)),关心指数部分的话,即为 (xm equiv 0 (mod P-1)) ,即(xm = n(P-1))。
注意到(m)是最小的,怎么最小呢?我们要让 (xm)是 (P-1)的倍数,我们将 (x)和 (P-1)质因数分解, (x)缺少的那些质因数就是造成(x)不是 (P-1)的倍数的原因,这缺少的部分就由 (m)补上,那这个 (m)就是最小的了。注意这里的(m)就是一个数的阶(order)。它就是 (x)相对于 (P-1)缺少的那部分质因数,所以也必定是 (P-1)的因子
这里得到了另一个简单但也深刻的定理,也是最后求一个数的阶的理论依据:
- (ord(a_i) | P-1)
对于 (a_j)来说,就是 (ym^{prime}=kxm^{prime} = n^{prime}(P-1))。我们知道(xm)已经是 (P-1)的倍数了,那 (kxm)也必定是 (P-1)的倍数,但这里的(m)不一定是最小的,因为 (k)也带来了一些 (P-1)的质因数,因此 (m^prime)会比 (m)更小,它去掉了 (k)包括的 (P-1)的一些质因数,也即 (m^{prime} | m),即(ord(a_j) | ord(a_i))。
因此,如果我们求出了每个(a_i)的阶,剩下的就是求一个数的倍数有多少个。
如何快速求一个数的阶呢?注意到 (ord(a_i) | P-1),我们先假设其阶(m=P-1),此时必有 (a_i^{P-1} equiv 1(mod P)),但此时可能不是最小的,因为关于 (P-1)的质因数有多余的(跟上面的 (kxm)的 (m)不是最小的一个道理),我们要把多余的质因数去掉。
如何去除呢?其实只要枚举去除哪个质数,去除该质数的指数是多少即可。当去除的过多时,就不满足(a_i^{m} equiv 1(mod P)) ,但还能去除时,则还会满足该等式。所谓最小的(m),意味着任何一个更小的数,都不会满足该等式。
注意到 (P)只有 (1e13),质因数种类最多只有 (log P)个,每个质数的幂最大也只有 (log P) ,因此可以在(O(log^3 P))的复杂度内求出一个数的阶(还有一个(log)是快速幂)。
因此一开始先对(P-1)质因数分解,然后求出每个数的阶,此时显然不能(O(n^2))枚举阶,判断倍数关系。
注意到 (P-1)只有(10^{13}),最多只有 (12)个左右的质数,因此其因数个数最多只有 (2^12),是(d=O(10^3))的数量级,因为阶一定是(P-1)的倍数,虽然有 (O(n))个,但不同的阶的数量不超过 (O(d)),因此我们可以统计每个阶的数量,直接 (O(d^2))枚举每个阶的数量,判断倍数累加答案即可。
注意判阶数时的快速幂可能会爆long long
。
最终的时间复杂度是(O(nlog^3 P) + d^2(P-1)))
神奇的代码
#include
using namespace std;
using LL = long long;
long long qpower(__int128 a, __int128 b, long long mo) {
__int128 qwq = 1;
while (b) {
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
LL mo;
cin >> n >> mo;
LL phi = mo - 1, tmp = phi;
vector a(n);
for (auto& i : a)
cin >> i;
vector prime;
int half = sqrt(phi) + 1;
for (int i = 2; i cnt;
auto order = [&](LL x) {
LL m = phi;
for (auto& i : prime) {
while (m % i == 0 && qpower(x, m / i, mo) == 1) {
m /= i;
}
}
return m;
};
for (auto& i : a) {
cnt[order(i)]++;
}
LL ans = 0;
for (auto& i : cnt) {
for (auto& j : cnt) {
if (i.first % j.first == 0) {
ans += 1LL * i.second * j.second;
}
}
}
cout
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net