题目链接 题目大意: 给出一个字符串,由小写字母组成; 现在Alice和Bob在玩游戏,轮流从字符串中移除一个子串,Alice先操作; Alice允许移除偶数长度子串,Bob允许移除奇数长度子串;(也允许不移除) 最终看每个人移除子串的分数总和,字母a是1分,b是2分、、、z是26分; 问最终谁能赢得游戏,以及胜者领先的分数;
输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤5⋅1e4) 每个样例一行,字符串𝑠 (1≤|𝑠|≤2⋅1e5)
输出: 每个样例一行,胜者和胜者领先的分数;
Examples input 5 aba abc cba n codeforces output Alice 2 Alice 4 Alice 4 Bob 14 Alice 93
题目解析: Alice先手,并且可以移除偶数字符串,那么字符串如果是偶数,Alice会移除所有字符; 如果是奇数,Alice只会留下1个字符串,要么是最左边,要么是左右边的字符,选择一个较小值; Bob后手,只能选择alice剩下的字符串。
class Solution {
static const int N = 201010;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> str;
int sum = 0;
for (int i = 0; i < str.length(); ++i) {
sum += str[i] - 'a' + 1;
}
if (str.length() % 2) {
int bob = min(str[0], str[str.length() - 1]) - 'a' + 1;
int alice = sum - bob;
cout << (alice > bob ? "Alice" : "Bob") << " " << abs(alice - bob) << endl;
}
else {
cout << "Alice " << sum << endl;
}
}
}
}
ac;
题目链接 题目大意: 给出一个字符串,由小写字母组成; 如果这个字符串的所有子串都满足,构成字符串的字符数相差不超过1,则称这个字符串为完美字符串,比如说:
现在给出一个字符串,询问是否为完美字符串;
输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤2⋅1e4) 每个样例一行,字符串𝑠 (1≤|𝑠|≤2⋅1e5)
输出: 每个样例一行,如果是完美字符串则输出YES;如果不是完美字符串则输出NO;
Examples input 5 aba abb abc aaaaa abcba codeforces output YES NO YES YES NO
题目解析: 根据题目的要求,任意子串的字符数相差要在1以内,假设一共有k个不同字符; 那么从字符串中任意截取k长度的字符串,必然会由不同的字符组成,否则就会出现重复字符数>1,然后没出现的字符数位0,那么就不符合题目的要求; 并且由于可以任取,我们在[1, k]是由k个不同的字符构成,[2, k+1]也是k个不同的字符构成,由此可以推导出str[k+1] = str[1],并由此类推,完美字符串必然是abcd abcd abc 这样的重复构成; 这样只需要检测字符串是否满足这个特性即可。
class Solution {
static const int N = 201010;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> str;
int sum = 0, v[26] = {0};
for (int i = 0; i < str.length(); ++i) {
int index = str[i] - 'a';
if (!v[index]) {
v[index] = 1;
++sum;
}
}
bool ans = true;
memset(v, 0, sizeof(v));
for (int i = 0; i < sum; ++i) {
int index = str[i] - 'a';
if (!v[index]) {
v[index] = 1;
}
else {
ans = false;
break;
}
}
if (ans) {
int pos = sum;
while (pos < str.length() && ans) {
for (int i = pos; i < str.length() && i < (pos + sum); ++i) {
if (str[i] != str[i - sum]) {
ans = 0;
break;
}
}
pos += sum;
}
if (ans) {
cout << "YES" << endl;
}
}
if (!ans) {
cout << "NO" << endl;
}
}
}
}
ac;
题目链接 题目大意: 给出一个数字n,将数字n可以拆分成若干个整数之和; 现在想知道,有多少种拆分方法,要求拆分出来的整数都是回文数; (拆分出来的数字至少有一个不同,才算不同组合)
输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e4) 每个样例一行,整数 𝑛 (1≤𝑛≤4⋅1e4)
输出: 每个样例一行,输出不同的组合数字;结果可以对1e9+7取模;
Examples input 2 5 12 output 7 74
题目解析: 首先,把1到40000的回文数全部列出来,得到若干个回文数; 题目的要求是计算数字n拆分有多少种组合,我们只看数字1和2,就是将数字n拆成1和2的和; 这个和动态规划的经典题目类似:上n个台阶,每次有1步或者2步,最后有多少走法;
但是这个题目有点不同,就是对不同走法的判断,这里只有新增不同数字的情况,才认为是不同的;(1+2和2+1是一样的) 那么我们将回文数数字从小到大排列,然后判断每次回文数是否可以替换已有数字即可。 比如说: 考虑数字1,有dp[1]=1,dp[2]=1, dp[3]=1, dp[4]=1;(dp[i]表示数字i有多少总走法) 考虑数字2,有dp[1]=1,dp[2]=2, dp[3]=2, dp[4]=3;对于dp[2],引入2的时候多了2=2的选择,同时还有原来的2=1+1;对于dp[4],可以在dp[2]的基础上+2(新增2种选择4=2+2, 4=1+1+2),也可以不使用2,保留原来的4=1+1+1+1;
按照这种思路分析,可以得到状态转移方程还是dp[i]=dp[i]+dp[i-k];(k是回文数)
class Solution {
static const int N = 40100;
static const int MOD = 1e9 + 7;
int dp[N];
bool check(int k) {
vector<int> vec;
while (k) {
vec.push_back(k % 10);
k /= 10;
}
for (int i = 0; i < vec.size() / 2; ++i) {
if (vec[i] != vec[vec.size() - i - 1]) {
return false;
}
}
return true;
}
public:
void solve() {
vector<int> vec;
for (int i = 1; i < N; ++i) {
if (check(i)) {
vec.push_back(i);
}
}
dp[0] = 1;
for (int j = 0; j < vec.size(); ++j) {
for (int i = vec[j]; i < N; ++i) {
dp[i] = ((lld)dp[i] + dp[i - vec[j]]) % MOD;
}
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << dp[n] << endl;
}
}
}
ac;
题目链接 题目大意: 给出n个数字𝑎1,𝑎2,⋯,𝑎𝑛 ,要求构造一个长度不超过300的整数数组b,要求: 数组b中没有重复的元素; 数组b包括了数组a的所有数字; 数组b任意两个数字的差,其绝对值可以在数组b中找到相同数字。
输入: 第一行是整数t,表示有t个样例 (1≤𝑡≤50 ). 每个样例第一行是整数𝑛 (2≤𝑛≤100); 第二行是n个整数 𝑎1,𝑎2,⋯,𝑎𝑛 (−100≤𝑎𝑖≤100)
输出: 如果有解,先输出YES,再输出整数k,表示有k个整数; (𝑛≤𝑘≤300) 𝑏1,𝑏2,⋯,𝑏𝑘 (−1e9≤𝑏𝑖≤1e9) 如果无解则输出NO;
Examples input 4 3 3 0 9 2 3 4 5 -7 3 13 -2 8 4 4 8 12 6
output yes 4 6 0 3 9 yEs 5 5 3 1 2 4 NO Yes 6 8 12 6 2 4 10
题目解析: 构造出来的数组b中不会存在负数,证明: 假设a[i]-a[j],a[j]小于零,则必然需要一个比a[i]的数字a[k],但是a[k]-a[j]又会产生更大的数字;
所以数组a中存在负数无解; 其他的情况,就用1、2、3、4到max来填充即可。
class Solution {
static const int N = 200010;
public:
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int maxNum = 0, minNum = 200;
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
maxNum = max(maxNum, k);
minNum = min(minNum, k);
}
if (minNum < 0) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
cout << maxNum + 1 << endl;
for (int i = 0; i <= maxNum; ++i) {
cout << i << " ";
}
cout << endl;
}
}
}
}
ac;
题目链接 题目大意: 给出n个整数的数组,从左到右可以依次选择若干个整数,要求累加和在过程中始终不能为负数。 已知初始数字和为0,想知道最多能选择多少个数字。
输入: 第一行是整数 𝑛 (1≤𝑛≤2000) 第二行是n个整数𝑎1 , 𝑎2, ... ,𝑎𝑛 (−1e9≤𝑎𝑖≤1e9) 输出: 输出能选择的最多整数。
Examples input 6 4 -4 1 -3 1 -3 output 5
题目解析: 一种简单的策略: 遇到正的就吃,遇到负的就看当前能否吃下,能够吃则直接吃; 如果不能吃,则考虑是否将吃过的负数吐出来,如果存在某个负数的绝对值 比这个数字的绝对值要大,则可以把原来的负数吐出来,把这个数字吃进去;
可以用优先队列来记录负数,复杂度O(NlogN);
class Solution {
static const int N = 200010;
public:
int a[N];
priority_queue<int, vector<int>, greater<int> > q;
public:
void solve() {
int t = 1;
while (t--) {
int n;
cin >> n;
while (!q.empty()) {
q.pop();
}
lld sum = 0, ans = 0;
for (int i = 0; i < n; ++i) {
int tmp;
scanf("%d", &tmp);
if (sum + tmp >= 0) {
++ans;
sum += tmp;
if (tmp < 0) {
q.push(tmp);
}
}
else {
int top = 0;
if (!q.empty()) {
top = q.top();
}
if (top < tmp) {
q.pop();
q.push(tmp);
sum = sum - top + tmp;
}
}
}
cout << ans << endl;
}
}
}
ac;