ARC155比赛笔记

比赛传送门

发现自己的恶性循环：自闭打unr->打的挺好->自信满满打rated->掉分->自闭打unr

A - ST and TS Palindrome

给定长度为 $n$ 的字符串 $S$ 和一个数 $k$，问是否存在一个长度为 $k$ 的字符串 $T$ 满足字符串 $S+T$ 和 $T+S$ 都是回文串。
$n \le 2\cdot 10^5,k \le 10^{18}$

Tag: 字符串

设 $S$ 倒转后得到 $S’$。

考虑如果 $k>2n$，那么 $S’$ 必定是 $T$ 的前缀和后缀，设 $T=S’+t+S’$。

所以可以得到 $S+S’+t+S’$ 和 $S’+t+S’+S$ 都是回文串，进而得到 $S’+t$ 和 $t+S’$ 都是回文串。

简单分析可知，“$S’+t$ 和 $t+S’$ 都是回文串”与“ $S+t$ 和 $t+S$ 都是回文串”是等价的，所以整个转化过程就相当于把 $k$ 缩小了 $2n$。

这样一直转化下去，最后相当于把 $k$ 模上 $2n$。

之后分成 $k=0,1\le k \le n$ 和 $n+1\le j \le 2n-1$ 讨论，具体过程比较简单，这里就不赘述了。

Code

ll n, k;
string s, t;
bool ans;
bool check(string st) {
    rep(i, st.size())if (st[i] != st[st.size() - 1 - i])return 0;
    return 1;
}
void solve() {
    cin >> n >> k >> s;
    k %= 2 * n;
    if (!k)ans = check(s);
    else if (k <= n) {
        t = s.substr(0, k);
        reverse(t.begin(), t.end());
        ans = check(s + t) & check(t + s);
    }
    else {
        t = "";
        rep(i, k)t += '1';
        rep(i, n)t[i] = s[n - 1 - i];
        ans = 1;
        rep(i, n) {
            if (t[k - 1 - i] != '1' && t[k - 1 - i] != s[i])ans = 0;
            t[k - 1 - i] = s[i];
        }
        if (ans)ans = check(s + t) & check(t + s);
    }
    if (ans)cout << "Yes\n";
    else cout << "No\n";
}

B - Abs Abs Function

有一个非负整数对的集合 $T$，初始时 $T={A,B}$。每次操作，要么向 $T$ 中加入一个元素，要么给定区间 $[l,r]$，查询 $\min\limits_{x\in [l,r],(a,b)\in T} \lvert\lvert x-a \rvert -b \rvert$。
$q \le 2\cdot 10^5,A,B,l,r \le 10^9$

Tag: 数学

查询的东西函数图像画出来是一个 W。其实可以转化成 $\min{\lvert a+b-x\rvert,\lvert a-b-x\rvert}$。刚好它要求的也是 min，所以就拆成两个数 $a+b$ 和 $a-b$，查询改为 $\min\limits_{x\in [l,r],y\in T} \lvert x-y\rvert$。
这个东西用 set 维护一下就行了。

Code

ll q, t, a, b;
set<ll>s;
void solve() {
    cin >> q >> a >> b;
    s.insert(a + b), s.insert(a - b);
    while (q--) {
        cin >> t >> a >> b;
        if (t == 1)s.insert(a + b), s.insert(a - b);
        else {
            auto p = s.lower_bound(a);
            ll ans = MAXN;
            if (p != s.end()) {
                int x = *p;
                if (x <= b)ans = 0;
                else ans = x - b;
            }
            if (p != s.begin()) {
                p--;
                int x = *p;
                ans = min(ans, a - x);
            }
            cout << ans << endl;
        }
    }
}