A. Maximum GCD
题意：
t组输入，然后输入一个n，让你在区间[1,n]之间找出来两个不相等的数a，b。求出来gcd(a,b)（也就是a，b最大公约数）。让你求出来最大的gcd(a,b)是多少。
题解：
最大gcd(a,b)，那就是n/2向下取整的结果。因为如果gcd(a,b)越大，那么a/gcd(a,b)或者b/gcd(a,b)的值肯定越小，最小也就是2了，所以输出n/2就行
代码：
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<string.h>
7 #include<map>
8 #include <iostream>
9 #include <math.h>
10 using namespace std;
11 typedef long long ll;
12 int main()
13 {
14 int t;
15 scanf("%d",&t);
16 while(t--)
17 {
18 int n;
19 scanf("%d",&n);
20 printf("%d\n",n/2);
21 }
22 return 0;
23 }
View Code
B. GCD Compression
题意：
t组输入，你首先有一个长度为2*n的数组，你需要压缩a数组长度为n-1。你可以扔掉a数组中的两个元素，将剩下的元素两两一组相加，它的值作为新数组b的一个值。你需要保证这个新数组b的gcd大于1（即，gcd(b1,b2...b(n-1) >1）
题解：
刚开始不知道怎么写，如果考虑所有因子那就不好弄了。但是题目上面说了，你只需要保证你构造的新数组b的公共最大公因子大于1就行，那么我们取他们的因子里面至少包含2这个因子。包含2这个因子的话，只要新数组的值都是偶数就可以满足题意（因为他们至少有一个公因子2，而这个2都大于1.所以肯定会满足题意）。那么我们就只要能构造一个都是偶数的新数组就行。偶数+偶数、奇数+奇数、就这样凑肯定可以。因为我们还可以丢弃两个元素，如果a数组的偶数个数为奇数就把扔掉一个，同样如果a数组的奇数个数为奇数就把扔掉一个。
代码：
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<string.h>
7 #include<map>
8 #include <iostream>
9 #include <math.h>
10 using namespace std;
11 typedef long long ll;
12 const int maxn=2e3+10;
13 int que1[maxn],que2[maxn],index1,index2;
14 int main()
15 {
16 int t;
17 scanf("%d",&t);
18 while(t--)
19 {
20 index1=index2=0;
21 int n;
22 scanf("%d",&n);
23 for(int i=1;i<=2*n;++i)
24 {
25 int x;
26 scanf("%d",&x);
27 if(x%2)
28 {
29 que1[index1++]=i;
30 }
31 else que2[index2++]=i;
32 }
33 for(int i=1;i<index1;)
34 {
35 if(n==1)
36 break;
37 printf("%d %d\n",que1[i-1],que1[i]);
38 n--;
39 i+=2;
40 }
41 for(int i=1;i<index2;)
42 {
43 if(n==1)
44 break;
45 printf("%d %d\n",que2[i-1],que2[i]);
46 n--;
47 i+=2;
48 }
49 }
50 return 0;
51 }
View Code
C. Number Game
题意：
对于一个n，你可以从下面两种操作中选一种执行
1、将n除于它的奇数因子（它的因子不包括1但是包括它本身）
2、将n减去1
上面两种操作的前提都是n大于1.
如果谁没有办法执行操作，那么谁就输了
第一步由Ashishgup先走
题解：
1、特判
n==1的时候对方必胜
n==2的时候Ashishgup必胜
2、如果n是一个奇数，那么Ashishgup必胜。因为n可以执行操作1除于n的因子n本身
3、如果n为偶数，且有奇数因子，我们一定可以把n拆为一个奇数和一个没有奇数因子(除1外)的偶数相乘，这样Ashishgup留给对手的就是一个没有奇数因子的偶数x，对手只能做减一操作，如果x不为2，那么Ashishgup就得到一个奇数，直接除以自身即可，此时Ashishgup必胜。否则就输了。
所以我们只需要找出来n的最大奇数因子，然后判断一下n除于这个最大奇数因子的值等不等于2就行
代码：
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<string.h>
7 #include<map>
8 #include <iostream>
9 #include <math.h>
10 using namespace std;
11 typedef long long ll;
12 const int maxn=2e3+10;
13 int result(int n)
14 {
15 int ans=0;
16 for(int i=2; i<=n/i; ++i)
17 {
18 if(n%i==0)
19 {
20 if(i%2 && n/i!=2)
21 ans=max(ans,i);
22 if((n/i)%2 && i!=2)
23 ans=max(ans,n/i);
24 // if(i!=2 && n/i!=2)
25 // {
26 // if(i%2==1 || (n/i)%2==1)
27 // {
28 // return true;
29 // }
30 // }
31 }
32 }
33 if(ans) return 1;
34 return 0;
35 }
36 int main()
37 {
38 int t;
39 scanf("%d",&t);
40 while(t--)
41 {
42 int n;
43 scanf("%d",&n);
44 if(n%2)
45 {
46 if(n==1)
47 {
48 printf("FastestFinger\n");
49 }
50 else printf("Ashishgup\n");
51 }
52 else
53 {
54 int ans=result(n);
55 //printf("%d***\n",ans);
56 if(n==2)
57 {
58 printf("Ashishgup\n");
59 }
60 else if(ans)
61 {
62 printf("Ashishgup\n");
63 }
64 else printf("FastestFinger\n");
65 }
66 }
67 return 0;
68 }
View Code
D. Odd-Even Subsequence
题意：
给你一个长度为n的数组v，你需要把它的长度缩减为k。缩减操作就是删除v数组中的某个位置的元素。注意元素下标从1开始，而且你只能删除某个位置的元素，并不能改变它们的顺序。我们设我们操作过后长度为k的数组为a，那么我们设这个数组所有奇数下标所对应的值中最大的那个值为x，我们设这个数组所有偶数下标所对应的值中最大的那个值为y，我们只需要输出min(x,y)就行。我们要尽量使输出的值尽量小
题解：
答案具有单调性，二分答案，然后看能不能满足有大于等于k个元素满足条件。因为我们最后输出的是min(x,y)，所以只要偶数下标的满足那个答案，或者奇数下标的满足答案就行。
这里对偶数下标满足答案为例：
假设偶数下标所对应的值中最大的那个值小于等于答案，那么我们取第一个元素就直接取原数组的第一个，然后取第二个元素就要满足那个元素的值要小于等于二分的答案。第三个值就取我们去第二个元素后面那个就行。具体见代码
代码：
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<string.h>
7 #include<map>
8 #include <iostream>
9 #include <math.h>
10 using namespace std;
11 typedef long long ll;
12 const int maxn=2e5+10;
13 int n,k,a[maxn];
14 bool check(int x,bool flag)
15 {
16 int cnt=0;
17 for(int i=1; i<=n; i++)
18 {
19 if(flag||a[i]<=x)
20 {
21 cnt++;
22 flag=!flag;
23 }
24 }
25 return cnt>=k;//��û��k������������Ԫ��
26 }
27 int main()
28 {
29 scanf("%d%d",&n,&k);
30 for(int i=1; i<=n; i++)
31 {
32 scanf("%d",&a[i]);
33 }
34 int l=1,r=1e9,ans;
35 while(l<=r)
36 {
37 int mid=(l+r)/2;
38 if(check(mid,0)||check(mid,1))
39 {
40 ans=mid;
41 r=mid-1;
42 }
43 else
44 {
45 l=mid+1;
46 }
47 }
48 printf("%d\n",ans);
49 return 0;
50 }
51
View Code