贪心学不明白

yanzihe · 2024-11-16 16:12:14 · 个人记录

（标题和正文内容无关）

模拟赛总结：

比赛：信友队NOIP模拟十一

T1：

题意：求所有子区间的的次大值和

解法：显然的拆贡献，只需要维护每个数前后第一个和第二个比它大的数。我首先想到了 O(nlog^2n) 的二分+主席树做法，幸好没有实现它，后来换了一个 O(nlogn) 的单调栈+二分。

理论上应该在20分钟以内写完这道题，但是很多细节让我写了整整1.6h。细节包括相同的数怎么处理（这个最耗时，其实简单钦定一下就可以了，但为了处理它我写了一大车代码）,二分用upper还是lower,要不要有加减一偏移量。

最好的办法是在写代码前用我的方法算一了比较大的数据，一方面防止算法假掉，更重要的是缩减调试时间。这句话我也不知道总结了多少遍了，什么时候能做到呢？

T2:

题意:求有多少个区间查询会恰好由 k 个线段树上节点组合而成。

解法：O(nk^2logn)做法是显然的，直接树上DP维护前后缀即可，由于 k 太大则答案是 0，所以复杂度是 O(nlog^3n)，注意到绝大部分点的子树都是满二叉树, 可以直接预处理，只有少部分点子树是右偏完全二叉树(不超过 logn个)，所以特殊处理这些点，可以做到 O(log^3n)。

这道题我一眼秒掉了，然后调试了整整2h，得到了0分的高分，望周知。

主要问题和T1是一样的，很多细节没有考虑好直接开写，结果一直在处理各类细节。一方面我并没有通过手算前检验细节问题，另一方面我实现方式太劣了。（虽然思路正确）
对比一下思路类似但却天差地别的做法：
优美的解法：

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(ll i=a;i<=b;i++)
#define rrep(i, a, b) for(ll i=a;i>=b;i--)
typedef long long ll;
const ll N=2e5+9;
ll c, t, n, k;
struct infor{
    ll ans;vector <ll> l, r;
};
unordered_map <ll, infor> f;
ll solve(ll len, vector<ll> &l, vector <ll> &r){//l是前缀，r是后缀
    if(f.find(len)!=f.end()){
        l=f[len].l;r=f[len].r;return f[len].ans;
    }
    if(len==1){
        rep(i, 0, k)l.emplace_back(0);l[1]++;
        rep(i, 0, k)r.emplace_back(0);r[1]++;
        return 0;
    }
    ll mid=len/2;
    vector <ll> zl, zr, yl, yr;
    ll ans=solve(mid, zl, zr)+solve(len-mid, yl, yr);
    rep(i, 1, k-1){
        ans+=zr[i]*yl[k-i];
    }if(k==2)ans--;
    l.emplace_back(0);r.emplace_back(0);
    rep(i, 1, k){
        l.emplace_back(zl[i]+yl[i-1]);
    }l[1]++;l[2]--;
    rep(i, 1, k){
        r.emplace_back(yr[i]+zr[i-1]);
    }r[1]++;r[2]--;
    f.insert(make_pair(len, (infor){ans, l, r}));
    return ans;
}
int main(){
    freopen("seg.in", "r", stdin);
    freopen("seg.out", "w", stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> c >> t;
    while(t--){
        cin >> n >> k;
        if(k>2*log2(n)){cout << 0 << endl;continue;}
        if(k==1){
            ll d=log2(n), ext=(n-((1<<d)))*2;
            cout << (1LL<<(d+1))-1+ext << endl;
            continue;
        }
        vector <ll> tmp1, tmp2;
        cout << solve(n, tmp1, tmp2) << endl;;
        f.clear();
    }
    return 0;
}

劣质的写法：（赛时代码）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=a;i<=b;i++)
#define rrep(i, a, b) for(ll i=a;i>=b;i--)
#define debug(a) //cout << #a << ' ' << a << endl;
const ll N=2e5+9, MOD=998244353;
const ll K=59;
ll c, t, n, k, d, ext;
ll f[N][K], g[N][K];//f是内组合答案，g是前/后缀答案（应许占满）,g[i][0]=1
ll ans=0;
ll maxk=50;
void dfs(ll d, ll you, vector <ll> &z, vector <ll> &y){//0前缀1后缀
    //u有一个右偏完全二叉树,深度为d,要求、算出内组合的答案累加到ans中，然后返回前缀，后缀方案数(用vector 返还)（方案数应许占满，不选也可以）
        ll len=(1LL<<(d-1));
    if(you==len){
        you=0;
    }else if(you==0){
        d--;
    }
    if(you==0){
        rep(i, 0, maxk){
            z.emplace_back(g[d][i]);y.emplace_back(g[d][i]);
        }
        // cout << f[d][k] << endl;
        ans+=f[d][k];return;
    }

    if(d==1){
        if(k==1)ans++;
        z.emplace_back(1);
        y.emplace_back(1);
        z.emplace_back(1);
        y.emplace_back(1);
        return;
    }
    vector <ll> riz, riy;
    if(you<=len/2){
        debug(d);
        dfs(d-1, you, riz, riy);
        //左侧是一个深度为d-1的满树
        ans+=f[d-1-(you?1:0)][k];//左侧内组合
        for(ll i=1;i<riz.size();i++){
            if(k-i>0)ans+=g[d-1-(you?1:0)][k-i]*riz[i];
            if(i==1&&k-i==1)ans--;
        }
        z.clear();y.clear();
        z.emplace_back(1);y.emplace_back(1);
        rep(i, 1, maxk){
            z.emplace_back(g[d-1-(you?1:0)][i]+(i-1<riz.size()?riz[i-1]:0));
        }//z[1]--;//左边占满，右边不选和右侧选0重复了

        rep(i, 1, maxk){
            y.emplace_back(g[d-1-(you?1:0)][i-1]+(i<riy.size()?riy[i]:0));
        }//y[1]--;
    }else{
        dfs(d-1, you-(len/2), riz, riy);
        ans+=f[d-1-(you?1:0)][k];//右侧内组合
        for(ll i=1;i<riy.size();i++){
            if(k-i>0)ans+=g[d-1-(you?1:0)][k-i]*riy[i];
            if(i==1&&k-i==1)ans--;
        }
        z.clear();y.clear();
        z.emplace_back(1);y.emplace_back(1);
        rep(i, 1, maxk){
            z.emplace_back(g[d-1-(you?1:0)][i-1]+(i<riz.size()?riz[i]:0));
        }//z[1]--;
        rep(i, 1, maxk){
            y.emplace_back(g[d-1-(you?1:0)][i]+(i-1<riy.size()?riy[i-1]:0));
        }//y[1]--;
    }
}
int main(){
    freopen("seg.in", "r", stdin);
    freopen("seg.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    rep(i, 1, maxk)
        g[i][0]=1;
    rep(i, 1, maxk){
        rep(j, 1, maxk){
            g[i][j]=g[i-1][j]+(j>1?g[i-1][j-1]:0);
            if(i>=2&&j==2)g[i][j]--;
            if(j==1)g[i][j]++;
        }
    }
    rep(i, 1, maxk){
        rep(j, 1, maxk){
            f[i][j]=f[i-1][j]*2;
            rep(t, 1, j-1){
                f[i][j]+=g[i-1][t]*g[i-1][j-t];
            }
            if(j==2&&i>=2)f[i][j]--;
            if(j==1)f[i][j]++;
        }
    }
    cin >> c >> t;
    while(t--){
        cin >> n >> k;//k=1特判掉吧
        d=log2(n);
        ext=(n-((1<<d)))*2;
        // cout << d+2 << endl;
        if(k==1){
            cout << (1LL<<(d+1))-1+ext << endl;
            continue;
        }
        ans=0;
        vector <ll> tmp1, tmp2;
        dfs(d+2, ext, tmp1, tmp2);
        cout << ans << endl;
    }
    return 0;
}

可以看到劣质写法充斥着大量的特判和分讨，而优质写法就很自然，而且优质写法写起来很快，而且一遍AC。其实最好在写代码前预计一下，如果实现起来比较困难就尝试更换写法来避免分讨。

T3

有 n 个字符串，求所有满足这样条件的字符串：和所有其它 n-1 个字符串的都恰好有 k 处不同的字符。
我写了一个暴力和一个部分分，期望得分 40，实际得分 90，难评。
来自韦神的高档做法：
考虑按位做，统计每一位上，有多少字符串在这一位上不同，所有位的答案加起来如果是 k(n-1)，那么这个字符串就有可能是符合条件的。为了提高正确率可以给每一个字符串随机赋一个权值。我这里用的是二维和哈希。
像本题这种要比较很多东西，要求判断是否全部相等的题目，可以把很多东西并成一个和哈希 O(1) 比较。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(ll i=a;i<=b;i++)
#define rrep(i, a, b) for(ll i=a;i>=b;i--)
typedef long long ll;
const ll N=2e3+9;
mt19937_64 myrand;
struct Complex{
    unsigned long long a, b;
    Complex operator +(Complex &y)const{
        return (Complex){a+y.a, b+y.b};
    }
    Complex operator -(Complex &y)const{
        return (Complex){a-y.a, b-y.b};
    }
    Complex operator *(ll &y)const{
        return (Complex){a*y, b*y};
    }
    bool operator ==(const Complex &y)const{
        return a==y.a&&b==y.b;
    }
    void Rand(){
        a=myrand();b=myrand();
    }
}val[N], sumval, all;
Complex sum[N][35];//sum[i][0～25]表示第i位是0~25的所有字符串的权值和
string s[N];
ll n, m, k;
int main(){
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    myrand.seed(time(0));
    cin >> n >> m >> k;
    rep(i, 1, n){
        cin >> s[i];
        val[i].Rand();
        sumval=sumval+val[i];
    }
    rep(i, 1, n){
        rep(j, 0, m-1){
            sum[j][s[i][j]-'a']=sum[j][s[i][j]-'a']+val[i];
        }
    }
    rep(i, 1, n){
        all=(Complex){0, 0};
        rep(j, 0, m-1){
            all=all+sumval-sum[j][s[i][j]-'a'];
        }
        if(all==(sumval-val[i])*k){
            cout << i << endl;
        }
    }
    return 0;
}

T4

哈哈，我根本没做！ 50分是显然的，但是没有时间了。
过题数是没有用的，不要为了在已有高部分分的基础上为了一个AC数浪费大把的部分分。
其实T2的80分是平凡的，而100分比较麻烦，实际上这里的20分远远不如后面的一些部分分来的有效。为了争取做出题而花费的大量时间不如到后面取拿部分分，应该摒弃过题数这种指标，就单纯拿总分最大化作为目标。