ABC 284
A - Sequence of Strings
题意：
有n个字符串\(s_1, s_2, s_3, ..., s_n\)，要求按\(n, n - 1, n - 2, ..., 1\)的顺序输出
样例：
输入
3
Takahashi
Aoki
Snuke
输出
Snuke
Aoki
Takahashi
水题，直接贴代码，过。
代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
int n;
string s[20];
int main(){
n = read();
for(int i = 1;i <= n; ++i){
cin >> s[i];
}
for(int i = n; i >= 1; --i){
cout << s[i] << endl;
}
return 0;
}
B - Multi Test Cases
题意：
有 t 组数据.
每组数据中有一个 n 和 一个数组\(a_1, a_2, a_3, ..., a_n\)
求对每组数据来说 a 数组中 共有几个奇数
样例：
输入
4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000
输出
2
1
5
0
水题再过
代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
int t, n ,v;
int main(){
t = read();
while(t--){
n = read();
int cnt = 0;
while(n--){
if(read() % 2 == 1)cnt++;
}
cout << cnt << endl;
}
return 0;
}
C - Count Connected Components
题意：
有 n 个点 1 ~ n， m 条边 1 ~ m，求图中共有多少个连接部分
样例：
输入
5 3
1 2
1 3
4 5
输出
2
分析：
直接贴并查集模板
代码：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
int p[10100];
void init(int x){
for (int i = 1; i <= x; i++)
p[i] = i;
}
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y){
int fx = find(x);
int fy = find(y);
if (fx != fy)
p[fx] = fy;
}
int cnt = 0;
int main() {
int n = read(), m = read();
init(n);
while (m--)
merge(read(), read());
for(int i = 1; i <= n; ++i) {
if (p[i] == i) cnt++;
}
cout << cnt;
}
D - Happy New Year 2023
题意：
有 t 组询问：
每组询问有一个 n ；
求 质数q , p， 使得 \(q ^ 2 \times p = n\)
输出 q, p
数据范围：
\(1 \leqslant t \leqslant 10\)
\(1 \leqslant q \leqslant 9 \times 10 ^ 8\)
样例：
输入
3
2023
63
1059872604593911
输出
17 7
3 7
104149 97711
分析：
这道题的关键并不是判质数， 而是找到一对p, q
因为题目保证有解，所以不必判断无解以及p, q不是质数
结合数据范围我们能得到， \(\min{q, p} \gtrapprox 2.1 \times 10 ^ 6\) ,所以令 \(maxn = 2.1 \times 10 ^ 6\)
而从 1 到 maxn 遍历一遍也不会超时
我们就for 2 ~ maxn 判断是否有值能成为 p 或 q,遇到输出即可
代码：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
int main(){
int t = read();
while(t--){
ll n = read();
int bj = 0;
for(ll i = 2; i <= 2100000; ++i){
if(n % i == 0 && (n / i) % i == 0){
print(1ll * i);
printf(" ");
print(1ll * (n / i / i));
puts(" ");
bj = 1;
break;
}
}
if(bj == 1) continue;
for(ll i = 2; i <= 2100000; ++i){
if(n % i == 0 && ((int)sqrt(n / i) == sqrt(n / i))){
print(1ll * (sqrt(n / i)));
printf(" ");
print(1ll * (1ll * i));
puts(" ");
break;
}
}
}
return 0;
}
E - Count Simple Paths
题意：
有 n 个点 1 ~ n， m 条边 1 ~ m，保证每个点的出度不超过10
令 k 为由点 1 出发的简单路径（不含重复节点）的数量
输出 \(\min({k, 10 ^ 6})\)
数据范围：
\(1 \leqslant n \leqslant 2 \times 10 ^ 5\)
\(0 \leqslant m \leqslant \min({2 \times 10 ^ 5, \tfrac{n(n - 1)}{2}})\)
所有数值均为int内
保证为简单图
分析：
直接链式前向星建图，dfs从1出发，统计经过的不重复的点数即可
代码：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
vector<ll> v[200005];
void addedge(int x, int y){
v[x].push_back(y);
}
bool vis[200005];
ll ans=0;
void dfs(int x){
vis[x]=1;
for(int i = 0; i < v[x].size(); ++i){
if(vis[v[x][i]] == 0) dfs(v[x][i]);
}
++ans;
vis[x] = 0;
if(ans == 1000000){
cout << ans;
exit(0);
}
return;
}
int main(){
int n = read(), m = read();
for(int i = 1; i <= m; ++i){
int u = read(), v = read();
addedge(u, v), addedge(v, u);;
}
dfs(1);
cout << ans;
return 0;
}
剩下的不会了
求大佬们点赞关注