Codeforces Round #747 (Div. 2) – 解题报告

A – Consecutive Sum Riddle

思博题,没什么好讲的。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        ll n;
        scanf("%lld", &n), printf("%lld %lld\n", -n + 1, n);
    }
    return 0;
}
继续阅读Codeforces Round #747 (Div. 2) – 解题报告

NOI 复习专题 – DP

斜率优化

斜率优化其实不是很难,可以理解为在平面上的一些点作为决策点,而你现在有一条斜率为 \(k\) 的直线,你需要使其经过一个合适的点,使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。

继续阅读NOI 复习专题 – DP

「Codeforces 724F」Uniformly Branched Trees – 题解

主要思路

啊,又是无根树 DP。首先讨论奇偶性,如果是奇数的话可以直接 DP;如果不是,则需要容斥一波。

设置状态 \(dp[scale][maxPart][degree]\),意为大小为 \(scale\)、最大子树大小为 \(maxPart\) 且根度数为 \(degree\) 的方案树。转移其实很好想,看代码吧。

继续阅读「Codeforces 724F」Uniformly Branched Trees – 题解

BZOJ3590:[SNOI2013]Quare – 题解

主要思路

我操这个题是真的有意思(做完后索然无味)。

肯定这个题状压 DP 没跑的,所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难,我们需要思考一个归纳的方式来构造一个双连通图。

继续阅读BZOJ3590:[SNOI2013]Quare – 题解

AtCoder Grand Contest 041 – 解题报告

A – Table Tennis Training

思博题,考虑两端和奇偶性即可。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ll n, A, B, ans = 0x7fffffffffffffff;
    scanf("%lld%lld%lld", &n, &A, &B);
    ans = min(A - 1, n - B) + 1 + ((B - A - 1) >> 1);
    if (!((A^B) & 1))
        ans = min(ans, (B - A) >> 1);
    printf("%lld\n", ans);
    return 0;
}
继续阅读AtCoder Grand Contest 041 – 解题报告