长乐 Day 1

Posted on By 陈, 梓域

爬起来比跌倒多一次，就是成功。

今天早上上课，其余时间打题。
重新学了递推，贪心和二分，虽然之前学过，但仍是听不懂受益匪浅。
（那讲师无非就是照着课件念，课件书里都有，还不如自己看书呢）
下午打的题有些难度，除昨晚把递推基本打完之外，另外两者只是各AC了4题。其中收获如预料般还挺多的。
突然发现，这里高手还挺多的，几个坐在后面的小孩有点厉害。

有题二分【防具布置】卡了很久，一直时间超限。
原本写法：

#include 
#define f_for(a, b, i) for (int(i) = (a); (i) <= (b); (i)++)

#define ll long long

using namespace std;
const int L = 2e5 + 10;
int T, N, s[L], e[L], d[L], M = INT_MAX;
int Be(int a) {
    int c = 0;
    f_for(1, N, i) if (s[i] > N;
    f_for(1, N, i) cin >> s[i] >> e[i] >> d[i];
    if (!(Be(M) % 2)) {
        cout << "There's no weakness." << '\n';
        return;
    }
    int l = 0, r = M;
    while (l > 1;
        if (Be(mid) & 1)
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << " " << Be(l) - Be(l - 1) <> T;
    while (T--) Do();
}

后来我发现从上面做一个优化会AC，正解如下：

#include 
using namespace std;
typedef long long LL;
const int L = 2e5 + 10;
struct R {
    LL s, e, d;
} O[L];
int t, n;
LL C(LL p) {
    LL ans = 0;
    for (int i = 1; i  p)
            continue;
        ans += (min(O[i].e, p) - O[i].s) / O[i].d + 1;
    }
    return ans;
}
int main(void) {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i > O[i].s >> O[i].e >> O[i].d;
        LL l = 0, r = (1LL << 31) - 1;
        while (l < r) {
            LL mid = (l + r) / 2;
            if (C(mid) % 2 == 0)
                l = mid + 1;
            else
                r = mid;
        }
        LL ans = C(r) - C(r - 1);
        if (ans & 1)
            cout << r << " " << ans << '\n';
        else
            cout << "There's no weakness." << '\n';
    }
}

差不多就是这样了，不想当话痨。

训练日志