【day11】比赛题笔记

C – Palindromic Matrix

题目大意:

一个矩阵如果行的顺序颠倒后不改变,列的顺序颠倒后也不改变,我们就称其单元格中有整数值的平方矩阵为回文矩阵。
给你一个n*n的矩阵,让你判断他是不是回文举证

思路:
  1. 模拟呗。。每行每列作为一个字符串判断是否回文
  2. 啊理解错题目了,那些数字是可以重排的,于是我决定暴力 全排列结合马拉车,于是在答案是NO的案例中超时了。。毕竟算完400个数字的全排列,需要A(400,400),天数啊。得再想别的办法了
  3. 前面加了一段自以为天衣无缝的判NO,但还是卡在第五个点了,洛谷说这个点我没有答案而裁判有。于是我决定换题

E – Secret Passwords

题目大意:

给定n个字符串
如果存在一个或多个字母同时在字符串a和b中出现 这a和b就被分在同一组,如果a和c在同一组 b和c在同一组 则a和b也在同一组
问所有的字符串最后被分成几组

思路:
  1. 并查集+kmp判断两个字符串是否相互包含。并查集的父节点改成map实现
  2. 我又曲解题意了,洛谷的翻译真的很不全面啊,以后看完翻译对着题目再看一次细节
  3. 不不不,是我自己曲解了翻译的意思,只要俩字符串有至少一个的字母相同他俩就合并了。我错怪洛谷了
  4. 那么就不一定需要kmp了,只要标记以下字母就行
  5. AC了

F – Rumor

题目大意:

有n个人,其中有m对朋友,现在你有一个秘密你想告诉所有人,第i个人愿意出价a[i]买你的秘密,获得秘密的人会免费告诉它的所有朋友(他朋友的朋友也会免费知道),现在他们想出最少的价钱买秘密,那么你最少能得到多少钱?

思路:
  1. 并查集+贪心,不确定,征求网友意见
  2. 没错,然后WA了以下,拿去洛谷一测发现是ans爆炸了,于是开到longlong果断AC

H – Ania and Minimizing

题目大意:

给你长度为n的数,再给你一个数k,让你改变k个数使这整个数最小

思路:
  1. 模拟,看了样例发现是有规律的。先判断是不是一位是的话输出0,不是的话第一位改成1,接着k-1位改成0,不满k-1则全改成零为止
  2. 判一下k为0,直接输出原数
  3. 关于怎么处理k-1比数的位数还小的情况:
    for(int i=1;i<n && k;i++)
      if(s[i]!='0')s[i]='0',k--;
    原文作者:R0chel
    原文地址: https://blog.csdn.net/weixin_42995665/article/details/104310595
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞