A. United We Stand

题意

给定一个 nn 的数的序列 aa，把他分成两个序列 bb 和 cc，使得对于所有 cic_i 都不是任意 cjc_j 的因数。

解法

  1. 若 aa 所有数相同
    显然不论怎么分都不可以。
  2. 其他
    把 aa 中所有的最大值分到 cc，其他的分到 bb，这是一个合法解。
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
57
58
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int n=read();
    vector<int> v;
    for(int i=0;i<n;i++){
        v.push_back(read());
    }

    sort(all(v));
    int maxn=v[n-1];
    if(v[0]==maxn){
        puts("-1");
    }
    else{
        vector<int> v1,v2;
        for(int i=0;i<n;i++){
            if(v[i]!=maxn)v1.push_back(v[i]);
        }
        for(int i=0;i<n;i++){
            if(v[i]==maxn)v2.push_back(v[i]);
        }
    
        printf("%lu %lu\n",v1.size(),v2.size());
        for(int x:v1)printf("%d ",x);
        puts("");
        for(int x:v2)printf("%d ",x);
        puts("");
    }
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Olya and Game with Arrays

题意

给定 nn 个数列，每个数列有 mim_i 个数。

现在可以从每个序列中至多拿出来一个数，放进任意一个数列中。
求出这样操作和序列最小值的和的最大值。

解法

考虑贪心。我们要从序列中移出最小的数，然后全部放进一个序列中。
通过枚举就可以 O(n)O(n) 解决这个问题。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 25005;
vector<int> v[N];

int n;
void solve(int kase){
    n=read();
    for(int i=0;i<n;i++){
        v[i].clear();
        int k=read();
        for(int j=0;j<k;j++){
            v[i].push_back(read());
        }
        sort(all(v[i]));
    }


    ll ans = 0;
    ll minn=INT_MAX;
    for(int i=0;i<n;i++){
        if(v[i].size()==1)ans+=v[i][0];
        else ans+=v[i][1];
        minn =min(minn,(ll)v[i][0]);
    }



    ll t=0;
    for(int i=0;i<n;i++)t+=v[i][0];

    for(int i=0;i<n;i++){ // 如果全部丢给这里的话？
        ll o;
        if(v[i].size()==1)o=v[i][0];
        else o=v[i][1];


        t=max(t,ans-o+minn);
    }

    printf("%lld\n",t);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Another Permutation Problem

题意

给定一个 nn，求出一个 1∼n1\sim n 的排列 pp，使得

∑i=1n(pi⋅i)−max⁡j=1n(pj⋅j) \sum_{i=1}^n(p_i\cdot i) - \max_{j=1}^n{(p_j\cdot j)}

最大。

解法

通过 O(n!)O(n!) 打表，不难发现答案的排列一定是

1,2,3,…,k,n,n−1,n−2,…,k+11,2,3,\ldots,k,n,n-1,n-2,\ldots,k+1

的形式。

因此就可以 O(n2)O(n^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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int a[150];

void solve(int kase){
    int n=read();



    int val = 0;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            a[j]=j;
        }
        int k =n;
        for(int j=i;j<=n;j++){
            a[j]=k--;
        }


        int ans = 0;
        int maxn = 0;
        for(int j=1;j<=n;j++){
            ans += a[j]*j;
            maxn=max(maxn,a[j]*j);
        }
        if(ans-maxn>val){
            val=ans-maxn;
        }
    }

    printf("%d\n",val);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Andrey and Escape from Capygrad

题意

在一个线段上，有 nn 个传送门。传送门由两个区间确定 [l,r],[a,b] ([a,b]⊆[l,r])[l,r],[a,b]\ ([a,b]\subseteq [l,r])，在 [l,r][l,r] 内就可以传送到 [a,b][a,b] 内的任意一个点。

现在给出 qq 个询问，每次询问给出一个初始位置 xx，请回答往右最远能够走到哪里。

解法

我们知道两个结论。

  1. 不可能往左传送。
  2. 如果要传送，一定传送到 bb 点。

因此，我们就可以用一个类似 dp 的思路，从大往小进行维护。

  1. 在 bib_i 的时候，把它对应的最右位置压入一个 set。
  2. 在 lil_i 的时候，把它对应的最右位置从 set 中删掉。
  3. 在 xx 的时候，最远位置就是 set 中的最大值。
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

void solve(int kase){
    int n=read();
    vector<tuple<int,int,int>> events;
    for(int i=0;i<n;i++){
        int l=read(),r=read(),a=read(),b=read();
        events.push_back({b,1,i});
        events.push_back({l,-1,i});
    }


    int q=read();
    vector<int> ans(q);
    vector<int> seg(n);
    multiset<int> s;
    for(int i=0;i<q;i++){
        events.push_back({read(),0,i});
    }

    sort(all(events),greater<tuple<int,int,int>>());
    for(auto [u,v,w]:events){
        if(v==1){
            seg[w]=u;
            if(s.size())seg[w]=max(seg[w],*s.rbegin());
            s.insert(seg[w]);
        }
        else if(v==0){
            ans[w]=u;
            if(s.size())ans[w]=max(ans[w],*s.rbegin());
        }
        else{
            s.erase(s.find(seg[w]));
        }
    }

    for(auto x:ans){
        printf("%d ",x);
    }
    puts("");
}   

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}