Codeforces Round #813 (Div. 2)A-E1

Codeforces Round #813 (Div. 2)

A
签到
题意：给定一个排列，要求前k个数是从1到n，每次可以选两个数交换位置，最少交换几次达到要求。

一眼题，不解释了。

#include 
using namespace std;
//#define int long long
const int N = 1e5+100;
int a[N];
int b[N];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=a[i];
        }
        sort(b+1,b+1+n);
        int ans=0;
        for(int i=1;i<=k;i++)
        {
            if(a[i]>b[k])
            {
                ans++;
            }
        }
        cout<<ans<<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

B
题意：输出一个排列，要求排列每一项和对应下表的lcm之和最大。

思路:互质lcm最大，相邻两数互质，后往前交换相邻数即可。

#include 
using namespace std;
//#define int long long
const int N = 1e5+100;
int a[N];
int b[N];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            a[i]=i;
        }
        if(n&1)
            for(int i=n;i>=2;i-=2)
                swap(a[i],a[i-1]);
        else
        for(int i=n;i>=1;i-=2)
            swap(a[i],a[i-1]);
        for(int i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<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

C
题意：给定一个数组，每次可以选择某一个值x，令所有等于x的数为0，求最少几次操作让数组变为单调递增。

思路：先找到最后的下降点，然后这个点之前的所有数统统为0.然后在找最后一个为0的点，把这个点之前的数再统统变0即可。

#include 
using namespace std;
//#define int long long
const int N = 1e5+100;
int a[N];
int b[N];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            a[i]=i;
        }
        if(n&1)
            for(int i=n;i>=2;i-=2)
                swap(a[i],a[i-1]);
        else
        for(int i=n;i>=1;i-=2)
            swap(a[i],a[i-1]);
        for(int i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<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

D
题意：给定一个数组，数组每个元素视为一个点，数组值视为点权，以这些点构成完全无向图，两点的边权值就是这两点之间（包括这两点）所有点的最小点权。

你可以进行k次操作，每次操作选择一个点修改其数值为任意值。

问：两点之间最短路的最大值是多少。

思路：

抽象问题，两点i和j（i 1.两点之间的最小值
2.i到1，1再到j
3.j到n，n再到i

这三种情况下的最小值就是最短路径。

那么显然区间越大需要考虑的最小值越多，所以选择相邻两点最优，既最优方案为：i=j-1

每次枚举一个答案 ans
1.如果点i和j的权值比答案小，显然要将他们都修改
2.修改完i和j后，考虑第二种路径，第二种路径的权值就是1到i之间最小值*2。
3.第三种路径就是j到n之间最小值 * 2

所以预处理出所有乘二还小于ans的数，并且做前缀和。

选择i和j两点i=j-1时需要花费
res=0
if(a[i] res++;
if(a[i+1] res++;
这么多：res+pre[i-1]+pre[n]-pre[i+1]

#include 

using namespace std;
const int N = 1e5+100;
int n,k;
int pre[N];
int a[N];
bool check(int ans)
{
    int res=0;
    for(int i=1;i<=n;i++)
    {
        pre[i]=0;
        if(a[i]*2<ans)
            pre[i]=1;
        pre[i]+=pre[i-1];
    }
    for(int i=1;i<=n-1;i++)
    {
        res=0;
        if(a[i]<ans)
            res++;
        if(a[i+1]<ans)
            res++;
        if(res+pre[i-1]+pre[n]-pre[i+1]<=k)
            return true;
    }
    return false;
}
int main()
{
    int t;
    for(cin>>t;t;t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        int l=1,r=1e9;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid))
            {
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        cout<<r<<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
53
54
55
56

E1

题意：给定l和r作为左右闭边界，枚举范围内的三个数i，j，k（i=i+j+k

思路：首先，k作为最大值，i+j+k一定小于3k并且大于k，而lcm又是k的倍数，所以lcm想要大于三数之和，必须满足：lcm大于等于3k

但是直接计算不好算。
根据以上推论，我们还能退出，如果想要然lcm小于i+j+k，那么只有一种情况：lcm==2k

三元组总数是n*(n-1)*(n-2)/6
减去所有lcm==2k的情况即可。

如何枚举lcm等于2k？先枚举2k，然后枚举2k的因子，k个另外两个因子构成的三元组一定满足lcm=2k

#include
#include
#include
#include
#define int long long
#define fastio  cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define endl '\n'
using namespace std;
const int maxn = 4e5 + 5;
bool v[maxn];
vector<int> factor[maxn];
signed main()
{
    int t,l,r;
    for(int i=1;i<maxn;i++)
        for(int j=2*i;j<maxn;j+=i)
            factor[j].push_back(i);
    for(cin>>t;t;t--)
    {
        cin>>l>>r;
        int len=r-l+1;
        int res=len*(len-1)*(len-2)/6;
        for(int i=l+2;i<=r;i++)
        {
            vector<int> v;
            for(auto x:factor[2*i])
            {
                if(x<l)
                    continue;
                if(i%x&&x*2<=i)
                continue;
                if(x>=i)
                 break;
                for(auto y:factor[2*i])
                {
                    if (y<l)
                        continue;
                    if (y>=x)
                     break;
                    if (i%x||i%y)
                        res-=2*i<x+y+i;
                    else
                    res--;
                }
            }
        }
        cout<<res<<endl;
    }
}

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