Problem A 企鹅和矩阵

题面

小企鹅polo有一个由整数组成的$n \times m$矩阵，他每次让矩阵中的某个元素增加或减少$d$，求最小操作次数使得矩阵中的所有元素相同，如果不能输出$-1$。

题解

骗分过样例，暴力出奇迹。贪心不会死，就怕你dp。

CWOI提醒您：代码千万行，正解第一条。暴力不规范，亲人两行泪。

代码

#include <algorithm>
#include <iostream>
#include <limits.h>
using namespace std;
int a[10005];
int sum[10005];
int n, m, d;
int find( int x ) {
    int l = 1, r = n;
    while ( l <= r ) {
        int m = ( l + r ) / 2;
        if ( a[m] > x ) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return r;
}
int main() {
    ios::sync_with_stdio( false );
    cin >> n >> m >> d;
    n = n * m;
    sum[0] = 0;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
    }
    sort( a + 1, a + 1 + n );
    int M = INT_MAX;
    bool ok = 0;
    sum[1] = a[1];
    for ( int i = 2; i <= n; i++ ) {
        sum[i] = sum[i - 1] + a[i];
        if ( ( a[i] - a[i - 1] ) % d != 0 ) {
            cout << -1 << endl;
            return 0;
        }
    }
    ok = 0;
    for ( int i = 1; i <= 10000; i++ ) {
        int k = find( i );
        if ( k == 0 )
            continue;
        int ans = i * k - sum[k] + ( sum[n] - sum[k] - ( n - k ) * i );
        if ( ans % d == 0 && ans / d <= M ) {
            M = ans / d;
            ok = 1;
        }
    }
    if ( ok == 1 )
        cout << M << endl;
    else
        cout << -1 << endl;
    return 0;
}

Problem B 排序

众所周知，熟练掌握至少一种排序算法是参加NOIP的必备技能。常见的排序算法有冒泡排序、归并排序、快速排序、奇偶排序、猴子排序、梳排序、鸡尾酒排序、臭皮匠排序等。

在这里，介绍一种利用栈进行排序的方法。例如，当数组中的元素为$1,3, 2$时，我们可以利用栈对其进行排序： $1$入栈；$3$入栈；$3$出栈；$2$入栈；$2$出栈；$1$出栈。在这个例子中，出栈序列是$3$，$2$，$1$，因而实现了对数组的排序。遗憾的是，在不打乱入栈顺序的前提下，有时仅仅借助一个栈是不能实现对数组的完全排序。例如给定数组 $2,1,3$，借助一个栈，能获得的字典序最大的出栈序列是$3$，$1$，$2$。（$2$入栈；$1$入栈；$3$入栈；$3$出栈；$1$出栈； $2$ 出栈）。

现请你借助一个栈，在不打乱入栈顺序的情况下，对数组进行从大到小排序。当无法完全排序时，请输出字典序最大的出栈序列。

题解

按照题目给的入栈顺序依次入栈 ，当遇到这个数组中最大的数的时候，直接将其出栈（他已经是最大了，出栈顺序要求尽量从大到小所以它一进来就应该直接出去）然后接着依次入栈再遇到最大的数（不包括已经出栈的数了）时，同样直接出栈，直到走完一遍，然后把压入栈的数依次出栈就好了。

代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
#define N 1111111
using namespace std;
int stack[N], a[N];
bool in_stack[N], is_print[N];
int getint() {
    char ch;
    do {
        ch = getchar();
    } while ( ch != '-' && ( ch < '0' || ch > '9' ) );
    int ans = 0, f = 0;
    if ( ch == '-' )
        f = 1;
    else
        ans = ch - '0';
    while ( isdigit( ch = getchar() ) )
        ans = ans * 10 + ch - '0';
    if ( f )
        ans *= -1;
    return aa = ans;
}
void outint( int x ) {
    if ( x >= 1000000 )
        putchar( '0' + ( x / 1000000 ) % 10 );
    if ( x >= 100000 )
        putchar( '0' + ( x / 100000 ) % 10 );
    if ( x >= 10000 )
        putchar( '0' + ( x / 10000 ) % 10 );
    if ( x >= 1000 )
        putchar( '0' + ( x / 1000 ) % 10 );
    if ( x >= 100 )
        putchar( '0' + ( x / 100 ) % 10 );
    if ( x >= 10 )
        putchar( '0' + ( x / 10 ) % 10 );
    putchar( '0' + x % 10 );
    putchar( ' ' );
    return;
}
int main() {
    int n = getint();
    for ( int i = 1; i <= n; i++ )
        a[i] = getint();
    int top = 0, pos = 0;
    for ( int i = n; i >= 1; i-- ) {
        if ( is_print[i] || ( in_stack[i] && stack[top] != i ) )
            continue;
        while ( top > 0 && stack[top] > i ) {
            int t = stack[top];
            in_stack[stack[top]] = false;
            is_print[stack[top]] = true;
            outint( stack[top] );
            top--;
        }
        while ( !in_stack[i] ) {
            stack[++top] = a[++pos];
            in_stack[a[pos]] = true;
        }
        top--;
        in_stack[i] = false;
        is_print[i] = true;
        outint( i );
    }
    while ( top > 0 ) {
        int t = stack[top];
        top--;
        outint( t );
    }
    return 0;
}

Problem C 花花森林

题面

花花有一棵带$n$个顶点的树$T$，每个节点有一个点权$a_i$。

• 有一天，他认为拥有两棵树更好一些。所以，他从$T$中删去了一条边。
• 第二天，他认为三棵树或许又更好一些。因此，他又从他拥有的某一棵树中去除了一条边。
• 如此往复。每一天，花花都会删去一条尚未被删去的边，直到他得到了一个包含了$n$棵只有一个点的树的森林。

花花认为树最重要的特征就是它的直径。所以他想请你算出任一时刻他拥有的所有树的直径的乘积。因为这个数可能很大，他要求你输出乘积对$100000007$取模之后的结果。

题解

i>树的直径的一个性质：对于两棵树，合并后的直径的两端点一定是之前两直径的四端点之二。

看到这种可逆的操作问题，我们自然地想到要倒着做。把断边转化成连边，变成两棵树的合并，并求其合并后的直径，那么把之前的断点记录一下，用倍增LCA$O(log_2N)$求出那个最大值即可。

其它树的值不用都计算，只需除以两个数的值、再乘回合并后的值即可（用逆元）。总时间复杂度$O(Nlog_2N)$。

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/419.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。