F 之后补吧。
A 小红的 red
思路：
模拟
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void solve()
{
string s;
cin>>s;
map<char,int>mp;
mp['r']++;
mp['e']++;
mp['d']++;
for(int i=0;i<s.size();i++){
if(mp[s[i]]==0){
cout<<"No"<<endl;
return;
}
}
cout<<"Yes"<<endl;
}
|
B 小红的矩阵构造
思路：
显然当矩阵只有一行或者一列时才可构造。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void solve()
{
int n,m;
cin>>n>>m;
if(n==1&&m>=2){
cout<<"0";
for(int i=1;i<m;i++){
cout<<"1";
}
return;
}else if(n>=2&&m==1){
cout<<"0";
for(int i=1;i<n;i++){
cout<<"1"<<endl;
}
return;
}
cout<<"-1";
}
|
C 小红的数据结构
思路：
模拟一下就好了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| const int N=2e5+5;
int a[N];
void solve()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<PII> op(q);
for(int i=0;i<q;i++){
int m;
cin>>m;
if(m==1){
int x;
cin>>x;
op[i]={m,x};
}else{
op[i]={2,0};
}
}
stack<int> st;
queue<int> que;
bool flag1=1;
int idx=1;
for(auto o:op){
if(o.first==1){
st.push(o.second);
}else{
if(st.top()!=a[idx]){
flag1=0;
break;
}else{
st.pop();
idx++;
}
}
}
idx=1;
bool flag2=1;
for(auto o:op){
if(o.first==1){
que.push(o.second);
}else{
if(que.front()!=a[idx]){
flag2=0;
break;
}else{
que.pop();
idx++;
}
}
}
if(flag1&&flag2){
cout<<"both"<<endl;
}else if(flag1){
cout<<"stack\n";
}else if(flag2){
cout<<"queue\n";
}else{
cout<<"-1";
}
}
|
D 小红的部分相同字符串
思路：
并查集+快速幂
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| const int N=2e5+5;
const int MOD=998244353;
int a[N];
int f[N];
void init(){
for(int i=0;i<=N;i++)f[i]=i;
}
int find(int x){
if(f[x]!=x)f[x]=find(f[x]);
return f[x];
}
void merge(int a,int b){
int aa=find(a);
int bb=find(b);
if(a>b){
f[aa]=bb;
}else{
f[bb]=aa;
}
}
int qmi(int a,int b){
int ans=1;
while(b){
if(b&1){
ans=ans*a%MOD;
}
a=a*a%MOD;
b>>=1;
}
return ans;
}
void solve()
{
int n,k;
cin>>n>>k;
for(int i=0;i<k;i++){
int u,v;
cin>>u>>v;
merge(u,v);
}
int cnt=0;
for(int i=1;i<=n;i++){
if(find(i)==i)cnt++;
}
cout<<qmi(26,cnt);
}
|
E 小红的树权值
思路：
dfs 贪心。遍历子节点，如果没有被删那就删自己。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=1e5+5;
int st[N];
vector<int> g[N];
int a[N];
int dfs(int u,int f){
st[u]=0;
int cnt=0;
for(int v:g[u]){
if(v==f)continue;
cnt+=dfs(v,u);
}
for(int v:g[u]){
if(v==f)continue;
if(!st[v]){
st[u]=1;
}
}
a[u]=cnt+st[u];
return a[u];
}
void solve()
{
int n;
cin>>n;
memset(g,0,sizeof g);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
signed main(){
IOS
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
|
