北京信息科技大学第十二届程序设计竞赛暨ACM选拔赛（同步赛）

爱丽丝的人偶（一）

https://ac.nowcoder.com/acm/contest/8755/A

个人题解(做完题赶快写题解，趁热打铁，希望对你有帮助)

A题链接：https://ac.nowcoder.com/acm/contest/8755/A

题目描述：找到任意一组满足题目中描述的条件的数组就好了

思路：n,1,n-1,2,n-2,3.... 这样就是一组解

#include <iostream>
using namespace std;

const int N = 110;
int t,n,m;
char g[N][N];

int main()
{
    int n;
    cin >> n;

    int l = 1,r = n;
    while(l < r)
    {
        cout << r << ' ' << l << ' ';
        r --;
        l ++;
    }
    if(n % 2 != 0)
    cout << l << endl;

    return 0;
}

B题链接：https://ac.nowcoder.com/acm/contest/8755/B

题目描述：求

思路：先算出该怎么计算就怎么算，比如 ,就先算出，然后再算出，那么答案不就是吗，因为这个地方算出的结果可能很大，所以要在算的过程中不断地取模，而且这个让取模的数是个大素数，所以可以通过乘法逆元来求出最终答案, ,这个可以通过快速幂迅速求出来

#include <iostream>
#include <set>
using namespace std;

typedef long long LL;
const int mod = 1e9 + 7;
LL n,k;
set<LL>st;

LL qmi(LL a,LL b)
{
    LL res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b = b >> 1;
    }
    return res;
}

int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i ++)
    {
        LL x;
        cin >> x;
        st.insert(x);
    }
    LL m = st.size();
    LL s1 = 1,s2 = 1;
    for(int i = m;i > m - k;i --)
    {
        s1 = s1 * i % mod;
    }
    for(int i = 1;i <= k;i ++)
    {
        s2 = s2 * i % mod;
    }
    LL s3 = s1 * qmi(s2,mod - 2) % mod;
    cout << s3 << endl;
    return 0;
}

C题链接：https://ac.nowcoder.com/acm/contest/8755/C

题目描述：简简单单的思维题

思路：输出A的情况就是1,2或者2,1

#include <iostream>
using namespace std;

const int N = 110;
int t,n,m;
char g[N][N];

int main()
{
    int a,b;
    cin >> a >> b;
    if(a == 1 && b == 2 || a == 2 && b == 1){
        cout << 'A' << endl;
    }else{
        cout << 'B' << endl;
    }

    return 0;
}

D题链接：https://ac.nowcoder.com/acm/contest/8755/D

题目描述：如果能在有限次操作将字符串变成匹配的，请输出最少的操作次数。否则输出-1

思路：先把那些不能匹配的括号找出来，找出来的括号肯定是类似于这个样子的))))((((,如果这样的括号数量为奇数，那么肯定不能通过一定的操作次数让他们都找到自己的匹配方，所以此时 l + r肯定是偶数,如果l是偶数 那么答案就是 l + r >> 1，比如))))，l = 4,r = 0,操作两次就可以达到我们的目的，如果l是奇数，那么r也肯定是奇数，所以答案就是(l + 1 >> 1 ) + (r + 1 >> 1)，这里画个图就好了

#include <iostream>
#include <stack>
using namespace std;

typedef long long LL;


int main()
{
    int n;
    string str;

    cin >> n;
    cin >> str;
    stack<char>stk;
    int l = 0,r = 0;
    for(auto &x : str){
        if(stk.size()){
            if(x == ')'){
                if(stk.top() == '('){
                    stk.pop();
                }else{
                    stk.push(x);
                }
            }
            else{
                stk.push(x);
            }
        }else{
            stk.push(x);
        }
    }

    while(stk.size())
    {
        if(stk.top() == ')'){
            l ++;
        }else{
            r ++;
        }
        stk.pop();
    }

    if((l + r) % 2 != 0){
        cout << -1 << endl;
    }
    else{
        if(l % 2 == 0){
            cout << (l + r >> 1 )<< endl;
        }else{

            int ans = l + 1 >> 1;
            ans += r + 1 >> 1;
            cout << ans << endl;
        }
    }

    return 0;
}

E题链接：https://ac.nowcoder.com/acm/contest/8755/E

题目描述：输入一个01字符串,有多少个字串可以操作k次，这里的k次不懂得话，看样例说明

思路：先统计出每段1和0的个数，如果k等于1的话，那么对于每一段就是1 + 2 + 3 + ....，求和公式,否则就是i就是从第k项开始，看第i项与第i-k项乘起来,具体看代码

#include <iostream>
#include <queue>
using namespace std;

typedef long long LL;

LL n,k;

int main()
{
    string str;
    cin >> n >> k;
    cin >> str;
    vector<int>v;
    for(int i = 0;i < n;i ++){
        int cnt = 0;
        int j = i;
        for(j = i;j < n;j ++){
            if(str[j] == str[i]){
                cnt ++;
            }else{
                break;
            }
        }
        i = j - 1;
        v.push_back(cnt);
    }
    LL res = 0;

    if(k == 1){

        for(auto &x : v){
            res += 1ll*(x + 1)* x / 2;
        }

    }else{
        k --;
        for(int i = k;i < v.size();i ++)
        {
             res += 1ll*v[i] * v[i - k] ;
        }

    }
    cout << res << endl;

    return 0;
}

F题链接：https://ac.nowcoder.com/acm/contest/8755/F

题目描述：小A每次可以任取 连续的 未被吞噬过的 三部分，将其中的黑暗全部吞噬，并获得中间部分的饱食度,小A想知道，自己能获得的饱食度最大值是多少

思路：dp[i]代表以第i项为结尾的最大值是多少,从第四项开始计算，小A可以吃当前这个黑暗数量dp[i - 3] + a[i],也可以不吃dp[i - 1]

dp[i] = max(dp[i - 3] + a[i],dp[i - 1]);
#include <iostream>
#include <queue>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
LL dp[N];
LL a[N];

int main()
{
    int n;    
    cin >> n;

    for(int i = 1;i <= n;i ++)
        cin >> a[i];

    dp[2] = a[2];
    dp[3] = max(a[3],a[2]);
    LL res = a[3];

    for(int i = 4;i < n;i ++)
    {
        dp[i] = max(dp[i - 3] + a[i],dp[i - 1]);
        res = max(res,dp[i]);
    }

    if(n == 3){
        res = dp[2];
    }

    cout << res << endl;
    return 0;
}

G题链接：https://ac.nowcoder.com/acm/contest/8755/G

题目描述：略

思路：找到所有数的最大公约数,然后判断一下给的数能否整除最大公约数 (证明略),最大公约数我一般都是调用库函数，你也可以自己去写.

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL n,k;
LL t;
LL a[N];
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }

    t = a[1];

    for(int i = 2;i <= n;i ++){
        t = __gcd(a[i],t);
    }

    cin >> k;
    while(k --){
        LL x;
        cin >> x;
        if(x % t == 0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }


    return 0;
}

H题链接：https://ac.nowcoder.com/acm/contest/8755/H

题目描述：找到一个最长链

思路：通过dp来求树的直径的一种变形，如果两个点可以到达也就是颜色不一样,那么 res = max(res,dp[u] + dp[j] + 1);dp[u] = max(dp[u],dp[j] + 1); 否则res = max(res,dp[u]);之前写过一个两种算法求树的直径的博客(写的不太好),有兴趣的同学可以看看https://blog.csdn.net/weixin_44235647/article/details/106661379

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
const int N = 1e6 + 10;

int n;
int w[N];

int h[N],e[N],ne[N],idx;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
int res = 0;
int dp[N];

void dfs(int u,int fa)
{
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j,u);
        if(w[u] == w[j]){
            res = max(res,dp[u]);
        }else{
            res = max(res,dp[u] + dp[j] + 1);
            dp[u] = max(dp[u],dp[j] + 1);
        }
    }
}

int main()
{
    memset(h,-1,sizeof h);

    cin >> n;
    for(int i = 1;i <= n;i ++){
        char c;
        cin >> c;
        if(c == 'R'){
            w[i] = 1;
        }else if(c == 'G'){
            w[i] = 2;
        }
    }

    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    cout << res << endl;
    return 0;
}

I题链接：https://ac.nowcoder.com/acm/contest/8755/I

题目描述：这个考察应该是逆元，而B题考察的应该是卢卡斯定理

思路： ，然后注意一下精度,不懂得话，就全开long long

#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
const int N = 1e6 + 10;
LL n,k,m;
LL t;
LL a[N];

LL qmi(LL a,LL b)
{
    LL res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b = b >> 1;
    }
    return res;
}

int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);

    LL s1 = 0,s2 = 0,s3 = 0;

    for(int i = 1;i <= n;i ++){
        int x;
        scanf("%d",&x);
        s1 += x;
    }

    for(int i = 1;i <= m;i ++){
        int x;
        scanf("%d",&x);
        s2 += x;
    }

    for(int i = 1;i <= k;i ++){
        int x;
        scanf("%d",&x);
        s3 += x;
    }

    s1 = s1 % mod;
    s2 = s2 % mod;
    s3 = s3 % mod;

    LL sum = s1 * s2 % mod * s3 % mod;
    LL sum1 = n * m % mod * k % mod;
    printf("%lld",sum*qmi(sum1,mod - 2) % mod);
    return 0;
}

J题链接：https://ac.nowcoder.com/acm/contest/8755/J

题目描述：见题目说明

思路：先求出a,b的最近公共祖先t,然后统计根节点0到a的路径上所有不同的字母分别对应的总数，0到b的路径上所有不同的字母分别对应的总数，然后减去0到t的路径上所有不同的字母分别对应的总数，再把节点t对应的字母加上相应位置，如果字母出现的总数为偶数次那么加上答案，如果为奇数次，就加上奇数次-1，最终答案再加1; 倍增法求LCA

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
const int N = 1e6 + 10;

int n,q;
int w[N];

int h[N],e[N],ne[N],idx;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
int dist[N];
int dp[N][30];
int f[N][20];

void dfs(int u,int fa)
{
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dist[j] = dist[u] + 1;
        for(int i = 1;i <= 26;i ++)
            dp[j][i] = dp[u][i];
        int c = w[j];
        dp[j][c] ++;
        f[j][0] = u;

        for(int i = 1;i <= 16;i ++)
        {
            int k = f[j][i - 1];
            f[j][i] = f[k][i - 1];
        }
        dfs(j,u);
    }
}

int lca(int a,int b)
{
    if(dist[a] < dist[b]){
        swap(a,b);
    }

    for(int i = 16;i >= 0;i --)
    {
        if(dist[f[a][i]] >=  dist[b]){
            a = f[a][i];
        }
    }
    if(a == b){
        return a;
    }

    for(int i = 16;i >= 0;i --)
    {
        if(f[a][i] != f[b][i]){
            a = f[a][i];
            b = f[b][i];
        }
    }
    return f[a][0];
}

int main()
{
    memset(h,-1,sizeof h);
    cin >> n;

    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }

    for(int i = 1;i <= n;i ++)
    {
        char c;
        cin >> c;
        w[i] = c - 'a' + 1;
    }
    dist[1] = 1;
    dfs(1,0);

    cin >> q;
    while(q --)
    {
        int a,b;
        cin >> a >> b;
        int t = lca(a,b);

        int arr[28] = {0};

        for(int i = 1;i <= 26;i ++)
            arr[i] += dp[a][i];
        for(int i = 1;i <= 26;i ++)
            arr[i] += dp[b][i];

        for(int i = 1;i <= 26;i ++)
            arr[i] -= dp[t][i] * 2;

        arr[w[t]] ++;
        int cnt = 0;
        bool flag = false;
        for(int i = 1;i <= 26;i ++)
        {
            if(arr[i] % 2 == 0){
                cnt += arr[i];
            }else if(arr[i]){
                cnt += arr[i] - 1;
                flag = true;
            }
        }
        cout << cnt + flag << endl;
    }
    return 0;
}

k题链接：https://ac.nowcoder.com/acm/contest/8755/k

题目描述：略

思路：m 除以二 上取整 判断与k的大小关系

#include <iostream>
using namespace std;

const int N = 110;
int t,n,m;
char g[N][N];

int main()
{
    int n,m,k;
    cin >> n >> m >> k;

    m = m + 1 >> 1;
    if(m <= k){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }


    return 0;
}
全部评论
感谢兰子哥哥出的题~~~
点赞 回复 分享
发布于 2020-11-21 18:46
H题的点数N为什么要开到1000000，题目不是说是100000吗？ 而且我发现10w确实也A不掉。
点赞 回复 分享
发布于 2020-11-22 01:15
因为这个题的图是无向边，所以得建两次边，那么得分配节点，至少开20W多一点，为了保险起见一般都开30W，建图的时候我喜欢把数组开的稍微大一些，这样就能保证不会发生一些不必要的错误，如果你使用vector的话，那么就可以开10W多一点了
点赞 回复 分享
发布于 2020-11-22 11:58

相关推荐

11-25 00:45
安徽理工大学 Java
点赞 评论 收藏
分享
11-20 23:18
Fachhochschule lübeck Erlang
点赞 评论 收藏
分享
10-28 11:04
已编辑
美团_后端实习生(实习员工)
双非小子现在还没有offer
每天都在阴暗的爬行&nbsp;连面试都没有几个
一个2人：我说几个点吧，你的实习经历写的让人觉得毫无含金量，你没有挖掘你需求里的 亮点， 让人觉得你不仅打杂还摆烂。然后你的简历太长了🤣你这个实习经历看完，估计没几个人愿意接着看下去， sdk， 索引这种东西单拎出来说太顶真了兄弟，好好优化下简历吧
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
10-05 10:13
已编辑
红利真好啊
我也想随便进大厂把车门焊死然后diss后面的人不努力呀😌
HHHHaos：让这些老登来现在秋招一下，简历都过不去
点赞 评论 收藏
分享
昨天 18:05
中国人民大学 Unity3D客户端
点赞 评论 收藏
分享
5 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
331249次浏览 3133人参与
# 上班苦还是上学苦呢？ #
73439次浏览 656人参与
# 阿里云管培生offer #
37305次浏览 424人参与
# 地方国企笔面经互助 #
4571次浏览 12人参与
# 如果有时光机，你最想去到哪个年纪？ #
22032次浏览 415人参与
# 选完offer后，你后悔学本专业吗 #
22048次浏览 159人参与
# 百度开奖 #
185773次浏览 1165人参与
# 我的实习求职记录 #
6072318次浏览 83552人参与
# 如何一边实习一边秋招 #
997178次浏览 12669人参与
# 找工作时遇到的神仙HR #
553716次浏览 3803人参与
# 入职第一天，你准备什么时候下班 #
21672次浏览 144人参与
# 招聘要求与实际实习内容不符怎么办 #
10823次浏览 277人参与
# bilibili求职进展汇总 #
33330次浏览 357人参与
# 许愿池 #
214922次浏览 2535人参与
# 学历or实习经历，哪个更重要 #
54100次浏览 424人参与
# 你今年的平均薪资是多少？ #
71059次浏览 345人参与
# 实习工作，你找得还顺利吗？ #
248022次浏览 2913人参与
# 通信硬件薪资爆料 #
609597次浏览 5198人参与
# 海康威视求职进展汇总 #
400921次浏览 3408人参与
# 携程求职进展汇总 #
135921次浏览 932人参与
# 正在实习的你，几点下班 #
53446次浏览 396人参与
# 工作两年想退休了 #
53150次浏览 673人参与
牛客网
牛客企业服务