img

牛客练习赛120

抽奖黑幕

如果都相等显然插入1最优

如果不等

插入最大最优秀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int t,n;
    long long sum=0;
    long long a[1000000];
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>n;
        sum+=n;   
        for(int i=0;i<n-1;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n-1);
            if(a[0]==a[n-2])
            {
                cout<<1<<endl;
            }else{
        cout<<a[n-2]<<endl;
            }
    }
    return 0;
}

生成函数

只要能够凑出差值即可

盲猜最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    long a,b,c,m,res;
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>a>>b>>c>>m;
       res=gcd(gcd(a,b),c);
        if(m%res==0){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

选择交换

可以证明一定是排序取首尾加加加

因为要记录

所以需要记录下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int a,b;
}a1[1000000],ans[1000000];
bool camp(node &x,node &y){
    return x.a<y.a;
}
int main(){
    int t,n;
    cin>>t;
    for(int i=0;i<t;i++){
        int res=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a1[i].a;
            a1[i].b=i;
        }
        sort(a1+1,a1+n+1,camp);
        long num=a1[1].a+a1[n].a;
        for(int i=2;i<=(n-1)/2+1;i++)
        {
            if(a1[i].a+a1[n-i+1].a!=num)
            {
                cout<<"NO"<<endl;
                res=1;
                break;
            }
        }
        if(res==0){
            int ant=0;
            cout<<"YES"<<endl;
        for(int i=1;i<=n;i++)
        {
            while(a1[i].b!=i)
            {
                ant++;
                 ans[ant].a = a1[i].b;
             ans[ant].b = i;
             swap(a1[i], a1[a1[i].b]);
            }
        }
            cout<<ant<<endl;
          while(ant){
              cout<<ans[ant].a<<" "<<ans[ant].b<<endl;
              ant--;
          }  
     }
    }
    return 0;
}

数数大师

D的话弄一个前缀和

只需要奇数偶数即可

最后的答案是前缀和为奇数的个数加上前缀和为奇数的个数乘于前缀和为偶数的个数

因为前缀和已经是奇数了

因此只需要进行记录

然后前面或者后面有偶数的前缀和直接乘上就好

因为偶数减去奇数还是奇数减去偶数都是奇数

因此这样是没有问题的

设奇数数量为x

偶数数量就是n-x

答案就是\(x+(n-x)*x=(n-x+1)*x=-x*x+(n+1+x\)

我们就是要让x最大

x怎么样可以最大，函数开口向下

显然是二分之一（n+1)时候，这里是个中学生都会罢

因此关键就是我们怎么样能够让奇数个数(n+1)/2呢

这是可以办到的吗，在k次有限操作里

这就是本题的难点了。

证明是看评论区一位大佬的

情况1. 假如如果不操作时， x > (n + 1) / 2, 那么在第一个位置执行一次操作后，x 变为 (n - x) < (n + 1) / 2 情况2， 假如如果不操作时， x <= (n + 1) / 2,那么在第一个位置执行一次操作后，x 变为 (n - x) >= (n + 1) / 2 总体的思路就是这样

因此是可以实现修改一次取得最大值

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2e5 + 10;
int n,k;
int a[N];
void solve()
{
    cin >> n >> k;
    int pre = 0, cnt = 0;
    for(int i = 1;i <= n;i ++)
    {
        cin >> a[i];
        pre = pre ^ (a[i] & 1);
        cnt += (pre & 1);
    }
    if(k) cnt = (n+1)2;
    cout << cnt * (n-cnt+1) << endl;
}
 
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
 
    int t;
 
    cin >> t;
 
    while (t --)
        solve();
 
    return 0;
}