(Week 15)综合复习(C++,字符串,数学)

news/2024/2/27 21:23:54

文章目录

    • T1 [Daimayuan]删删(C++,字符串)
        • 输入格式
        • 输出格式
        • 样例输入
        • 样例输出
        • 数据规模
        • 解题思路
    • T2 [Daimayuan]快快变大(C++,区间DP)
        • 输入格式
        • 输出格式
        • 样例输入
        • 样例输出
        • 数据规模
        • 解题思路
    • T3 [Daimayuan]饿饿 饭饭2(C++,数学)
        • 输入格式
        • 输出格式
        • 数据规模
        • 样例输入
        • 样例输出
        • 解题思路
    • T4 [Daimayuan]子串分值和(C++,字符串)
        • 输入格式
        • 输出格式
        • 样例输入
        • 样例输出
        • 数据规模
        • 解题思路
    • T5 [Daimayuan]蒟蒻(C++,STL)
        • 输入格式
        • 输出格式
        • 样例输入
        • 样例输出
        • 数据规模
        • 解题思路
    • T6 [Daimayuan]锦标赛(C++,模拟)
        • 输入格式
        • 输出格式
        • 样例输入1
        • 样例输出1
        • 样例输入输出2
        • 数据规模
        • 解题思路
    • T7 [Daimayuan]可重排列(C++,字符串)
        • 输入格式
        • 输出格式
        • 样例输入
        • 样例输出
        • 数据规模
        • 解题思路
    • T8 [Daimayuan]进制转换(C++)
        • 题面
        • 输入格式
        • 输出格式
        • 输入样例1
        • 输出样例1
        • 输入样例2
        • 输出样例2
        • 输入样例3
        • 输出样例3
        • 解题思路
    • T9 [Daimayuan]循环子串(C++,字符串)
        • 题目描述
        • 输入格式
        • 输出格式
        • 数据范围
        • 样例输入
        • 样例输出
        • 提示
        • 解题思路
    • T10 [Daimayuan]饿饿 饭饭之暑假大狂欢(C++,数学)
        • 输入格式
        • 输出格式
        • 数据范围
        • 样例输入
        • 样例输出
        • 解题思路

T1 [Daimayuan]删删(C++,字符串)

给定一个字符串,你可以删除多个(可以是 000) 相同 的字符,这样操作之后,你能否得到一个回文串?如果能,求最小化删除的个数。

输入格式

多组数据。

每一组数据包含两行,分别为字符串的长度 NNN,以及一个仅由小写字母组成的字符串 SSS

输出格式

对于每一组数据,输出一行。

如果不可能得到一个回文串,输出 −1−11。反之则输出最小操作次数。

样例输入

4
8
bilibili
3
qwq
9
daimayuan
7
xcpcxpc

样例输出

1
0
-1
2

解释:

在第一个例子中,删除开头的 b 得到 ilibili

第二个例子中,qwq 本身已回文,不需要操作。

第三个例子中,可以看到 daimayuan 不能靠仅删除一种字符得到一个回文串。

数据规模

1≤N≤1051≤N≤10^51N105, 但保证 ∑N≤2×105\sum{N}≤2×10^5N2×105

解题思路

并没有巧妙的办法,就是简单的枚举262626种字母,找出其中删除的最少的即可

检测的思路如下:

从左右两端开始匹配

(1)if str[left] == str[right]left++, right--

(2)if str[left] != str[right]

如果左侧字符可以删除,那么删除左侧字符(left++

如果右侧字符可以删除,那么删除右侧字符(right--

如果左右都不可以删除,本轮删除失败,继续尝试下一个字符

#include <iostream>
#include <string>
using namespace std;
const int max_n = 2e5;
const string compose = "abcdefghijklmnopqrstuvwxyz";string str;
int n1, n2;int main() {cin >> n1;for (int i = 0; i < n1; i++) {cin >> n2 >> str;int ans = -1;for (char c: compose) {int l = 0, r = n2 - 1;int temp = 0;while (l <= r) {if (str[l] == str[r]) {l++; r--;}else {if (str[l] == c) {l++;temp++;}else if (str[r] == c) {r--;temp++;}else {temp = -1;break;}}}if (temp != -1)if (ans == -1) ans = temp;else ans = min(ans, temp);}cout << ans << endl;}return 0;
}

T2 [Daimayuan]快快变大(C++,区间DP)

给定一个长度为 nnn 的数组 a1,a2,…,ana_1,a_2,…,a_na1,a2,,an,接下来进行 n−1n−1n1 次操作。每次选择一个下标 xxx ,将 axa_xaxax+1a_{x+1}ax+1 合并成 ax∗ax+1mod1000003a_x*a_{x+1}mod1000003axax+1mod1000003 ,并且你会获得 (ax−ax+1)2(a_x−a_{x+1})^2(axax+1)2 的分数。

所以每次操作后,数组的长度将会减 111,当最后只剩下一个元素时停止操作。输出最终能获得的最大分数。

输入格式

第一行一个数字 nnn

接下来一行 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1,a2,,an

输出格式

一个数,表示答案。

样例输入

3
1 2 3

样例输出

26

数据规模

所有数据保证 1≤n≤300,1≤ai≤1061≤n≤300,1≤a_i≤10^61n300,1ai106

解题思路

是没见过的船新版本DP

首先简单说明一下每轮操作的含义

对于要合并的长度为lenlenlen的区间[l,r][l,r][l,r],我们先分别合并左右两部分[l,k][l,k][l,k][k+1,r][k+1,r][k+1,r],那么容易知道:

dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + (num[l][k] - num[k + 1][r]) ** 2)

也就是说合并区间[l,r][l,r][l,r]所得到的分数等于分别合并左右区间得到的分数再加上最后一次合并得到的分数

DPDPDP的基本思想就是对于任意一个长度为lenlenlen的区间(第一重循环),我们尝试其所有可能的划分(第三重循环),找出其中的最大值

第二重循环?它负责遍历每一个长度为lenlenlen的区间

而我们从小到大遍历lenlenlen,保证了在动态规划过程中,所有长度小于lenlenlen的区间最优结构已经得到,所以DPDPDP是可行的

AC代码如下

#include <iostream>
using namespace std;
const int mod_num = 1000003;
const int max_n = 300;long long num[max_n + 1][max_n + 1], dp[max_n + 1][max_n + 1];
int n;int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> num[i][i];for (int i = 1; i < n; i++) {for (int j = i + 1; j <= n; j++) {num[i][j] = num[j][j];num[i][j] = (num[i][j] * num[i][j - 1]) % mod_num;}}for (int len = 2; len <= n; len++) {for (int l = 1, r = len; r <= n; l++, r++) {for (int k = l; k < r; k++) {dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + (num[l][k] - num[k + 1][r]) * (num[l][k] - num[k + 1][r]));}}}cout << dp[1][n] << endl;return 0;
}

T3 [Daimayuan]饿饿 饭饭2(C++,数学)

接着《饿饿 饭饭》 的故事,在两天后,食堂的工作人员回来了,整个食堂又回到了原来井井有条的状态。

两个月后,由于天气越来越热,大家的胃口越来越小了,作为食堂管理员的CCCCCC非常担心孩子们的身体健康,所以他决定开展一个活动来调动孩子们吃饭的积极性,顺便考验一下孩子们的数学水平。活动内容如下:

先让每一个孩子都抽一个球,每一个球上有一个数字, 然后给这个孩子nnn个数字,每一个孩子都有无数次操作机会,每一次都会选中一个数将它乘上222,或者乘上333,请问这个孩子可以通过上面的操作将这nnn个数都变成相同的吗?

如果回答正确,这个回答正确的孩子就可以得到一份免费的午餐,但是这对于孩子们来说是在是太困难了,但是他们都想吃到免费的午餐,所以他们都想请你告诉他们正确的答案,让他们都迟到免费的午餐。

输入格式

111行给定一个数TTT,表示有TTT个小孩子请你告诉他正确的答案。

222T+1T+1T+1行,第111个数是每个孩子抽到的数字nnn,第222n+1n+1n+1个数是对应的nnn个数字。

输出格式

如果可以变成相同的,输出YES。如果不能变成相同的,输出NO

数据规模

1≤T≤100,1≤n≤2×105,1≤ai≤1091≤T≤100,1≤n≤2×10^5,1≤a_i≤10^91T100,1n2×105,1ai109

数据保证∑i=1Tn≤2×105\sum^{T}_{i=1}{n}≤2×10^5i=1Tn2×105

样例输入

2
4 75 150 75 50
3 100 150 250

样例输出

YES
NO

解题思路

将每个数字拆解成两部分的乘积:2、32、323和其他数字

我们尝试把所有数字的第一部分除去,如果剩余部分相等,输出YES

反之,输出NO

AC代码如下

#include <iostream>
using namespace std;
const int max_t = 100;
const int max_n = 2e5;
const int max_a = 1e9;int t, n;
int num_arr[max_n];int main() {cin >> t;for (int i = 0; i < t; i++) {cin >> n;for (int j = 0; j < n; j++) {cin >> num_arr[j];while (num_arr[j] % 2 == 0) num_arr[j] /= 2;while (num_arr[j] % 3 == 0) num_arr[j] /= 3;}int j, same = num_arr[0];for (j = 1; j < n; j++) if (num_arr[j] != same) break;if (j != n) cout << "NO" << endl;else cout << "YES" << endl;}return 0;
}

T4 [Daimayuan]子串分值和(C++,字符串)

对于一个字符串 SSS ,我们定义 f(S)f(S)f(S)SSS 中出现的不同的字符个数。 例如 f(aba)=2f(aba)=2f(aba)=2f(abc)=3f(abc)=3f(abc)=3,f(aaa)=1f(aaa)=1f(aaa)=1

现在给定一个字符串 SSS (假设长度为 lenlenlen),请你计算 ∑i=0len−1∑j=ilen−1f(S[i:j])\sum_{i=0}^{len−1}\sum_{j=i}^{len−1}f(S[i:j])i=0len1j=ilen1f(S[i:j])

输入格式

输入一行包含一个由小写字母组成的字符串 SSS

输出格式

输出一个整数表示答案。

样例输入

ababc

样例输出

28

数据规模

所有数据保证字符串长度 len≤1000000len≤1000000len1000000,字符串下标从 000len−1len−1len1

解题思路

直接正面求解每一个字符串的分值显然会TLETLETLE,那么尝试其他方法

我们的想法是单独处理每一个字符的分值,然后累加起来

直接去找该字符出现在多少字符串中并不容易,正难则反,我们尝试去寻找该字符没有出现在多少字符串中

举个例子ababc,其中a没有出现的字符串显然只有b,b,c,bc

所以想要找到所有没有出现a的字符串,我们只需要保存a出现过的每一个位置,然后根据间隔字符串长度计算即可

AC代码如下

#include <iostream>
#include <vector>
using namespace std;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const int max_len = 1e6;vector<int>vocab[26];
long long ans = 0;inline long long calc(long long num) {return num * (num + 1) / 2;
}int main() {string str;cin >> str;int len = str.size();for (int i = 0; i < len; i++) {vocab[str[i] - 'a'].push_back(i);}for (char c : alpha) {long long sum = calc(len);if (!vocab[c - 'a'].empty()) {int l = 0;auto iter = vocab[c - 'a'].begin();while (iter != vocab[c - 'a'].end()) {sum -= calc(*iter - l);l = *iter + 1; iter++;}sum -= calc(len - l);ans += sum;}}cout << ans << endl;return 0;
}

后排提醒:要开long long,否则会炸

T5 [Daimayuan]蒟蒻(C++,STL)

便利蜂的货架上摆了一排蒟蒻果冻,搞得鶸尛鱻眼花缭乱…

对于每个果冻,都有一个价格 www 和口感 ttt。鶸尛鱻有一个购物篮子,在挑选蒟蒻果冻的时候,他有以下几种操作:

  • 操作 111:把一个价格为 www,口感为 ttt 的果冻放入篮子。
  • 操作 222:拿出篮子中 最为廉价 的果冻。
  • 操作 333:拿出篮子中 口感最差 的果冻。(ttt 越小,口感越差)

鶸尛鱻不喜欢重复,当操作 111价格或口感 与篮中已有果冻重复时,他会立刻将其放回货架。

经过 nnn 次操作后,鶸尛鱻确定了要购买的若干果冻,请你帮他求出篮子里果冻的总价格。

输入格式

111 行一个正整数 nnn,代表操作次数。

222 行至第 (n+1n+1n+1)(n+1n+1n+1) 行,每行 一个或三个 整数,分别表示 opopopwwwttt

wwwttt 当且仅当 op=1op=1op=1 时存在。

输出格式

输出一个整数,表示篮子里果冻的总价格。

样例输入

6
1 1 1
1 2 5
2
1 3 3
3
1 5 2

样例输出

7

数据规模

所有数据保证 1≤n≤1051≤n≤10^51n1051≤w,t≤1061≤w,t≤10^61w,t106,且保证输入合法

解题思路

需要维护两个顺序,一个是价格的升序排序,一个是口感的升序排序

显然需要维护两个数组,关键在于使两个数组维持同步

利用maperase操作可以根据键值删除元素的性质,可以很容易实现这一点

AC代码如下

#include <iostream>
#include <map>
using namespace std;
const int max_n = 1e5;
const int max_w = 1e6;
const int max_t = 1e6;map<int, int>m1, m2;
int w, t, n, op;
long long ans;int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> op;if (op == 1) {cin >> w >> t;if (m1.count(w) == 0 && m2.count(t) == 0) {m1[w] = t;m2[t] = w;}}else if (op == 2) {m2.erase(m1.begin()->second);m1.erase(m1.begin());}else {m1.erase(m2.begin()->second);m2.erase(m2.begin());}}for (auto it : m1) {ans += (long long)(it.first);}cout << ans << endl;return 0;
}

T6 [Daimayuan]锦标赛(C++,模拟)

nnn个玩家参加比赛,他们分别有能力值a1,a2,…,ana_1,a_2,…,a_na1,a2,,an

需要进行n−1n−1n1轮比赛,每一轮在剩下的玩家里任选两个玩家i,ji,ji,j。如果∣ai−aj∣>K|a_i−a_j|>Kaiaj>K,那么其中能力值高的玩家会获胜,能力值低的玩家会被淘汰。如果∣ai−aj∣≤K|ai−aj|≤KaiajK,那么两个玩家都有可能获胜,另一个玩家被淘汰。

n−1n−1n1轮比赛之后,只剩下一个玩家。问有多少个玩家可能是最后获胜的玩家。

输入格式

第一行,两个整数n,Kn,Kn,K,表示玩家的总人数,和获胜条件中的参数。

接下来一行nnn个整数a1,a2,…,ana_1,a_2,…,a_na1,a2,,an,表示玩家的能力值。

输出格式

一个整数,表示最后可能获胜的玩家个数。

样例输入1

5 3
1 5 9 6 3

样例输出1

5

样例输入输出2

见下发文件。

数据规模

101010组数据。

测试点111满足n≤5n≤5n5

测试点222满足n≤10n≤10n10

测试点3,4,53,4,53,4,5满足n≤1000n≤1000n1000

对于100100100%的数据,满足n≤105n≤10^5n105,1≤ai,K≤1091≤a_i,K≤10^91ai,K109

解题思路

能力值越高的越容易获胜,这是显然的

如果我们要计算最多有多少人可能获胜,自然要求出能获胜的最低能力值是多少

题目中给出了一个能够以弱胜强的最大能力差值KKK,能力差值大于KKK的时候弱的一方不可能获胜

所以我们让能力值大的先开始比赛,每次比赛都让能力值小的一方获胜(前提是能获胜)

最后当能力值小的一方不可能获胜的时候,我们就得到了最多有多少人可能获胜

AC代码如下

#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 1e5;
const int max_a = 1e9;
const int max_k = 1e9;int n;
long long k, gamer[max_n + 1];int main() {cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> gamer[i];}sort(gamer + 1, gamer + 1 + n, greater<long long>());long long ans = 1;long long buffer = gamer[1];for (int i = 2; i <= n; i++) {if (buffer - gamer[i] <= k) {ans++;buffer = gamer[i];}else break;}cout << ans << endl;return 0;
}

T7 [Daimayuan]可重排列(C++,字符串)

请按字典序从小到大的顺序输出所有序列,满足序列中有 p1p_1p1111, p2p_2p2222, ......... , pnp_npnnnn

输入格式

第一行一个整数 nnn

第二行 nnn 个整数 p1p_1p1,p2p_2p2,…,pnp_npn

输出格式

按字典序从小到大的顺序一行一行输出所有满足条件的序列,每行一个序列,相邻两个数字需要用空格隔开。

样例输入

3
1 2 2

样例输出

1 2 2 3 3
1 2 3 2 3
1 2 3 3 2
1 3 2 2 3
1 3 2 3 2
1 3 3 2 2
2 1 2 3 3
2 1 3 2 3
2 1 3 3 2
2 2 1 3 3
2 2 3 1 3
2 2 3 3 1
2 3 1 2 3
2 3 1 3 2
2 3 2 1 3
2 3 2 3 1
2 3 3 1 2
2 3 3 2 1
3 1 2 2 3
3 1 2 3 2
3 1 3 2 2
3 2 1 2 3
3 2 1 3 2
3 2 2 1 3
3 2 2 3 1
3 2 3 1 2
3 2 3 2 1
3 3 1 2 2
3 3 2 1 2
3 3 2 2 1

数据规模

对于 100100100% 的数据,保证 1≤n≤91≤n≤91n9,1≤pi≤91≤p_i≤91pi9,保证满足条件的序列个数不超过 10510^5105 个。

解题思路

这里我们隆重介绍一个新的偷懒工具,next_permutationprev_permutation

传入的参数是数组的起止位置指针,功能是对数组本身操作,得到下一个/上一个字典序排列

然后怎么做就不用我说了吧qwqqwqqwq

AC代码如下

#include <iostream>
#include <algorithm>
using namespace std;void read(string& str) {int n1, n2;cin >> n1;for (int i = 1; i <= n1; i++) {cin >> n2;str.append(n2, i + '0');}
}int main() {string str = ""; read(str);int len = str.size();do {for (int i = 0; i < len; i++) printf("%c ", str[i]);printf("\n");}while (next_permutation(str.begin(), str.end()));return 0;
}

T8 [Daimayuan]进制转换(C++)

题面

让我看看是谁不会进制转换,哦原来是我


以不同进制的形式输入 nnn 个非负整数,求出它们的和并以 mmm 进制的形式输出。

使用大写字母 A ~ Z 依次代表 101010 ~ 353535, 小写字母 a ~ z 依次代表 363636 ~ 616161

输入格式

第一行输入两个整数 1≤n≤101≤n≤101n102≤m≤622≤m≤622m62

接下来 nnn 行,每行输入一个整数 2≤t≤622≤t≤622t62, 一个 ttt 进制数 0≤x≤1090≤x≤10^90x109

输出格式

一个 mmm 进制数,为最终的结果

输入样例1

2 2
2 1
6 10

输出样例1

111

输入样例2

1 10
52 aA0

输出样例2

97864

输入样例3

2 52
36 AMD
52 YES

输出样例3

dJD

解题思路

由任意进制转换为十进制:

遍历每一位上的数字,乘以其位权重,累加

由十进制转换为任意进制:

对十进制数进行取模,余数插入转换后结果的左侧,然后将十进制数除以101010,循环操作直到十进制数为000

AC代码如下

#include <iostream>
#include <map>
#include <string>
using namespace std;
const int max_n = 10;
const int max_m = 62;
const int max_t = 62;
const int max_len = 64;
const string sign_set = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";int n, t;
long long m;
string num;
map<char, int>convert;
char output[max_len + 1];void init() {int len = sign_set.size();for (int i = 0; i < len; i++) {convert.insert(pair<char, int>(sign_set[i], i));}
}int main() {init();cin >> n >> m;long long decimal = 0;for (int i = 0; i < n; i++) {cin >> t >> num;int p = 1;int len = num.size() - 1;for (int i = len; i >= 0; i--) {decimal += (long long)(convert[num[i]] * p);p *= t;}}int idx = max_len - 1;while (decimal != 0) {output[idx--] = sign_set[decimal % m];decimal /= m;}cout << &(output[++idx]) << endl;return 0;
}

T9 [Daimayuan]循环子串(C++,字符串)

题目描述

一个字符串SSS是另一字符串TTT的循环子串当且仅当存在kkk, TTT所有字符循环右移kkk位后得到的新串T′T′T,满足SSST′T′T的子串。

例如: abccefab的循环子串。 (cefab循环右移222位得到abcef, abcabcef的子串)

一个串PPP是完全循环串当且仅当对于它的任一子串HHH, 都有HreverseHreverseHreversePPP的循环子串 (HreverseHreverseHreverseHHH的倒转, 如abc reversereversereverse后 为cba)。

给一个长度为nnn的字符串, 判断它是不是完全循环串。

输入格式

第一行一个正整数ttt, 表示测试数据组数。

对于每一组数据,第一行一个正整数nnn, 表示字符串的长度。接下来一行一个长度为nnn的字符串. 仅包含小写字母。

输出格式

对于每组测试数据,如果这个串是完全循环串, 输出YES,否则输出NO。每组测试数据之间输出换行。

数据范围

对于所有数据 有 1≤t≤1001≤t≤1001t100, 1≤n≤1031≤n≤10^31n103, ∑n≤103\sum n≤10^3n103

样例输入

2
4
ccca
11
eeaafbddfaa

样例输出

YES
NO

提示

  1. 本道题目只需要语法知识就可以解决。

  2. 任意子串是什么意思呢?

  3. 如果一个子串包含另一个子串,那么我们是不是只需要求出大子串的合法情况,就可以推出小子串的合法情况。

  4. 从大的子串向小的子串考虑 最大的子串是什么呢?

解题思路

假设abc是循环子串,那么cba也应该是循环子串,则有***abc***cba***

*注:这里将abccba调换也可以,*的数量可以是任意的

进一步假设abcd是循环子串,则有***abcd*dcba***

不难发现,如果abcd是循环子串,则abc自然也是循环子串

所以我们只需要证明最大的循环子串符合条件即可

也就是将给定字符串反转,然后寻找其是否存在

而对于可以循环右移的字符串,我们只需要将其复制然后拼接,在处理之后的字符串中寻找即可

AC代码如下

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int max_t = 100;
const int max_n = 1e3;string str;
int t, len;int main() {cin >> t;for (int i = 0; i < t; i++) {cin >> len >> str;string rev = str;reverse(rev.begin(), rev.end());str = str + str;if (str.find(rev) != -1)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

T10 [Daimayuan]饿饿 饭饭之暑假大狂欢(C++,数学)

故事接着《饿饿 饭饭 2》,又过了几个月,暑假来啦!!!

这天,cccccc和他的小伙伴们决定一起去游乐园玩,他们一天将游乐园的所有设施玩了个遍,甚至大摆锤,过山车他们还去了很多次,愉快的时间总是很短暂的,很快时间就来到了晚上,但是你以为一天的娱乐时光就这样结束了吗,那你就猜错啦。

晚上,游乐园晚上的partypartyparty就开始啦,其中有一个游戏环节,赢的人可以得到免费的西瓜,饿到不行的cccccc和他的小伙伴非常希望得到这个西瓜。

包括cccccc和他的小伙伴,有ttt个玩家参与了这个游戏,每个玩家都有一张带有数字的卡片。第iii张卡片上有nin_ini个数字,分别是m1,m2,...mnm_1,m_2,...m_nm1,m2,...mn

游戏过程中,主持人从袋子里一个一个地取出编号的球。 他用洪亮而清晰的声音大声念出球的编号,然后把球收起来。 如果玩家的卡片上有对应的数字,就可以将它划掉。 最先从他的卡片上划掉所有数字的人获胜。 如果多人同时从他们的卡片上划掉所有数字,那么这些人都不能赢得比赛。 在游戏开始时,袋子里有 100100100 个球,编号从 111100100100,所有球的编号都是不同的。

cccccc偷偷知道了每个玩家的数字。 想请你确定每个玩家是否可以在最有利于他的情况下赢得比赛。

输入格式

第一行给出一个数ttt,代表ttt个玩家。

接下来第二行到t+1t+1t+1行,每行第一个数为nin_ini,代表这个人手中有nnn个卡片,接下来给出序列a1...ana_1...a_na1...an表示这个人所拥有的卡片的数字。

输出格式

输出ttt行,每一行给出第iii个人在最有利的情况下是否能赢得比赛,可以输出YES, 不可以输出NO

数据范围

1≤t≤100,1≤n≤100,1≤mi≤1001≤t≤100,1≤n≤100,1≤m_i≤1001t100,1n100,1mi100

样例输入

3
1 1
3 2 4 1
2 10 11

样例输出

YES
NO
YES

解题思路

不难发现,如果有一个人不能获胜,那么一定是有其他人的数字集合是他的子集(注:由于可以一次性划去多个数字,重复个数字直接按单个数字处理即可)

那么采用最简单的判断思路——暴力搜索

计算一下时间复杂度:最多需要判断100100100个人,对于每个人需要搜索其余999999个人,每人最多有100100100个数字,所以时间复杂度上限是10610^6106,可以接受

所以我们可以采用二维bool数组存储每一个人数字,然后进行||的操作:

num_arr[i][k] != (num_arr[i][k] || num_arr[j][k])

当且仅当num_arr[i][k]没有k数字(为falsefalsefalse),且num_arr[j][k]k数字(为truetruetrue)时表达式为真

如果表达式为真,就可以停止判断了,因为二者有不同的元素;如果表达式始终为假,那么就说明j的数字集合是i的子集,i不可能获胜

AC代码如下

#include <iostream>
using namespace std;
const int max_n = 100;
const int max_len = 100;bool num_arr[max_n + 1][max_len + 1];
int n, m;int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> m;int num;for (int j = 0; j < m; j++) {cin >> num;num_arr[i][num] = true;}}for (int i = 1; i <= n; i++) {bool win = true;for (int j = 1; j <= n; j++) {if (i == j) continue;int k;for (k = 1; k <= max_len; k++) {if (num_arr[i][k] != (num_arr[i][k] || num_arr[j][k])) {break;}}if (k == max_len + 1) {win = false;break;}}if (win) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

http://www.ppmy.cn/news/38985.html

相关文章

【实习_面试全程辅导分享】海康威视_测开面经

📡📡海康威视的面试题与其他很多公司都是不同的,面试官更看重的是你这个面试的人,靠不靠谱,更多的是看重你的临场应变能力以及如何解决问题的能力,如何与身边的同事相处,如何更快的融入集体,一起完成项目的能力与积极性! 分享一些日常: 🕰面试题来了! ⏳1.听…

当下的网络安全行业前景到底怎么样?还能否入行?

前言网络安全现在是朝阳行业&#xff0c;缺口是很大。不过网络安全行业就是需要技术很多的人达不到企业要求才导致人才缺口大常听到很多人不知道学习网络安全能做什么&#xff0c;发展前景好吗&#xff1f;今天我就在这里给大家介绍一下。网络安全作为目前比较火的朝阳行业&…

01背包二维数组转一维数组

01背包二维数组转一维数组 01背包是一种经典的动态规划问题&#xff0c;是指在给定容量的情况下&#xff0c;选择一些物品放入背包&#xff0c;使得物品的总价值最大&#xff0c;且不能超过背包的总重量&#xff0c;01表示选或不选两种状态&#xff0c;每种物品只有这两种状态…

闪存系统性能优化方向集锦?AC timing? Cache? 多路并发?

声明 主页: 元存储的博客_CSDN博客 依公开知识及经验整理,如有误请留言。 个人辛苦整理,付费内容,禁止转载。 内容摘要 1. 优化 AC Timing,提升总线频率 1.1 优化 AC Timing 1.2 优化总线频率 2. 使用 Cache Read/Program

怎样架设传奇 30分钟学会传奇架设;画面精美大气的战神冰雪传奇,时下最流行的微端搭建设技术分享

服务器配置&#xff1a;2核4G/1M以上配置 服务器系统&#xff1a;Windows Server 2008 R2 x64 说明&#xff1a;大唐冰雪使用当下流行的微端技术&#xff0c;客户端只有23MB,所有主要资源是在服务器上更新。 所以为了不占用服务器太多宽带&#xff0c;以及下载速度的要求&…

MySQL四种日志binlog/redolog/relaylog/undolog

优质博文&#xff1a;IT-BLOG-CN 一、binlog binlog记录数据库表结构和表数据变更&#xff0c;比如update/delete/insert/truncate/create&#xff0c;它不会记录select。存储着每条变更的SQL语句和XID事务Id等等。binlog日志文件如下&#xff1a; [root192.168.10.11]# mysq…

3/31~4/2总结

封装 封装指的是将对象的状态信息隐藏在对象内部&#xff0c;不允许外部程序直接访问对象内部信息&#xff0c;而是通过该类所提供的方法来实现对内部信息的操作和访问 访问控制符 一共4个&#xff1a;privite,default,protected,public,访问控制级别由小到大 privite (…

GPT-4问世;LLM训练指南;纯浏览器跑Stable Diffusion

1.多模态GPT-4正式发布&#xff1a;支持图像和文本输入&#xff0c;效果超越ChatGPT OpenAI的里程碑之作GPT-4终于发布&#xff0c;这是一个多模态大模型&#xff08;接受图像和文本输入&#xff0c;生成文本&#xff09;。主要能力有&#xff1a; GPT-4可以更准确地解决难题&a…

IDEA使用JDBC详解(2023最新)

第一步&#xff1a;新建一个java项目 第二步&#xff1a;导入jdbc驱动jar包 jdbc的jar包下载 下载地址&#xff1a; 官方下载地址&#xff1a; MySQL :: Download Connector/J 备用下载地址&#xff1a; mysql5的jdbc驱动包 mysql8的jdbc驱动包 右键根目录新建一个文件夹…

towhee+elasticsearch实现本地以图搜图

towhee-img-search towheeelasticsearch实现本地以图搜图 github地址&#xff1a;https://github.com/xjhqre/towhee-img-search elasticsearch版本为 7.4.2 elasticsearch安装方法参考我的这篇文章&#xff1a;全文检索-ElasticSearch 使用方法 一、使用 OSS 存储图片&a…

研究生课程网站《面向对象程序设计》

研究生课程网站《面向对象程序设计》是可以运行于任何平台的的教师和学生互动交流系统,系统采用windows作为开发平台,wamp为运行环境,主要实现了教师共享资源、学生提交选题、提交报告,教师收取,资源的上传和下载等. 本文采用PHP技术开发了基于Web的研究生课程网站《面向对象程…

vs code配置go语言开发环境

VS code 配置go语言开发环境1.下载go安装包1.1go语言安装包1.2安装步骤1.3 检查go环境1.dos界面输入 go version2.vs code配置go语言2.1 安装go语言开发扩展2.2安装go开发工具包1.配置国内代理地址2.安装go开发工具包3.配置windows系统环境1.下载go安装包 1.1go语言安装包 官…

FMSoft uniGUI Professional 1.90.0.1564 Crack

uniGUI Web 应用程序框架将 Web 应用程序开发体验扩展到一个新的维度。uniGUI使Delphi开发人员能够使用一组独特的可视化组件在 IDE 中创建、设计和调试 Web 应用程序。每个组件都旨在提供与 Delphi VCL 中对应的可视化组件相同的功能。这提供了一个非常舒适的开发环境&#xf…

贡献最大的发明

这个问题没有唯一的答案&#xff0c;因为人类的发明涵盖了广泛的领域&#xff0c;例如医学、工程、通讯、农业、科学等等。以下列举了一些被认为是最重要的发明&#xff1a; 电力&#xff1a;电力的发明使得人类可以使用电能来驱动各种机器和设备&#xff0c;极大地改变了我们…

【LeetCode每日一题】——1984.学生分数的最小差值

文章目录一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】一【题目类别】 滑动窗口 二【题目难度】 简单 三【题目编号】 1984.学生分数的最小差值 四【题目描述】 给你…

【JavaScript】45_间接修改css样式

16、间接修改css样式 除了直接修改样式外&#xff0c;也可以通过修改class属性来间接的修改样式 通过class修改样式的好处&#xff1a; 可以一次性修改多个样式对JS和CSS进行解耦 元素.classList 是一个对象&#xff0c;对象中提供了对当前元素的类的各种操作方法 元素.c…

彻底理解FreeRTOS中的队列(Queue)

“队列”&#xff08;Queue&#xff09;提供了任务与任务之间通信的机制。在这样的场景&#xff1a;一个或多个其他的任务产生数据&#xff0c;主任务要依次处理数据&#xff0c;队列就显得非常有用了。 参考资料&#xff1a;《Mastering the FreeRTOS Real Time Kernel》-Cha…

零基础学习Java 01

目录 java语言特性 JDK、JRE、JVM 字符编码 数据类型 数据类型默认转换 标识符命名方法 java语言特性 简单性&#xff1a;相对于其他编程语言而言&#xff0c;java较为简单&#xff0c;例如&#xff1a;java不再支持多继承&#xff0c;C是支持多继承的&#xff0c;多继承…

JVM 字符串常量池(StringTable)

String的基本特性 String&#xff1a;字符串&#xff0c;使用一对 “” 引起来表示String s1 "hello" ; // 字面量的定义方式String s2 new String("hello"); // new 对象的方式 String被声明为final的&#xff0c;不可被继承 String实现了…

两个数组的交集(力扣刷题)

给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;https://leetcode.cn/problems/intersection-of-two-arrays 说…
最新文章