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)$。

Last modification:July 24th, 2019 at 08:38 pm
如果您觉得我的文章有用,请赏一颗糖糖。