CWOI提高组练习赛2

一场自闭的考试。

00:00

加载中……请稍等……

00:00

加载中……请稍等……

讨论

求将一个$n\times m$的长方形，划分成$n×m$个$1×1$的正方形，任意选出一个由这些小正方形组成的矩形（包括正方形），求面积的期望值对$998244353$取模的值。$n,m\in \mathbb{N^*}\bigcap [1 ,10^{10^5}]$

题解

注意到面积的期望值是面积的和与正方形总个数的比值，考虑对其分别计算。

设矩形个数为$c$，面积和为$s$。

$$ \begin{align} c&=\sum_{i=1}^nn+1-i\sum_{i=1}^m(m+1-i)\\&=\cfrac{n(n+1)}{2}\times\cfrac{m(m+1)}{2}\\&=\cfrac{mn(m+1)(n+1)}{4} \end{align} $$

$$ \begin{align} s&=\sum_{i=1}^ni\times(n+1-i)\sum_{i=1}^ii\times(m+1-i)\\&=\cfrac{n(n+1)(n+2)}{6}\times\cfrac{m(m+1)(m+2)}{6}\\&=\cfrac{mn(m+1)(n+1)(m+2)(n+2)}{36} \end{align} $$

两式相除。

$$ \cfrac sc=\cfrac{(m+2)(n+2)}{9} $$

由费马小定理得逆元为$443664157$。

代码

a, b = input().split()
x = int(a)
y = int(b)
print((x+2) % 998244353*(y+2) % 998244353 * 443664157 % 998244353)

战斗

题目

题解

$f_{i+1,j+h_i}$表示到第$i$个回合，给予伤害为$j$时，剩下的最大魔⼒值。

$f_{i+1,j+h_i}=\max \limits_{i=1}^4\left\{f_{i+1,j+h_i}, f_{i,j}-p_i\right\}$

另外再将连招计为一种神奇的四回合招式即可。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int h[7], p[7], dp[7][11000];
int main() {
    cin >> n >> m >> h[1] >> p[1];
    for ( int i = 2; i <= 5; i++ ) {
        cin >> h[i] >> p[i];
        h[6] += h[i];
        p[6] += p[i];
    }
    h[6] += 3 * h[5];
    for ( int i = 0; i <= 4; i++ ) {
        for ( int j = 0; j <= m; j++ ) {
            dp[i][j] = -1e9;
        }
    }
    dp[0][0] = 0;
    for ( int i = 0; i <= n - 1; i++ ) {
        for ( int j = 0; j <= m; j++ ) {
            for ( int k = 1; k <= 5; k++ ) {
                if ( dp[0][j] - p[k] >= 0 ) {
                    if ( j + h[k] > m ) {
                        if ( dp[0][j] != -1e9 ) {
                            cout << "yes";
                            return 0;
                        }
                    }
                    else {
                        dp[1][j + h[k]] = max( dp[1][j + h[k]], dp[0][j] - p[k] );
                    }
                }
            }
            if ( i + 4 <= n && dp[0][j] - p[6] >= 0 ) {
                if ( j + h[6] > m ) {
                    if ( dp[0][j] != -1e9 ) {
                        cout << "yes";
                        return 0;
                    }
                }
                dp[4][j + h[6]] = max( dp[4][j + h[6]], dp[0][j] - p[6] );
            }
        }
        for ( int k = 0; k <= 3; k++ ) {
            for ( int j = 0; j <= m; j++ ) {
                dp[k][j] = dp[k + 1][j];
            }
        }
    }
    cout << "no";
    return 0;
}

魔法

题目

给出$n$个定义域和值域为$\mathbb{N^*}\bigcap [1 ,k]$的函数，选择一个函数$f(x)$，可以使你的数变成$f(x)$。试求开始数为$x\in\mathbb{N^*}\bigcap [1 ,k]$时最终值的最大值。

题解

大力广搜即可。

代码

#include <bits/stdc++.h>
using namespace std;
int fuck[505][20005], linemax[505];
bool vis[505][20005];
struct status {
    int now, val;
    status() {}
    status( int a, int b ) {
        now = a;
        val = b;
    }
    bool operator<( const status& that ) const {
        return val == that.val ? now > that.now : val < that.val;
    }
};
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while ( ch < '0' || ch > '9' ) {
        if ( ch == '-' )
            w = -1;
        ch = getchar();
    }
    while ( ch >= '0' && ch <= '9' )
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    int n, x, k, ans = 0;
    n = read();
    x = read();
    k = read();
    for ( int i = 1; i <= n; i++ ) {
        for ( int j = 1; j <= k; j++ ) {
            fuck[i][j] = read();
        }
    }
    queue< status > q;
    q.push( status( 0, x ) );
    while ( !q.empty() ) {
        status deal = q.front();
        q.pop();
        ans = max( ans, deal.val );
        if ( ans == k ) {
            break;
        }
        for ( int i = deal.now + 1; i <= n; i++ ) {
            if ( !vis[i][deal.val] ) {
                q.push( status( i, fuck[i][deal.val] ) );
                vis[i][deal.val] = true;
            }
        }
    }
    cout << ans << endl;
    return 0;
}