目錄
- A - Ahahahahahahahaha
- B - Big Vova
- C - Chocolate Bunny
A - Ahahahahahahahaha
題意：
給你一個01串，最多能删去一半，删完以後要使 a 1 − a 2 + a 3 − a 4 + … = 0 a_1−a_2+a_3−a_4+…=0 a1−a2+a3−a4+…=0，也就是下标為奇數的數之和等于下标為偶數的數之和。
輸入：
首行T，接下來T組資料，一行給出n，下一行給出n個數，即01串的主體。
4
2
1 0
2
0 0
4
0 1 1 1
4
1 1 0 0
輸出：
輸出删減完以後的01串。
1
0
1
0
2
1 1
4
1 1 0 0
思路：
開始想的很複雜。實際上就是讨論0和1的個數。
- 0的個數大于等于1，也就是0的個數大于等于一半，是以直接輸出所有的0；
- 1的個數大于0，基本操作同上，但是此時需要注意，若1的個數為奇數，內插補點不是為0而是為1，是以是奇數少輸出一個1；
B - Big Vova
參考： B. Big Vova（暴力）
題意：
給你一個長度為n的數組a，求一個數組b，可以使得數組c的字典序最大，其中
c i = G C D ( b 1 , … , b i ) c_i=GCD(b_1,…,b_i) ci=GCD(b1,…,bi)
輸入：
首行輸入T，接下來T組資料，每組第一行輸入n，第二行輸入n個數字，即數組a本體。
7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17
輸出：
按順序輸出數組b，每個元素間以空格間隔。
5 2
8 2 1 3
9 3 8
100 50 25 75 64
42
128 96 80 88 52 7
17 2 4 8 16
思路：
詳見連結。
代碼：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 1000005
typedef unsigned long long ll;
using namespace std;
int a[N];
int b[N];
bool vis[N];
int gcd(ll c, ll b)
{
ll tmp;
while(b)
{
tmp = b;
b = c % b; c = tmp;
}
return c;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
memset(vis, 0, sizeof(vis));
int n;
scanf("%d", &n);
int cnt = 0;
int maxx = -1, maxi = -1;
for(int i = 0; i < n; i++)
{
scanf("%d", a + i);
if(a[i] > maxx)
{
maxx = a[i];
maxi = i;
}
}
b[cnt++] = maxx;
vis[maxi] = 1;
for(int i = 1; i < n; i++)
{
int maxg = -1;
int maxgi = -1;
for(int j = 0; j < n; j++)
{
if(vis[j])
continue;
if(gcd(maxx, a[j]) > maxg)
{
maxg = gcd(maxx, a[j]);
maxgi = j;
}
}
//cout << maxg << ' ' << maxgi << endl;
b[cnt++] = a[maxgi];
vis[maxgi] = 1;
maxx = maxg;
}
for(int i = 0; i < n; i++)
printf("%d ", b[i]);
printf("\n");
}
}
C - Chocolate Bunny
題意：
互動題，有一個1到n的置換（即1到n每個數出現且僅出現一次的數組），你可以詢問2×n次，每次詢問兩個下标i和j，系統會告訴你 a i ( m o d a ) j a_i \pmod a_j ai(moda)j的值。你最終要按順序輸出這個置換。
輸入：
根據輸出的詢問，給出 a i ( m o d a ) j a_i \pmod a_j ai(moda)j的值。
3
1
2
1
0
輸出：
用
? i j
的格式詢問，得到答案後用
！ a b
的格式輸出置換。
? 1 2
? 3 2
? 1 3
? 2 1
! 1 3 2
思路：
對任意的 a i a_i ai與 a j a_j aj，由于置換中沒有重複的數字，是以兩個數一定有一個比另一個大。是以兩個數互換詢問後（?$a_i a_j $ ? a j a i a_j a_i ajai），必定能問出其中一個數。如，設n>k，則n%k<k，k%n=k，是以互換詢問一定能問出兩個數中較小的那個數。互換詢問n次，每次問兩次，剛好問2×n次。
代碼：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <iomanip>
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 10010
#define M 110
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int a[N];
int main()
{
int n;
scanf("%d", &n);
int j = 1;
for(int i = 2; i <= n; i++)
{
printf("? %d %d\n", i, j);
fflush(stdout);
int res1;
scanf("%d", &res1);
printf("? %d %d\n", j, i);
fflush(stdout);
int res2;
scanf("%d", &res2);
if(res1 > res2)
{
a[i] = res1;
}
else
{
a[j] = res2;
j = i;
}
}
printf("!");
for(int i = 1; i <= n; i++)
{
if(!a[i])
printf(" %d", n);
else
printf(" %d", a[i]);
}
printf("\n");
return 0;
}
賽後總結：
- 沒有及時寫題解，有點記不清了，就記得A題卡了心态有點崩。還好還是漲分了。以及B題讀題一直讀不懂，好在C題比較簡單，挽回一城。了解能力和思維還是有待提高。
- 下次一定及時寫題解。說實話着急打比賽還不如慢慢來，把每一場都總結好。
多多包涵，努力進步
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)