目录
- 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=)