第四届“灵犀杯”算法设计大赛非官方题解

不会C++的noah

2024-12-16 15:07:00

发布于：浙江

85阅读

0回复

0点赞

求官方看看#创作计划#（之所以不在标题写是因为字数不够了）

T1.亚冬会志愿者选拔
小模拟，稍微模拟一下就行了(代码1star,题意0star)
code:

#include<bits/stdc++.h>
using namespace std;
struct node{
	int id,s;
}a[5000];
int n,m,cnt[111];
bool cmp(node a,node b){
	if (a.s==b.s){
		return a.id<b.id;
	}
	return a.s>b.s;
}
int main(){
	cin>>n>>m;
	m=floor(m*1.5);
	for (int i=1;i<=n;++i){
		cin>>a[i].id>>a[i].s;
		cnt[a[i].s]+=1;
	}
	sort(a+1,a+1+n,cmp);
	int g=-1,num=0;
	for (int i=100;i>=0;--i){
		if (m>cnt[i]){
			m-=cnt[i];
			num+=cnt[i];
		}else{
			g=i;
			num+=cnt[i];
			break;
		}
	}
	cout<<g<<" "<<num<<endl;
	for (int i=1;i<=num;++i){
		cout<<a[i].id<<" "<<a[i].s<<endl;
	}
	
	return 0;
}

T2.简单的数学
根据题目筛出质数即可(带一点读题困难,代码1star,题意2star))

code:

#include <bits/stdc++.h>
using namespace std;
int b[111];
vector<int> a;
bool isp(int n){
	if (n<=1){
		return 0;
	}else if (n==2){
		return 1;
	}else{
		for (int i=2;i*i<=n;++i){
			if (n%i==0){
				return 0;
			}
		}
		return 1;
	}
}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;++i){
    	cin>>b[i];
	}
	int ans=0;
	for (int i=1;i<=m;++i){
		int x;
		cin>>x;
		a.push_back(b[x]); 
	}
	for (int i=0;i<a.size();++i){
		if (isp(a[i])){
			ans+=a[i];
		}
	}
	cout<<ans<<endl;
    return 0;
}

T3.苹果和虫子
使用ceil或者(y+x-1)/x求出除掉的苹果就行了（记得与0取max!）
(代码2star,题意0star)
code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,x,y;
    cin>>n>>x>>y;
    cout<<max(n-(y+x-1)/x,0)<<endl;
    return 0;
}

T4.规范操作
这道题对于熟练STL-vector的就很简单（不会的自行学习）
(代码3star,题意1star)
code:

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
int main(){
	int m;
    cin>>n>>m;
    for (int i=1;i<=n;++i){
    	int x;
    	cin>>x;
    	a.push_back(x);
	}
	while (m--){
		int A,b;
		cin>>A>>b;
		int p=0;
		for (int i=0;i<a.size();++i){
			if (a[i]==A){
				p=i;
				break;
			}
		}
		a.insert(a.begin()+p+1,b);
	}
	for (int i=0;i<a.size();++i){
		cout<<a[i]<<" ";
	}
	cout<<endl;
    return 0;
}

T5. 神秘镜像
仅次于T11的思考题
由于s是经过k次镜像得的
可证当 $1 \le k$ 时， $s_i=s_{n-i-1}(1 \le i \le n)$ (其实就是回文串)
证明：
设：
$s=s_1s_2s_3……s_n$
则
当第一次镜像在右侧时：
$s=s_1s_2s_3……s_ns_ns_{n-1}s_{n-2}s_{n-3}……s_1$
可证满足 $s_i=s_{n-i-1}(1 \le i \le n)$
当第一次镜像在左侧时：
$s=s_1s_2s_3……s_ns_ns_{n-1}s_{n-2}s_{n-3}……s_1$
可证满足 $s_i=s_{n-i-1}(1 \le i \le n)$
由此可证当 $1 \le k$ 时， $s_i=s_{n-i-1}(1 \le i \le n)$
$Q.E.D$
所以，根据这个规律，就可以轻松的写出代码（由上思路）(code3star,题意4star)
code:

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin>>s;
    int n=s.size();
    while (n%2==0){
    	bool f=0;
    	for (int i=0;i<n/2;++i){
    		if (s[i]!=s[n-i-1]){
    			f=1;
    			break;
			}
		}
		map<char,int> ma;
		for (int i=0;i<n/2;++i){
			//cout<<s[i]<<endl;
			ma[s[i]]+=1;
		}
		for (int i=n/2+1;i<n;++i){
			//cout<<s[i]<<endl;
			if (!ma[s[i]]){
				f=1;
				break;
			}
		}
		if (f){
			break;
		}
        n/=2;
	}
	cout<<n<<endl;
    return 0;
}

T6.均衡序列
简单，不做解释（代码1star,题意1star）
code:

#include <bits/stdc++.h>
using namespace std;
int n,a[3333],d[3333];
int main(){
    cin>>n;
    for (int i=1;i<=n;++i){
    	cin>>a[i];
	}
	for (int i=1;i<n;++i){
		d[i]=abs(a[i+1]-a[i]);
	}
	sort(d+1,d+n);
	for (int i=1;i<n;++i){
		if (d[i]!=i){
			cout<<"Not jolly"<<endl;
			return 0;
		}
	}
	cout<<"Jolly"<<endl;
    return 0;
}

T7.不用再算了
看正解是 $O(n\sqrt{}n)$ 的，为社么我试了会T啊
于是某人默默写了一个线性筛并成了赛时最优解
code(题意1star,代码2~3star)

#include <bits/stdc++.h>
using namespace std;
bool ret[100000010];
vector<int> p;
void ei(int n){
    for (int i=2;i<=n;++i){
        if (!ret[i]){
            p.push_back(i);
        }
        for (int j=0;j<p.size();++j){
            if (p[j]*i>n){
                break;
            }
            ret[p[j]*i]=1;
            if (i%p[j]==0){
                break;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    ei(n);
    int ans=0;
    for (int i=2;i<=n;++i){
        if (!ret[i]){
        	//cout<<i<<endl;
        	ans+=1;
		}
    }
    cout<<ans<<endl;
    return 0;
}

T8.好串
签到题promax,不做解释
code(代码1star,题意0star)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while (t--){
    	map<char,int> ma,ma1;
    	int n;
    	cin>>n;
    	string s,t;
    	cin>>s>>t;
    	for (int i=0;i<n;++i){
    		ma[s[i]]=0;ma[t[i]]=0;
    		ma1[s[i]]=0;ma1[t[i]]=0;
		}
		for (int i=0;i<n;++i){
			ma[s[i]]+=1;ma1[t[i]]+=1;
		}
		bool f=0;
		for (int i=0;i<n;++i){
			if (ma[s[i]]!=ma1[s[i]]){
				cout<<"NO"<<endl;
				f=1;
				break;
			}
		}
		if (!f){
			cout<<"YES"<<endl;
		}
	}
    return 0;
}

T9.新年贺礼
~~不是你把签到题放T9你有什么意思~~
过于简单，代码请自行完成

T10.健康饮食
我赌这题肯定有认为要正好摄入那么多然后dfs的人
其实这题就是for+if就没了
（题意2~4star,代码1/4star）
code:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[111],cai[111][111];
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;++i){
		cin>>a[i];
	}
	for (int i=1;i<=n;++i){
		for (int j=1;j<=m;++j){
			cin>>cai[i][j];
			a[j]-=cai[i][j];
		}
	}
	for (int i=1;i<=m;++i){
		if (a[i]>0){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
    return 0;
}

T11.欢乐数组

有点难度的思维题

考虑贪心,设 $b_i=a_i+/-1(1 \le i \le n-1)$ ,将偏差直接算在 $b_n$ 上（也就是 $b_n=(\sum_1^na_i)-(\sum_1^{n-1}|a_i-b_i|)$ ）
最后判断一下b就行了
(代码2star,题意4star)
code:

#include <bits/stdc++.h>
using namespace std;
int a[1111],n;
string f(int a[]) {
    long long sum=0;
    for (int i=1;i<=n;++i){
        sum+=a[i];
    }
    int b[1111]={0};
    long long cnt=0;
    for (int i=1;i<n;++i) {
        if (a[i]>1) {
            b[i]=a[i]-1;
        } else {
            b[i]=a[i]+1;
        }
        cnt+=b[i];
    }
    b[n]=sum-cnt;
    for (int i=1;i<=n;++i) {
        if (b[i]<=0 || b[i]==a[i]) {
            return ":-(";
        }
    }
    return "^_^";
}

int main() {
    int t;
    cin>>t;
    while (t--){
    	cin>>n;
        for (int i=1;i<=n;++i) {
            cin>>a[i];
        }
        cout<<f(a)<<endl;
    }
    return 0;
}

结语：

给个精选把！给个点赞吧！给个评论吧！

有帮助，赞一个

去预览

0/2000

全部评论 10

🐱‍🚀
顶

1周前来自广东
0
复仇者_Erika😈😈😈
顶

1周前来自湖南
0
AC君
hi，感谢分享题解！为了更好地组织和存档这些宝贵的学习资源，我们建议将题解发布在具体题目里的题解区域，参考。这样不仅方便您自己日后查阅，也便于其他学习者参考和学习。

1周前来自浙江
0
不会C++的noah
ding

1周前来自浙江
0
不会C++的noah
ding

1周前来自浙江
0
不会C++的noah
ding

1周前来自浙江
0
不会C++的noah

1周前来自浙江
0
不会C++的noah
1

1周前来自浙江
0
不会C++的noah
ding

1周前来自浙江
0
不会C++的noah
顶

1周前来自浙江
0

有点难度的思维题

给个精选把！给个点赞吧！给个评论吧！

全部评论 10

热门讨论