题目1
题目链接
题目大意：
在二维坐标系上，小明站在原点（0，0），每次可以往上下左右四个方向分别位移1个单位；
现在有n个点，小明需要去遍历；
但是4个方向对应的按钮，小明最多只能按3个，如果4个方向的按钮全部按过，则直接失败。
问小明是否能够顺利完成。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例第一行，整数 𝑛 (1≤𝑛≤100)
接下来n行整数，每行2个整数表示目标点 𝑥𝑖 , 𝑦𝑖 (−100≤𝑥𝑖,𝑦𝑖≤100 )
输出：
每个样例一行，如果可以成功则输出YES，如果失败则输出NO；
Examples
input
6
3
1 -1
0 0
1 -1
4
-3 -2
-3 -1
-3 0
-3 1
4
1 1
-1 -1
1 -1
-1 1
6
-4 14
-9 -13
-14 5
14 15
-8 -4
19 9
6
82 64
39 91
3 46
87 83
74 21
7 25
1
100 -100
output
YES
YES
NO
NO
YES
YES
题目解析：
假设只能向上、向右走，那么小明可以访问到第一象限上面的点，但是可以遍历到所有点吗？
假设第一象限上，有四个点组成一个正方形，小明必然会有对角线的点无法访问。
同理，小明站在原点上，将n个点分配到四个象限。
当存在对角象限同时存在点时，必然无解。比如说（1，1）和（-1，-1），须要用到4个方向。
但是这个象限处理方式，在遇到0时，比较难以处理。
重新思考题目，其实4个方向，就是分别对应x坐标的正负，y坐标的正负。
那么假设所有的点，对应到x坐标，如果没有小于零，那么对应按钮↓可以不用。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[2] = {0}, b[2] = {0};
while (n--) {
int x, y;
cin >> x >> y;
if (x != 0) a[x > 0 ? 0:1] = 1;
if (y != 0) b[y > 0 ? 0:1] = 1;
}
if (a[0] + a[1] + b[0] + b[1] < 4) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
ac;
题目2
题目链接
题目大意：
有n个整数的数组a，数组中每个元素互不相同；
现在可以选择一个数字k，将数组中每一个元素进行对k取余的操作，然后将余数替代原来的元素；
要求选择一个整数k，使得数组在操作后所有元素有且仅有2个不同的值。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤500)
每个样例
第一行，整数 𝑛 (1≤𝑛≤100)
第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤1e17)
输出：
每个样例一行，输出满足要求的 𝑘 (1≤𝑘≤1e18 )，题目保证有解；
Examples
input
5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1
output
7
30
3
5000
1000000000000000000
题目解析：
由于题目要求最后的余数有且仅有两个数字，而取余之后有2个余数的情况，自然就能想到k=2。
我们对题目整数的值进行分类讨论：
1、元素如果有奇数和偶数，%2就有0和1；
2、如果全是偶数，也就是都是2 * x，那么可以再考虑k=4、8、16以此类推；
3、如果全是奇数，假如1、3、5、7，%2全部是1，那么%4呢？首先排除0和2，因为都是奇数，不会产生偶数；那么结果只有2种情况，要么是1，要么3；
那么假如全部是3呢？比如说3，7，11呢？那么必然全部可以抽象成4 x k + 3。可以继续用8来取余。转化为k为奇数或者偶数。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<lld> a;
for (int i = 0; i < n; ++i) {
lld x;
cin >> x;
a.push_back(x);
}
lld ans = 2;
do {
map<lld, int> h;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!h[a[i] % ans]) {
h[a[i] % ans] = 1;
++cnt;
}
}
if (cnt > 1) break;
} while (ans *= 2);
cout<< ans << endl;
}
}
}
ac;
题目3
题目链接
题目大意：
有n个整数的数组a，我们定义区间[l, r]的区间和为相邻元素的绝对值之和，用数学定义来表示：
𝑓(𝑙,𝑟)=|𝑎[𝑙] − 𝑎[𝑙+1]| + |𝑎[𝑙+1] − 𝑎[𝑙+2]| + … + |𝑎[𝑟−1] − 𝑎[𝑟]|.
如果区间长度为1，则区间和为0。
现在需要将数组分隔成k个连续子数组，保证元素的相对顺序不变；
现在想知道，分隔完之后所有数组进行区间和，总和最小为多少？
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例两行
第一行整数𝑛,𝑘 (1≤𝑘≤𝑛≤100 ).
第二行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤500)
输出：
每个样例，输出最小的区间和。
Examples
input
3
4 2
1 3 5 2
6 3
1 9 12 4 7 2
12 8
1 9 8 2 3 3 1 8 7 7 9 2
output
4
11
2
题目解析：
两个分析思路。
1、n的思考角度，从重复子问题来看，dp[i][j]表示前i个数字分隔成j段的最小值，那么dp[i][j]就可以由dp[i-1][j]和dp[1~i-1][j-1]来转移；
2、k的思考角度，k=1时可以直接计算，k=2时我们会选择一个相邻绝对值最大值去分开，k=3时就是选择前2个相邻绝对值最大值去分开。
两个思路都可以解决问题，但是思路2的实现难度要低很多。
class Solution {
static const int N = 201010;
int a[N];
int b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n - 1; ++i) b[i] = abs(a[i] - a[i+1]);
sort(b, b + n - 1);
int sum = 0;
for (int i = 0; i < n - k; ++i) sum += b[i];
cout << sum << endl;
}
}
}
ac;
题目4
题目链接
题目大意：
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例两行
第一行整数𝑛,𝑘 (1≤𝑘≤𝑛≤100 ).
第二行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤500)
输出：
每个样例，输出最小的区间和。
Examples
input
3
4 2
1 3 5 2
6 3
1 9 12 4 7 2
12 8
1 9 8 2 3 3 1 8 7 7 9 2
output
4
11
2
题目解析：
n=1时，最小值就是a[1];
n=2时，最小值就是a[1]&a[2];
n=k时，最小值就是a[1]~a[k]的与，因为and操作只会使得结果更小；
假设最小值结果为m；
m不为0时，集合数量只能为1，因为拆分两个集合结果就变成2m，值会更大；
m为0时，集合数量可以拆分为多个&值为0的区间，那么从左到右遍历，累计出现&结果为0就算一个区间。
class Solution {
static const int N = 201010;
static const int inf = 0x7fffffff;
int a[N];
int b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int m = a[0];
for (int i = 1; i < n; ++i) m = m&a[i];
if (!m) {
int cur = inf, ans = 0;
for (int i = 0; i < n; ++i) {
cur = cur & a[i];
if (cur == m) {
++ans;
cur = inf;
}
}
cout << ans << endl;
}
else {
cout << 1 << endl;
}
}
}
}
ac;
题目5
题目链接
题目大意：
给出n个整数数组a，现在可以进行操作：
选择数组中某个位置k，将a[k]以及之后的数字进行异或操作，将生成的数字放在第k+1位（原来位置k后面的数字被移除）；
现在可以进行任意次上述操作，想知道在这个操作过程中，生成的数字最大为多少。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例两行
第一行整数𝑛 (1≤𝑛≤1e5).
第二行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤2^8)
输出：
每个样例一行，输出最大的生成数字。
Examples
input
3
4
0 2 5 1
3
1 2 3
5
8 2 4 12 1
output
7
3
14
题目解析：
n=1时，只有一个值a[1];
n=2时，除了a[1~2]，新增是a[1]&a[2];
n=3时，除了a[1~3]，新增是a[3]&a[2]（选择2和3合并），a[1]&a[2]（先选择位置3生成a[4]=a[3]，这样抵消a[3]，再选择位置1生成a[1]&a[2]&a[3]&a[4]=a[1]&a[2])，a[1]&a[2]&a[3]（选择位置1）;
从末尾开始分析可以得知，每个末尾的数字有两种选择，要么加入前面的合成，要么复制一次然后被抵消；
题目给出的a[i]的范围很小，可以由此来降低复杂度，我们用dp[i][j]表示第i个整数往后，拼出结果数字为j的可能性，dp[i][j]=1表示有解，dp[i][j]=0表示无解；
这样从最后面往前dp就可以得到所有可能出现数字。
class Solution {
static const int N = 202010;
static const int M = 260;
static const int inf = 0x7fffffff;
int a[N];
int dp[N][M];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n+1; ++i)
for (int j = 0; j < M; ++j) dp[i][j] = 0;
int ans = 0;
for (int i = n - 1; i >= 0; --i) {
dp[i+1][0] = 1;
for (int j = 0; j < M; ++j) {
if (dp[i + 1][j]) {
dp[i][j ^ a[i]] = 1;
ans = max(ans, j ^ a[i]);
}
}
}
cout << ans << endl;
}
}
}
ac;
