题解 | #ABC#

活着的证据

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

A.活着的证据

  1. 在保位数不超过n的前提下,尽可能地增大数的位数。
  2. 从左往右填,先尽可能地填5,,若没填满n位且还有1剩余,在用剩下的1填后面的位。
  3. 填完1轮后,若还有1剩余,把剩下的1用完或把每个数加到8为止。
  4. 注意加的时候对5来说能加3,对1来说只能加1
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 5000010;

int w[N], n, m;
int u, v;

int main(){
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &u, &v, &n);
        for (int i = 1; i <= n; i ++)   w[i] = 0;
        if (u + v <= n) {   //V+I的个数<=n
            while (u --)    printf("5");//前面全填5
            while (v --)    printf("1");//后面全填3
        }
        else {  //V+I的个数>n
            int i;

            //先贪心地填满n位
            for (i = 1; i <= n && u; u --, i ++)    w[i] = 5;   //先把5填完
            for (; i <= n && v; v --, i ++)  w[i] = 1;  //填2

            //把剩下的1用完
            for (i = 1; i <= n && v; i ++) {
                int t;  
                if (w[i] == 5)   t = min(3, v);//填5,最多能加3
                else t = min(2, v); //填1,最多能加2
                v -= t;
                w[i] += t;
            }
            for (i = 1; i <= n; i ++)  printf("%d", w[i]);
        }
        puts("");
    }
    return 0;
}

B.寻寻觅觅寻不到

定义:
1. l[i]:表示s与t的前i个字符是否匹配
2. r[i]:表示s与t从后往前错位匹配是否可以匹配到i

l[i]好理解,那么r[i]的错位匹配是什么意思呢。
假设输入的字符串分别是s和t(s,t的长度为n),要截取的长度是k。因为t是s截取一段长度为k的字串搬到后面得到的,t原来的末尾位置是从n-k。从后往前匹配的时候,s从n开始,t从n-k开始枚举。

举个栗子:
s="abcdef"    
t="abefcd"
k=2
l数组为:110000
r数组为:000011    (s从n开始枚举,t从n-2开始枚举)

预处理出两个数组后,枚举截取的起点。当s中去掉截取的字串后的前后缀与t的前后缀匹配,并且t的后k为与s截取的部分匹配的时候,就说明截取这个区间放到后面可以得到t。

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 300010;

char s[N], t[N];
int n, m, k;
bool l[N], r[N];
//l[i]=1表示s与t的前i个字符匹配
//r[i]=1表示s与t从后往前错位匹配可以匹配到i

bool check(int i, int j) {  //判断s截取的部分是否与t的后k个字符匹配
    for (int u = 1; u <= k; u ++, i ++, j ++) {
        if (s[i] != t[j])   return false;
    }
    return true;
}

int main() {
    int T;

    cin >> T;
    while (T --) {
        cin >> s + 1 >> t + 1 >> k;
        n = strlen(s + 1), m = strlen(t + 1);
        if (n != m) {
            cout << "NO\n";
            continue;
        }
        for (int i = 0; i <= n; i ++)   l[i] = r[i] = 0;    //初始化
        l[0] = r[n + 1] = 1;    //注意边界:在截取的区间是s[n-k,n]会用到

        for (int i = 1; i <= n; i ++)
           l[i] = l[i - 1] && (s[i] == t[i]);  //前缀匹配
        for (int i = n, j = m - k; i >= 1 && j >= 1; i --, j --)
            r[i] = r[i + 1] && (s[i] == t[j]);//后缀错位匹配

        bool flag = 0;
        for (int i = 1; i <= n - k + 1; i ++) { //遍历截取的起点
            if (l[i - 1] && r[i + k] && check(i, m - k + 1))    {
                flag = 1;
                break;
            }
        }
        if (flag)   cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

C.踩不出足迹

根据题目给出的提示可以发现,同或就是对异或取反得到的结果。我们先把n-1次操作全看成是异或操作假设n-1次异或操作后得到的答案是t。无论中间步骤进行了多少次取反操作,最终答案我们都只会得到两种值t和t取反后的值,因此我们只要比较两种值的大小就行。
注意题目的输入刚好卡到了2的64次方,要用unsigned long long。另外如果像下面代码的这种写法,要对特判,因为1<<64也会爆unsinged long long

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

int main() {

    int n, k;
    LL ans = 0;
    cin >> n >> k;
    while (n --) {
        ULL x;
        cin >> x;
        ans ^= x;
    }
    if (n == 1)    cout << ans;
    else {
        LL tem = ~ans, tem2 = 0;
        if (k < 64)        tem2 |= tem & ((1ull << k) - 1);
        else tem2 = tem;
        cout << max(ans, tem2);
    }
    return 0;
}

全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
07-01 17:14
中北大学 Java
兄弟们是真是假
牛客46374834...:我在boss上投java岗从来没成功过
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务