Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)

A题：

既然保证了不同那么排个序就行了。

#include <bits/stdc++.h>
using namespace std;
int a[105],b[105];
int main()
{
    int t; scanf("%d",&t);
    while(t--){
        int n; scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",b+i);
        }
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        for(int i=1;i<=n;i++) printf("%d ",a[i]);
        puts("");
        for(int i=1;i<=n;i++) printf("%d ",b[i]);
        puts("");
    }
}

B题：

维护左右端点的下标，找到匹配的括号就好了。

#include <bits/stdc++.h>
using namespace std;
int a[1005];
int main()
{
    string str;
    vector<int> res;
    cin>>str;
    int l=0,r=str.size()-1;
    while(l<r){
        while(str[l]!='(') l++;
        while(str[r]!=')') r--;
        if(l>=r) break;
        res.push_back(l+1);
        res.push_back(r+1);
        l++,r--;
    }
    if(res.size()==0) cout<<0<<endl;
    else {
        sort(res.begin(),res.end());
        cout<<1<<endl;
        cout<<res.size()<<endl;
        for (auto it:res) cout << it << ' ';
        cout << endl;
    }
}

C题：

鸽巢定理，可以把大区间排除，然后小区间就直接暴力就行了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
int a[N];
signed main()
{
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int res=1;
    if(n>m) {
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            res=res*abs(a[i]-a[j])%m;
        }
    }
    cout<<res<<endl;
}

E题：

最大对数的构造方法是，每个$a_i$的下标就是他的值一定是构造的最大的。因为我们可以证明出每个二元组得到的$a_k$一定是两两不同的。所以我们在n以内的对数就是$0/2+1/2+3/2...+(n-1)/2$因为要把自己给扣掉。然后我们如果这样构造的方案都小于m那么答案就是-1，否则我们需要让res=m就从后忘前减去。最后我们不满足if条件的时候我们的res的值一定是落在m到m+(i-1)/2的范围之内的。这样答案还是多了。但是又不能直接减去(i-1)/2，这样减去太多了。所以我们直接让区间左端点向右移动(res-m)*2这样就相当于减去了多余的对数(res-m)个。
其实当m=0的时候直接构造一连串连续的奇数就行了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+7;
int a[N],res[N];

signed main()
{
    int res=0;
    int n,m; scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) a[i]=i;
    for(int i=1;i<=n;i++) res+=(i-1)/2;
    if(res<m) {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=n;i>=1;i--){
        if(res-(i-1)/2>=m){
            res-=(i-1)/2;
            a[i]=5e8+i*10000;
            continue;
        }
        a[i]+=(res-m)*2;
        break;
    }
    for(int i=1;i<=n;i++) printf("%lld ",a[i]);
    cout<<endl;
}