秦皇岛2020CCPC补题

秦皇岛2020CCPC A,E,F,G,I,K

A. A Greeting from Qinhuangdao

知识点：简单题
复杂度：$O(logn)$

#include
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
template<class T> using vc = vector;

void solve()
{
    ll n, m;
    cin >> n >> m;
    ll f = n * (n - 1);
    ll g = (m + n) * (m + n - 1);
    ll gc = __gcd(f, g);
    f /= gc;
    g /= gc;
    cout << f << '/' << g << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    cin >> T;
    rep(i, 1, T)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}

E. Exam Results

知识点：贪心
复杂度：$O(nlogn+n)$

这题我很快就有了思路，但是只是在脑海中过了一遍，其实少考虑了一些情况，所以直接WA了一发
然后debug时看到一个变量爆 $int$ 了，以为是这里错了，又WA一发，
最后还是在队友的帮助下考虑到了错误的情况，属实不应该交的那么快

我们将所有的分数和对应的人放在一起，按分数为权值排序，然后枚举最大值，
此时我们能得到及格线 $p\mathrm{\%}\ast max$ 用双指针就能快速得到有多少个人及格，
需要注意的是及格线 $p\mathrm{\%}\ast max$ 要上取整，并且枚举的最大值要合法^[1]

---

#include
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define int ll
#define pii pair
#define pll pair
template<class T> using vc = vector;
template<class T> using vvc = vc>;

const int N = 2e5 + 5;

pll s[N * 2];

void solve()
{
    int n, p;
    cin >> n >> p;
    vc<int> st(n + 1), st2(n + 1);
    rep(i, 1, n)
    {
        ll a, b; cin >> a >> b;
        s[i * 2 - 1] = { a,i };
        s[i * 2] = { b,i };
    }
    sort(s + 1, s + n + n + 1);
    int cnt = 0, ans = 0, tmp = 0;
    ll L = 1, fx;
    rep(i, 1, n * 2)
    {
        fx = s[i].fi * p;
        if (st2[s[i].se]++ == 0) tmp++;
        if (st[s[i].se]++ == 0) cnt++;
        while (s[L].fi * 100 < fx)
        {
            if (--st[s[L].se] == 0) cnt--;
            L++;
        }
        if(tmp == n) ans = max(ans, cnt);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    cin >> T;
    rep(i, 1, T)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}

---

F. Friendly Group

知识点：并查集
复杂度：$O(n)$

这题是队友A的，但是由于我少清空了w数组WA了一发
我真该死啊.jpg

我们观察，当一个朋友关系连接两个连通块时，不看该边时，这两个连通块至少是两颗树，所以当我让这两个连通块连接时，重新选择连通块时，不会让这两个连通块的答案更少^[2]，所以每一条边都必连，然后枚举连通块判读是否选取即可

---

#include
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define pii pair
#define pll pair
template<class T> using vc = vector;
template<class T> using vvc = vc>;

const int N = 3e5 + 5;


int f[N], w[N], sz[N];
void init(int n)
{
    rep(i, 0, n) f[i] = i, sz[i] = 1, w[i] = 0;
}

int find(int u)
{
    if (u == f[u]) return u;
    return f[u] = find(f[u]);
}

void unite(int u, int v)
{
    int fu = find(u), fv = find(v);
    if (fu == fv) w[fu]++;
    else
    {
        w[fv] += w[fu] + 1;
        sz[fv] += sz[fu];
        f[fu] = fv;
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    init(n);
    rep(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        unite(u, v);
    }
    ll ans = 0;
    rep(i, 1, n) if (find(i) == i)
    {
        if (w[i] > sz[i]) ans += w[i] - sz[i];
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    cin >> T;
    rep(i, 1, T)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}

---

G. Good Number

知识点：简单题
复杂度：$O(lo{g}^{2}n)$

这题有点小恶心，注意判断边界即可

---

#include
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define int ll
#define pii pair
template<class T> using vc = vector;
template<class T> using vvc = vc>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

ll ksm(ll x, int n)
{
    ll ret = 1;
    while (n)
    {
        if (n & 1) ret = ret * x;
        n >>= 1;
        x = x * x % mod;
    }
    return ret;
}

void solve()
{
    int n, k;
    cin >> n >> k;
    if (k == 1) cout << n << endl;
    else
    {
        ll x = (ll)pow(2, log2(n) / k), ans = 0;
        rep(i, 1, x)
        {
            if (i == x) ans += (n - ksm(i, k)) / i + 1;
            else ans += (ksm(i + 1, k) - ksm(i, k) - 1) / i + 1;
        }
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    cin >> T;
    rep(i, 1, T)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}

---

I. Interstellar Hunter

知识点：线性代数
复杂度：$O(Qlog(x+y))$

只要能想到题解中的 任意时刻，能到达的点集可使用两个基向量表示，该题就很简单了
简单模拟下，乱搞就过了，可以让其中一个基向量平行与x轴或者y轴，可以减少很多情况

---

#include
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define pii pair
#define pll pair
template<class T> using vc = vector;
template<class T> using vvc = vc>;

void solve()
{
    int n; cin >> n;
    pll a = { 0,0 }, b = { 0,0 };
    ll ans(0);
    rep(i, 1, n)
    {
        ll op, x, y, w;
        cin >> op >> x >> y;
        if (op == 1) // 操作1
        {
            while (x)
            {
                ll d = a.fi / x;
                a.fi -= d * x; a.se -= d * y;
                swap(x, a.fi); swap(y, a.se);
            }
            if (y) b.se = __gcd(b.se, abs(y));
            if (b.se) a.se %= b.se;
        }
        else // 操作2
        {
            cin >> w;
            if (a.fi)
            {
                ll d = x / a.fi;
                x -= d * a.fi; y -= d * a.se;
            }
            if (b.se) y %= b.se;
            if (!x && !y) ans += w;
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    cin >> T;
    rep(i, 1, T)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}

---

K. Kingdom's Power

知识点：树形dp
复杂度：$O(nlogn)$

头一次被卡常，2s时限，1800ms过的，一开始使用vector开空间有个小常数T了

对于每一个点来说，我们按照子树的最大深度进行排序，
除了去第一颗子树的士兵一定是从根节点来的，
否则我们需要考虑去当前子树的士兵是从根节点来的还是上一颗子树的最大深度来的
简单的都不像树形dp，有点像套着树形dp的贪心

---

#include
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define pii pair
#define pll pair
#define int ll
template<class T> using vc = vector;
template<class T> using vvc = vc>;

const int N = 1e6 + 5;

vc<int> h[N];
int len[N], d[N];

void dfs(int u)
{
    for (auto v : h[u])
    {
        d[v] = d[u] + 1;
        dfs(v);
        len[u] = max(len[u], len[v] + 1);
    }
}

bool cmp(int a, int b) { return len[a] < len[b]; }

ll ans = 0;
void dfs2(int u)
{
    sort(h[u].begin(), h[u].end(), cmp);
    int lim = h[u].size();
    if (lim) dfs2(h[u][0]);
    rep(i, 1, lim - 1)
    {
        ans += min(d[u], len[h[u][i - 1]] + 1);
        dfs2(h[u][i]);
    }
}

void solve()
{
    int n; cin >> n;
    rep(i, 1, n)
    {
        h[i].clear();
        len[i] = d[i] = 0;
    }
    ans = n - 1;
    rep(i, 2, n)
    {
        int f; cin >> f;
        h[f].push_back(i);
    }
    dfs(1);
    dfs2(1);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    cin >> T;
    rep(i, 1, T)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}

---

1. 当一个人的两个分数都大于此时的最大值时，该最大值不合法 ↩︎

2. 如果另一个连通块是树(树有n个点，n-1条边),则该连通块的权值会+1+(n-1)-n，如果有更多的边时，答案会更优 ↩︎