2024 第一次周赛

A:

题目大意

骑士每连续 i 天每天会得到 i 个金币，（i = 1， 2， 3 ， …）,那么展开看每一天可以得到的金币数：1 2 2 3 3 3 4 4 4 5 5 5 5 5 …
可以发现就是1个1 ，2个2, 3个3…,那么我们相同的一段分开来看，他们的加和正好就是这段里面相同数字的平方，而每一段里的数字个数就等于这段里的相同数字，那么我们想知道到第k 个数完整加了多少段就可以从1 开始遍历，如果 k = 7 ,那么前面加了完整的三段分别是1， 2 2 ， 3 3 3，看成个数就是1 ， 2 ， 3，那么我们就能想到用数列加和公式 n * ( n + 1) / 2 算出来他的个数，那么剩下的不够下一段的个数直接乘下一段应为的数就好了，比如这个例子就是 7 - 3 * （3 + 1）/ 2 = 1；这个应该是一个 4 ，最后答案就是完整的段 加上剩余的段 = 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 1 * 4 = 18。

下面展示一些 `详细代码`。

#include<stdio.h>
int main()
{int k ;// 有k天scanf("%d",&k);//输入kint res = 0;//用来记录加到第 i 段时 总个数 >= kfor(int i =1;i <= 200;i ++){if(i*(i + 1) / 2 >= k){res = i;//记录break;//已经找到跳出循环}}int m = res - 1;//m 表示第k天之前加了多少个完整的段（就是相邻赐予金币数相同的一段天数）int cnt = k - m *(m + 1)/ 2;//记录完整的m段之后剩余的天数，最多满足完整的下一段int ans = 0;//记录总金币for(int i = 1;i <= m;i ++)//m段逐个加起来{ans = ans + (i * i);}ans += (m + 1) * cnt;//把剩余的加起来，因为前面已经加了m个完整的段，那么剩余的每一天得到的金币都是m + 1,并且剩余的天数即cnt不可能大于m + 1.printf("%d" , ans);//输出答案return 0;
}

B:

//题解：暴力，从1~n挨个搜索，对每次搜索到的数进行while循环以查找x出现的次数，多说无益直接看代码。

#include<stdio.h>
int main() {int n, x;scanf("%d%d", &n, &x);int count = 0;for (int i = 1; i <= n; i++)//从1~n挨个搜索{int j = i;while (j != 0){if (j % 10 == x) {//判断其最后一位是否为xcount++;}j /= 10;//去掉最后一位，继续向下查找}}printf("%d", count);return 0;
}

C：

特判：由题意得：n个位置，k个人，同时n≥k≥0；因此，k可以为n，也可以为0。考虑这两种情况。在k=n||k=0，这两种情况下，牛牛无法坐上过山车，因此最少位置和最多位置均为0；

正常情况：
最多：k<n,进行模拟，当k=1，010，最多有两个位置，k=2，010010，最多有四个位置，以此类推，k==t，最多有2t个位置。此时让我们想结果成立的条件，n≥t*3;但是如果条件不成立呢？最多已经是2t了，所以此时最多便是除去这k个人之外的所有位置，即n-t。

最少：除去特判的0，最少情况就只有1111__或者__1111的情况了，此时最少为1。

#include <bits/stdc++.h>
using namespace std;int main() {long long n, k;cin >> n >> k;if (k == n || k == 0)cout << "0 0" << '\n';else if (n >= k * 3)cout << "1 " << 2 * k << '\n';elsecout << "1 " << n - k << '\n';return 0;
}

D:

E：

 这道题是一个图论的最短路径问题，节点1是中心节点，与其相连的边权为A，其他边权为B。题目要求找到从节点1出发，收集所有7个节点的宝石的最短时间。#include <stdio.h>int main() {int a, b; scanf("%d %d", &a, &b); // 输入A和B // 通过分析图的结构，最短路径可以直接计算如下：// 1. 对于节点1，与节点2, 3, 4, 5, 6, 7之间的距离分别为A。// 2. 两个相邻的非中心节点之间的路径为B。// 如果A的值大于等于B，则最短时间应该从节点1到达某个外围节点，然后沿着外围环路收集其他宝石。// 即最短时间为 a+ 5 * b // 如果A的值小于B，选出这两种情况的最小值，即min(a + 5 *b, 11* a);   if (a + 5 * b > 11 * a){      printf("%d", 11 * a);    return 0;   }   else {  printf("%d", a + 5 * b );return 0;    }}

F:

思路：看到题目最终让输出一个数首先要想能不能用二分来做，二分要首先确定边界，并且判断有无单调性，该题就能用二分来做， 二分枚举mex的值判断是否符合条件，二分判断之后最终将确定下来mex，不懂二分的可以看看这篇博客：https://blog.csdn.net/2301_80882026/article/details/135197055?ops_request_misc=%257B%2522request%255Fid%2522%253A%25225665E938-4BE3-45AB-B426-0C876A134A13%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=5665E938-4BE3-45AB-B426-0C876A134A13&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_blogfirst_rank_ecpm_v1~rank_v31_ecpm-1-135197055-null-null.nonecase&utm_term=%E4%BA%8C%E5%88%86&spm=1018.2226.3001.4450

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int>PII;
const int N=1e6+10;
const int MOD = 1e9 + 7;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;int t;
int n;
int a[N];
bool st[N];
bool check(int x)
{memset(st ,0, sizeof st);//初始化for(int i = 1; i <= n; i ++){int o = a[i];while(o && (o >= x || st[o])) o /= 2;st[o] = true;//能够到达的数}for(int i = 0; i < x; i ++) //注意mex的定义，要判断x符不符合只需要判断小于x的所有数是否均能到达{if(st[i] == 0) return false;//说明到达不了x}return true;
}
int main()
{cin >> t;while(t --){cin >> n;int res = 0;for(int i = 1; i <= n; i ++)cin >> a[i], res = max(res, a[i]);int l = 0, r = res + 1;while(l < r)//二分mex{int mid = (l + r + 1) >> 1;if(check(mid)) l = mid;else r = mid - 1;}cout << l << '\n';}return 0;
}

G:

//解析：
//如果n为偶数，那两两交换即可完成 即n/2；
//若n为奇数，则要多交换一次，即多出的那个数与谁交换都可以，为(n+1)/2次。
#include<stdio.h>
signed main()
{int n, m;scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &m);if (n == 1) printf("-1");//只有n==1时不行else printf("%d", (n + 1) / 2);//可简称写为(n+1)/2;return 0;
}

H:

#include<stdio.h>
const int N=1e5+10;
bool st[N];
int main()
{int n;scanf("%d",&n);int cnt=0;for(int i=0;i<=9;i++)//先判断从1-10的好数，这要在之后的好数判定中有基础if(i%2==0) st[i]=true;for(int i=1;i<=n;i++)//暴力枚举从1到n的数{int x=i,sum=0;while(x)//求x的位数之和{int c=x%10;sum+=c;x/=10;}//位数之和是偶数，不大于它本身，是个好数if(sum<=i&&st[sum]&&sum%2==0){cnt++;st[i]=true;}}printf("%d\n",cnt);
}