第一题
题目: Problem - 1629A - Codeforces
题意:
有n个数，每个数有两个属性Wi和Vi，给定我们一个初始值k。如果当前某个数的Wi 小于k，那么就可以把Vi加到k上，求k最大值为多少。
输入格式
输入包含多个样例，第一行是一个整数t，代表有t个整数。
每个样例第一行是两个整数n和k。
每个样例第二行有n个整数，分别为W1 ~ Wn。
每个样例第三行有n个整数，分别为V1 ~ Vn。
数据范围
1 ≤ t ≤ 100
1 ≤ n ≤ 100, 1 ≤ k ≤ 1000
1 ≤ Wi, Vi ≤ 1000
输出格式
输出一个整数。
输入样例：
4
3 10
20 30 10
9 100 10
5 1
1 1 5 1 1
1 1 1 1 1
5 1
2 2 2 2 2
100 100 100 100 100
5 8
128 64 32 16 8
128 64 32 16 8输出样例：
29
6
1
256思路:
- 水题，将所有数字按属性W从小到大排序，循环判断k是否大于Wi，如果大于就加上Vi，否则退出。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int N = 150;
int n,k;
PII p[N];
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n >> k;
for (int i = 1; i <= n; ++i)cin >> p[i].first;
for (int i = 1; i <= n; ++i)cin >> p[i].second;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; ++i)
{
if (p[i].first <= k)k += p[i].second;
else break;
}
cout << k << endl;
}
return 0;
}第二题
题目: Problem - 1629B - Codeforces
题意:
给定我们一个集合和k次操作，集合中的数为区间[l, r]中的整数，每次操作可以从集合中取出两个数，并将两个数的积加入到集合中，直到k次操作结束或者集合中只有一个数。如果结束后集合中所有的数的最大公因数大于1，输出 YES ，否则输出 NO
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例只有一行，有三个数，l，r，k。
输出格式
一个整数，表示第几个字符串。
数据范围
1≤ N ≤105
YES 或 NO
输入样例：
9
1 1 0
3 5 1
13 13 0
4 4 0
3 7 4
4 10 3
2 4 0
1 7 3
1 5 3输出样例：
NO
NO
YES
YES
YES
YES
NO
NO
YES思路:
- 看上去好像很难（一眼以为不会，就去做D题了，结果D题连WA两次，一看榜发现B题通过率很高，痛！），其实很简单。
- 考虑这样一个问题，什么时候集合中所有数的最大公因子大于1，显然当集合中只有1个数且不为1或者集合中全部为偶数时一定符合。前者的最大公因子就是这个数本身，后者最小的公因子是2。
- 那么问题就转化为k次操作是否能将所有的所有的奇数转化为偶数，怎么转化？奇数乘奇数得到的是奇数，奇数乘偶数得到的是偶数。每次操作可以去掉一个奇数，直接比较集合中的奇数和k谁大就可以了。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int N = 150;
int n;
int main()
{
int t;
cin >> t;
while (t--)
{
int l, r, k;
bool flag = false;
cin >> l >> r >> k;
if (l == r && l != 1)flag = true;
int m = (r - l + 1);
if (m % 2 == 0)m /= 2;
else if (l % 2 == 0)m /= 2;
else m = m / 2 + 1;
if (m <= k || flag == true)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}第四题
题目: Problem - 1629D - Codeforces
题意:
有n个字符串，我们可以删除任意个字符串，问能否在不调整字符串的顺序的前提下，使得剩下的字符串成为回文串。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例第一行是一个整数n，表示有n个字符串。
接下来有n行字符串，每个字符串的长度为1~3。
输出格式
YES 或 NO
数据范围
1 ≤ t ≤ 100
1 ≤ n ≤ 105
输入样例：
6
5
zx
ab
cc
zx
ba
2
ab
bad
4
co
def
orc
es
3
a
b
c
3
ab
cd
cba
2
ab
ab输出样例：
YES
NO
NO
YES
YES
NO思路:
- 很容易想到我们可以用map来存出现过的字符串，每个字符串根据串的长度分类讨论：
- 如果字符串长度为1，显然它的逆序串就是本身，输出
YES。 - 如果字符串长度为2，那么需要判断是否可以和长度为2或者长度为3的字符串组成回文串。
- 字符串长度为3，需要判断是否可以和长度为2或者长度为3的字符串组成回文串。同时要将字符串的前两个字符取出存好，以便于和后面长度为2的字符串组成回文。
- 如果字符串长度为1，显然它的逆序串就是本身，输出
- 这里有个大坑，从长度为3的串中取出的子串不能和初始长度为2的串存在一起，否则将会造成混乱，比如会将abc，dba视为回文串。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int N = 150;
int n;
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
bool flag = false;
//要将长度为2的字符串用两个map来存，作用主要体现在将2+3和3+3的匹配区分开。
//如果用一个map存，会出现混乱，比如abc，dba会判断为回文子串
unordered_map<string, int>p23,pp2;//前者存原始长度为2和3的字符串，后者存从长度为3的字符串中截取的字符串
for (int i = 1; i <= n; ++i)
{
string s;
cin >> s;
if (s.size() == 1)flag = true;
else if (s.size()==2)
{
string s1 = s;
reverse(s1.begin(),s1.end());
if (p23[s1]||pp2[s1] || s1[0] == s1[1])flag = true;
p23[s]++;
}
else
{
string s1 = s;
reverse(s1.begin(), s1.end());
if (p23[s1]||s1[0]==s1[2])flag = true;
string s2 = s.substr(1, 2);
reverse(s2.begin(), s2.end());
if (p23[s2])flag = true;
s2 = s.substr(0, 2);
pp2[s2]=p23[s]=1;
}
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
