5题半—-rk167
最接近cpgg的一次，可惜f少出了半道题，时间不够了
A
https://ac.nowcoder.com/acm/contest/75766/A
分类讨论字符相同还是不相同
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
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
char a,b;cin>>a>>b;
if(a==b){
cout<<2<<'\n';
cout<<a<<'\n';
cout<<a<<a<<'\n';
}else{
cout<<4<<'\n';
cout<<a<<'\n';
cout<<b<<'\n';
cout<<a<<b<<'\n';
cout<<b<<a<<'\n';
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
B
https://ac.nowcoder.com/acm/contest/75766/B
随便找一个排列内的数输出n+1或其他不在排列内的都可以
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
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
int n;cin>>n;
vector<int>v(n);
map<int,int>mp;
rep(i,0,n-1){cin>>v[i];mp[v[i]]=i+1;}
rep(i,1,n)
if(!mp[i]){
cout<<0<<'\n';
return;
}
cout<<1<<'\n';
rep(i,1,n){
if(mp[i])cout<<mp[i]<<' '<<n+1;
return;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
C
https://ac.nowcoder.com/acm/contest/75766/C
注意数据范围，别用stoi，会爆
很简单，从前到后贪心取字符串输出就好
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
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
string s;
cin>>s;
vector<string>v;
int i=0,j=0;
while(i<s.size()&&j<s.size()){
while((s[j]-'0')%2)j++;
string t=s.substr(i,j-i+1);
v.push_back(t);
i=j+1;
j++;
}
sort(v.begin(),v.end(),[&](string s,string t){
if(s.size()==t.size())return s<t;
else return s.size()<t.size();
}
);
for(auto &i:v){
cout<<i<<'\n';
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
D
https://ac.nowcoder.com/acm/contest/75766/D
分类讨论，出现两个以上种类肯定不行
出现两个一定是分成两段，不会出现三段，如样例二，模拟填充到两边就好
出现一种的话设这个数字为n就填n+1
0个随便填
出现两个或者一个填完要检查，因为可能按最优方法填完也没有答案，比如只出现一种但数组两端都不为0
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
int n;cin>>n;
vector<int>v(n+1);
map<int,int>mp;
int cnt=0;
rep(i,1,n){
cin>>v[i];
mp[v[i]]++;
}
cnt=mp[0ll];
mp.erase(0ll);
if(mp.size()>2){
cout<<-1;
return;
}
if(mp.size()==1){
if(cnt<1){
cout<<-1;
return;
}
int a=0;
for(auto i:mp)a=i.first;
if(v[1]!=0&&v[n]!=0){
cout<<-1 ;
return;
}
if(v[1]==0){
int i=1;
for(i=1;i<=n;i++){
if(v[i]==a)break;
if(v[i]==0ll)v[i]=a+1;
}
for(int j=i;j<=n;j++){
if(v[j]==0)v[j]=a;
}
}
else if(v[n]==0){
int i=n;
for(i=n;i>=1;i--){
if(v[i]==a)break;
if(v[i]==0ll)v[i]=a+1;
}
for(int j=i;j>=1;j--){
if(v[j]==0)v[j]=a;
}
}
int ans=0;
rep(i,2,n)ans+=abs(v[i]-v[i-1]);
if(ans!=1){
cout<<-1;
return;
}
}
if(mp.size()==2){
map<int,int>vis;
int i=1;
int pre=v[1];
while(v[i]==0ll||vis.size()<=1&&i<=n){
if(v[i]!=0ll)vis[v[i]]++;
if(vis.size()<=1&&v[i]!=0ll)pre=v[i];
if(vis.size()==2)break;
i++;
}
i--;
rep(j,1,i){
if(v[j]==0)v[j]=pre;
}
rep(j,i+1,n){
if(v[j]==0ll)v[j]=v[i+1];
}
int ans=0;
rep(i,2,n)ans+=abs(v[i]-v[i-1]);
if(ans!=1){
cout<<-1;
return;
}
}
if(mp.size()==0){
rep(i,1,n-1)cout<<1<<' ';
cout<<2;
return;
}
rep(i,1,n)cout<<v[i]<<' ';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
E
https://ac.nowcoder.com/acm/contest/75766/E
解法一：根据深度分类，枚举根节点为p还是d
解法二：两次树形dp（闲的无聊就试了一下树形dp是不是真的能做
注意如果全为？就为根节点先随便赋值填充答案就好
解法一：
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
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=1e5+10;
using namespace std;
vector<int>g[N];
bool eq=1;
string s;
int dep[N];
void dfs(int u,int fa){
if(fa==0)dep[u]=0;
else dep[u]=dep[fa]+1;
for(auto &v:g[u]){
if(v==fa)continue;
dfs(v,u);
}
}
void solve(){
int n;cin>>n;
cin>>s;
s=" "+s;
rep(i,1,n)if(s[i]!='?')eq=0;
rep(i,1,n-1){
int l,r;cin>>l>>r;
g[l].push_back(r);
g[r].push_back(l);
}
if(eq)s[1]='d';
dfs(1,0);
const string t="dp";
for(int k=0;k<=1;k++){
string ans(n+1,' ');
bool ok=1;
rep(i,1,n){
int x=(k^dep[i])%2;
if(s[i]!='?'&&t[x]!=s[i]){ok=0;break;}
ans[i]=t[x];
}
if(ok){rep(i,1,n)cout<<ans[i];return;}
}
cout<<-1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
解法二：
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=1e5+10;
using namespace std;
vector<int>g[N];
int dp[N][2];
bool eq=1;
string s;
void dfs(int u,int fa){
if(s[u]=='p')dp[u][0]=1;
if(s[u]=='d')dp[u][1]=1;
if(s[u]=='?')dp[u][0]=dp[u][1]=1;
for(auto &v:g[u]){
if(v==fa)continue;
dfs(v,u);
dp[v][1]=dp[u][0]=dp[v][1]*dp[u][0];
dp[v][0]=dp[u][1]=dp[v][0]*dp[u][1];
}
}
void dfs2(int u,int fa){
if(dp[u][0]==1){
for(auto &v:g[u]){
if(v==fa)continue;
dp[v][0]=0;
dfs2(v,u);
}
}
if(dp[u][1]==1){
for(auto &v:g[u]){
if(v==fa)continue;
dp[v][1]=0;
dfs2(v,u);
}
}
}
void solve(){
int n;cin>>n;
cin>>s;
s=" "+s;
rep(i,1,n)if(s[i]!='?')eq=0;
rep(i,1,n-1){
int l,r;cin>>l>>r;
g[l].push_back(r);
g[r].push_back(l);
}
dfs(1,0);
if(dp[1][0]==0&&dp[1][1]==0){
cout<<-1;
return;
}
if(eq)dp[1][0]=0;
dfs2(1,0);
rep(i,1,n){
if(dp[i][0]&&s[i]=='?')s[i]='p';
if(dp[i][1]&&s[i]=='?')s[i]='d';
}
rep(i,1,n)cout<<s[i];
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
F
https://ac.nowcoder.com/acm/contest/75766/F
构造题（吐吐吐吐
具体看代码画图理解
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
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
int n,m,x;cin>>n>>m>>x;
if(x==2){
cout<<-1;
return;
}
vector<vector<int>>v(n+1,vector<int>(m+1,0));
if(x%4==0){
int k=x/4;
v[1][1]=v[1][m]=v[n][1]=v[n][m]=k;
rep(i,1,n){
rep(j,1,m){
cout<<v[i][j]<<" \n"[j==m];
}
}
return;
}else{
int k=(x-6)/4;
v[1][1]=v[1][m]=v[n][1]=v[n][m]=k;
v[1][2]=v[1][3]=v[3][1]=v[2][1]=v[2][3]=v[3][2]=1;
rep(i,1,n){
rep(j,1,m){
cout<<v[i][j]<<" \n"[j==m];
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
