A
找到一个可能的就是YES，否则NO
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
| #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;
string s,t,x;cin>>s>>t>>x;
bool fg=1;
for(int i=0;i<n;i++)
{
if(x[i]!=s[i]&&x[i]!=t[i])fg=0;
}
if(!fg)cout<<"YES\n";
else cout<<"NO\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
return 0;
}
|
B
组合数
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
| #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=3e5+10;
using namespace std;
void solve(){
i64 n;cin>>n;
vector<i64>v(n+1);
vector<i64>cnt(n+1);
for(int i=1;i<=n;i++){cin>>v[i];cnt[v[i]]++;}
if(n<=2)
{
cout<<0<<'\n';
return;
}
i64 pre=0,ans=0;
for(int i=0;i<=n;i++){
if(cnt[i]>=2){
ans+=cnt[i]*(cnt[i]-1)/2*pre;
}
if(cnt[i]>=3){
ans+=cnt[i]*(cnt[i]-1)*(cnt[i]-2)/6;
}
pre+=cnt[i];
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
return 0;
}
|
C
https://codeforces.com/contest/1922/problem/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
| #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=1e4+10;
using namespace std;
void solve(){
int n;cin>>n;
vector<i64>v(n+1);
vector<i64>pre(n+1);
vector<i64>pre1(n+1);
for(int i=1;i<=n;i++)cin>>v[i];
if(n>=2)pre[2]=1;
for(int i=2;i<n;i++){
if(v[i+1]-v[i]<v[i]-v[i-1])pre[i+1]=pre[i]+1;
else pre[i+1]=pre[i]+v[i+1]-v[i];
}
if(n>=2)pre1[n-1]=1;
for(int i=n-1;i>1;i--){
if(v[i]-v[i-1]<v[i+1]-v[i])pre1[i-1]=pre1[i]+1;
else pre1[i-1]=pre1[i]+v[i]-v[i-1];
}
int m;cin>>m;
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
if(x<y)cout<<pre[y]-pre[x]<<'\n';
else cout<<pre1[y]-pre1[x]<<'\n';
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
return 0;
}
|
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #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(){
i64 n;cin>>n;
vector<int>a(n+2),l(n+1),r(n+1);
vector<int>b(n+2);
vector<int>v;
rep(i,0,n-1){
cin>>a[i];
v.push_back(i);
}
rep(i,0,n-1)cin>>b[i];
for(int i=0;i<n;i++){
l[i]=i-1;
r[i]=i+1;
}
r[n-1]=-1;
a[n]=0;
vector<int>vis(n+1,-1);
for(int k=0;k<n;k++){
vector<int>die;
for(auto &i:v){
int sum=0;
if(l[i]!=-1){
sum+=a[l[i]];
}
if(r[i]!=-1){
sum+=a[r[i]];
}
if(sum>b[i])die.emplace_back(i);
}
v.clear();
for(auto &i:die)vis[i]=k;
cout<<die.size()<<" \n"[k==n-1];
for(auto &i:die){
if(l[i]!=-1){
r[l[i]]=r[i];
if(vis[l[i]]<k){
v.emplace_back(l[i]);
vis[l[i]]=k;
}
}
if(r[i]!=-1){
l[r[i]]=l[i];
if(vis[r[i]]<k){
v.emplace_back(r[i]);
vis[r[i]]=k;
}
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
return 0;
}
|
E
经典cf构造，我的想法就是在一个上升的序列里面插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
| #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(){
i64 x;cin>>x;
deque<i64>v;
int k=200;
while(x>1){
if(x%2){
x--;
v.push_front(0);
}else{
v.push_front(k--);
x/=2;
}
}
cout<<v.size()<<'\n';
for(auto &i:v)cout<<i<<' ';
cout<<'\n';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
return 0;
}
|
