题目链接
A. Trip for Meal
题意
三个点之间两两有路径,分别长为\(a,b,c\),现在从第一个点出发,走\(n-1\)条边,问总路径最小值。
思路
记起始点相邻的边为\(a,b\),相对的边为\(c\).
首先肯定走\(a,b\)中的最小值(不妨设为\(a\)),到达另一个顶点。那么这个顶点所连的两条边\(a,c\)中必然有一个是\(a,b,c\)三者中的最小值,否则最小值就为\(b\),与初始的选择矛盾。
于是接下来只需要在最小值的路上反复走即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int n, a ,b,c;
scanf("%d", &n);
--n;
scanf("%d%d%d", &a,&b,&c);
if (n==0) { putchar('0'); exit(0); }
if (b > a) swap(a,b);
int ans = b;
--n;
if (b > c) ans += n*c;
else ans += n*b;
printf("%d\n", ans);
return 0;
}
B. Divisibility of Differences
题意
从\(n\)个数中取\(m\)个数关于\(\%k\)同余。
思路
统计\(\%k=0,1,...,k-1\)的数的个数。
Code
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
int a[maxn], cnt[maxn], ans[maxn];
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
++cnt[a[i] % k];
}
for (int i = 0; i < k; ++i) {
if (cnt[i] >= m) {
printf("Yes\n");
int tot = 0;
for (int j = 0; j < n && tot < m; ++j) {
if (a[j] % k == i) ans[tot++] = a[j];
}
printf("%d", ans[0]);
for (int i = 1; i < tot; ++i) printf(" %d", ans[i]); printf("\n");
exit(0);
}
}
printf("No\n");
return 0;
}
C. Classroom Watch
题意
给定一个数\(n(n\leq 1e9)\),已知\(n=x+(x各数位上数字之和)\),求所有满足条件的\(x\).
思路
显然,\(x\)最大只有\(9\)位,于是各数位上数字之和\(\leq 9*9=81\),循环\(81\)次\(check\)即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int ans[100];
int digit(int x) {
int ret = 0;
while (x) {
ret += x % 10;
x /= 10;
}
return ret;
}
int main() {
int n;
scanf("%d", &n);
int tot = 0;
for (int i = max(n-81,0); i <= n; ++i) {
if (i+digit(i) == n) ans[tot++] = i;
}
printf("%d\n", tot);
for (int i = 0; i < tot; ++i) printf("%d\n", ans[i]);
return 0;
}
D. Sorting the Coins
题意
给定一个全\(0\)的串,询问\(n\)次,每次在上一次询问的基础上将串中某一个指定位置处的\(0\)变为\(1\),并问经过多少次操作能够使整个串左边全\(0\),右边全\(1\).
一次操作:从左到右扫描,每遇到一个\(1\),如果它右边是\(0\),就将它与右边的\(0\)交换位置,再从下一个位置继续开始扫描直至结束。
思路
首先,最右边的若干个\(1\)是不用处理的;而对于其左边所有的没有与最右边那块连接起来的\(1\),效果上每次只能将其中一个(即最右边的那个)移到与最右边的若干个\(1\)合并。所以操作次数即为当前总的\(1\)的个数减去最右边的连续的\(1\)的个数。
又因为最右边的连续的\(1\)在整个过程中肯定是逐渐向左延伸的,故可以记录左端点每次看是否可以向左拓展,时间复杂度\(O(n)\).
Code
#include <bits/stdc++.h>
#define maxn 300010
using namespace std;
typedef long long LL;
bool a[maxn];
int main() {
int n;
scanf("%d", &n);
int l = n+1, r = n+1;
putchar('1');
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
a[x] = 1;
while (l > 1 && a[l-1]) --l;
printf(" %d", i+1-(r-l));
}
putchar('\n');
return 0;
}
小结
这样的题目...有些遗憾晚上有课没能打_(:з」∠)_
\(B\)和\(C\)都很普通;
\(D\)很快想出了其中的道道但关于写法还是绕了路,一开始是去记录最右边的没有与最右边的\(1\)连续的一块然后各种讨论后来发现不行;
\(A\)一上来还真被蒙住了_(:з」∠)_在讨论是走两条边还是三条边...好题好题.
说遗憾什么的...反正\(EF\)也不会做,\(ABCD\)又过了超级多_(:з」∠)_
不遗憾不遗憾。