第二届图灵杯个人题解

• 更好的阅读体验：点这

A 改bug

• 签到题，没啥好说的，转义字符也没有，直接输出He1I0ωorld！即可

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;

void solve() {
    printf("He1I0ωorld！");
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // cin >> t;
    t = 1;
    while(t--) solve();
    return 0;
}

B 幂之和

• $1\le x\le 10001\backslash le\; x\; \backslash le\; 1000$1≤x≤1000，太小了，直接打表判定，下面程序没有任何优化，纯粹的暴力

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
ll t, n, m, arr[N];
map<ll, bool> mp;
void solve() {
    for(ll i = 1; i <= 1000; ++i) {
        for(ll j = 1; j <= 1000; ++j) {
            ll a = i * i * i, b = j * j * j;
            if(a + b > 1000) break;
            mp[a + b] = 1;
        }
    }
    cin >> n;
    if(mp[n]) cout << "YES" << endl;
    else cout << "NO" << endl;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // cin >> t;
    t = 1;
    while(t--) solve();
    return 0;
}

C 求弧长

• 第一种情况，$\beta =\pi -\alpha \backslash beta\; =\; \backslash pi\; -\; \backslash alpha$β=π−α，可在$△ABC\backslash triangle\; ABC$△ABC中，根据$A{C}^2=A{B}^2+B{C}^2-2ABBC\cos \alpha AC^2\; =\; AB^2\; +\; BC^2\; -\; 2ABBC\backslash cos\{\backslash alpha\}$AC2=AB2+BC2−2ABBCcosα求出$\alpha =arccos\frac{A{B}^2+B{C}^2-A{C}^2}{2ABBC}\backslash alpha\; =\; arccos\{\backslash frac\{AB^2\; +\; BC^\; 2\; -\; AC^2\}\{2ABBC\}\}$α=arccos2ABBCAB2+BC2−AC2​，再求出$\beta =\pi -\alpha \backslash beta\; =\; \backslash pi\; -\; \backslash alpha$β=π−α。答案即为$\beta \ast r\backslash beta\; *\; r$β∗r
• 第二种情况，利用$G{I}^2=r^2+r^2-2r^2\cos \gamma GI^2\; =\; r^2\; +\; r^2\; -\; 2r^2\backslash cos\{\backslash gamma\}$GI2=r2+r2−2r2cosγ，$\gamma =arccos\frac{2r^2-G{I}^2}{2r^2}\backslash gamma\; =\; arc\; cos\{\backslash frac\{2r^2\; -\; GI^2\}\{2r^2\}\}$γ=arccos2r22r2−GI2​可以求出$\gamma \backslash gamma$γ，$ans=\gamma \ast rans\; =\; \backslash gamma\; *\; r$ans=γ∗r
• 判定是哪种情况：
• 设圆心为$OO$O，两条线同圆交点分别为$P,QP,Q$P,Q；考虑$△PQO\backslash triangle\; PQO$△PQO，可得$P{Q}^2=r^2+r^2-2r^{2}cos\beta PQ^2\; =\; r^2\; +\; r^2\; -\; 2r^2cos\backslash beta$PQ2=r2+r2−2r2cosβ；即$PQ=\sqrt{2r^2(1-cos\beta )}PQ\; =\; \backslash sqrt\{2r^2(1\; -\; cos\backslash beta)\}$PQ=2r2(1−cosβ)​。判定$ABAB$AB和$PQPQ$PQ的大小即可，若$PQ>ABPQ\; >\; AB$PQ>AB则为情况二，否则为一

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const double pi = acos(-1);
const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
ll t;
double dis(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void solve() {
    double xa, xb, xc, ya, yb, yc, r;
    scanf("%lf %lf %lf %lf %lf %lf %lf", &xa, &ya, &xb, &yb, &xc, &yc, &r);
    double AB = xb - xa, AC = dis(xa, ya, xc, yc), BC = dis(xb, yb, xc, yc);
    double theta = acos((AC * AC + BC * BC - AB * AB) / (2 * AC * BC));
    double gamma = pi - theta;
    double PQ = sqrt(2*r*(1 - cos(gamma)));
    if(PQ - AB >= eps) {
        double beta = acos((2 * r - AB * AB) / (2 * r));
        printf("%.6lf\n", beta * sqrt(r));
    } else {
        printf("%.6lf\n", gamma * sqrt(r));
    }
}

signed main() {
    cin >> t;
    while(t--) solve();
    return 0;
}

D 模模模

• 直接猜lcm(a,b) + 1然后就AC了，设$x=k_{1}a+1=k_{2}b+1x\; =\; k\_1a\; +\; 1\; =\; k\_2b\; +\; 1$x=k1​a+1=k2​b+1，所以$k_{1}a=k_{2}bk\_1a\; =\; k\_2b$k1​a=k2​b，若要使得$xx$x最小，则$k_1,k_{2}k\_1,k\_2$k1​,k2​尽可能小，即：$lcm(a,b)=k_{1}a=k_{2}blcm(a,b)\; =\; k\_1a\; =\; k\_2b$lcm(a,b)=k1​a=k2​b最优，所以$x=lcm(a,b)+1x\; =\; lcm(a,b)\; +\; 1$x=lcm(a,b)+1
• 补充一句：$a\ast b=gcd(a,b)\ast lcm(a,b)a*b\; =\; gcd(a,b)*lcm(a,b)$a∗b=gcd(a,b)∗lcm(a,b)。求$lcmlcm$lcm时一般先除后乘防溢出（即$lcm=a/gcd\ast blcm\; =\; a/gcd*b$lcm=a/gcd∗b而不是$lcm=ab/gcdlcm\; =\; ab/gcd$lcm=ab/gcd）

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll t, n, m, arr[N];

void solve() {
    ll a, b;
    cin >> a >> b;

    ll lcm = a / __gcd(a, b) * b;
    cout << lcm + 1 << endl;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    // t = 1;
    while(t--) solve();
    return 0;
}

E Magic Stone Merging

• k<0的情况已经被叉了，现在$k\ge 0k\; \backslash ge\; 0$k≥0

• 很容易看出来是直接排，从大到小选，难度主要是后面的处理问题。这里稍微证一下怎么选

• 假设对序列$a_1,a_2\cdots a_{n}a\_1,a\_2\backslash cdots\; a\_n$a1​,a2​⋯an​考虑如何使得其结果更大。

• $val=(\cdots ((a_1{a}_2+k)a_3+k)\cdots )a_n+kval\; =\; (\backslash cdots((a\_1\; a\_2\; +\; k)\; a\_3\; +\; k)\backslash cdots)a\_n\; +\; k$val=(⋯((a1​a2​+k)a3​+k)⋯)an​+k

  $=a_1{a}_2\cdots a_n+k(a_3{a}_4\cdots a_n+a_4{a}_5\cdots a_n+\cdots +a_n+1)=\; a\_1a\_2\backslash cdots\; a\_n\; +\; k(a\_3\; a\_4\; \backslash cdots\; a\_n\; +\; a\_4a\_5\; \backslash cdots\; a\_n\; +\backslash cdots\; +a\_n+\; 1)$=a1​a2​⋯an​+k(a3​a4​⋯an​+a4​a5​⋯an​+⋯+an​+1) $={\prod }_{i=1}^n{a}_i+k\left(\right({\sum }_{i=3}^n{\prod }_i^n{a}_i)+1)=\; \backslash prod\_\{i\; =\; 1\}^\{n\}\; a\_i\; +\; k((\backslash sum\_\{i\; =\; 3\}\; ^\; \{n\}\; \backslash prod\_\{i\}^\{n\}a\_i)\; +\; 1)$=∏i=1n​ai​+k((∑i=3n​∏in​ai​)+1)

• 显然只有$k\left(\right({\sum }_{i=3}^n{\prod }_i^n{a}_i)+1)k((\backslash sum\_\{i\; =\; 3\}\; ^\; \{n\}\; \backslash prod\_\{i\}^\{n\}a\_i)\; +\; 1)$k((∑i=3n​∏in​ai​)+1)影响最后结果，这个式子$a_{i}a\_i$ai​越靠后，影响越大。要使得这个式子最大，即从小往大排列$a_{i}a\_i$ai​即可

• 但是由于有取模的存在，直接使用堆去存权值会出问题。所以考虑设置顶标$toptop$top去标记取模后的相对大小参考，并作为堆的$ke{y}_{1}key\_1$key1​，权值作为堆的$ke{y}_{2}key\_2$key2​

• 多提一句顶标的事，顶标有且仅有在$valval$val溢出$modmod$mod时使用，此后顶标作为排序参考，而$ke{y}_{2}key\_2$key2​（即$valval$val）仅用于去更新下一个$valval$val。而在没溢出的时候，用不上顶标

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
ll t, n, k, arr[N];
void solve() {
    cin >> n >> k;
    ll ans = 0;
    for(int i = 1; i <= n; ++i) cin >> arr[i];
    int top = 0, flag = 0;
    if(k > 0) {
        priority_queue<pair<ll, ll> , vector<pair<ll, ll> > , greater<pair<ll, ll> > > q;
        for(int i = 1; i <= n; ++i) q.push({0, arr[i]});
        while(q.size() > 1) {
            pair<ll, ll> a = q.top(); q.pop();
            pair<ll, ll> b = q.top(); q.pop();
            ll val2 = a.second * b.second + k;
            if(val2 >= mod || flag) q.push({++top, val2 % mod}), flag = 1;
            else q.push({0, val2});
        }ans = q.top().second;
    } else {
        for(int i = 1; i <= n; ++i) ans = ans * arr[i] % mod;
    }
    cout << ans % mod << endl;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // cin >> t;
    t = 1;
    while(t--) solve();
    return 0;
}

F 向上取整

• （牛客sqrt形式不正确，这里改成图片）

（图片看不清参考下面）

• 考虑取$now=\lceil \sqrt{n}\rceil now\; =\; \backslash lceil\; \backslash sqrt\{n\}\backslash rceil$now=⌈n​⌉，对$[now+1,n-1][now\; +\; 1,\; n\; -\; 1]$[now+1,n−1]中任意的$ii$i进行$\lceil \frac{arr\left[i\right]}{arr\left[n\right]}\rceil \to 1\backslash lceil\; \backslash frac\{arr[i]\}\{arr[n]\}\backslash rceil\; \backslash to\; 1$⌈arr[n]arr[i]​⌉→1，再进行两次$\lceil \frac{a\left[n\right]}{a\left[now\right]}\rceil \to \lfloor \sqrt{n}\rfloor \to 1\backslash lceil\; \backslash frac\{a[n]\}\{a[now]\}\; \backslash rceil\; \backslash to\; \backslash lfloor\; \backslash sqrt\{n\}\backslash rfloor\; \backslash to\; 1$⌈a[now]a[n]​⌉→⌊n​⌋→1。最后将$n=now,now=\lceil \sqrt{n}\rceil n=\; now,now\; =\; \backslash lceil\; \backslash sqrt\{n\}\backslash rceil$n=now,now=⌈n​⌉。循环以上过程，直到合法停止（即$now=n=2now\; =\; n\; =\; 2$now=n=2时）
• 下面证明以上构造合法：
• 对于每次循环，对$[now+1,n-1][now\; +\; 1,\; n\; -\; 1]$[now+1,n−1]使用一次操作，对$nn$n使用两次操作。即在一次循环内，使得$k=n-nowk\; =\; n\; -\; now$k=n−now个数构造为$11$1，共使用$k+1k\; +\; 1$k+1次操作
• 由题意得最大操作次数为$n+6n\; +\; 6$n+6，则以上循环次数不超过$6+2=86\; +\; 2\; =\; 8$6+2=8次(前者为额外付出的预留次数，后者为序列$a_1,a_{2}a\_1,a\_2$a1​,a2​不需要操作剩余的操作次数)。即最坏情况下$\sqrt[8]{n_{max}}\ge 2\backslash sqrt[8]\{n\_\{max\}\}\; \backslash ge\; 2$8nmax​​≥2才符合条件，对于此题的$n_{max}=3\ast 10^{5}n\_\{max\}\; =\; 3*10^5$nmax​=3∗105是完全足够了的

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const double pi = acos(-1);
const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
ll t, n, arr[N], ans = 0;
vector<pair<int, int> > Move;
void tra(int l, int r) {
    for(int i = l + 1; i < r; ++i) {
        ++ans;
        Move.push_back({i, r});
    }ans += 2;
    Move.push_back({r, l});
    Move.push_back({r, l});
}

void solve() {
    cin >> n;
    ans = 0;
    Move.clear();
    for(int i = 1; i <= n; ++i) arr[i] = i;
    int now = ceil(sqrt(n));
    while(now >= 2 && n > 2) {
        tra(now, n);
        n = now;
        now = ceil(sqrt(n));
    }
    cout << ans << endl;
    for(auto i : Move) cout << i.first << " " << i.second << endl;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//别用sc和read
    cin >> t;
    // t = 1;
    while(t--) solve();
    return 0;
}

G Color Sequence

• $dsuontreedsu\backslash \; on\backslash \; tree$dsu on tree，树上启发式合并板子题
• 前置：树链剖分
• 题意就是给你一颗树，有边权。对上面每一个节点$uu$u，统计$uu$u的子树中，对称的链最长是多长。
• 对称：和回文意思一样，所有权中，出现奇数次的权最大有一个，其他权均为出现偶数次。考虑对权$1\le w\le 1\backslash le\; w\; \backslash le$1≤w≤状压映射到$2^{w}2^\{w\}$2w上，然后采用$XorXor$Xor统计映射权，最后的$ansans$ans若为$2^{k}2^k$2k则为合法路径
• 相同状压权值下，我们贪心的将其记录为深度更深的，可以证明答案是最大的
• 对于节点$uu$u而言，它的答案有以下方法得到，取$ans\left[u\right]=max(\cdots )ans[u]\; =\; max\{(\backslash cdots)\}$ans[u]=max(⋯)
  • 子树中最大的回文链长度
  • 选取节点$uu$u开始，与任一子链组成的回文链长度
  • 任意两个子链，经过$uu$u组成的回文链长度
• 然后先跑一遍树剖，把轻重链分出来($dfsdfs$dfs)
  • 先跑轻链，不留下它的影响，记录仅轻链答案
  • 再先跑重链，再跑轻链，记录重链所有的影响，算出含重链的答案
• $in\left[i\right]in[i]$in[i]记录状压权值为$ii$i的最深深度，$Xor\left[i\right]Xor[i]$Xor[i]统计$root\to iroot\backslash to\; i$root→i路径上的状压权值

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 5e5 + 7;
const int X = 23;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t, n, lca_dep = 0, maxx = 0, ans[N];
int hson[N], top[N], fa[N], dep[N], sz[N];
vector<pair<int, int> > G[N];
int Xor[1 << X], in[1 << X];

int dfs(int now, int depth) {
    dep[now] = depth + 1;
    hson[now] = 0, sz[now] = 1, sz[hson[now]] = 0;
    for(auto i : G[now]) {
        int to = i.first;
        if(dep[to]) continue;
        Xor[to] = (1 << i.second) ^ Xor[now]; 
        fa[to] = now;
        sz[now] += dfs(to, depth + 1);        
        if(sz[hson[now]] < sz[to]) hson[now] = to;
    }return sz[now];
}
void Clear(int now) {
    in[Xor[now]] = 0;
    for(auto i : G[now]) Clear(i.first);
}
void Updata(int now) {
    in[Xor[now]] = max(in[Xor[now]], dep[now]);
    for(auto i : G[now]) Updata(i.first);
}
void cal(int now) {
    if(in[Xor[now]]) maxx = max(maxx, in[Xor[now]] + dep[now] - lca_dep);
    for(int i = 1; i < (1 << X); i <<= 1) {
        if(in[i ^ Xor[now]]) maxx = max(maxx, dep[now] + in[i ^ Xor[now]]- lca_dep);
    }for(auto i : G[now]) cal(i.first);
}

void dsu(int now, bool ishson) {
    for(auto i : G[now]) {
        if(i.first == hson[now]) continue;
        dsu(i.first, false);
    }
    if(hson[now]) dsu(hson[now], true);
    lca_dep = dep[now] * 2;
    for(auto i : G[now]) maxx = max(maxx, ans[i.first]);
    for(auto i : G[now]) {
        if(hson[now] == i.first) continue;
        cal(i.first), Updata(i.first);
    }
    if(in[Xor[now]]) maxx = max(maxx, dep[now] + in[Xor[now]] - lca_dep);
    for(int i = 1; i < (1 << X); i <<= 1) {
        if(in[i ^ Xor[now]]) maxx = max(maxx, dep[now] + in[i ^ Xor[now]]- lca_dep);
    }
    if(!in[Xor[now]]) in[Xor[now]] = dep[now];
    ans[now] = maxx;
    if(!ishson) {
        maxx = 0;
        Clear(now);
    }
}

void solve() {
    cin >> n;
    for(int i = 2; i <= n; ++i) {
        int f, w;
        cin >> f >> w;
        G[f].push_back({i, w});
    }dfs(1, 1);
    dsu(1, true);
    for(int i = 1; i <= n; ++i) cout << ans[i] << " ";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//别用sc和read
    t = 1;
    while(t--) solve();
    return 0;
}