Greed
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using std::vector; using std::sort; int cmp(const void * x, const void * y) { //x < y return (*((long long *)(x))) > (*((long long *)(y))) ? 1 : -1; } long long a[100005], b[100005]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n; scanf("%d", &n); for (int i = 0; i < n; i++)scanf("%lld", &a[i]); for (int i = 0; i < n; i++)scanf("%lld", &b[i]); //qsort(b, n, sizeof(long long), cmp); sort(b, b + n); long long sum = 0; for (int i = 0; i < n; i++) sum += a[i]; if (sum > b[n - 1] + b[n - 2]) printf("NO "); else printf("YES "); return 0; }
Wrath
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using std::vector; using std::sort; int cmp(const void * x, const void * y) { //x < y return (*((long long *)(x))) > (*((long long *)(y))) ? 1 : -1; } int stack[1000005], top = 0; long long l; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld", &l); while (top > 0 && i - stack[top - 1] <= l) top--; stack[top++] = i; } printf("%d ", top); return 0; }
Pride
把一个不是1的数变成1肯定至少要1次操作，所以全变成1的最少操作次数肯定不会比a中不是1的数字个数还少。假定最初a中已经有了几个1，则直接输出n-1的个数。如果最初a中没有1，则首先用最少的操作次数弄出来一个1，然后再用n-1次操作把其他数字变成1。求弄出1的最少操作次数的方法是这样的：首先把a中相邻的数字两两求最大公约数，再对得到的数组再对相邻数字两两求最大公约数，直到出现1：则最少操作次数为迭代次数；全相同且不为1：说明不可能出现1。至于为啥，我也不知道，直觉是这样的，试了试居然过了。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using std::vector; using std::sort; int cmp(const void * x, const void * y) { //x < y return (*((long long *)(x))) > (*((long long *)(y))) ? 1 : -1; } long long gcd(long long a, long long b) { long long k; while (b != 0) { k = b; b = a % b; a = k; } return a; } long long a[2][2005]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n, cnt = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld", &a[0][i]); if (a[0][i] == 1) cnt++; } if (cnt) { printf("%d ", n - cnt); return 0; } int last = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < n - i; j++) { a[1 - last][j] = gcd(a[last][j], a[last][j + 1]); } bool same = true, find1 = false; for (int j = 0; j < n - i; j++) { if (a[1 - last][j] == 1) find1 = true; if (j + 1 < n - i && a[1 - last][j] != a[1 - last][j + 1]) same = false; } if (find1) { printf("%d ", n - 1 + i); return 0; } if (same) { printf("-1 "); return 0; } last = 1 - last; } printf("-1 "); return 0; }
Gluttony
把每个数字用大于它的最小的数字代替，最大的数字用最小的数字代替，没有-1的情况。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using std::vector; using std::sort; int cmp(const void * x, const void * y) { //x < y return (*((long long *)(x))) > (*((long long *)(y))) ? 1 : -1; } int n; long long a[25], b[25], c[25]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); b[i] = a[i]; } qsort(a, n, sizeof(long long), cmp); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (b[i] == a[j]) { c[i] = j; break; } } } for (int i = 0; i < n; i++) c[i] = (c[i] + 1) % n; for (int i = 0; i < n; i++) printf("%lld ", a[c[i]]); return 0; }
Envy
按边长从小到大处理（kruskal），各个询问中涉及的边也按从小到大处理。
当处理长度为i的边时，先不在整体的边集里处理，依次判断各个询问中涉及相同长度的边集全部加入会不会产生环，然后把长度为i的边全部加入最小生成树中（这个过程中产生环也无所谓，不加就行了）。
这个题标签里有个dsu，不过我用普通合并和启发式合并分别提交反而是普通合并比较快。他们都说启发式合并比较优，但是我觉得挺反直觉的，因为合并过程是一样的，得到的结果本质上也是一样的，所以我觉得启不启发没什么区别。强行要说的话，就是启发式能减少一点之后在路径压缩上花的时间。
Sloth
Last