2019 ICPC XuZhou Regional Online Contest

比较水的一场。

题目链接：https://www.jisuanke.com/contest/3005?view=challenges

---

A：

CRT可以抄板子解决，就算看不出斐波那契博弈，推一下必胜必败点就能猜出来。

可惜当时在切M，推完SG来不及做。待补。

B：

被卡常卡飞的题，最后还是卡常搞过去的。明明都是并查集为啥我们T飞啊。

/* Contest xuzhou_2019_online
 * Problem B
 * Team: Make One For Us
 */
#include <bits/stdc++.h>

using namespace std;

int read(void) {
    char ch;
    do {
        ch = getchar();
    } while (!isdigit(ch));
    int ret = 0;
    while (isdigit(ch)) {
        ret *= 10;
        ret += ch - '0';
        ch = getchar();
    };
    return ret;
}

struct range {
    int l, r;
    bool operator < (const range &r) const {
        return l < r.l;
    }
};

int main(void) {
    int n, q;
    n = read();
    q = read();
    unordered_map <int, int> mp;
    vector <pair <int, int>> query(q);
    // vector <int> nums(2 * q + 1);
    set <range> st;
    // nums[0] = -1;
    for (int i = 0; i < q; i++) {
        query[i].first = read();
        query[i].second = read();
        // nums[1 + i] = query[i].second;
        // nums[1 + i + q] = query[i].second + 1;
    }
    // nums.emplace_back(n + 1);
    // sort(nums.begin(), nums.end());
    // nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
    // for (unsigned int i = 0; i < nums.size(); i++) {
    //     mp[nums[i]] = i;
    // }
    // for (int i = 0; i < q; i++) {
    //     query[i].second = mp[query[i].second];
    // }
    for (int i = 0; i < q; i++) {
        // for (auto e: st) {
        //     cout << e.l << ", " << e.r << endl;
        //     cout << "_____________" << endl;
        // }
        auto t = query[i].second;
        if (query[i].first == 1) {
            // delete nums[t]
            auto next = st.upper_bound({t, 0});
            range nxt = {t, t};
            if (next != st.begin()) { // 它有前驱(prev)也有后继(next)
                auto prev = next;
                prev--;
                if (prev->l <= t && t <= prev->r) { // 已经存在这样的区间
                    continue;
                } else { // 需要进行更新
                    if (prev->r + 1 == t) { // 可以和左侧合并
                        nxt.l = prev->l;
                        st.erase(prev);
                    }
                }
            }
            if (next != st.end()) {
                if (next->l == t + 1) { // 可以和右侧合并
                    nxt.r = next->r;
                    st.erase(next);
                } 
            }
            st.emplace(nxt);

        } else if (query[i].first == 2) {
            // 是否被包含？
            auto next = st.upper_bound({t, 0});
            if (next != st.begin()) {
                auto prev = next;
                prev--;
                if (prev->l <= t && t <= prev->r) { // 已经存在包含它的区间
                    int ans = prev->r + 1;
                    printf("%d
", ans == n + 1 ? -1 : ans); // 输出答案
                } else { 
                    printf("%d
", t); // 不存在包含它的区间，答案是自身
                }
            } else { // 没有找到，不被包含
                printf("%d
", t);
            }

        }
    }
    return 0;
}

C：

签到，出题人工地英语，原题是Codeforces 4A。

#include<bits/stdc++.h>

using namespace std;

int main()
{    
    int n;
    cin >> n;
    if(n >= 4&&n % 2 == 0){
        cout << "YES" <<endl;
    }else {
        cout << "NO" << endl;
    }

    return 0;
}

D：

因为数据范围很小，就变成了1000次KMP的无脑题。

#include<bits/stdc++.h>

using namespace std;
const int maxn = 200000;

void getFail(char* p,int* nxt)
{
    int m = strlen(p);
    nxt[0] = 0;nxt[1] = 0;
    for(int i = 1;i < m;i++){
        int j = nxt[i];
        while(j && p[i] != p[j]) j = nxt[j];
        nxt[i+1] = p[i] == p[j] ? j + 1:0;
    }
}

bool find(char* T,char* P,int *f){
    int n = strlen(T),m = strlen(P);
    getFail(P,f);
    int j = 0;
    for(int i = 0;i < n;i++){
        while(j && P[j] != T[i]) j = f[j];
        if(P[j] == T[i]) j++;
        if(j == m){
            return true;
        }
    }
    return false;
}
int nxt[maxn];
void init(int n)
{
    for(int i =0;i <= n;i++){
        nxt[i] = 0;
    }
}


int main()
{
    char T[maxn];
    scanf("%s",T);
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        char s[maxn];
        scanf("%s",s);
        int len1= strlen(T);
        int len2 = strlen(s);
        init(max(len1,len2));
        if(len1 > len2){
            if(find(T,s,nxt)){
                printf("my child!
");
            }else {
                printf("oh, child!
");
            }
        }else if(len1 == len2){
            if(find(T,s,nxt)){
                printf("jntm!
");
            }else {
                printf("friend!
");
            }
        }else{
            if(find(s,T,nxt)){
                printf("my teacher!
");
            }else {
                printf("senior!
");
            }
        }
    }
    return 0;
}

E：

把数组元素和下标绑定后按数组元素值升序排序，对于每一个元素a[i]，答案就是区间[i+1,n]里元素对应下标的最大值。线段树即可。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

int read(void) {
    char ch;
    do {
        ch = getchar();
    } while (!isdigit(ch));
    int ret = 0;
    while (isdigit(ch)) {
        ret *= 10;
        ret += ch - '0';
        ch = getchar();
    };
    return ret;
}

const int maxn = 5e5 + 10;
struct Node {
    int maxn;
} segt[maxn << 2];

int n, m, ans[maxn];
pair<int, int> a[maxn];

void maintain(int curpos) {
    segt[curpos].maxn = max(segt[lson].maxn, segt[rson].maxn);
}

void build(int curpos, int curl, int curr) {
    if (curl == curr) {
        segt[curpos].maxn = a[curl].second;
        return;
    }
    int mid = curl + curr >> 1;
    build(lson, curl, mid); build(rson, mid + 1, curr);
    maintain(curpos);
}

int query(int curpos, int curl, int curr, int ql, int qr) {
    if (ql <= curl && curr <= qr) {
        return segt[curpos].maxn;
    }
    int mid = curl + curr >> 1, ret = -1;
    if (ql <= mid) ret = max(ret, query(lson, curl, mid, ql, qr));
    if (mid < qr) ret = max(ret, query(rson, mid + 1, curr, ql, qr));
    return ret;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        a[i].first = read();
        a[i].second = i;
    }
    sort(a + 1, a + 1 + n);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        if (i == n) {
            ans[a[i].second] = -1;
            break;
        }
        int queryL = lower_bound(a + 1, a + 1 + n, mp(a[i].first + m, 0)) - (a + 1) + 1;
        int maxPos = query(1, 1, n, queryL, n);
        if (maxPos > a[i].second) ans[a[i].second] = maxPos - a[i].second - 1;
        else ans[a[i].second] = -1;
    }
    for (int i = 1; i < n; i++) printf("%d ", ans[i]);
    printf("%d
", ans[n]);
    return 0;
}

G：

Manacher魔改一下就能过的题。待补。

K：

O(n^2logn)暴力贪心。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 200000;

const double eps = 1e-3;
bool dcmp(double x,double y)
{
    if(abs(x - y) < eps){
        return true;
    }else {
        return false;
    }
}
struct Point{
    double x,y;
    bool operator == (Point rhs)const{
        return (dcmp(x,rhs.x) && dcmp(y,rhs.y));
    }
    bool operator < (Point rhs)const{
        if(dcmp(x,rhs.x)){
            return y < rhs.y;
        }else {
            return x < rhs.x;
        }
    }
}P[maxn];
vector<Point> vec;
set<Point> S;
bool CMP(Point p1,Point p2)
{
    if(dcmp(p1.x,p2.x)){
        return p1.y < p2.y;
    }else {
        return p1.x < p2.x;
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> P[i].x >> P[i].y;
    }
    if(n == 1 || n == 2){
        cout << 0 << endl;
        return 0;
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(i == j) continue;    
            Point val;
            val.x = P[i].x + P[j].x;
            val.y = P[i].y + P[j].y;
            val.x /= 2.0;
            val.y /= 2.0;
            vec.push_back(val);
        }
    }
    for(int i = 1;i <= n;i++){
        vec.push_back(P[i]);
    }
    sort(vec.begin(),vec.end(),CMP);
    int mx = 0;
    int tot = 1;
    Point pos; 
    for(int i = 1;i < vec.size();i++){
        if(mx < tot){
            mx = tot;
            pos.x = vec[i].x;
            pos.y = vec[i].y;
        }
        if(vec[i] == vec[i-1]){
            tot++;
        }else {
            tot = 1;
        }
        if(mx < tot){
            mx = tot;
            pos.x = vec[i].x;
            pos.y = vec[i].y;
        }
    }
    for(int i = 1;i <= n;i++){
        S.insert(P[i]);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        Point Sym;
        Sym.x = pos.x + (pos.x - P[i].x);
        Sym.y = pos.y + (pos.y - P[i].y);
        if(!S.count(Sym)){
            ans ++ ;
        }
    }
    cout << ans << endl;
    return 0;
}

M：

队友说的记录26个字母位置乱搞完事(好像很真)。

/* Contest xuzhou_2019_online
 * Problem M
 * Team: Make One For Us
 */
#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    string a, b;
    vector <int> pos[26];
    cin >> n >> m;
    cin >> a >> b;
    int ptr = 0;
    // record position of each letter
    for (unsigned int i = 0; i < a.length(); i++) {
        pos[a[i] - 'a'].emplace_back(i);
    }
    int ans = -1;
    // for each letter in target string
    for (unsigned int i = 0; i < b.length(); i++) {
        int cur = b[i] - 'a';
        // try to find the same letter (cur)
        auto self = lower_bound(pos[cur].begin(), pos[cur].end(), ptr);
        for (int nxt = cur + 1; nxt < 26; nxt++) {
            auto upgrade = lower_bound(pos[nxt].begin(), pos[nxt].end(), ptr);
            if (upgrade != pos[nxt].end()) {
                auto p = *upgrade;
                ans = max(ans, (int) (i + a.length() - p));
            }
        }
        if (self != pos[cur].end()) {
            // found the letter, continue
            ptr = *self + 1; // take *self, go on
            if (i + 1 == b.length()) {
                ans = max(ans, (int) (i + a.length() - ptr + 1));
                if (ans == b.length()) {
                    ans = -1;
                }
            }
        } else {
            // not found
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

// [abcd]
//  0123