【题解】2023年第六届传智杯复赛第二场题解

补题连接：https://ac.nowcoder.com/acm/contest/72974

排行榜（此为清理作弊之前的榜）：

A组：https://acexam.nowcoder.com/exam-rank?uid=1&paperId=17312728

B组：https://acexam.nowcoder.com/exam-rank?uid=1&paperId=17312729

复赛第二场的难度综合来看和第一场接近。略微降低了后期题难度，中期题增加了一个偏模拟的解析几何题供算法基础较差的同学冲刺，可惜通过率并不高。

一共8题，其中A组使用6题：ACDEGH；B组使用6题：ABDEFG

A 小红称体重

alt

通过率：94.86%

知识点：模拟

纯签到题，按题意模拟遍历数组即可。

参考代码：

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, x;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }

    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i - 1] < x && a[i] >= x) {
            ans++;
        }
    }

    std::cout << ans << "\n";

    return 0;
}

B 小红的回文子串

alt

通过率：52.69%

知识点：字符串，贪心、枚举

本题最优复杂度的做法是O(n)，即每次修改字符时要么和相同，要么和相同。枚举时维护对答案贡献的增减即可。

不过本题的数据范围仅有100，可以直接枚举每种修改方式的结果计算答案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[101026],sum[101010];
int suma[101010],sumb[101010];
int pow2[101010];
int mod=1e9+7;
signed main(){
    int n,i,j=0,k,x,y,c=0;
    string s;
    cin>>s;
    n=s.length();
    for(i=2;i<n;i++)c+=s[i]==s[i-2];
    for(i=2;i<n-2;i++){
        if(s[i-2]==s[i+2]&&s[i-2]!=s[i])return cout<<c+2,0;
    }
    for(i=2;i<n;i++){
        if(s[i-2]!=s[i]&&(i>=n-2||s[i]!=s[i+2]))return cout<<c+1,0;
        if(s[i-2]!=s[i]&&(i<=3||s[i-2]!=s[i-4]))return cout<<c+1,0;
    }
    cout<<c;

}

C 小红的字母游戏

alt

通过率：65.05%

知识点：贪心，排序

一个显然的贪心思路是，优先选择在中出现次数更多的字母。因此我们可以先统计每个字母的出现次数，然后降序遍历计算即可。

#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;
    std::vector<int> cnt(26);
    for (auto c : s) {
        cnt[c - 'a']++;
    }
    
    std::sort(cnt.begin(), cnt.end(), std::greater());
    ll ans = 0;
    for (int i = 0; i < 26; i++) {
        if (k > cnt[i]) {
            ans += 1LL * cnt[i] * cnt[i];
            k -= cnt[i];
        } else {
            ans += 1LL * k * k;
            break;
        }
    }

    std::cout << ans << '\n';

    return 0;
}

D 小红的质数数组

alt

通过率：33.90%

知识点：数论，模拟

我们可以先用筛法将不超过2e5范围内的素数全部筛出来，这样后面就可以O(1)判断某个数是不是素数了。现在需要找到一个下标满足：交换后，相邻两数之和都是素数。一个比较直接的方法是模拟每次交换，看看新增的“相邻两数之和”和减少的“相邻两数之和”对答案的影响即可。

参考代码（模拟交换）：

#include<bits/stdc++.h>
using namespace std;
int isp[202020],a[101010];
int main(){
    int n,i,j,c=0;
    for(i=1;i<=2e5;i++)isp[i]=1;
    isp[1]=0;
    for(i=1;i<=2e5;i++){
        if(!isp[i])continue;
        for(j=i*2;j<=2e5;j+=i)isp[j]=0;
    }
    cin>>n;
    vector<int>v;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=2;i<=n;i++)c+=isp[a[i]+a[i-1]];
    for(i=1;i<n;i++){
        int cc=c;
        if(i>1)cc-=isp[a[i]+a[i-1]];
        if(i<n-1)cc-=isp[a[i+1]+a[i+2]];
        
        if(i>1)cc+=isp[a[i+1]+a[i-1]];
        if(i<n-1)cc+=isp[a[i]+a[i+2]];
        if(cc==n-1)v.push_back(i);
    }
    if(v.size()==1)cout<<v[0]<<'\n';
    else cout<<-1<<'\n';
}

参考代码2（树状数组维护前缀和）：

#include <bits/stdc++.h>

using ll = long long;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n = 0) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    // return the sum of [0, x)
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    // return the sum of [l, r)
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    int kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }

    Fenwick<int> fen(n - 1);
    auto is_prime = [&](int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    };
    for (int i = 0; i < n - 1; i++) {
        if (is_prime(a[i] + a[i + 1])) {
            fen.add(i, 1);
        }
    }

    std::vector<int> ans;
    for (int i = 0; i < n - 1; i++) {
        std::swap(a[i], a[i + 1]);
        int sum = is_prime(a[i] + a[i + 1]);
        if (i - 1 >= 0) {
            sum += is_prime(a[i - 1] + a[i]);
            sum += fen.rangeSum(0, i - 1);
        }
        if (i + 2 < n) {
            sum += is_prime(a[i + 1] + a[i + 2]);
            sum += fen.rangeSum(i + 2, n - 1);
        }
        if (sum == n - 1) {
            ans.push_back(i);
        }
        std::swap(a[i], a[i + 1]);
    }

    if (ans.size() == 1) {
        std::cout << ans[0] + 1 << "\n";
    } else {
        std::cout << "-1\n";
    }

    return 0;
}

E 小红的平面划线

alt

通过率：1.17%

知识点：几何，枚举

考虑到一共最多只有180个点，因此直接枚举即可：首先枚举两点确定直线，然后进行判定。

判定点在直线上/左侧/右侧需要使用叉乘，根据叉乘结果的正负性得知答案。

本题还有个坑点，即的时候（此时一共3个点），此时可以随机在平面上任取一点（比如(114514,1919810)），枚举这个点和三个点中任意一点进行判定即可。

参考代码：

#include <iostream>
#include <vector>
using namespace std;
#define point pair<int,int>
pair<int,int>a[202];

int jud(point a,point b,point c){
    point ab={b.first-a.first,b.second-a.second};
    point bc={c.first-b.first,c.second-b.second};
    int cnt=ab.first*bc.second-ab.second*bc.first;
    if(cnt>0)return 1;
    if(cnt<0)return -1;
    return 0;
    
}
vector<int> getline(point a,point b){

    int xa=a.first,ya=a.second,xb=b.first,yb=b.second;
    vector<int>res= {yb-ya,xa-xb,ya*(xb-xa)-xa*(yb-ya)};
    return res;
}
int main() {
    int n,i,j,k;
    cin>>n;
    for(i=0;i<3*n;i++){
        cin>>a[i].first>>a[i].second;
    }
    if(n==1){
        point c={114514,1919810};
        if(jud(c,a[0],a[1])*jud(c,a[0],a[2])==-1){
            vector<int>res=getline(c, a[0]);
                cout<<res[0]<<" "<<res[1]<<" "<<res[2];
                return 0;
        }
        if(jud(c,a[1],a[2])*jud(c,a[1],a[0])==-1){
            vector<int>res=getline(c, a[1]);
                cout<<res[0]<<" "<<res[1]<<" "<<res[2];
                return 0;
        }
        if(jud(c,a[2],a[0])*jud(c,a[2],a[1])==-1){
            vector<int>res=getline(c, a[2]);
                cout<<res[0]<<" "<<res[1]<<" "<<res[2];
                return 0;
        }
        cout<<-1;
        return 0;
    }
    for(i=0;i<3*n;i++){
        for(j=0;j<3*n;j++){
            if(i==j)continue;
            int tong[3]={};
            for(k=0;k<3*n;k++){
                tong[jud(a[i],a[j],a[k])+1]++;
            }
            if(tong[0]==tong[1]&&tong[0]==tong[2]){
                 vector<int>res=getline(a[i], a[j]);
                 cout<<res[0]<<" "<<res[1]<<" "<<res[2];
                 return 0;
            }
        }
    }
    cout<<-1;

}

F 小红和小紫的拿球游戏

alt

通过率：6.95%

知识点：博弈，概率

首先我们假设小紫不是随机取，那么当小红取了第一个球后，小紫每次必取和第一个球相同的颜色，小红必取和第一个球不同的颜色，这样才是最优策略。

那么小红的策略就可以确定了：首先第一次取的一定是较多的那个颜色，之后每回合都取和该球不同的颜色。若，则小红必胜；若，那么当且仅当小紫每次都取到和小红初始颜色相同的球时小紫才能获胜。若，则小紫除了最后一回合外，每回合必须都取到和小红初始颜色相同的球时小紫才能获胜。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int _;
    cin>>_;
    while(_--){
        int a,b,i,j;
        cin>>a>>b;
        if(a<b)swap(a,b);
        if(a-b>=2)cout<<1<<'\n';
        else{
            double p=1;
            a--;
            while(a&&b){
                p*=1.0*a/(a+b);
                a--,b--;
            }
            printf("%.9f\n",1-p);
        }
    }
}

G 小红的树上切割

alt

通过率：2.54%

知识点：树形dp

我们定义代表：对于号节点，它的子树切割后的红色点数量为的方案数。

那么当维护dp转移时，有以下几种情况：

  1. 对于dp[u][0]，讨论某孩子，若取，则不切；若取，则切。

  2. 对于dp[u][1]，讨论某孩子，若取，则不切；若取，则切。另外还需要加上前面得到的dp[u][0]和dp[v][1]构成dp[u][1]的情况。

参考代码：

#include <bits/stdc++.h>

using ll = long long;

template <typename T, auto f = std::multiplies<T>()>
constexpr static T power(T a, int64_t b) {
    assert(b >= 0);
    T res;
    if constexpr (std::is_arithmetic_v<T>) {
        res = 1;
    } else {
        res = a.identity();
    }
    while (b) {
        if (b & 1) {
            res = f(res, a);
        }
        b >>= 1;
        a = f(a, a);
    }
    return res;
}

template <typename T, T MOD>
struct ModInt {
    using prod_type = std::conditional_t<std::is_same_v<T, int>, int64_t, __int128>;
    T val;
    constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
    constexpr ModInt operator+() const { return ModInt(val); }
    constexpr ModInt operator-() const { return ModInt(MOD - val); }
    constexpr ModInt inv() const { return power(*this, MOD - 2); }
    constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }
    constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }
    constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }
    constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }
    constexpr ModInt &operator+=(const ModInt x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt x) {
        val = prod_type(val) * x.val % MOD;
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }
    bool operator==(const ModInt b) const { return val == b.val; }
    bool operator!=(const ModInt b) const { return val != b.val; }
    friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept { return is >> x.val; }
    friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept { return os << x.val; }
    constexpr static ModInt identity() { return 1; }
    constexpr ModInt pow(int64_t p) { return power(*this, p); }
};
using Z = ModInt<int, 1'000'000'007>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> c(n);
    for (auto &i : c) {
        std::cin >> i;
    }
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::vector dp(n, std::vector<Z>(2));
    auto dfs = [&](auto &&self, int u, int f) -> void {
        dp[u][c[u]] = 1;
        for (auto v : g[u]) {
            if (v == f) continue;
            self(self, v, u);
            dp[u][1] = dp[u][1] * (dp[v][0] + dp[v][1]) + dp[u][0] * dp[v][1];
            dp[u][0] *= dp[v][0] + dp[v][1];
        }
    };

    dfs(dfs, 0, -1);

    std::cout << dp[0][1] << "\n";

    return 0;
}

H 小红的字符修改

alt

通过率：5.45%

知识点：线段树/树状数组，哈希

本题考察大家对数据结构的掌握程度。假设没有修改操作，那么本题就是一个简单的字符串哈希：判断和两段的哈希值是否相同即可。

现在加入了修改操作，我们则需要使用线段树维护哈希数组的修改：将哈希数组看成是一个进制的大数，我们每次修改即修改其中的一位，可以直接统计修改该节点对线段树每个节点带来的影响。由于本题为单点修改，因此也可以用树状数组进行维护，代码相对更简短。

参考代码：

#include <bits/stdc++.h>

template <typename T>
constexpr static T power(T a, int64_t b) {
    assert(b >= 0);
    T res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
        }
        b >>= 1;
        a *= a;
    }
    return res;
}

template <typename T, T MOD>
struct ModInt {
    using prod_type = std::conditional_t<std::is_same_v<T, int>, int64_t, __int128>;
    T val;
    constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
    constexpr ModInt operator+() const { return ModInt(val); }
    constexpr ModInt operator-() const { return ModInt(MOD - val); }
    constexpr ModInt inv() const { return power(*this, MOD - 2); }
    constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }
    constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }
    constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }
    constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }
    constexpr ModInt &operator+=(const ModInt x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt x) {
        val = prod_type(val) * x.val % MOD;
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }
    bool operator==(const ModInt b) const { return val == b.val; }
    bool operator!=(const ModInt b) const { return val != b.val; }
    friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept { return is >> x.val; }
    friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept { return os << x.val; }
    constexpr static ModInt identity() { return 1; }
    constexpr ModInt pow(int64_t p) { return power(*this, p); }
};

namespace Hashing {
constexpr uint64_t mod = 1'000'000'000'000'000'003ULL;
using hash_t = ModInt<int64_t, mod>;

const hash_t base = std::mt19937_64(std::chrono::steady_clock::now().time_since_epoch().count())() % mod;
static std::vector<hash_t> pow{1};

static void expand_pow(size_t index) {
    if (index < pow.size()) {
        return;
    }
    auto old_size = pow.size();
    pow.resize(index * 2 + 1);
    for (auto i = old_size; i <= index * 2; i++) {
        pow[i] = pow[i - 1] * base;
    }
}

hash_t get_pow(size_t sz) {
    expand_pow(sz);
    return pow[sz];
}
} // namespace Hashing 

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n = 0) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    // return the sum of [0, x)
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    // return the sum of [l, r)
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    std::string s;
    std::cin >> s;

    Fenwick<Hashing::hash_t> hash(n);
    for (int i = 0; i < n; i++) {
        hash.add(i, Hashing::get_pow(i) * s[i]);
    }

    auto substr = [&](int l, int r) {
        return hash.rangeSum(l, r) / Hashing::get_pow(l);
    };

    while (q--) {
        int op;
        std::cin >> op;

        if (op == 1) {
            int p;
            char c;
            std::cin >> p >> c;
            p--;
            hash.add(p, Hashing::get_pow(p) * (c - s[p]));
            s[p] = c;
        } else {
            int l1, r1, l2, r2;
            std::cin >> l1 >> r1 >> l2 >> r2;
            l1--;
            l2--;            
            std::cout << (substr(l1, r1) == substr(l2, r2) ? "Yes" : "No") << "\n";
        }
    }

    return 0;
}
全部评论
请问小红的平面划线这道题，是保证输入数据点对不重复吗，如果是题干哪里体现了这一点，如果不是这个样例是不是过不去 2 1 1 1 1 1 2 1 2 1 3 1 3 而且重复的点计数的话属于一个点还是多个，比赛时考虑这一点用了set去重导致结果错误，我把我代码中set去重的部分删掉就ac了
2 回复 分享
发布于 2023-12-25 13:15 黑龙江
学算法，就上牛客，XCPC铜牌不是梦，心动不如行动，点此下方链接报名立减20元： 基础算法入门班：https://www.nowcoder.com/courses/cover/live/724?coupon=ARgGejk 进阶数据结构专题课：https://www.nowcoder.com/courses/cover/live/707?coupon=AQDlsi4 作者：Try_harder_one 链接：https://www.nowcoder.com/discuss/376062552252448768?sourceSSR=users 来源：牛客网
点赞 回复 分享
发布于 2024-01-18 10:20 河北
E 小红的平面划线 这道题我用的是数学思维过了样例，和自己增加了样例，可还是过不了。
点赞 回复 分享
发布于 2024-01-03 14:28 广东
想问问大佬，小红小紫那题怎么思考的呀，感觉好妙。但是又有些不理解，小红的策略为什么是每次取不同颜色的球，小紫每次取相同颜色的球啊，好像和题目讲得相反
点赞 回复 分享
发布于 2023-12-30 12:01 广东
录像用阿里云盘行吗
点赞 回复 分享
发布于 2023-12-25 21:22 河北
B组几百名有希望进国赛
点赞 回复 分享
发布于 2023-12-25 18:05 山东
为什么point c={114514,1919810}
点赞 回复 分享
发布于 2023-12-25 17:07 陕西
A组33名可以进决赛吗？
点赞 回复 分享
发布于 2023-12-25 14:36 四川
大概多久能公布最终晋级决赛的榜单
点赞 回复 分享
发布于 2023-12-25 13:35 山东

相关推荐

06-17 17:59
已编辑
广西科技大学 测试工程师
字节实习入职一周了，强度确实非同寻常
基本上早10晚10的状态，伙食确实很好，但白天只有吃饭的时候才有一点活人味所幸的是团队，mentor还有小伙伴们都很好，希望就是这样相互支撑着，慢慢地就度过去了吧晚上9:30之后可以打车报销，基本上每天都可以用到这个“福利”（补偿）。但是打了一次之后，就感觉从一个封闭的环境在迅速的过渡到另一个封闭的屋子里，生命太过封闭而不够敞亮了。所以现在更喜欢下班之后就慢慢悠悠地走两公里回到我狭小的出租屋，在路上听一点喜欢的歌，和朋友聊一会儿天，看一看车水马龙的世界和匆匆而过的行人。生命就这样轻轻地慢慢地聚拢，然后再一次迎接崭新的明天。
不吃香菜双非版：建议骑车，每天下班骑车回去都感觉自由飞翔
字节跳动公司福利 1011人发布 聊聊这家公司值得去吗
点赞 评论 收藏
分享
06-19 11:05
西安电子科技大学 Java
点赞 评论 收藏
分享
06-19 13:42
北京交通大学 Java
点赞 评论 收藏
分享
评论
8
11
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 你找实习最大的坎坷是什么 #
23971次浏览 300人参与
# 蔚来工作体验 #
17907次浏览 67人参与
# 实习最想跑路的瞬间 #
17630次浏览 135人参与
# 如果可以，你希望哪个公司来捞你 #
91246次浏览 382人参与
# 我的职场心眼子段位 #
16246次浏览 449人参与
# 机械/汽车制造公司爆料 #
40236次浏览 208人参与
# 比亚迪精密制造工作体验 #
19729次浏览 39人参与
# 比亚迪工作体验 #
58334次浏览 235人参与
# 机械制造公司评价 #
118025次浏览 302人参与
# 理想汽车工作体验 #
30532次浏览 274人参与
# 对妈妈没说出口的话 #
45026次浏览 761人参与
# 大疆今年的机械笔试难吗？ #
40973次浏览 452人参与
# 机械制造2023笔面经 #
118606次浏览 756人参与
# 春招别灰心，我们一人来一句鼓励 #
113048次浏览 1294人参与
# 秋招投简历越早越好吗 #
66427次浏览 630人参与
# 这些公司卡简历很严格 #
37941次浏览 190人参与
# 职业发展规划如何回答 #
37957次浏览 236人参与
# 我的求职精神状态 #
90491次浏览 1051人参与
# 市场营销人求职交流聚集地 #
120743次浏览 1089人参与
# 机械人，你被简历秒挂的企业有哪些？ #
41044次浏览 275人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务