寒假颓废了很久，果然菜的抠脚。虽然没有整场打下来，但是依旧改变不了我菜的事实。姑且记一下。

A – 写文案（CodeForces 165B）

思路很简单，先确定边界然后再搜索。

S = v + \left\lfloor \frac{v}{k} \right\rfloor + \left\lfloor \frac{v}{k^{2}} \right\rfloor + ... + \left\lfloor \frac{v}{k^{p}} \right\rfloor

其中，p满足\left\lfloor \frac{v}{k^{p+1}} \right\rfloor = 0。简单放缩取一个下界：

n \leq S < v \cdot \left( 1 + \frac{1}{k} + ... + \frac{1}{k^{p}} \right) < \frac{v-\frac{v}{k^{p}}}{1-\frac{1}{k}}

v > (1+\frac{1}{k}) \cdot n -1

中途记错了等比求和，卡了一哈。

#include <iostream>

#define LL long long
using namespace std;

LL calc_limit(LL k, LL n) {
    return n - n / k - 1;
}

LL calc(LL v, LL k) {
    LL t = 1, acc = 0;
    while (v / t > 0) {
        acc += v / t;
        t *= k;
    }
    return acc;
}

int main() {
    LL n, k, i;
    cin >> n >> k;
    i = calc_limit(k, n);
    while (calc(i, k) < n) i++;
    cout << i << endl;
    return 0;
}

B – 摆石子（HDU 4248）

纯用排列好像很复杂，我谔谔。感觉是dp，短时间没写出转移方程，跳了。之后想了一下，多组数据感觉dp可能悬？范围倒是还好，丢个状转。

dp\left[ i, j \right] = dp\left[ i-1, j - k \right] \cdot \left( {k \atop j} \right)

i是加入的组，j是序列长度，k为组i加入的数目。以后写（咕）

C – 算数字（POJ 2739）

写了一辈子的弱智题。线性筛+枚举序列尾。结果首先是无限RE。以为是数组下标越界，甚至数组没初始化、_for宏都怀疑了，结果其实是有个变量没初始化。然而还有问题，就是查找序列尾的函数，改的时候漏了改最后的return。

int near(int n) {
    for (int i=1; i < ind; i++) {
        if (prime[i]>=n)
            return i;
    }
    return 1;
}

应该返回最后一个素数的下标。很好的教训。

D – 复制玩具（CodeForces 922A）

这个x – (y – 1)判断下就行，结果沙雕的以为!(x >= 0 && y >= 1)的条件可以包括y == 1 && x != 0了。当时以为是数据范围的问题，所以写大数类去了。然后就没时间了，真是沙雕。

E – 蛙跳（CodeForces 1077A）

签到题

#include<iostream>

using namespace std;

int main() {
    long long a, b, k, offset, kase;
    cin >> kase;
    while (kase--) {
        cin >> a >> b >> k;
        offset = a - b;
        cout << offset * (k / 2) + (k % 2 ? a: 0) << endl;
    }
    return 0;
}

F – 地铁（POJ 2502）

写完结点读入和距离计算就只剩半小时了，打扰了。之后补（咕）

G – 半素数（CodeForces 26A）

线性筛+因数计数，>2的可以直接放过。

int main() {
    int n, num = 0, pri;
    cin >> n;
    seive(n);
    memset(mark, 0, sizeof(mark));
    for (int i = 1; i < total; i++) {
        pri = primes[i];
        if (n / pri < 1) break;
        for (int i = 4; i <= n; i++) {
            if (mark[i] > 2) continue;
            mark[i] += i % pri == 0;
        }
    }
    for (int i = 4; i <= n; i++) {
        if (mark[i] == 2) {
            num++;
        }
    }
    cout << num << endl;
    return 0;
}

H – 骨牌摆放(POJ 2506)

当时跳了，后悔了。其实类似斐波那契，就是一个递推。F(n)=F(n-1)+2*F(n-2)。

I – 几点了（HDU 6077）

这个跳了，更后悔了。其实找一两个特征点就行。当时觉得找起来慢就过了。

J – 匹配字（HDU 2222）

跳了两个简单的然后选了J，真的沙雕。当时想20分钟，就写个kmp搏一搏吧。果然事情没那么简单，TLE了，然后比赛TLE了。

反思

题做的不够，解决问题完全没条理。出了错几乎是手忙脚乱的。时间分配不合理。