Contest
A. ssoj2964 交错的士兵
(n) 个数的排列，从左到右依次为 1, 2, …, (n)。(n) 次操作，对于第 (i) 次操作，从左到右分成很多段，每段 (i) 个，若末尾有剩余，剩余部分自成一段；然后对于每一段，段中第一个数移动到该段末尾，其余数向左移动对齐。输出经过 (n) 次操作后的排列。(1le nle 10^6)。
[input] 4 [output] 4 2 3 1
显然 (n^2) 模拟会超时。考虑 (O(nlog n)) 做法：观察到每次操作仅每段第一个数有较大位移，其余数仅仅向左移动一位。所以如果不移动其余数，仅移动数列头、尾指针和每段第一个数。
代码实现坑点很多。
#include <cstdio>
#include <algorithm>
using namespace std;
int n, d[2000006];
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) d[i]=i;
for (int i=2; i<=n; ++i) {
for (int j=n/i*i-(n%i==0?i:0)+i-1; j>=i-1; j-=i)
d[min(n+i-1,j+i)]=d[j];
}
for (int i=n; i<n+n; ++i) printf("%d ", d[i]);
return 0;
}
B. ssoj2965 乙女文楽
(n) 个数的数列。不多于 (k) 次修改机会，每次修改将删去所有值为 (x) 的数。最大化连续等值区间长度。(1le nle 10^5,0le kle n-1, 1le a_ile n)。
尺取法。维护区间头尾指针，保证区间中不多于 (k+1) 种数值。随时更新答案。
#include <cstdio>
#include <algorithm>
using namespace std;
int n, k, a[100005], ans, cnt, col[100005];
int main() {
scanf("%d%d", &n, &k);
for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
for (int i=1, j=1; i<=n; ++i) {
if (++col[a[i]]==1) ++cnt;
while (cnt>k+1) if (--col[a[j++]]==0) --cnt;
ans=max(ans, col[a[i]]);
}
printf("%d
", ans);
return 0;
}
C. ssoj2674 Delicious Apples
一个环长度为 (L), 上面有 (n) 棵树，篮子一次可装 (k) 个苹果；给出每棵树的位置和树上的苹果数，求将所有苹果运回原点的最少的总距离。(1le n,kle 10^5,sum a_ile 10^5,1le Lle 10^9)。
贪心。根据题目意思，有 “原路返回” 和 “走一圈” 两种走法。显然，当只有不多于 (k) 个苹果且位于环下部时，走一整圈更优；对于其他情况，显然原路返回更优。实际上，可以证明最优解中只有不多于一次 “走一圈”。
对苹果树离散，分为左右半边，分别贪心。枚举 “走一圈” 包含的苹果数量。
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
int T, n, L, k;
ll sl[100005], sr[100005], l[100005], r[100005], lt, rt, ans;
inline int read() {
char c; while (!isdigit(c=getchar()));
int v=c-48; while (isdigit(c=getchar())) v=v*10+c-48;
return v;
}
int main() {
T=read();
while (T--) {
memset(sl, 0, sizeof(sl)), memset(sr, 0, sizeof(sr)),
memset(l, 0, sizeof(l)), memset(r, 0, sizeof(r));
L=read(), n=read(), k=read();
lt=0, rt=0;
for (int i=1, pos, num; i<=n; ++i) {
pos=read(), num=read();
if ((pos << 1)<=L) while (num--) l[++lt]=pos;
else while (num--) r[++rt]=L-pos;
}
sort(l+1, l+1+lt), sort(r+1, r+1+rt);
for (int i=1; i<=lt; ++i) {
if (i<=k) sl[i]=l[i]; else sl[i]=sl[i-k]+l[i];
}
for (int i=1; i<=rt; ++i) {
if (i<=k) sr[i]=r[i]; else sr[i]=sr[i-k]+r[i];
}
ans=(sl[lt]+sr[rt])<<1;
for (int i=1; i<=lt && i<=k; ++i) {
ll Le=lt-i, Ri=rt-k+i;
ans=min(ans, ((sl[Le]+sr[Ri])<<1)+L);
}
printf("%lld
", ans);
}
return 0;
}
本题代码调试过程中出现玄学错误。太痛苦了……
D. 三角形牧场 (pasture)
和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。 她拥有 (N) ((3≤N≤40)) 块木板，每块的长度 (L_i) ((1≤L_i≤40)) 都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。 请帮助 Hei 小姐构造这样的牧场，并计算出这个最大牧场的面积。
暴力枚举三角形两边长度（第三边可以推算出来，即与总长相减），对于所有可能的三角形，Heron 公式更新答案。易证三角形任意一边长度不超过总长的一半。Heron 公式：(S=sqrt{p(p-a)(p-b)(p-c)}), 其中 (displaystyle p=frac{a+b+c}{2}).
预处理三角形可能的两边，复杂度 $O(np^2)approx O(n^5) $。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1e-5;
int n, x[43], L, p;
int f[803][803];
double ans;
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &x[i]), L+=x[i];
double p=L/2.0;
f[0][0]=1;
for (int i=1; i<=n; ++i)
for (int a=p; a>=0; --a) for (int b=p; b>=0; --b)
if (a>=x[i] && f[a-x[i]][b] || b>=x[i] && f[a][b-x[i]])
f[a][b]=1;
for (int a=p; a; --a) for (int b=p; b; --b) if (f[a][b]) {
int c=L-a-b;
if (a<p && b<p && c<p)
ans=max(ans, (p-a)*(p-b)*(p-c));
}
if (ans<eps) printf("-1
");
else printf("%d
", (int)(sqrt(p*ans)*100));
return 0;
}
在逻辑运算当中，|| 和 && 是 短路符号，| 和 & 不是。而运算符优先级 |、& 要比 ||、&& 高，其中 || 比 && 高。利用以上几点即可继续缩短代码。