CWOI提高组练习赛2

Author：薇薇安
发布时间：June 6, 2020
167views
No comments
1410 words
Categories：题解

## 讨论

求将一个$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$。

### 代码

```python
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\}$

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

### 代码

```cpp
#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]$时最终值的最大值。

### 题解

大力广搜即可。

### 代码

```cpp
#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;
}
```
<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/793.html">https://www.starroad.top/archives/793.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote>

Last modification：October 23rd, 2020 at 07:14 pm

如果您觉得我的文章有用，给颗糖糖吧~

CWOI提高组练习赛2

薇薇安 • 2020 年 06 月 06 日

## 讨论

### 题解

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

设矩形个数为$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$。

### 代码

```python
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\}$

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

### 代码

## 魔法

### 题目

### 题解

大力广搜即可。

### 代码

CWOI提高组练习赛2

Leave a Comment Cancel reply

Handsome静态资源加速

Handsome 主题使用阿里云镜像加速

成都外国语学校信息学集训课 Day13

洛谷自动打卡机

NOIP初赛知识点总结

Mathjax添加化学方程式支持

【题解】P2878 [USACO07JAN]Protecting the Flowers S

CWOI2019CSP提高组模拟测试一

成都外国语学校信息学夏令营 Day12

物理预习：1.3 平抛运动

CWOI提高组练习赛2