程序员进阶之算法练习（八十七）
题目1
题目链接
题目大意：
给出一个整数的数组，长度为n；
现在可以进行以下的操作：
选择长度不小于2的区间[l, r]，将区间内的整数依次进行异或操作，然后将得到的整数替换区间所有的数字；
比如说数组[1,5,4,1,4,7]，当我们选择区间[1,5,4]进行异或操作，得到结果是4，然后替换原来的区间内所有数字得到：
[1,5,4,1,4,7]→[4,4,4,1,4,7]
问，如何找到一个操作，使得数组所有元素都为0；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤500)
每个样例两行
第一行整数𝑛(2≤𝑛≤100)
第二行整数𝑎1,𝑎2,…,𝑎𝑛(0≤𝑎𝑖≤100)
输出：
每个样例第一行输出操作次数m，接下来m行，每行2个整数表示操作区间；（m不能大于8）
Examples
input
3
1
100000
2
1 1
3
10 3 3
output
1
2 1
1 3 2
题目解析：
当n=偶数时，令l=1，r=n，我们可以得到一个元素相同的数组；再重复一次这样的操作，由于偶数个一样的数字进行异或，结果就全部是0；
当n=奇数时，类似偶数的做法，我们可以先对偶数长度的区间[1, n-1]进行上述操作，使得区间归零；再对区间[2, n]进行相同操作即可；
stdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n % 2) {
printf("4\n%d %d\n%d %d\n", 1, n - 1, 1, n - 1);
printf("%d %d\n%d %d\n", 2, n, 2, n);
}
else {
printf("%d\n%d %d\n%d %d\n", 2, 1, n, 1, n);
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目2
题目链接
题目大意：
有一个整数n，现在有无限个整数1到k；
现在需要从整数1-k中选择任意个数字，要求满足：
1、这些整数的和等于n；
2、这些整数不包括整数x；
问，是否存在这样的组合；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例一行整数𝑛,𝑘 and 𝑥 (1≤𝑥≤𝑘≤𝑛≤100 ).
输出：
每个样例，如果无解直接输出NO；
如果有解，则先输出YES；然后下一行输出组合的整数个数m，接下来一行输出m个整数；
Examples
input
5
10 3 2
5 2 1
4 2 1
7 7 3
6 1 1
output
YES
6
3 1 1 1 1 3
NO
YES
2
2 2
YES
1
7
NO
题目解析：
分类讨论，假设x!=1，那么必然可以用1来组合所有的数字；
如果 x=1，那么整数1不能选：
1、如果k=1，无解；
2、如果k=2，偶数有解（全部是2），奇数无解；
3、如果k=3，偶数有解（全部是2），奇数有解（去掉一个3变成偶数，剩下全部是2）；
扩展思路：
这个题目还有个实现方式，采用动态规划，我们用dp[i]表示整数i是否有解，同时用pre[i]记录整数i有解的上一个整数（用于输出）；
用提供的整数分别去计算所有状态，最终看dp[n]是否有解。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k, x;
cin >> n >> k >> x;
if (x != 1) {
cout << "YES" << endl;
cout << n << endl;
while (n--) {
cout << "1 ";
}
cout << endl;
}
else {
if (k == 1) {
cout << "NO" << endl;
}
else if (k == 2) {
if (n % 2) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
cout << n / 2 << endl;
while (n) {
cout << 2 << " ";
n -= 2;
}
cout << endl;
}
}
else {
// 2 & 3
cout << "YES" << endl;
cout << n / 2 << endl;
if (n % 2) {
cout << 3 << " ";
n -= 3;
}
while (n) {
cout << 2 << " ";
n -= 2;
}
cout << endl;
}
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目3
题目链接
题目大意：
在一个二维的网格上，每次可以走向相邻格子；
Alice和Bob在网格位置（xA, yA）上，Bob要前往格子(xB, yB)，Alice要前往格子(xC, yC)；
假设Alice和Bob都只会选择到达目的地的最短路径，现在想知道，他们两个可以共同经过的格子数，最大为多少；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例3行
第一行整数𝑥𝐴 and 𝑦𝐴 (1≤𝑥𝐴,𝑦𝐴≤1e8 )
第二行整数𝑥B and 𝑦B (1≤𝑥B,𝑦B≤1e8 )
第三行整数𝑥C and 𝑦C (1≤𝑥C,𝑦C≤1e8 )
输出：
每个样例一行，输出可以共同经过的最大格子数。
Examples
input
3
3 1
1 3
6 4
5 2
2 2
7 2
1 1
4 3
5 5
output
3
1
6
题目解析：
首先以位置A为坐标原点，重新绘制坐标轴，我们得到新的坐标位置B和C。
此时两个人都在坐标原点，坐标B、C分别在四大象限或者数轴上。
可以分情况讨论2个人坐标位置在相同象限、不同象限的情况，但是这样分析简单，实现起来比较复杂。
另外一种做法，就是拆解从原点到坐标B和坐标C的过程。
比如说先考虑横坐标X，如果他们两个人方向相同，则得到两个人X坐标较小值为共同距离；
再考虑横坐标Y，如果他们两个人方向相同，则得到两个人Y坐标较小值为共同距离；
加上在原点的共同格子，就得到答案了。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
pair<int, int> a, b, c;
cin >> a.first >> a.second;
cin >> b.first >> b.second;
cin >> c.first >> c.second;
b.first -= a.first;
b.second -= a.second;
c.first -= a.first;
c.second -= a.second;
int ans = 1;
// 判断x相同的数量
if (b.first > 0 && c.first > 0) ans += min(abs(b.first), abs(c.first));
if (b.first < 0 && c.first < 0) ans += min(abs(b.first), abs(c.first));
// 判断y相同的数量
if (b.second > 0 && c.second > 0) ans += min(abs(b.second), abs(c.second));
if (b.second < 0 && c.second < 0) ans += min(abs(b.second), abs(c.second));
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目4
题目链接
题目大意：
小明要设置密码，密码长度为m，由数字0到9组成，并且密码不能为字符串s的子序列；
同时有字符串l和字符串r，小明设置的密码a要满足 l[i] <= a[i] 且 a[i] <= r[i];
问，小明是否能够找到满足要求的密码。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例4行
第一行字符串𝑠(1≤|𝑠|≤3⋅1e5)
第二行整数𝑚 ，表示字符串l和m的长度 (1≤𝑚≤10 )
第三行字符串l
第四行字符串r
输出：
每个样例一行，如果有满足要求的密码，则输出YES；如果不存在则输出NO；
Examples
input
5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11
output
YES
NO
YES
NO
YES
题目解析：
如果采用暴力做法，枚举小明可能存在的密码数量，会有比较大的数量，并且判断是否为子序列也有O(N)的复杂度；
换一种分析的思路，站在小明的角度，对于第i个密码，他一共有vec若干个选择，也就是区间（l[i]， r[i]）；
对于字符串s，我们从左到右遍历，如果某个字符没有出现在vec中，那么这个字符对题目没有影响，可以直接跳过；
如果某个字符c在vec中出现，那么可以在vec中移除这个字符，表示小明无法选择这个字符；
不断重复这个过程，直到vec为空（进入i+1个密码字符），或者字符串s遍历完。
如果最终字符串s遍历完了，vec还有字符，那么存在vec中存在的字符，必然就是字符串s不存在的字符子序列。
证明：
这个题目没有想到很好的证明方式，就是在分析题目过程中，突然浮现在脑海中的一种贪心思路。
核心思想，字符串想用更少字符区间去覆盖小明能选择的字符。
对于第1个字符，假设有若干个选择，那么字符串s最少需要区间[1, pos1]才能覆盖到这么多选择；
同理对于第2个字符，我们需要[pos1 + 1, pos2]这样的区间去覆盖；
...
直到第m个字符。
假设字符串m能切割出来m个这样的区间，那么必然小明是无解的。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
string s;
char a[20], b[20];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> s;
int m;
cin >> m;
cin >> a >> b;
int ans = 0, pos = 0;
for (int i = 0; i < m; ++i) {
vector<char> v;
for (int j = a[i]; j <= b[i]; ++j) {
v.push_back(j);
}
while (!v.empty() && pos < s.length()) {
vector<char>::iterator it = find(v.begin(), v.end(), s[pos]);
if (it != v.end()) {
v.erase(it);
}
++pos;
}
if (pos == s.length() && !v.empty()) {
ans = 1;
}
}
cout << (ans == 1 ? "YES":"NO") << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目5
题目链接
题目大意：
小明在参加比赛，一共做了n道题目；
初始状态0分，每道题目有得分a[i]，如果是正数则加分，如果是负数则扣分；
现在可以选定一个整数k，在计算得分的过程中，如果小明分数大于等于k，则后续分数不会再小于k分（如果遇到负数，扣分之后最小分为k）；
问整数k为多少，才能使得小明最后分数最大。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例2行
第一行整数n ，表示数组长度（1 ≤ n ≤ 3e5)
第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛 (−1e9≤𝑎𝑖≤1e9 ; 𝑎𝑖≠0 )
输出：
每个样例一行，输出使得小明分数最大整数k（区间范围内[−1e18, 1e18])，如果有多个可以输出任意一个；
Examples
input
4
4
3 -2 1 2
3
-1 -2 -1
2
4 2
7
5 1 -3 2 -1 -2 2
output
3
0
25
6
题目解析：
如果题目没有负数，则任意选择整数即可；
如果题目只有1个负数，那么选择这个负数前面的元素之和作为k，这样就可以抵消该负数的扣分；
如果题目有2个负数，假如两个负数连起来能产生更大的负数，那么就用第一个负数前面的元素之和；如果两个负数中间存在正数，并且该正数大于任何一个负数，那么两个负数必然无法产生更大负数，那么选择较大负数前面的元素之和作为整数k；
如果题目有更多负数，其实也可以简化为前面的情况，也就是找到一个区间，区间内元素之和是最大的负数，那么这个区间前面的元素之和就是k；
每个位置记录一下sum[i]表示包括第i个元素的区间最小和，对于i+1元素，要么与前面区间和sum[i]合并，得到sum[i]+a[i]；要么就是单独成为一个区间a[i]；
遍历一遍就可以得到最大负数的连续区间。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 301010;
lld a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
lld minSum = 0, pos = -1, curSum = 0;
for (int i = 0; i < n; ++i) {
curSum = min(0ll, curSum) + a[i];
if (curSum < minSum) {
minSum = curSum;
pos = i;
}
}
if (minSum < 0) {
lld tmp = 0;
do {
tmp += a[pos];
--pos;
} while (tmp != minSum);
lld ans = 0;
for (int i = 0; i <= pos; ++i) ans += a[i];
cout << ans << endl;
}
else {
cout << 0 << endl;
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
