2022牛客暑期多校训练营1 个人题解

---

title :2022牛客暑期多校训练营1 题解
date : 2022-8-16
tags : ACM,练习记录
author : Linno

---

2022牛客暑期多校训练营1 题解

题目链接 ：https://ac.nowcoder.com/acm/contest/33186

补题进度 ：7/11

A - Villages: Landlines

签到题，记录做右端点，然后按左边排一下序，合并右端点能够到达的点，否则就再供一次电就行了。

#include 
#define int long long
using namespace std;
struct dat
{
	int p,d,l,r;
}a[1000005],b[1000005];
int l,r,n,p[1000005],d[1000005],cnt,ans;
bool cmp(dat a,dat b)
{
	if (a.l!=b.l) return a.l<b.l;
	else return a.r<b.r; 
}
signed main()
{
	cin>>n;
	//cin>>x>>r;
	for (int i=1;i<=n;++i) 
	 {
	 	scanf("%lld%lld",&p[i],&d[i]);
	 	a[i].p=p[i];
	 	a[i].d=d[i];
	 	a[i].l=p[i]-d[i];
	 	a[i].r=p[i]+d[i];
	 }
	sort(a+1,a+1+n,cmp);
	l=a[1].l; r=a[1].r;
	for (int i=2;i<=n;++i)
	 {
	 	if (a[i].l<=r) r=max(r,a[i].r);
		 else {
		 	b[++cnt].l=l;
		 	b[cnt].r=r;
		 	l=a[i].l; 
		 	r=a[i].r;
		 }
	 }
	b[++cnt].l=l;
	b[cnt].r=r;
	for (int i=2;i<=cnt;++i)
	  ans+=b[i].l-b[i-1].r;
	cout<<ans;
	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

B - Spirit Circle Observation

没补。

C - Grab the Seat!

范围很小，每次询问单独去求就行了。对于(0,1)和(0,m)到询问的点做两条线，斜率在这之间的点都会被覆盖掉，就可算出每一行可选位置的数量，然后求min得到最终一行可选座位数量。

#include
using namespace std;
const int N=2e5+7;
struct dat {
	long long x,y;
} a[N];
long long n,m,k,q,p,x,y,pos[N],ans;
double maxx,mini[N];

int main() {
	cin>>n>>m>>k>>q;
	for (int i=1; i<=k; ++i) {
		scanf("%lld%lld",&a[i].x,&a[i].y);
	}
	for (int i=1; i<=q; ++i) {
		scanf("%lld%lld%lld",&p,&x,&y);
		a[p].x=x;
		a[p].y=y;
		for (int j=1; j<=m; ++j)
			pos[j]=n+1,mini[j]=n+1;

		for (int j=1; j<=k; ++j)
			pos[a[j].y]=min(pos[a[j].y],a[j].x);
		ans=0;
		maxx=0;
		for (int j=2; j<=m; ++j) {
			if (pos[j]!=n+1) {
				maxx=max(maxx,(double)(j-1.0)*1.0/pos[j]);
			}
			mini[j]=min(mini[j],(double)(j-1.0)*1.0/maxx);
		}
		mini[m]=min(mini[m],pos[m]*1.0);
		maxx=0;
		for (int j=m-1; j>=1; j--) {
			if (pos[j]!=n+1) {
				maxx=max(maxx,abs((double)(j-m)*1.0/pos[j]/1.0));
			}
			mini[j]=min(mini[j],(double)(j-m)*1.0/(-maxx*1.0));
		}
		mini[1]=min(mini[1],pos[1]*1.0);
		for (int j=1; j<=m; ++j) {
			long long f=floor(mini[j]);
			if (mini[j]-f<1e-8) ans+=f-1;
			else ans+=f;
		}
		printf("%lld\n",ans);
	}
	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

D - Mocha and Railgun

直观感觉就是沿原点连线，然后直接射出去的投影是弧长最大的，不会严格证，但这是最好想的切入口。

#include 
#include 
#include 
#include 
#include 
using namespace std;
double R,x,y,r,d,maxi,mini,dl,len,a,ans; 
int T;
int main()
{
    cin>>T;
    while (T--)
    {
        scanf("%lf",&R);
        scanf("%lf%lf%lf",&x,&y,&r);
        d=sqrt(x*x+y*y);
        maxi=sqrt(R*R-(d-r)*(d-r));
        mini=sqrt(R*R-(d+r)*(d+r));
        dl=maxi-mini;
        len=sqrt(dl*dl+2*r*2*r);
        a=asin(len/2.0/R);
        ans=2*a*R;
        printf("%.10lf\n",ans);
    }
    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

E - LTCS

待补。

F - Cut

待补。

G - Lexicographical Maximum

签到题，只要看字符串里有没有9即可。

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
string str;

void Solve(){
	cin>>str;
	int len=str.length(),flag=1;
	for(int i=0;i<len-1;++i){
		if(str[i]!='9') flag=0;
	}
	if(flag) cout<<str<<"\n";
	else{
		for(int i=0;i<len-1;++i) cout<<9;
		cout<<"\n";
	}
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	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

H - Fly

可以转化为背包问题，然后用NTT优化。

#include 
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e5+5e4;
const int G=3,Gi=332748118;
const int lim=40001;

int fpow(int a,int b=mod-2){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

int a[N],A[N],F[N],g[N];
int n,m,K,cnt[N],r[N<<1];
vector<int>had[62];
int vis[N], tag;

inline int get(int x){
	int len=1;
	while (len<=x) len<<=1;
	return len;
}

void NTT(int *A, int len, int tag){
	for(int i=1;i<=len;i++) r[i]=(r[i>>1]>>1)|((i&1)?(len>>1):0);
	for(int i=0;i<len;i++){
		if (i<r[i])	swap(A[i],A[r[i]]);
	}
	for(int mid=1;mid<len;mid<<=1){
		int wn=fpow(tag?G:Gi,(mod-1)/(mid<<1));
		for(int j=0;j<len;j+=(mid<<1)){
			for (int k=0,w=1;k<mid;k++,w=w*wn%mod){
				int x=A[j+k],y=w*A[j+k+mid]%mod;
				A[j+k]=(x+y)%mod;
				A[j+k+mid]=(x+mod-y)%mod;
			}
		}
	}
	if(tag) return;
	int invlen=fpow(len);
	for(int i=0;i<len;i++) A[i]=A[i]*invlen%mod;
}

signed main() {
	scanf("%d%lld%lld",&n,&m,&K);
	a[0]=1;
	++cnt[1];
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),++cnt[a[i]];
	for (int i=1,x,y;i<=K;i++){
		scanf("%d%d",&x,&y);
		had[y].push_back(x);
	}
	int len=get(lim);
	int w=fpow(3,(mod-1)/len);
	A[0]=1;
	for(int i=1;i<len;i++) A[i]=A[i-1]*w%mod;
	for(int i=0;i<len;i++) F[i]=1;
	for(int i=0;i<=lim;i++){
		if(cnt[i]){
			for (int j=0;j<len;j++){
				F[j]=F[j]*fpow((A[(j*i)&(len-1)]+1)%mod,cnt[i])%mod;
			}
		}
	}
	NTT(F,len,0);
	len=get(2*lim);
	memset(A,0,sizeof(A));
	A[0]=1;
	for(int i=0;(i<=60)&&m;i++){
		memcpy(g,F,sizeof(F));
		++tag;
		for(auto x:had[i]){
			if(vis[x]!=tag){
				vis[x]=tag;
				for(int j=a[x];j<=lim;j++){
					g[j]=(g[j]+mod-g[j-a[x]])%mod;
				}
			}
		}
		NTT(A,len,1);
		NTT(g,len,1);
		for (int j=0;j<len;j++) g[j]=g[j]*A[j]%mod;
		NTT(g,len,0);
		memset(A,0,sizeof(A));
		for(int j=m%2;j<=2*lim;j+=2) A[j>>1]=g[j];
		m>>=1;
	}
	printf("%d", A[0]);
	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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

I - Chiitoitsu

只需要考虑凑原来手牌里单个的牌，然后$dp[i][j]$表示表示牌库剩i张牌时凑齐j对时的概率，算出每轮摸到单的概率和摸到废牌的概率就可以了，不需要过多的策略。

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int dp[205][10];
string str;

inline int fpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

void Solve(){
	cin>>str;
	set<int>cnt;
	for(int i=0;i<str.length();i+=2){
		int hs=str[i]*131+str[i+1];
		cnt.insert(hs);
	}
	int x=cnt.size(),y=13-x;
	cout<<dp[13][y]<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	for(int i=136;i>=13;--i){
		for(int j=0;j<=6;++j){
			int lft=13-2*j;
			int p1=3*lft*fpow(136-i,mod-2)%mod;
			int p2=(1-p1+mod)%mod;
			dp[i][j]=(dp[i+1][j+1]*p1+dp[i+1][j]*p2+1)%mod;
		}
	}
	int T=1;
	cin>>T;
//	clock_t start,finish;
//	start=clock();
	for(int i=1;i<=T;++i){
		cout<<"Case #"<<i<<": ";
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	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

J - Serval and Essay

如果一个点y只能被另一个点x推断出来，那么显然可以合并，并且x继承所有y能推断的点，那么我们就不需要考虑y了，模拟这个过程去反复合并即可。

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
//#define int long long
#define pii pair<int,int>
#define mk make_pair
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

set<int>to[N],from[N];
int n,fa[N],sz[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
} 

void Merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y) return;
	if(to[x].size()<to[y].size()) swap(x,y);
	fa[y]=x;
	sz[x]+=sz[y];
	vector<pii> mg;
	for(auto t:to[y]){
		to[x].insert(t);
		from[t].erase(y);
		from[t].insert(x);
		if(from[t].size()==1) mg.emplace_back(mk(t,x));
	}
	for(auto p:mg){
		Merge(p.first,p.second);
	}
}

void Solve(){
	n=read();
	for(int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
	for(int i=1;i<=n;++i){
		int k=read();
		for(int j=1,y;j<=k;++j){
			y=read();
			to[y].insert(i);
			from[i].insert(y);
		}
	}
	for(int i=1;i<=n;++i){
		if(from[i].size()==1){
			Merge(*from[i].begin(),i);
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans=max(ans,sz[i]);
	printf("%d\n",ans);
	for(int i=1;i<=n;++i) to[i].clear(),from[i].clear();
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
	T=read();
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	for(int i=1;i<=T;++i){
		printf("Case #%d: ",i);
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	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
78
79
80

K - Villages: Landcircles

没补。