鱼C论坛

 找回密码
 立即注册
查看: 424|回复: 11

[心之碎片] - 20240817模拟赛

[复制链接]
发表于 2024-8-21 22:23:15 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
总结与反思
B - 对于求权值总和 / 乘积 等于定值要想到背包dp
C - sgt 维护的值看看是否冗余, 只需要单点修改的东西不需要进入 up 和 dn



B - ppip 数列
ppip看到了一个各元素均为正整数、长度为k、各元素之和为n的不降数列。
他想要知道这种数列的个数,对998244853取模。

转化为 权值为 1 - k 的物品, 不限制取的个数, 总和为 n 的方案数, 转化为完全背包问题

在遇到【不易处理的限制】与【就算有限制也很好处理,可惜没限制】的问题时,可以通过转转转将其转化。
原本横向的性质,在新问题上必须纵向考虑。
对于有关【整数】、【重复】等的问题,可考虑将【有无】与【数量之差】相互转化。
f[0] = 1;
    cin >> n >> k;
    n -= k;

    for (int i = 1; i <= k; i++) {
        for (int j = i; j <= n; j++) {
            f[j] = (f[j] + f[j - i]) % P;
        }
    }

    cout << f[n];

D - P4472 [BJWC2018] 八维
倍增, 哈希
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
typedef pair<int, int> pii;

const int N = 505;
const ll B = 233;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

char s[N][N];
int n, m, K;
ll p[N], f[N][N][30];
long long same, all;
pii g[N][N][30];
unordered_map<ll, int> cnt;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> K;
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }

    int lim = log2(K);
    p[0] = B;
    for(int i = 1; i <= lim; i++){
        p[i] = p[i - 1]*p[i - 1];
    }

    for(int d = 0; d < 8; d++){
        // 录入 f, g
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                f[i][j][0] = s[i][j];
                g[i][j][0] = make_pair((i + dx[d] + n) % n, (j + dy[d] + m) % m);
            }
        }

        // 倍增
        for(int k = 1; k <= lim; k++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    int x = g[i][j][k - 1].first;
                    int y = g[i][j][k - 1].second;

                    f[i][j][k] = f[i][j][k - 1]*p[k] + f[x][y][k - 1];
                    g[i][j][k] = g[x][y][k - 1];
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                ll hash = 0;
                auto cur = make_pair(i, j);

                for(int k = lim; k >= 0; k--){
                    if((K >> k) & 1){
                        hash = hash*p[k] + f[cur.first][cur.second][k];
                        cur = g[cur.first][cur.second][k];
                    }
                }

                cnt[hash]++;
            }
        }
    }

    for(auto v : cnt){
        same += 1ll*v.second*v.second;
    }
    all = 64ll*n*n*m*m;

    cout << same / __gcd(same, all) << '/' << all / __gcd(same, all);

    return 0;
}

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +5 收起 理由
~风介~ + 5 + 5 + 5 鱼C有你更精彩^_^

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-21 22:23:37 | 显示全部楼层
在这段描述中,你提到了两道题,以及你对解决方案的总结与反思。让我为你进一步简化和解释:

### B - ppip 数列

#### 问题描述:
你需要找到所有长度为k的、不降的正整数数列,这些数列的元素之和为n,并对结果进行取模运算。

#### 解题思路:
这个问题可以通过将其转换为完全背包问题来解决:
1. 视每个数列元素为背包中的物品,每个物品的权值为1到k。
2. 求权值总和为\(n - k\)的方案数。

#### 解决方法:
使用动态规划来解决背包问题。你的思路是正确的,可以通过完全背包的DP实现。

#### 示例代码:
#include <iostream>
#include <vector>
#define MOD 998244853

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    n -= k;

    vector<int> dp(n + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= k; ++i) {
        for (int j = i; j <= n; ++j) {
            dp[j] = (dp[j] + dp[j - i]) % MOD;
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}

### C - sgt 维护的值看看是否冗余
你提到`sgt`(线段树)需要维护的值时,需要确认是否存在冗余。对于只需要单点修改的情况,不需要进入`up`和`dn`。

### 总结:
1. **转化思路** - 对于不容易处理的复杂限制条件,可以尝试通过不同的角度(例如横向与纵向转换)来简化问题。
2. **背包问题** - 遇到求解和或积等于某定值的问题时,可以通过背包DP的方式来解决。
3. **数据结构优化** - 在使用数据结构如线段树时,确保操作的值没有冗余,优化复杂度。对于单点修改,只需要更新相关节点,不需要进行其他多余操作。

希望这些解答能帮助你更清晰地理解和解决这些问题!如果还有其他不明白的地方,随时提问。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-22 08:58:28 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-22 12:31:54 | 显示全部楼层

回帖奖励 +3 鱼币

666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-22 20:21:44 | 显示全部楼层

回帖奖励 +3 鱼币

666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-23 09:37:00 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-23 16:17:43 | 显示全部楼层

回帖奖励 +3 鱼币

闻币而来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-23 16:22:16 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-24 11:45:56 | 显示全部楼层

回帖奖励 +3 鱼币

&#128076;
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-29 09:24:56 | 显示全部楼层

回帖奖励 +3 鱼币


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-9-1 10:02:20 | 显示全部楼层

回帖奖励 +3 鱼币

看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-9-4 17:16:53 | 显示全部楼层

回帖奖励 +3 鱼币

谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-5 04:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表