題目1
題目鏈接
題目大意：
給出n個(gè)整數(shù)，每次可以選擇其中兩個(gè)整數(shù)a[i]和a[j]，令a[i]=x和a[j]=y，但是需要滿足a[i] | a[j] = x | y；（|是或操作）
現(xiàn)在可以進(jìn)行任意次操作，問n個(gè)整數(shù)的最小和是多少。
輸入：
第一行樣例數(shù)，??(1≤??≤1000)
每個(gè)樣例兩行，第一行是?? (2≤??≤100)
第二行是n個(gè)整數(shù)??1,??2,…,???? (0≤????<2^30)
輸出：
每個(gè)樣例一行，輸出最小和。
Examples
input
4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6
output
3
31
6
7
題目解析：
1和3的或操作會(huì)得到3，那么相當(dāng)于1被清0；
也就是說，兩個(gè)整數(shù)中間相同的二進(jìn)制位數(shù)可以消除其中一個(gè)；
那么題目轉(zhuǎn)化為，對(duì)于(1<<k)，k從0到30，只要出現(xiàn)過一次就可消除其他整數(shù)；
于是題目變成對(duì)于(1<<k)，k從0到30，所有出現(xiàn)過的數(shù)字的和。
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
bool vis[31] = {0};
int ans = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
for (int j = 0; j < 30; ++j) {
if (x & (1 << j) && !vis[j]) {
ans += (1 << j);
vis[j] = 1;
}
}
}
cout << ans << endl;
}
}
}
ac;
題目2
題目鏈接
題目大意：
給出n個(gè)整數(shù)的數(shù)組，每次可以選擇數(shù)組其中一個(gè)元素修改為任意整數(shù)；
現(xiàn)在不希望數(shù)組中出現(xiàn)任何元素滿足，??[??]>??[???1] and ??[??]>??[??+1]；
問最少需要操作修改多少次元素，才能滿足要求。
輸入：
第一行樣例數(shù)，(1≤??≤10000)
每個(gè)樣例兩行，第一行是?? (2≤??≤2?1e5)
第二行是n個(gè)整數(shù)??1,??2,…,???? (1≤????≤1e9)
輸出：
每個(gè)樣例兩行，第一行輸出最小修改次數(shù)；
第二行輸出修改之后的n個(gè)整數(shù)；
Examples
input
5
3
2 1 2
4
1 2 3 1
5
1 2 1 2 1
9
1 2 1 3 2 3 1 2 1
9
2 1 3 1 3 1 3 1 3
output
0
2 1 2
1
1 3 3 1
1
1 2 2 2 1
2
1 2 3 3 2 3 3 2 1
2
2 1 3 3 3 1 1 1 3
題目解析：
先找到元素a[i]滿足??[??]>??[???1] and ??[??]>??[??+1]，要使得滿足題目要求，只有三種可能：
1、修改a[i-1]；
2、修改a[i]；
3、修改a[i+1]；
為了方便決策，我們假設(shè)從左到右遍歷數(shù)組，現(xiàn)在遇到了a[i]不符合要求，那么可以選擇將a[i-1]或者a[i+1]變大，或者將a[i]變??；
容易知道這三者對(duì)于已經(jīng)遍歷到的元素a[1]到a[i+1]是沒有區(qū)別的（因?yàn)槎紳M足要求），但是考慮到后續(xù)還有a[i+2]的元素，那么將a[i+1]變大的選擇會(huì)更優(yōu)；
并且我們可以使得a[i+1]=max(a[i], a[i+2])，這樣就可以最大程度利用這一次修改機(jī)會(huì)。
然后不斷循環(huán)這個(gè)操作直到數(shù)組末尾。
class Solution {
static const int N = 200010;
string str;
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];
}
int ans = 0;
for (int i = 1; i + 1 < n; ++i) {
if ((a[i] > a[i - 1]) && (a[i] > a[i + 1])) {
a[i + 1] = max(a[i], a[i + 2]);
++ans;
}
}
cout << ans << endl;
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
}
}
ac;
題目3
題目鏈接
題目大意：
給出長度為n的由0和1組成的字符串a(chǎn)，現(xiàn)在可以對(duì)字符串a(chǎn)執(zhí)行下面的操作：
1、將a2=min(a1, a2)，然后移除a1；
2、將a2=max(a1, a2)，然后移除a1；
現(xiàn)在有長度為m的字符串b，想問字符串a(chǎn)是否能通過任意次操作1或者操作2，得到字符串b；
輸入：
第一行，整數(shù)?? 表示t個(gè)樣例?? (1≤??≤2000)
每個(gè)樣例第一行 整數(shù) ??, ?? (1≤??,??≤50, ??≤??)
第二行長度為n的字符串a(chǎn)
第三行長度為m的字符串b
輸出：
每個(gè)樣例一行，如果可以則輸出YES；否則輸出NO；
Examples
input
10
6 2
001001
11
6 2
110111
01
6 2
000001
11
6 2
111111
01
8 5
10000101
11010
7 4
1010001
1001
8 6
01010010
010010
8 4
01010101
1001
8 4
10101010
0110
7 5
1011100
11100
output
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
題目解析：
不管是操作1、操作2，都無法影響后續(xù)字符串；
那么給出的字符串b，其實(shí)只有第一個(gè)字符的組成，a是有辦法去選擇；
也就是說對(duì)于字符串a(chǎn)來說，后面的m-1個(gè)字符，必須和b一樣；然后前面的字符必須出現(xiàn)過1次b的第一個(gè)字符；
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;
if (n == 1) {
cout << (a[0] == b[0] ? "YES" : "NO") << endl;
continue;;
}
if (m == 1) {
int find = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == b[0]) find = 1;
}
if (find) cout << "YES" << endl;
else cout << "NO" << endl;
continue;
}
int ok = 1;
for (int i = 1; i < m; ++i) {
if (b[i] != a[n - m + i]) ok = 0;
}
int find = 0;
for (int i = 0; i <= n - m; ++i) {
if (a[i] == b[0]) find = 1;
}
if (find && ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
ac;
題目4
題目鏈接
題目大意：
有2??個(gè)人參加比賽，編號(hào)是1到2n；
比賽采用的是淘汰賽的機(jī)制，1和2比，3和4比，然后接著是勝者按照編號(hào)大小繼續(xù)比賽；
已知編號(hào)x和y的人參加比賽，會(huì)有下面的結(jié)果：
1、x+y是奇數(shù)，則勝者是編號(hào)較小者；
2、x+y是偶數(shù)，則勝者是編號(hào)較大者；
輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 (1≤??≤1000)
每個(gè)樣例一行，整數(shù)?? (1≤??≤30)
輸出：
每個(gè)樣例輸出一行，輸出最后的勝者編號(hào)。
Examples
input
2
3
1
output
7
1
題目解析：
仔細(xì)看圖中的條件，發(fā)現(xiàn)這里面條件的x+y是奇數(shù)，只會(huì)出現(xiàn)在第一輪比賽；
從第二輪比賽開始，參賽全部是奇數(shù)，則一定是較大者獲勝；
思考??：
假設(shè)參加比賽初始順序是亂序的呢？那就手動(dòng)算一遍，因?yàn)檩喆问莑og級(jí)別遞進(jìn)，總體的復(fù)雜度可以控制在NlogN；
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (1 << n) - 1 << endl;
}
}
}
ac;
題目5
題目鏈接
題目大意：
給出n個(gè)整數(shù)的數(shù)組a，現(xiàn)在可以選擇數(shù)組中三個(gè)元素a[x],a[y],a[z]（其中x<y<z），令a[x]=a[y]-a[z]；
現(xiàn)在可以執(zhí)行不超過n次操作，要求數(shù)組變成非遞減；
輸入：
第一行樣例數(shù)，(1≤??≤10000)
每個(gè)樣例兩行，第一行是 ?? (3≤??≤2?1e5)
第二行是n個(gè)整數(shù)??1,??2,…,???? (?1e9≤????≤1e9)
輸出：
每個(gè)樣例第一行輸出操作次數(shù)k，如果無解則輸出-1；
有解的情況，接下來k行，每一行包括整數(shù)x,y,z，表示每次操作的數(shù)組元素序號(hào)；（沒有要求最少操作次數(shù)）
Examples
input
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
output
2
1 2 3
3 4 5
-1
0
題目解析：
題目有一個(gè)很重要的條件，沒有要求最少操作次數(shù)。
那么對(duì)于數(shù)組中只有最后兩個(gè)整數(shù)是有意義的，如果第n個(gè)元素>=0，那么必然有解：可以把前面的元素都替換成a[n-1]-a[n]；
先判斷下數(shù)組是不是本身符合要求；
其他的情況根據(jù)a[n-1]和a[n] 的大小就可以判斷。
思考??：
如果要求最小次數(shù)呢？
class Solution {
static const int N = 200010;
string str;
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 (a[n - 1] < a[n - 2]) {
cout << -1 << endl;
}
else {
int rightIndex = n - 3;
while (rightIndex >= 0) {
if (a[rightIndex] > a[rightIndex + 1]) {
break;
}
--rightIndex;
}
if (rightIndex < 0) {
cout << 0 << endl;
}
else {
if (a[n - 1] >= 0) {
cout << rightIndex + 1 << endl;
for (int i = 0; i < rightIndex + 1; ++i) {
cout << i + 1 << " " << rightIndex + 2 << " " << n << endl;
}
}
else {
cout << -1 << endl;
}
}
}
}
}
}
ac;
