zhangas

Pay more attention

0%

SDKD2023SummerTeamContest A

Veröffentlicht am Bearbeitet am

SDKD2023 Summer TeamContest A——NCC_17011

C - Cosmic Commute

题目链接
无向图从1到n存在m条light trains
m>=n-1 所以点1和n一定是联通的
存在k个wormhole 可以随机传送到另外k-1个位置 且at most once
求最少经过多少条light trains 可以到达点n
思路

• Compute dist(s, w) and dist(w, t) for each wormhole w and sum S using two BFS from s and t.
• Determine the wormhole you should enter to minimize the expected distance.
• If you enter wormhole w , the expected distance from s to t is
$$dist_w=dist(s,w)+\frac{1}{k-1}\sum dist(w_1,t)(w_1≠w)=dist(s,w)+\frac{1}{k-1}(S-dist(w_1,t))\with\quad S=\sum dist(w_1,t)$$

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
//bfs两次 求任一点到1和n的距离dist1数组和dist2数组
void bfs(int u,int dist[]){
	memset(st,0,sizeof(st));
	queue<int>q;
	q.push(u);
	dist[u]=0;
	st[u]=1;
	while(q.size()){
		int t=q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];//t->j
			if(dist[j]>dist[t]+1){
				dist[j]=dist[t]+1;
				if(!st[j]){
					q.push(j);
					st[j]=1;
				}
			}
		}
	}
}
signed main(){
	memset(dist1,0x3f,sizeof(dist1));
	bfs(1,dist1);
	memset(dist2,0x3f,sizeof(dist2));
	bfs(n,dist2);
	int sum=0;//计算S 所有wormhole点到n的距离之和
	for(int i=1;i<=k;i++){
		sum+=dist2[hole[i]];
		dist1[hole[i]]*=(k-1);
	}
	int mi=dist1[n]*(k-1);//不使用wormhole的最短距离
	for(int i=1;i<=k;i++){
		int t=sum-dist2[hole[i]]+dist1[hole[i]];
		mi=min(mi,t);
	}
	int t=gcd(mi,k-1);
	cout<<mi/t<<'/'<<(k-1)/t;
}

D - DnD Dice

题目链接
读了一遍题 dp？ 数学正态分布！
两个6面骰子的结果和出现次数
2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 5 4 3 2 1
一个4面骰子和一个6面骰子的结果和出现次数
2 3 4 5 6 7 8 9 10
1 2 3 4 5 4 3 2 1
观察可发现数字出现的次数成正态分布
需要注意分奇偶使用两个指针l r向前后移动输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[25];
signed main(){
	a[4]=read(),a[6]=read(),a[8]=read(),a[12]=read(),a[20]=read();
	int mi=a[4]+a[6]+a[8]+a[12]+a[20];
	int ma=a[4]*4+a[6]*6+a[8]*8+a[12]*12+a[20]*20;
	int mid=mi+ma>>1;
	if((ma+mi)%2==0){
		cout<<mid<<' ';
		for(int l=mid-1,r=mid+1;r<=ma&&l>=mi;l--,r++){
			cout<<r<<' '<<l<<' ';
		}
	}
	else{
		for(int l=mid,r=mid+1;r<=ma&&l>=mi;l--,r++){
			cout<<r<<' '<<l<<' ';
		}
	}
	return 0;
}

E - Eszett

题目链接
签到 ss转化为G输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
signed main(){
	string s;cin>>s;
	for(auto &i:s)i=tolower(i);
	cout<<s<<endl;
	for(int i=0;i<s.size()-1;i++){
		if(s[i]=='s'&&s[i+1]=='s'){
			string ans=s.substr(0,i);
			ans+='B';
			ans+=s.substr(i+2,s.size()-1);
			cout<<ans<<endl;
		}
	}
	return 0;
}

I - Investigating Frog Behaviour on Lily Pad Patterns

题目链接
set存储目前所以的空位 且最多最多移动到ma+q的位置上(最右端的青蛙连续跳q次)
借助upper_bound函数查找第一个大于x的数

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
int a[200005];
int mp[1000005];
set<int>st;
int ma;
signed main(){
	int n=read();
    for(int i=1;i<=n;i++){
		a[i]=read();
        mp[a[i]]=1;
        ma=max(ma,a[i]);
    }
    int q=read();
    for(int i=1;i<=ma+q;i++) {
        if(!mp[i])st.insert(i);
    }
    for(int i=0;i<q;i++){
        int tt=read();
        auto t=st.upper_bound(a[tt]);
        int b=*t;
        cout<<b<<endl;
        st.erase(t);//删掉空座t
        st.insert(a[tt]);//添加产生的新空座 注意该青蛙后面的frog可以到达这个位置
        a[tt]=b;//更新跳跃青蛙的位置
    }
}

G - German Conference for Public Counting

题目链接
每个数字都可以由0-9的卡牌组成
求从0-N需要多少张不同的卡牌
特判前两位大小情况 0一定是长度-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
33
int cnt[15];
bool check(char c,string s){
	for(auto &i:s){
		if(i<c)return false;
	}
	return true;
}
signed main(){
	int n=read();
	string a=to_string(n);
	if(n<10)cout<<n+1;
	else{
		int len=a.size();
		for(int i=1;i<a[0]-'0';i++){
			cnt[i]=len;
		}
		cnt[0]=len-1;
		if(a[0]<a[1]){
			cnt[a[0]-'0']=len;
		}
		else if(a[0]==a[1]){
			if(check(a[0],a))cnt[a[0]-'0']=len;
			else a[a[0]-'0']=len-1;
		}
		for(int i=0;i<=9;i++){
			if(!cnt[i])cnt[i]=len-1;
		}
		int ans=0;
		for(int i=0;i<=9;i++)ans+=cnt[i];
		cout<<ans;
	}
	return 0;
}

L - Loop Invariant

题目链接
首先给出balanced的定义->可以通过不断插入括号的操作获得的序列
特点是序列内的括号是一一对应存在的
将括号序列的前后连起来 求是否存在切割点满足切割后仍是balanced序列但不于前序列相同
思路: 先将序列分解成对应的子序列 再将序列复制前后联通 剪枝N^2暴力

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
string t[1000010];
signed main(){
	string s;cin>>s;
	int len=s.size();
	int l=0,r=0;
	int p=0;
	int cnt=0;
	for(int i=0;i<len;i++){
		if(s[i]=='(')l++;
		else r++;
		if(l==r&&l&&r){
			t[++cnt]=s.substr(p,i-p+1);
			p=i+1;
			l=0,r=0;
		}
	}
	int f=0;
	for(int i=cnt+1;i<=cnt*2-1;i++){
		t[i]=t[i-cnt];//复制一遍 在遍历的时候满足前后联通
	}
	for(int i=2;i<=cnt;i++){
		if(t[i]==t[i-1]&&t[i+cnt-1]==t[i+cnt-2])continue;
        //剪枝 如果移动后与移动前的前后端都不变 那么一定不满足
		string tt="";
		for(int j=i;j<i+cnt;j++){
			tt+=t[j];
		}
		if(tt!=s){
			cout<<tt;
			return 0;
		}
	}
	cout<<"no";
	return 0;
}

M - Mischievous Math

题目链接
给出数d(1<=d<=100)构造出a b c三个数(1<=a,b,c<=100)两两不同
且满足a，b，c通过加减乘除运算 且a,b,c至多用一次后一定不等于d

1
2
3
4
5
6
7
8
signed main(){
	int n=read();
	if(n>=10)cout<<"1 2 3";//显然1 2 3 怎么运算也不会超过9
	else if(n>2)cout<<"98 99 100";
	else if(n==2)cout<<"96 99 100";
	else if(n==1)cout<<"96 98 100";
	return 0;
}

Summary

1.首次参加SDKD夏季集训 体验到前3h小时读题 后2h写题的训练方式 遗憾的是没有到现场参加
2.有不少题赛后发现仔细理解题目后 还是可以完成的,看到没有人去开新题 就不敢自己去试试。
3.代码模板熟练情况，构造题的思维，还有边界条件的处理，复杂度的剪枝优化等，需要强化。