小码王2025 XP03 A 题解
2025-08-03 10:17:31
发布于：广东
9阅读
0回复
0点赞
小码王2025 XP03 A 八月份第一期 2班 第一次考试题解
主讲教师徐昊轩
第一题 奖学金
#include <bits/stdc++.h>
using namespace std;
struct node{
int a,b,c,d,e;
};
int main(){
int n;
cin >> n;
vector<node> v(n + 10);
for(int i = 1;i <= n;i++){
cin >> v[i].a >> v[i].b >> v[i].c;
v[i].d = v[i].a + v[i].b + v[i].c;
v[i].e = i;
}
for(int j = 1;j <= n;j++){
for(int i = 1;i <= n;i++){
if(v[i + 1].d > v[i].d){
swap(v[i + 1].a,v[i].a);
swap(v[i + 1].b,v[i].b);
swap(v[i + 1].c,v[i].c);
swap(v[i + 1].d,v[i].d);
swap(v[i + 1].e,v[i].e);
}else if(v[i + 1].d == v[i].d){
if(v[i + 1].a > v[i].a){
swap(v[i + 1].a,v[i].a);
swap(v[i + 1].b,v[i].b);
swap(v[i + 1].c,v[i].c);
swap(v[i + 1].d,v[i].d);
swap(v[i + 1].e,v[i].e);
}else if(v[i + 1].a == v[i].a){
if(v[i + 1].e < v[i].e){
swap(v[i + 1].a,v[i].a);
swap(v[i + 1].b,v[i].b);
swap(v[i + 1].c,v[i].c);
swap(v[i + 1].d,v[i].d);
swap(v[i + 1].e,v[i].e);
}
}
}
}
}
for(int i = 1;i <= 5;i++){
cout << v[i].e << " " << v[i].d << endl;
}
return 0;
}
第二题 查找
#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int main(){
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
while(m--){
int x;
cin >> x;
int l = 1,r = n;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] >= x){
r = mid - 1;
}else if(a[mid] < x){
l = mid + 1;
}
}
if(a[l] == x){
cout << l << " ";
}else if(a[r] == x){
cout << r << " ";
}else{
cout << -1 << " ";
}
}
return 0;
}
第三题 连通块问题(DFS)
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=2e6+5;
bool vis[maxn];
int cnt=0;
vector<int> e[maxn];
void dfs(int now) {
cnt++;
vis[now]=true;
for(int i =0; i<e[now].size(); i++) {
int nxt=e[now][i];
if(!vis[nxt]) dfs(nxt);
}
}
int main() {
cin>>n>>m;
for(int i =1; i<=m; i++) {
int a,b;
cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
int x,y;
cin>>x>>y;
dfs(x);
if(vis[y]) cout<<cnt<<endl;
else cout<<0<<endl;
return 0;
}
第四题 木材加工
#include <bits/stdc++.h>
using namespace std;
bool check(vector<int>& L, int k, int mid) {
long long sum = 0;
for (int l : L) {
sum += l / mid;
if (sum >= k) return true;
}
return false;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> L(n);
for (int i = 0; i < n; ++i) cin >> L[i];
int left = 1, right = *max_element(L.begin(), L.end());
int ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(L, k, mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << ans << endl;
return 0;
}
第五题 拼接质数1(方法1）
#include<bits/stdc++.h>
using namespace std;
int n,a[1010],ans;
bool check(int x) {
if(x<=1) return 0;
for(int i=2;i*i<=x; i++) {
if(x%i==0) return false;
}
return true;
}
void dfs(int m,int sum) {
if(m==n+1) {
if(check(sum)) ans++;
return;
}
dfs(m+1,sum);
dfs(m+1,sum+a[m]);
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
dfs(1,0);
cout<<ans;
return 0;
}
第六题 快速幂
#include <iostream>
#include <cassert>
using namespace std;
typedef long long ll;
ll a, b, p;
ll quick_power(ll a,ll b){ //计算a的b次方
if(b == 0) return 1;
ll ans = quick_power(a,b/2); //先计算a的（b / 2）次方
ans = ans * ans % p;
if(b % 2 == 1){ //如果 b 是奇数，则 a ^ b = (a ^ (b / 2)) * (a ^ (b / 2)) * a
return a * ans % p;
}
return ans;
}
int main() {
cin >> a >> b >> p;
cout << a << "^" << b << " mod " << p << "=" << quick_power(a,b) % p;
return 0;
}
第七题 八皇后 Checker Challenge
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n;
int vis[N];
bool judge(int x,int y){
for(int i = 1;i <= x - 1;i++){
if(vis[i] == y){
return false;
}
}
for(int i = 1;i <= x - 1;i++){
if(x - i == y - vis[i]){
return false;
}
}
for(int i = 1;i <= x - 1;i++){
if(x + y == i + vis[i]){
return false;
}
}
return true;
}
int cnt = 0;
void check(){
cnt++;
if(cnt <= 3){
for(int i = 1;i <= n;i++){
cout << vis[i] << " ";
}
cout << endl;
}
}
void dfs(int now){
if(now == n + 1){
check();
return;
}
for(int i = 1;i <= n;i++){
if(judge(now,i)){
vis[now] = i;
dfs(now + 1);
vis[now] = 0;
}
}
}
int main(){
cin >> n;
dfs(1);
cout << cnt;
return 0;
}
这里空空如也
有帮助，赞一个