两个东西

1. IDI-Open 2016 - Building Fences

题目大概意思是给 K 根不同长度的木棍求截得至少 N 根且剩下的木棍总长度不长于这 N 根木棍的最小截取次数.
二分一下枚举这 N 段木棍的长度即可(一开始没搞得清还以为要整数TwT)
这里枚举得到的木棍长度 len 精度控制在 eps.
之后因为要计算长度为 L 的木棍截成长度为 len 的木棍需要 cut 的次数 num, 如果正好 num * len == L 那就需要 cut num - 1 次否则就是 num 次.
这里判断 num * len 和 L 的差的绝对值的时候不能再用 eps 来判断了, 因为 len 乘了 num 所以误差相应的扩大了 num, 所以应该是 fabs(num * len - L) < eps * num

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

double p[10007];

const double eps = 1e-8;

int main()
{
    int K, N, cnt;
    double l, r, mid, maxlen, num;

    while(scanf("%d%d", &K, &N) != EOF){
        for(int i = 0; i < K; i++) scanf("%lf", &p[i]);
        l = 0.0, r = 10000.0, maxlen = 0.0;
        while(r - l > eps){
            mid = (l + r) * 0.5;
            cnt = 0;
            for(int i = 0; i < K; i++) cnt += (int)(p[i] / mid);
            if(cnt >= N) maxlen = l = mid;
            else r = mid;
        }
        cnt = 0;
        for(int i = 0; i < K; i++){
            if(fabs(p[i] - maxlen) < eps) continue;
            num = (int)(p[i] / maxlen);
            if(fabs(p[i] / maxlen - (double)num) < eps * num) cnt += num - 1;
            else cnt += num;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

2. 2017 Multi-University Training Contest - Team 1 - Balala Power!

            for(int i = cnt - 1; i > pos; i--) order[i - 1] = order[i];

            for(int i = pos; i < cnt - 1; i++) order[i] = order[i + 1];

目标: 把 pos 位置之后的元素依次往前移动一个覆盖掉 pos 位置的元素.
实现所用时间: 24h

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const long long MOD = 1e9 + 7;

long long Count[27][100007], mod[100007];
char s[100007];
int order[27], maxlen, cnt, link[27];
bool vis[27], zero[27];

inline bool cmp(int u, int v){
    for(int i = maxlen + 4; i >= 0; i--) if(Count[u][i] != Count[v][i]) return Count[u][i] > Count[v][i];
    return false;
}

int main()
{
    int n, len, pos, temp, cas = 1;
    long long ans;

    mod[0] = 1, mod[1] = 26;
    for(int i = 2; i <= 100007; i++) mod[i] = (long long)mod[i - 1] * 26 % MOD;
    while(scanf("%d", &n) != EOF){
        memset(Count, 0, sizeof(Count));
        memset(vis, false, sizeof(vis));
        memset(zero, false, sizeof(zero));
        maxlen = cnt = 0;
        for(int i = 0; i < n; i++){
            scanf("%s", s);
            len = strlen(s);
            for(int j = 0; j < len; j++){
                Count[s[j] - 'a'][len - 1 - j]++;
                if(!vis[s[j] - 'a']) vis[s[j] - 'a'] = true, order[cnt] = s[j] - 'a', cnt++;
            }
            if(len > 1 && !zero[s[0] - 'a']) zero[s[0] - 'a'] = true;
            if(len > maxlen) maxlen = len;
        }
        for(int i = 0; i < 26; i++){
            if(vis[i]) for(int j = 0; j < maxlen + 4; j++){
                if(Count[i][j] >= 26) Count[i][j + 1] += Count[i][j] / 26, Count[i][j] %= 26;
            }
        }
        sort(order, order + cnt, cmp);
        if(cnt == 26 && zero[order[cnt - 1]]){
            for(pos = cnt - 1; pos >= 0; pos--) if(!zero[order[pos]]) break;
            temp = order[pos];
            for(int i = pos; i < cnt - 1; i++) order[i] = order[i + 1];
            order[cnt - 1] = temp;
        }
        ans = 0;
        for(int i = 25; i > 25 - cnt; i--){
            if(i == 0) break;
            for(int j = maxlen + 4; j >= 0; j--)
                ans = (ans + (Count[order[25 - i]][j] * mod[j] % MOD) * i % MOD) % MOD;
        }
        printf("Case #%d: %I64d\n", cas++, ans);
    }
    return 0;
}

最好的谎言是九分真一分假最难找的bug是别的地方全都没问题就这一个地方莫名其妙写崩了
大概以后要引入模块化设计和单元测试吧(迫真