Codeforces Round #728 (Div. 2)a-c

比眉伴天荒 2022-10-10 04:48 38阅读 0赞

https://codeforc.es/contest/1541

### cf ###

*  
 *  a
 *  b
 *  c

#  #

# a #

给定一个数n，1 2 3 4 … n 每个数不在原位，求最小移动次数，对应的序列  
分别讨论n为偶数和奇数的情况

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    { 
        int t, n;
        scanf("%d", &t);
        while(t--){ 
            scanf("%d", &n);
            if(n%2==0) for (int i = 2; i <= n; i+=2)
            { 
                printf("%d %d ",i,i-1);
            }else{ 
                int a[105];
                for(int i =1; i <= n; i++) a[i] = i;
                for (int i = 1; i <= n; i+=2){ 
                    if(i+2==n) { 
                        printf("%d %d %d",a[i+2],a[i],a[i+1]);break;
                    }
                    else printf("%d %d ",a[i+1],a[i]);
                }
            }
            printf("\n");
        }
        return 0;
    }

# b #

给定一个长为n的序列，满足  
 i < j i < j i<j  
 a i ∗ a j = i + j a\_i \* a\_j = i +j ai∗aj=i\+j  
给的数据不小，复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 可以过  
剪枝很重要，把 j > n j > n j>n 和  i > = j i >= j i>=j位置剪枝掉  
注意两个数的大小是 1 0 5 10^5 105乘的时候要扩展一下范围

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    int main()
    { 
       int t; scanf("%d",&t);
       while(t--)
       { 
            int n; scanf("%d",&n);
            int a[n+10];
            for(int i =1; i <= n; i++) scanf("%d",&a[i]);
            int ans = 0;
            for(int i =1; i <= n; i++) 
            { 
                int tmp = 1;
                while(1){ 
                    int x = tmp * a[i];
                    int j = x - i;
                    if(j > n) break;
                    if(j > i && (ll)a[i]*a[j] == (ll)(i+j)) ans++;
                    tmp++;
                }
                
            }
            printf("%d\n",ans);
       }
    }

# c #

权值最小，建立一个正向边，建立尽可能多的反向边。  
正向边最小的长度： a r r \[ n − 1 \] arr\[n-1\] arr\[n−1\]  
反向边：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]

orz的代码，截过来了：

#include<bits/stdc++.h>
    using namespace std;
    #define all(x) (x).begin(), (x).end()
    typedef long long ll;
    typedef vector<ll> vl;
    
    void solve()
    { 
        ll n; scanf("%lld",&n);
    
        vl arr(n);
    
        for(int i = 0;i<n;i++) cin >> arr[i];
    
        sort(all(arr));
    
        ll ans = arr[n-1];
    
    
        vl neg(n);
    
        neg[0] = 0;
    
        for(int i = 1;i<n;i++){ 
            neg[i] = neg[i-1] + i*(arr[i] - arr[i-1]);
            ans -= neg[i];
        }
        printf("%lld\n", ans);
    
    }
    
    
    int main(){ 
        int t = 1;
        cin >> t;
        while(t--)
    		solve();
      	return 0;
    }

用前缀和处理也可以

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221005/6bee8c7e8b0a423f9e03863b18322c4d.png