Codeforces Round #829 (Div. 2):
A:https://codeforces.com/contest/1754/problem/A
题意：给定一串由QA两个元素组成的字符串，判断是否Q的数量大于A的数量，如果是输出No，如果不是（这里分两种情况，一，Q和A的数量相等，二、A的数量大于Q的数量）则输出Yes；
做法:用标记数组记录当前位置的字符是否被记录过
从头开始遍历，如果碰到字符是Q，并且后面如果碰到A的话，就对Q和A的位置进行标记
然后用一个set来表示没有被记录过的字符集来记录Q 的个数
最后判断set是否为空就可以了
参考代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 const int N=1e2+10;
6 int n;
7 int t;
8 string s;
9 set<char>c;
10 bool vis[N];
11 void solved()
12 {
13 c.clear();
14 memset(vis,0,sizeof(vis));
15 cin>>n>>s;
16 for(int i=0;i<n;i++)
17 {
18 if(s[i]=='Q')
19 {
20 for(int j=i+1;j<n;j++)
21 {
22 if(s[j]=='A'&&!vis[j])
23 {
24 vis[i]=true;
25 vis[j]=true;
26 break;
27 }
28 }
29 }
30 }
31 for(int i=0;i<n;i++)
32 {
33 if(s[i]=='Q'&&!vis[i])
34 {
35 c.insert(s[i]);
36 }
37 }
38 if(c.empty())
39 {
40 cout<<"Yes"<<endl;
41 }
42 else
43 {
44 cout<<"No"<<endl;
45 }
46 }
47 signed main()
48 {
49 IOS;
50 cin>>t;
51 while(t--)
52 {
53 solved();
54 }
55 return 0;
56 }
其实写麻烦了，用cnt来消去QA的个数统计或者用栈来统计也是可以的，我这种做法纯属脑子有病。
B：https://codeforces.com/contest/1754/problem/B
题目大意：
给定一组数，来构造一组没有重复数字的数组，这个数组内实现
的最大化，比如，
给定n=4的话，可以实现一组数据：2，4，1，3
min{|4−2|,|1−4|,|3−1|}=min{2,3,2}=2
做法：可以这样来构造，如果是n是偶数的话，就构造为(n/2+1,1),(n/2+2,2).......
如果是奇数的话，就在偶数的基础上末尾加一n就可以了；
这样构造的依据是连续元素的最小差值不大于 ⌊n/2⌋。
要做到这一点，证明更大的价值是无法实现的。考虑值为 ⌊n/2⌋+1 的排列元素。它将在构造的排列中至少有一个相邻元素。而这个元素与相邻元素的最大绝对差最多是⌊n/2⌋。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 int t;
6 const int N=1e3+10;
7 vector<int>ans;
8 /*int a[N];
9 set<int>q;
10 vector<int>jishu;
11 vector<int>oushu;
12 void solved()
13 {
14 int n;
15 jishu.clear();
16 oushu.clear();
17 memset(a,0,sizeof(a));
18 cin>>n;
19 if(n<=3)
20 {
21 for(int i=1;i<=n;i++)
22 {
23
24 cout<<i<<" ";
25 }
26 cout<<endl;
27 return ;
28 }
29 for(int i=1;i<=n;i++)
30 {
31 if(i%2!=0)
32 {
33 jishu.push_back(i);
34 }
35 else
36 {
37 oushu.push_back(i);
38 }
39 }
40 for(int i=0;i<oushu.size();i++)
41 {
42 cout<<oushu[i]<<" ";
43 }
44 for(int i=0;i<jishu.size();i++)
45 {
46 cout<<jishu[i]<<" ";
47 }
48 cout<<endl;
49 }*/
50 void solved()
51 {
52 int n;
53 cin>>n;
54 int cnt=n/2;
55 for(int i=1;i<=n/2;i++)
56 {
57 cout<<i+cnt<<" "<<i<<" ";
58 }
59 if(n&1)
60 {
61 cout<<n<<endl;
62 }
63 else
64 {
65 cout<<endl;
66 }
67 }
68 signed main()
69 {
70 IOS;
71 cin>>t;
72 while(t--)
73 {
74 solved();
75 }
76 return 0;
77 }
830：A：https://codeforces.com/contest/1732/problem/A
题意：给定一组数，要求实现这个数组内所有元素的最大公约数是1，可以进行这样的操作：
选定一个数a[i],让这个数a[i]=__gcd(a[i],i)而这样做的价值是n-i+1;
要求在实现所有元素的最大公约数都是1的前提下找出最小价值
做法：可以这样看，对于一组数来讲n-1和n的最大公约数肯定是1，而最小代价也无非是从这两个数里面取，所以说答案一定是小于等于3的
由此，我们用num来表示这组数据的最大公约数，如果是1的话答案自然就是0；
如果__gcd(num,n)==1（选择i=n）答案就是1
如果__gcd(num,n-1)（选择i=n-1)答案就是2；
其余情况就是3
之所以看后面两个数的原因，是因为给定的连续自然数可以实现相邻的自然数互质
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 int t;
6 const int N=30;
7 int a[N];
8 int b[N];
9 int n;
10 vector<int>ans;
11 void solved()
12 {
13 cin>>n;
14 /*bool flag=false;
15 for(int i=1;i<=n;i++)
16 {
17 cin>>a[i];
18 b[i]=a[i];
19 }
20 if(n==1&&a[1]==1)
21 {
22 cout<<0<<endl;
23 return ;
24 }
25 else if(n==1&&a[1]!=1)
26 {
27 cout<<1<<endl;
28 return ;
29 }
30 for(int i=1;i<=n;i++)
31 {
32 b[i]=__gcd(a[i],i);
33 int j=1;
34 for(j=1;j<n;j++)
35 {
36 if(__gcd(b[j],b[j+1])==1)
37 {
38 flag=true;
39 }
40 else
41 {
42 flag=false;
43 break;
44 }
45 }
46 if(j==n&&flag)
47 {
48 cout<<n-i+1<<endl;
49 return ;
50 }
51 }*/
52 int num=0;
53 for(int i=1;i<=n;i++)
54 {
55 cin>>a[i];
56 num=__gcd(a[i],num);
57 }
58 if(num==1)
59 {
60 cout<<0<<endl;
61 return ;
62 }
63 if(__gcd(n,num)==1)
64 {
65 cout<<1<<endl;
66 }
67 else if(__gcd(n-1,num)==1)
68 {
69 cout<<2<<endl;
70 }
71 else
72 {
73 cout<<3<<endl;
74 }
75 }
76 signed main()
77 {
78 IOS;
79 cin>>t;
80 while(t--)
81 {
82 solved();
83 }
84 return 0;
85 }
标签：830,int,CF,long,cin,solved,num,829,define From： https://www.cnblogs.com/LQS-blog/p/16821496.html