题目链接
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
", 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
");
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("
");
exit(0);
}
}
printf("No
");
return 0;
}
C. Classroom Watch
题意
给定一个数(n(nleq 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
", tot);
for (int i = 0; i < tot; ++i) printf("%d
", 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('
');
return 0;
}
小结
这样的题目...有些遗憾晚上有课没能打_(:з」∠)_
(B)和(C)都很普通；
(D)很快想出了其中的道道但关于写法还是绕了路，一开始是去记录最右边的没有与最右边的(1)连续的一块然后各种讨论后来发现不行；
(A)一上来还真被蒙住了_(:з」∠)_在讨论是走两条边还是三条边...好题好题.
说遗憾什么的...反正(EF)也不会做，(ABCD)又过了超级多_(:з」∠)_
不遗憾不遗憾。