技术教程 2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) 正文

2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2022-11-12,,,,

这是一场三人组队赛来的，单人带电子模板不限时单挑试一下。按照难度排序。

B - Balls of Buma

题意：玩祖玛，射入任意颜色的球一个，当某段长度变长了且长度变长后>=3则这段就会消除，问把所有的球只用一次射击就消除的方法是多少？

题解：看起来一定要两边对称。

int n;

char s[300005];

int L[300005], R[300005], top;

void test_case() {

    top = 0;

    L[++top] = 1;

    R[top] = 1;

    for(int i = 2; i <= n; ++i) {

        if(s[i] == s[R[top]])

            R[top] = i;

        else {

            L[++top] = i;

            R[top] = i;

        }

    }

    if(!(top & 1)) {

        puts("0");

        return;

    }

    int mid = (top + 1) / 2;

    if(R[mid] == L[mid]) {

        puts("0");

        return;

    }

    for(int i = 1; i < mid; ++i) {

        if(s[R[mid - i]] != s[L[mid + i]]) {

            puts("0");

            return;

        } else {

            if(R[mid - i] - L[mid - i] + 1 + R[mid + i] - L[mid + i] + 1 < 3) {

                puts("0");

                return;

            }

        }

    }

    printf("%d\n", R[mid] - L[mid] + 1 + 1);

}

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    while(1) {

        n = reads(s + 1);

        test_case();

    }

}

L - Lexicography

题意：给n*l个字母，构造n个长为l的字符串，使得字典序最小的第k个字符串的字典序最小。

题解：别看错题了，下面的解法是错的。

int n, l, k;

char s[1000005];

void test_case() {

    sort(s + 1, s + 1 + n * l);

    int cur = l + 1;

    for(int i = 1; i < k; ++i) {

        for(int j = 1; j <= l; ++j) {

            putchar(s[cur]);

            ++cur;

        }

        putchar('\n');

    }

    for(int j = 1; j <= l; ++j)

        putchar(s[j]);

    putchar('\n');

    for(int i = k + 1; i <= n; ++i) {

        for(int j = 1; j <= l; ++j) {

            putchar(s[cur]);

            ++cur;

        }

        putchar('\n');

    }

}

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    while(1) {

        read(n), read(l), read(k);

        reads(s + 1);

        //puts(s + 1);

        test_case();

    }

}


int n, l, k;

char s[1000005];

char t[1005][1005];

void test_case() {

    sort(s + 1, s + 1 + n * l);

    int cur = 0;

    for(int j = 1; j <= l; ++j) {

        for(int i = 1; i <= k; ++i)

            t[i][j] = s[++cur];

        if(k == 1 || t[k][j] != t[k - 1][j]) {

            for(int tj = j + 1; tj <= l; ++tj)

                t[k][tj] = s[++cur];

            for(int ti = 1; ti < k; ++ti) {

                for(int tj = j + 1; tj <= l; ++tj)

                    t[ti][tj] = s[++cur];

            }

            break;

        }

    }

    for(int i = k + 1; i <= n; ++i) {

        for(int j = 1; j <= l; ++j)

            t[i][j] = s[++cur];

    }

    for(int i = 1; i <= n; ++i) {

        for(int j = 1; j <= l; ++j)

            putchar(t[i][j]);

        putchar('\n');

    }

}

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    while(1) {

        read(n), read(l), read(k);

        reads(s + 1);

        //puts(s + 1);

        test_case();

    }

}

但是这样填也不对，过不了这个样例：

4 4 4

abcdefabababcabc

aabc

abbd

abce

abcf

#至少应该是

aaef

abbd

abcc

abcc

不知道这样对不对？

int n, l, k;

char s[1000005];

char t[1005][1005];

void test_case() {

    sort(s + 1, s + 1 + n * l);

    int cur = 0, b = 1;

    for(int j = 1; j <= l; ++j) {

        for(int i = b; i <= k; ++i) {

            t[i][j] = s[++cur];

            if(i > 1 && t[i][j] > t[i - 1][j])

                ++b;

        }

        if(k == 1 || t[k][j] != t[k - 1][j]) {

            for(int tj = j + 1; tj <= l; ++tj)

                t[k][tj] = s[++cur];

            for(int ti = 1; ti < k; ++ti) {

                for(int tj = 1; tj <= l; ++tj)

                    if(t[ti][tj] == '\0')

                        t[ti][tj] = s[++cur];

            }

            break;

        }

    }

    for(int i = k + 1; i <= n; ++i) {

        for(int j = 1; j <= l; ++j)

            t[i][j] = s[++cur];

    }

    for(int i = 1; i <= n; ++i) {

        for(int j = 1; j <= l; ++j)

            putchar(t[i][j]);

        putchar('\n');

    }

}

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    while(1) {

        read(n), read(l), read(k);

        reads(s + 1);

        memset(t, '\0', sizeof(t));

        //puts(s + 1);

        test_case();

    }

}

还是WA29。发现应该把b++改成b=i，这样才对，因为可能会有连续几个一样的，一次跳过他们。变成WA45了，咋这么多数据呢？正式比赛可能都可以蒙混过关了。

多亏这两组样例发现了其实是有一定可能没有把其他字符串填满。

8 8 7

aaaaaaabbbbbbbbccccccccccddddddeeeeeeeffffffffgggggiiihhhhhhjjjj

8 8 2

aaaaaaabbbbbbbbccccccccccddddddeeeeeeeffffffffgggggiiihhhhhhjjjj

加油，看来单挑是有点难度，但是别怕。

int n, l, k;

char s[1000005];

char t[1005][1005];

void test_case() {

    sort(s + 1, s + 1 + n * l);

    int cur = 0, b = 1;

    for(int j = 1; j <= l; ++j) {

        for(int i = b; i <= k; ++i) {

            t[i][j] = s[++cur];

            if(i > 1 && t[i][j] > t[i - 1][j])

                b = i;

        }

        if(k == 1 || t[k][j] != t[k - 1][j]) {

            for(int tj = j + 1; tj <= l; ++tj)

                t[k][tj] = s[++cur];

            break;

        }

    }

    for(int i = 1; i <= n; ++i) {

        for(int j = 1; j <= l; ++j) {

            if(t[i][j] == '\0')

                t[i][j] = s[++cur];

            putchar(t[i][j]);

        }

        putchar('\n');

    }

}

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    while(1) {

        read(n), read(l), read(k);

        reads(s + 1);

        memset(t, '\0', sizeof(t));

        //puts(s + 1);

        test_case();

    }

}

E - Elections

题意：有n个候选人，其中第n个你不喜欢。有m个投票站，第m个投票站投给第n个候选人的票为a_mn，关闭最少的投票站使得你不喜欢的候选人不能胜出。胜出意味着它严格大于其他[1,n-1]个候选人。

题解：貌似反过来想，要让第i个候选人大于等于第n个，只需要把最大的若干个投票站加起来。



int n, m;

int a[105][105];

pii b[105];

vector<int> ans;

void test_case() {

    ans.clear();

    for(int i = 1; i <= m; ++i)

        ans.push_back(i);

    for(int j = 1; j <= n - 1; ++j) {

        for(int i = 1; i <= m; ++i)

            b[i] = {a[i][j], i};

        sort(b + 1, b + 1 + m, greater<pii>());

        int sum = 0, cur = m;

        //cout << "j=" << j << endl;

        bool suc = 1;

        for(int i = 1; i <= m; ++i) {

            sum += b[i].first;

            //cout << "sum=" << sum << endl;

            if(sum < 0) {

                suc = 0;

                if(cur < ans.size()) {

                    ans.clear();

                    for(int ii = i; ii <= m; ++ii)

                        ans.push_back(b[ii].second);

                }

                break;

            }

            --cur;

        }

        if(suc) {

            puts("0\n");

            return;

        }

    }

    int siz = ans.size();

    printf("%d\n", siz);

    if(siz == 0) {

        puts("");

        return;

    }

    sort(ans.begin(), ans.end());

    for(int i = 0; i < siz; ++i)

        printf("%d%c", ans[i], " \n"[i == siz - 1]);

}

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    while(1) {

        read(n), read(m);

        for(int i = 1; i <= m; ++i) {

            for(int j = 1; j <= n; ++j)

                read(a[i][j]);

            for(int j = 1; j <= n - 1; ++j) {

                a[i][j] -= a[i][n];

                //cout << a[i][j] << " ";

            }

            //cout << endl;

        }

        test_case();

    }

}

J - Just Arrange the Icons

题意：苹果手机上面共有n个图标，第i个图标的种类是ai，给屏幕定一个图标的上限s，要求分尽可能少的屏幕，满足以下条件：1、同一个屏幕中的图标的种类相同；2、每个屏幕要么放满，要么只差一个放满

题解：不知道怎么做，想着乱搞一发没想到真过了。首先图标的种类的绝对值是无所谓的，先进行一次离散化，然后统计每种的数量，然后发现数量相同的其实是对于固定的屏幕大小是一样的，可以再合并出来，再进行一次（伪）离散化统计。问题转换为：给定k种数字xi，每种数字xi有ci个，求哪些s，可以使得xi分到大小为s或者s-1的屏幕中。发现这个是可以很容易验证的，因为至少需要(xi+s-1)/s块屏幕，只需要都放s-1的值不比xi大就是合法。

然后来个random_shuffle()再剪枝使得复杂度更加玄学。

这个复杂度本身就是对的，因为s的上限其实就是最小的数量+1，而恰好有k种数字，所以复杂度是s*k，而这个值不超过n。

int n;

int a[2000005], b[2000005];

int cnt1[2000005], cnt2[2000005];

ll ans;

void check(int s) {

    ll cur = 0;

    for(int i = 1; i <= n; ++i) {

        ll x = cnt1[i];

        if((x + s - 1) / s * (s - 1) > x)

            return;

        cur += (x + s - 1) / s * cnt2[x];

        if(cur >= ans)

            return;

    }

    ans = cur;

}

void test_case() {

    sort(b + 1, b + 1 + n);

    int c1 = unique(b + 1, b + 1 + n) - (b + 1);

    for(int i = 1; i <= c1; ++i)

        cnt1[i] = 0;

    for(int i = 1; i <= n; ++i) {

        a[i] = lower_bound(b + 1, b + 1 + c1, a[i]) - b;

        ++cnt1[a[i]];

    }

    for(int i = 1; i <= c1; ++i)

        cnt2[cnt1[i]] = 0;

    for(int i = 1; i <= c1; ++i)

        ++cnt2[cnt1[i]];

    sort(cnt1 + 1, cnt1 + 1 + c1);

    n = unique(cnt1 + 1, cnt1 + 1 + c1) - (cnt1 + 1);

    ans = 0;

    for(int i = 1; i <= n; ++i)

        ans += 1ll * cnt2[cnt1[i]] * ((cnt1[i] + 1) / 2);

    int *s = a;

    for(int i = 1; i + 2 <= cnt1[1] + 1; ++i)

        s[i] = i + 2;

    int cnts = cnt1[1] + 1 - 3 + 1;

    if(cnts <= 0) {

        printf("%lld\n", ans);

        return;

    }

    random_shuffle(s + 1, s + 1 + cnts);

    for(int i = 1; i <= cnts; ++i)

        check(s[i]);

    printf("%lld\n", ans);

}

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    srand(time(0));

    int t;

    read(t);

    while(t--) {

        read(n);

        for(int i = 1; i <= n; ++i) {

            read(a[i]);

            b[i] = a[i];

        }

        test_case();

    }

}

K - Key Storage

2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)的相关教程结束。

《2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred).doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!