CSP - S 题解 （伪）

· · 个人记录

说是题解，其实基本上是抄题解。
总是要找个方法复习的。

Day 1

T1 grey码

小灰(月厨特有幻视)
根据题意模拟 ,记得开unsigned long long。

code

T2 括号树

神TM洛谷两个秋令营都压到了这题，提高老师甚至想出过这个idea，然后觉得太简单，就又改难了，栈 -> nlgn，n sqrt（n）数据结构。（分块大法好）

题意

在链上时就是一个括号匹配，借此维护题目要求的sum数组。
至此可获得55分。

显然链上问题可以用DFS解决，但显然唯一的难点是回溯时需要撤销当次的操作，在操作过程中，维护一个用于进行括号匹配的栈。

code

#include<cstdio>
#include<vector>
#define ll long long 
using namespace std;
const int maxn = 5e5 + 10;

vector<int> e[maxn];

int en;
ll s[maxn] , work[maxn] , sum[maxn];
void push(int x) {s[++en] = x;}
void del() {en --;}

int n;
int fa[maxn];
char ch[maxn];

void dfs(int now) {
    int de = 0;
    if(ch[now] == ')' && en) {
        de = s[en];
        work[now] = work[fa[de]] + 1;
        en --;
    }
    if(ch[now] == '('){s[++ en] = now;}
    sum[now] = sum[fa[now]] + work[now];

    for(int i=0;i<e[now].size();i++) {
        dfs(e[now][i]);
    }

    if(de) {
        s[++en] = de;
    } else {if(en) en--;}
}

int main() {
    scanf("%d",&n);
    scanf("%s",ch+1);

    int x , y;
    for(int i=2;i<=n;i++) {
        scanf("%d",&x);
        e[x].push_back(i);
        fa[i] = x;
    }

    dfs(1);

    ll ans = 0;
    for(int i=1;i<=n;i++) {
        ans ^= sum[i] * (1ll * i);
    }
    printf("%lld",ans);
    return 0;
}

Day 2

T1 Emiya家的饭

关于年番 《卫宫家今天的饭》我还是看了的。花之魔术师 梅林 提供特效
然而我梅林池歪了孔明。艹

关于题目，考试时只会打暴力，还因为层数维护问题写挂了。

显然DFS会T掉，最终只能用DP+容斥，来反向处理掉这个题目。

考虑枚举被选中了比 k/2 大的食材。

道 ，其它项被选 k 道，now 为当前被枚举项。则有方程： $$f[i][j][k] = f[i-1][j][k] + f[i-1][j][k-1]*(sum[i] - a[i][now] ) + f[i-1][j-1][k] * a[i][j] $$ 复杂度$O(mn^3)$，显然在大数据下会T，似乎在洛谷上能拿84分？？？ 可以意识到维护j和k的具体数值并无实际意义。 于是使 $f[i][j]$ 表示当前选择到第 i 道菜，被枚举项比其它项多j 道，now 为当前被枚举项。则有方程： $$f[i][j] = f[i-1][j] + f[i-1][j] * a[i][j] + f[i-1][j+1] * (sum[i] - a[i][now]) $$ ## code ```cpp #include<cstdio> #define int long long using namespace std; const int mo = 998244353; int n , m , ans; int sum[110]; int a[110][2030]; int f[110][220]; int work(int x) { f[0][n+3] = 1; for(int i = 1; i <= n; i++) { for(int j = -i; j <= i; j++) { int k = j + n + 3; //数组无法访问负数的位置 f[i][k] = 0; f[i][k] += f[i-1][k]; f[i][k] += f[i-1][k-1] * a[i][x]; f[i][k] %= mo; f[i][k] += f[i-1][k+1] * (sum[i] - a[i][x]); f[i][k] %= mo; } } int cnt = 0; for(int i=1;i<=n;i++){ cnt += f[n][i+n+3]; cnt %= mo; } return cnt; } signed main() { scanf("%lld%lld",&n,&m); ans = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%lld",&a[i][j]); sum[i] += a[i][j]; sum[i] %= mo; } ans *= sum[i] + 1; ans %= mo; } ans -= 1; for(int i = 1; i <= m; i++) { ans -= work(i); while(ans < 0) { ans += mo; } ans %= mo; } printf("%lld",ans); return 0; } ``` ## T2 划分 正解显然是一个dp，但考虑到数据范围，计算过程需要高精，dp方程需要优化。 ~~单调队列优化dp不是不在考纲里吗~~ 一个显然易见的方程 $f[i][j]$ 表示划分到第 i 个且前驱为 j 的最小值。 $$f[i][j] = min(f[j][k] + (sum[i] - sum[j])^2)$$ 显然如有维护$f[j][k]$的最小值便可直接转移。 时间复杂度大概为$O(n^3)$，应该跑不满，但是肯定会T掉。得分应该在32~64之间吧。 ~~似乎爆搜剪枝有32分~~ 从题解里找出来的方程： 以$f[i]$表示以 i 结尾的最优值，$l[i]$记录当前 i 的最后一段的和， $f[i] = min(f[j] + (sum[i]-sum[j])^2)$ 保证 $sum[i] - sum[j] > l[j]

改写判断条件得：sum[i] >= sum[j] + l[j]

因为f[j]完成计算后r[i] = sum[i] + l[j]便为一个固定值。

有一个我无法证明其正确性的结论。最优解的最后段与其它解相比最小。利用此性质可以进一步优化。