2022—SWJTU寒假选拔赛第一场复盘

请注意,文章中部分理解可能已被笔者废弃,本文最后更新于:7 个月前

比赛链接


题目列表

Stat # Title
Solved 21/90 A 惠老板观星
Solved 26/54 B Asuka大战兔子
Attempted 2/44 C 我不会debug
Solved 39/51 D 我要吃饭
2/6 E 删删删
Solved 12/27 F 大水题
0/17 G 你一定会种树吧
Attempted 3 / 17 H 货车
9/28 I 超级打字大师
1/3 J 简单数学
Attempted 5/23 K 小游戏
Solved 36/72 L cold玩真人cs
M 杰哥打怪

RANK

A-惠老板观星

B-Asuka大战兔子

C-我不会debug

D-我要吃饭

E-删删删

F-大水题

G-你一定会种树吧

H-货车

最开始用了个dfs,然后超时?之后才明白是(最小生成树)建边并查集,离线。

改了好久还是没调出来。

I-超级打字大师

J-简单数学

K-小游戏

一道本应该AC的题目。

错误原因是 w 忘了开 LL 。最重要的又看错了题,得分结果不用取 MOD ,只对 a[i][j] 的合并结果取 MOD!!!

#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline ll read(){
    ll sum=0,flag=1;char c;
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
    for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
    return flag*sum;
}


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)


ll a[330][330];
ll dp[330][330];

int main(){
    int n=read();

    FOR(i,1,n){
        a[i][i]=read();
    }
    FOR(k,1,n-1){ 
        FOR(i,1,n-k){//i - i+k
            FOR(j,0,k-1){
                ll w=(dp[i][i+j]+dp[i+j+1][i+k]+(a[i][i+j]-a[i+j+1][i+k])*(a[i][i+j]-a[i+j+1][i+k])); // 错误1
                if(dp[i][i+k]<=w){
                    dp[i][i+k]=w; //%MOD 错误2
                    a[i][i+k]=(a[i][i+j]*a[i+j+1][i+k])%1000003;
                }
            }
        }
    }
    cout<<dp[1][n]; //%MOD 错误2
}

L-cold玩真人cs

M-杰哥打怪

一道简单的 BFS ,但是没来得及了。