ABC445 ABCEF题解
2026-02-14 22:02:42
发布于：广东
41阅读
0回复
0点赞
怎么快速幂都能写挂啊我去。怎么数组都能开小啊我去。怎么求最大值写成求最小值啊我去。求不饭堂教程。
A
Difficulty：3- / Easy
Tag：-
没了。
namespace cjdst{
void solve(){
std::string s;
std::cin >> s;
std::cout << (s.front() == s.back() ? "Yes\n" : "No\n");
}
}
时间复杂度：。
B
Difficulty：3- / Easy
Tag：-
有了。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <std::string> a(n + 5);
int mx = 0;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
mx = std::max(mx, int(a[i].size()));
}
for(int i = 1; i <= n; i++){
for(int j = 1; j * 2 + a[i].size() <= mx; j++) std::cout << '.';
std::cout << a[i];
for(int j = 1; j * 2 + a[i].size() <= mx; j++) std::cout << '.';
std::cout << '\n';
}
}
}
时间复杂度：。
C
Difficulty：3- / Easy
Tag：拓扑排序
注意到 。题目让我们求的就是最终去哪个自环，而去掉自环后就变成 DAG 了，终点就是答案。所以拓扑排序即可。
不要傻傻写队列了，注意到从 是一个正确的拓扑序。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::vector <int> ans(n + 5);
for(int i = n; i; i--){
if(a[i] == i) ans[i] = i;
else ans[i] = ans[a[i]];
}
for(int i = 1; i <= n; i++){
std::cout << ans[i] << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
E
Difficulty：3.9 / Easy+
Tag：分解质因子
首先分解质因子
然后 LCM 就是所有数每个质因子最多个数次幂的乘积
然后维护最多个数和次多个数就行了
次多维护来干什么（）
去掉一个数可能删除了原来出现的最多次数，所以这时得用次多
// 卡常换码风
#include <bits/stdc++.h>
typedef std::pair <int, int> pii;
typedef long long ll;
const int N = 200000, M = 10000000;
const ll mod = 998244353;
bool vis[M + 5];
int frac[M + 5];
int a[N + 5];
std::vector <pii> v[N + 5];
int mx1[M + 5], mx2[M + 5];
std::vector <int> v2;
ll ksm(ll x, ll y){
y %= (mod - 1);
ll ans = 1;
while(y){
if(y & 1) ans = ans * x % mod;
x = x * x % mod, y >>= 1;
}
return ans;
}
void solve(){
int n;
std::cin >> n;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
for(int i = 1; i <= n; i++){
int cur = -1, ct = 0;
while(a[i] != 1){
if(cur != frac[a[i]]){
if(cur != -1){
v[i].push_back({cur, ct});
if(!mx1[cur]) v2.push_back(cur);
if(mx1[cur] < ct){
mx2[cur] = mx1[cur], mx1[cur] = ct;
}else if(mx2[cur] < ct) mx2[cur] = ct;
}
cur = frac[a[i]], ct = 1;
}else ct++;
a[i] /= frac[a[i]];
}
if(cur != -1){
v[i].push_back({cur, ct});
if(!mx1[cur]) v2.push_back(cur);
if(mx1[cur] < ct){
mx2[cur] = mx1[cur], mx1[cur] = ct;
}else if(mx2[cur] < ct) mx2[cur] = ct;
}
}
ll ans = 1;
for(int i:v2){
ans = ans * ksm(i, mx1[i]) % mod;
}
for(int i = 1; i <= n; i++){
ll tmp = ans;
for(auto j:v[i]){
if(j.second == mx1[j.first]){
tmp = tmp * ksm(j.first, (mod - 2) * (j.second - mx2[j.first])) % mod;
}
}
std::cout << tmp << ' ';
}
std::cout << '\n';
for(int i:v2){
mx1[i] = mx2[i] = 0;
}
for(int i = 1; i <= n; i++){
v[i].clear();
}
v2.clear();
}
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
vis[0] = vis[1] = 1;
for(int i = 2; i <= M; i++){
if(vis[i]) continue;
for(int j = i; j <= M; j += i){
vis[j] = 1;
if(!frac[j]) frac[j] = i;
}
}
int T;
std::cin >> T;
while(T--) solve();
}
时间复杂度 。
F
Difficulty：3.9 / Easy
Tag：Floyd
Floyd 瞎搞即可。
由于 Floyd 实现与矩阵乘法很像，所以就封装到 matrix 类了。
namespace cjdst{
class matrix{
public:
std::vector <std::vector <ll>> a;
int siz;
matrix(int n){
siz = n;
a.resize(siz + 5, std::vector <ll>(siz + 5, 0x3f3f3f3f3f3f3f3fll));
}
matrix(int n, std::vector <std::vector <ll>> v){
siz = n;
a = v;
}
matrix operator * (matrix b){
matrix ans(siz);
for(int k = 1; k <= siz; k++){
for(int i = 1; i <= siz; i++){
for(int j = 1; j <= siz; j++){
ans.a[i][j] = std::min(ans.a[i][j], a[i][k] + b.a[k][j]);
}
}
}
return ans;
}
};
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <std::vector <ll>> a(n + 5, std::vector <ll>(n + 5));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
std::cin >> a[i][j];
}
}
matrix x(n, a), ans(n, a);
m--;
while(m){
if(m & 1) ans = ans * x;
x = x * x, m >>= 1;
}
for(int i = 1; i <= n; i++){
std::cout << ans.a[i][i] << '\n';
}
}
}
时间复杂度：。
有帮助，赞一个