91709102 AGC001

Mysterious Light

给定光源，求按照题意规则反射的总距离

很容易观察出该题的重复子结构，每次可以看作从一个平行四边形的右下角向外发射，不妨设 \((a,\ b)\) 来表示平行四边形的两边即初始状态有 \((n-x,\ x)\)

我们尝试用 \((a,\ b)\) 推出下一个平行四边形的状态，显然 \[ (a,\ b)\rightarrow \begin{cases} \ (a-b,\ b),\ a > b\\\\ \ (a,\ b-a),\ b > a \end{cases} \]

显然终止状态为二元组其中一个变为 \(0\) 时

设 \(f(a,\ b)\) 为 \((a,\ b)\) 到达终止状态的路径则有

\[ f(a,\ b)\ =\ \begin{cases} 2b+f(a-b,\ b),\ a > b\\\\ 2a+f(a,\ b-a),\ b > a\\\\ a,\ a\ = b \end{cases} \]

很容易观察到这是一个更相减损的过程并用辗转相除优化

进一步的，我们观察最后路径会发现，不重不漏的走过所有轨迹三角形下面的边的路径总长度为 \(n-(n,\ x)\)，这样即可快速的出答案

#include <algorithm>
#include <cctype>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long int64;
inline int64 read(int64 f = 1, int64 x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
int64 n, x;
int main()
{
    n = read(), x = read(); 
    printf("%lld\n", 3*(n-__gcd(n, x)));
    return 0;
}

Shorten Diameter

删除一些点，使树的直径小于等于K，当且仅当删除某点不会对树的联通性产生影响时才可以删除，求最少点数

我们注意到 \(n\) 的范围，这道题一定是一道枚举，观察到最终的树一定存在一个中心，且当 \(n\) 是奇数时，最终中心是一条边，\(n\) 是偶数时，最终中心是一条边，枚举中心即可

#include <algorithm>
#include <cctype>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e3+5;
struct Edge
{
    int next, to;
    Edge(int next = 0, int to = 0):next(next), to(to) {};
}edge[N<<1];
int head[N], tot;
void _add(int x, int y) { edge[++tot] = Edge(head[x], y); head[x] = tot; }
void add(int x, int y) { _add(x, y); _add(y, x); }
int n, k;
void dfs(int x, int fa, int *d)
{
    for(int i = head[x]; i; i = edge[i].next)   
    {
        int y = edge[i].to; if(y == fa) continue;
        d[y] = d[x]+1; dfs(y, x, d);
    }
}
int d[N][N], ans;
int main()
{
    n = read(), k = read(), ans = n;
    for(int i = 1; i < n; ++i) 
    {
        int x = read(), y = read();
        add(x, y);
    }
    for(int x = 1; x <= n; ++x) dfs(x, 0, d[x]);
    if(k&1)
    {
        for(int i = 1; i <= tot; i += 2)
        {
            int u = edge[i].to, v = edge[i+1].to, c = 0;
            for(int y = 1; y <= n; ++y) c += d[u][y] > k/2&&d[v][y] > k/2;
            ans = min(ans, c);
        }
    }
    else
    {
        for(int x = 1; x <= n; ++x) 
        {
            int c = 0;
            for(int y = 1; y <= n; ++y) c += d[x][y] > k/2;
            ans = min(ans, c);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Arrays and Palindrome

给定数列 \(A\) 并给 \(A\) 进行重排序，并构造数列 \(B\)，满足 \(\sum_A=\sum_B\) 并确定两种字符串的回文串划分使得字符串只能由同种字符构造

通过手算样例过程中的推理建成图论模型，注意到这是一个一笔画问题，且 \(A\) 中奇数个数不超过 \(2\)，模拟构造即可

#include <algorithm>
#include <cctype>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{   
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e5+5;
int n, m;
int a[N], b[N], cnt, ans;
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) a[i] = read(), cnt += (a[i]&1);
    if(cnt > 2) return puts("Impossible"), 0;
    for(int i = 1; i <= m; ++i) if(a[i]&1) swap(a[i], a[1]), i = m;
    for(int i = 2; i <= m; ++i) if(a[i]&1) swap(a[i], a[m]);
    if(a[1] != 1) b[++ans] = a[1]-1;
    for(int i = 2; i < m; ++i) b[++ans] = a[i]; b[++ans] = n;
    for(int i = 1; i < ans; ++i) b[ans] -= b[i];
    for(int i = 1; i <= m; ++i) printf("%d ", a[i]); puts("");
    printf("%d\n", ans);
    for(int i = 1; i <= ans; ++i) printf("%d ", b[i]); puts("");
    return 0;
}

BBQ Hard

给定数对 \((a,\ b)\) 求 \(\sum_{i=1}^n\sum_{j=i+1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}\)

考虑 \(\binom{a_i+b_i+a_j+b_j}{a_i+a_j}\) 的几何意义，即从 \((0,\ 0)\) 向上或向左到达 \((a_i+a_j,\ b_i+b_j)\) 的方案数，所以不妨平移一下即有 \((-a_i,\ -b_i)\) 到 \((a_j,\ b_j)\) 的方案数， \(O(n^2)\) 的 \(DP\) 即可

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e5+5, M = 4000+5, B = 2001, P = 1e9+7;
int n, a[N], b[N], fac[N], inv[N], ifac[N];
int f[M][M], ans;
int C(int n, int m) { return 1ll*fac[n]*ifac[n-m]%P*ifac[m]%P; }
int main()
{
    n = N-5, inv[1] = fac[0] = ifac[0] = 1;
    for(int i = 2; i <= n; ++i) inv[i] = 1ll*(P-P/i)*inv[P%i]%P;
    for(int i = 1; i <= n; ++i) fac[i] = 1ll*fac[i-1]*i%P, ifac[i] = 1ll*ifac[i-1]*inv[i]%P;
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = read(), ++f[B-a[i]][B-b[i]];
    for(int i = 1; i < M; ++i)
        for(int j = 1; j < M; ++j)
            f[i][j] = (f[i][j]+(f[i-1][j]+f[i][j-1])%P)%P;
    for(int i = 1; i <= n; ++i) 
        ans = (ans+f[B+a[i]][B+b[i]])%P, 
        ans = (1ll*ans+P-C(2*(a[i]+b[i]), 2*a[i]))%P;
    ans = 1ll*ans*inv[2]%P;
    printf("%d\n", ans);
    return 0;
}

Wide Swap

给定排列 \(P\)，当且仅当 \(i,\ j\) 满足 \(|p_i-p_j|=1\) 且 \(|i-j|\ge k\) 是可以交换 \(p_i\) 和 \(p_j\) 求最终字典序最小的排列

直接用题干的条件做极其困难，所以有一种十分启发性的想法

我们把下标和权值交换位置，即构造序列 \(q_{p_i}\ =\ i\) 我们发现这样构造拥有十分好的性质

首先交换就变成当 \(|q_i-q_{i+1}|\ge k\) 时交换 \(q_i\) 和 \(q_{i+1}\) 所以对于 \(q_i\) 而言，\(q_j\in\ [q_i-k+1,\ q_i+k-1]\) 永远不会在它前面

其次，最终要求的字典序最小可以理解为下标尽量小，权值尽量小，拓扑排序过程贪心即可

同时我们手算样例的过程中发现建图可以优化边数，用线段树维护偏序即可

#include <cctype>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 5e5+5, INF = 0x3f3f3f3f;
struct Edge
{
    int next, to; 
    Edge(int next = 0, int to = 0):next(next), to(to) {};
}edge[N<<1];
int tot, head[N], in[N];
void add(int x, int y) { edge[++tot] = Edge(head[x], y); head[x] = tot; ++in[y]; }
int val[N<<2];
void change(int x, int l, int r, int pos, int d)
{
    val[x] = min(val[x], d); if(l == r) return;
    int mid = (l+r)>>1;
    if(pos <= mid) return change(x<<1, l, mid, pos, d);
    else return change(x<<1|1, mid+1, r, pos, d);
}
int query(int x, int l, int r, int ql, int qr)
{
    if(ql > qr) return INF;
    if(ql <= l&&r <= qr) return val[x];
    int ret = INF, mid = (l+r)>>1;
    if(ql <= mid) ret = min(ret, query(x<<1, l, mid, ql, qr));
    if(qr > mid) ret = min(ret, query(x<<1|1, mid+1, r, ql, qr));
    return ret;
}
int n, m, k, ans[N], p[N];
priority_queue<pair<int, int> > q;
int main()
{
    memset(val, 0x3f, sizeof(val)); 
    n = read(), k = read();
    for(int i = 1; i <= n; ++i) p[read()] = i;
    for(int x = n, y; x; --x)
    {
        y = query(1, 1, n, max(p[x]-k+1, 1), p[x]-1); if(y != INF) add(x, y);
        y = query(1, 1, n, p[x]+1, min(p[x]+k-1, n)); if(y != INF) add(x, y);
        change(1, 1, n, p[x], x);
    }
    for(int x = 1; x <= n; ++x) if(!in[x]) q.push(make_pair(-p[x], x));
    while(q.size())
    {
        int x = q.top().second; q.pop();
        ++m; ans[p[x]] = m;
        for(int i = head[x]; i; i = edge[i].next)   
        {
            int y = edge[i].to;
            if(--in[y] == 0) q.push(make_pair(-p[y], y));
        }
    }
    for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}