MinamiMelon
0%

2022牛客寒假算法基础集训营1题解

发表于

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod=998244353;
ll f[2][15];
int a[100005];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		a[i]%=9;
	}
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=9;++j){
			f[i&1][j]=(f[1-(i&1)][j]+f[1-(i&1)][(j-a[i]+9)%9])%mod;
		}
	}
	for(int i=1;i<=9;++i){
		printf("%d ",f[n&1][i]);
	}
	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
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
char s[N];
int ST[3][20][N];

int main(){
	int n,T;
	scanf("%d%d%s",&n,&T,s+1);
	for(int i=1;i<=n;++i){
		if(s[i]=='W'){
			ST[0][0][i]=1;
			ST[1][0][i]=1;
			ST[2][0][i]=1;
		}else if(s[i]=='L'){
			ST[0][0][i]=0;
			ST[1][0][i]=-1;
			ST[2][0][i]=-1;
		}
	}
	for(int i=1;i<20;++i){
		for(int j=1;j+(1<<i)-1<=n;++j){
			for(int k=0;k<3;++k){
				ST[k][i][j]=ST[k][i-1][j]+ST[(k+ST[k][i-1][j]+3)%3][i-1][j+(1<<i-1)];
			}
		}
	}
	while(T--){
		int l,r,s;
		scanf("%d%d%d",&l,&r,&s);
		int dd=r-l+1;
		for(int i=19;i>=0;--i){
			if((dd>>i)&1){
				s+=ST[s%3][i][l];
				l+=(1<<i);
			}
		}
		printf("%d\n",s);
	}	
	return 0;
}

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
#include<bits/stdc++.h>
using namespace std;

const int N=100+5;
int f[N];

int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a==1){
			f[i]=3;
		}else if(b==1){
			if(!f[i-1]){
				f[i]=2;
			}else if(f[i-1]==1){
				f[i]=1;
			}
		}else if(c){
			if(!f[i-1]&&!f[i-2]){
				f[i]=1;
			}
		}
		ans+=f[i];
	}
	printf("%d",ans);
	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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1e5,M=1e5; 
ll prime[M],cnt;
bool nisp[N];

void findp(ll n){
	for(ll i=2;i<=n;++i){
		if(!nisp[i]){
			prime[++cnt]=i;
		}
		for(ll j=1;j<=cnt&&i*prime[j]<=n;++j){
			nisp[i*prime[j]]=1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
}

bool isprime(ll n){
	int r=sqrt(n);
	for(int i=2;i<=r;++i){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

int main(){
	findp(1000);
	int T;
	scanf("%d",&T);
	while(T--){
		ll n;
		scanf("%lld",&n);
		if(n==1){
			puts("-1");
			continue;
		}
		ll ans=1;
		for(int i=1;i<=cnt;++i){
			if(ans*prime[i]>n){
				break;
			}
			ans*=prime[i];
		}
		printf("%lld ",ans);
		for(ll i=n;i>0;--i){
			if(isprime(i)){
				printf("%lld\n",i);
				break;
			}
		}
	}
	return 0;
}

E

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,m;
		scanf("%lld%lld",&n,&m);
		if(m==1){
			if(n==1){
				puts("1");
			}else
				puts("-1");
		}else{
			ll ans=n/(m-1)*2;
			if(n%(m-1)==1||n%(m-1)==0){
				--ans;
			}else{
				++ans;
			}
			printf("%lld\n",ans-(m==2?2:0));
		}
	}
	return 0;
}

F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m,t,cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i){
			scanf("%d",&t);
			if(t<m){
				++cnt;
			}
		}
		printf("%d\n",n-cnt*2>0?n-cnt*2:-1);
	}
	return 0;
}

G

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N];
typedef pair<int,int> pii;
vector<pii> v;


int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		int res=0;
		for(int i=2;i<=n-1;++i){
			if(a[i-1]==a[i]||a[i+1]==a[i]) continue;
			int l=0,r=2e9;
			if(a[i-1]>a[i]){
				r=min(r,(a[i-1]+a[i]-1)/2);
			}else{
				l=max(l,(a[i-1]+a[i])/2+1);
			}
			if(a[i+1]>a[i]){
				r=min(r,(a[i+1]+a[i]-1)/2);
			}else{
				l=max(l,(a[i+1]+a[i])/2+1);
			}
			if(l>r) continue;
			if(l==0){
				++res;
			}else{
				v.emplace_back(l,1);
			}
			if(r<2e9){
				v.emplace_back(r+1,-1);
			}
		}
		sort(v.begin(),v.end(),[](pii x,pii y){
			if(x.first==y.first){
				return x.second>y.second;
			}
			return x.first<y.first;
		});
		int t=res;
		for(auto x:v){
			t+=x.second;
			res=min(res,t);
		}
		printf("%d\n",res);
		v.clear();
	}
	return 0;
}

H

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define sz(x) (t[x].r-t[x].l+1)
#define mid(x) (t[x].l+t[x].r>>1)
struct Node{
	int l,r,c;
	ll v;
}t[10005];
inline void upd(int o){
    t[o].v=(t[L(o)].v+t[R(o)].v);
    t[o].c=(t[L(o)].c+t[R(o)].c);
}
void buildt(int o,int L,int R){
    t[o].l=L,t[o].r=R;
    if(L==R){
    	t[o].c=t[o].v=0;
        return;
    }
    int M=L+R>>1;
    buildt(L(o),L,M);
    buildt(R(o),M+1,R);
    upd(o);
}
void add(int o,int p,int v){
	if(p<=t[o].l&&t[o].r<=p){
		++t[o].c;
		t[o].v+=v;
		return;
	}
	int M=mid(o);
	if(p<=M){
		add(L(o),p,v);
	}else{
		add(R(o),p,v);
	}
	upd(o);
}
ll ask(int o,int L,int R){
	if(R<L){
		return 0;
	}
    if(L<=t[o].l&&t[o].r<=R){
        return t[o].v;
    }
    int M=mid(o);
    ll ret=0;
    if(L<=M)
        ret=(ret+ask(L(o),L,R));
    if(M<R)
        ret=(ret+ask(R(o),L,R));
    return ret;
}
int asc(int o,int L,int R){
	if(R<L){
		return 0;
	}
    if(L<=t[o].l&&t[o].r<=R){
        return t[o].c;
    }
    int M=mid(o);
    ll ret=0;
    if(L<=M)
        ret=(ret+asc(L(o),L,R));
    if(M<R)
        ret=(ret+asc(R(o),L,R));
    return ret;
}

int main(){
	buildt(1,0,1000);
	int n;
	scanf("%d",&n);
	int tt;
	ll ans=0;
	scanf("%d",&tt);
	ans+=abs(tt+tt-1000);
	add(1,tt,tt);
	for(int i=2;i<=n;++i){
		scanf("%d",&tt);
		ans+=abs(tt+tt-1000);
		ll nv=ask(1,0,1000-tt-1),nc=asc(1,0,1000-tt-1);
		ans+=nc*1000-nv-tt*nc;
		nv=ask(1,1000-tt,1000),nc=asc(1,1000-tt,1000);
		ans+=nv+nc*tt-nc*1000;
		add(1,tt,tt);
	}
	printf("%lld",ans);
	return 0;
}

I

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll M=1e9+7;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
	    x=1,y=0;return;
	}
	exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
}
ll inv(ll a,ll p){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}
ll qpow(ll a,ll p,ll mod){
    ll ans=1;
    a%=mod;
    while(p){
        if(p&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        p>>=1;
    }
    return ans%mod;
}


int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,m;
		scanf("%lld%lld",&n,&m);
		if(n==1){
			puts("0");
		}else{
			ll val=inv(2,M);
			printf("%lld\n",(1-qpow(val,n-1,M)+M)%M*m%M);
		}
	}
	return 0;
}

J

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
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int a[N],b[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=m;++i){
			scanf("%d",&b[i]);
		}
		if(n<(k+1)/2){
			puts("-1");
		}else{
			sort(a+1,a+n+1,greater<int>());
			sort(b+1,b+m+1,greater<int>());
			int pa=(k+1)/2+1,ans=0,pb=1,now=(k+1)/2;
			for(int i=1;i<pa;++i){
				ans+=a[i];
			}
			while(now<k){
				if(pa<=n&&pb<=m){
					if(a[pa]>b[pb]){
						ans+=a[pa++];
					}else{
						ans+=b[pb++];
					}
				}else if(pb<=m){
					ans+=b[pb++];
				}else{
					ans+=a[pa++];
				}
				++now;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

K

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
char s[N];
int f[N][3][3][3];

inline char get(int j,int k,int l)
{
	int green=(j==0)+(k==0)+(l==0),red=(j==1)+(k==1)+(l==1);
	if(green>red)return 'G';
	if(green<red)return 'R';
	return 'B';
}

int main(){
	int n;
	scanf("%d%s",&n,s+1);
	for(int i=0;i<=n;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				for(int l=0;l<=2;++l){
					f[i][j][k][l]=-1e9;
				}
			}
		}
	}
	for(int i=0;i<=2;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				if(get(i,j,k)==s[3]){
					f[3][i][j][k]=(i==0)+(j==0)+(k==0);
				}
			}
		}
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				for(int l=0;l<=2;++l){
					if(get(j,k,l)==s[i]){
						for(int t=0;t<=2;++t)
							f[i][j][k][l]=max(f[i][j][k][l],f[i-1][t][j][k]+(l==0));
					}
				}
			}
		}
	}
	int ans=-1;
	for(int i=0;i<=2;++i){
		for(int j=0;j<=2;++j){
			for(int k=0;k<=2;++k){
				if(get(i,j,k)==s[n]){
					ans=max(ans,f[n][i][j][k]);
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

L

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 namespace std;

const int N=1e5;
char s[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,x=0,y=0;
		double ans=0;
		scanf("%d%s",&n,s+1);
		for(int i=1;i<=n;++i){
			if(s[i]=='L'){
				x++;
			}else if(s[i]=='R'){
				x--;
			}else if(s[i]=='U'){
				y++;
			}else{
				y--;
			}
			ans=max(ans,sqrt(x*x+y*y));
		}
		printf("%.12lf\n",ans);
	}
	return 0;
}