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

A.Kuroni and the Gifts
给你n个不同的a和b 让你分给n个人,要求每个人a,b之和不同,输出任意一种方案。
解 sort一遍即可,因为不存在相同的a和相同的b。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[105];
int b[105];
void work()
{
    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+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
    	printf("%d ",a[i]);
    }
    printf("\n");
    for(int i=1;i<=n;i++){
    	printf("%d ",b[i]);
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Kuroni and Simple Strings
给你一个括号串,取出子序列,要求子序列的前面必定是'(‘,后面必定是’)’,你可以取任意次,写出取出的次数和取出的数量和取出的位置。
解 双指针 一左一右,当左边找到'(‘,右边找到’)’时存入,只需要取一次。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
char a[1005];
int b[1005];
set<int>s;
void work()
{
    scanf("%s",a+1);
    int n;
    n=strlen(a+1);
   	int i=1;int j=n;
   	int ans=0;
	while(a[i]==')'&&i<=n)i++;
   	while(a[j]=='('&&j>=1)j--;
   	while(i<j){
   		ans+=2;
   		s.insert(i);
   		s.insert(j);
   		i++;
   		j--;
   		while(a[i]==')'&&i<=n)i++;
   		while(a[j]=='('&&j>=1)j--;
   	}
   	if(s.size()==0){
   		printf("0\n");
   		return ;
   	}
   	printf("%d\n",1);
   	printf("%d\n",ans);
   	for(auto i:s){
   		printf("%d ",i);
   	}
   	printf("\n");
 
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Kuroni and Impossible Calculation
给n个数和模数m,求\(\prod_{1\leq i<j\leq n}|a_i-a_j|\)%m。
解 当n超过m的时候,必定有两个数的模m为同一个值,差值模m必定为0,答案必定为0,所以n>m的时候直接0,小于等于m的时候暴力解即可

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[200005];
int sum[200005];
int vis[1005];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    if(n>m){
        printf("0\n");return;
    }
    ll ans=1;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ans=(ans*abs(a[i]-a[j]))%m;
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.Kuroni and the Celebration
交互题,给你n个点的树,n-1条边,你每次可以询问2个点,然后会返回2个点的LCA,让你在[n/2]次询问内找到根。
解 先假设ans为1,然后在while(1)内跑2次dfs,注意标记已经跑过的地方,那么得到的2个点就是包含当前ans的一条链,将这个输出询问,得到的答案做为新的ans(此时该链上其他所有被访问过的点都一定不是根),当第一次dfs只能找到当前的ans时(即该点直接相连的其他点都已经被访问过),那么答案就是ans

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
vector<int>v[1005];
int vis[1005];
int que(int x,int y)
{
    int k;
    cout<<"? "<<x<<" "<<y<<endl;
    cin>>k;
    cout.flush();
    return k;
}
int dfs(int x)
{
    vis[x]=1;
    for(int i=0;i<v[x].size();i++){
        if(!vis[v[x][i]]){
            return dfs(v[x][i]);
        }
    }
    return x;
}
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int ans=1;
    while(1){
        //printf("1\n");
        int tmp1=dfs(ans);
        int tmp2=dfs(ans);
        if(tmp1==ans){
            cout<<"! "<<ans<<endl;return;
        }else{
            ans=que(tmp1,tmp2);
        }
    }
}

E.Kuroni and the Score Distribution
构造一个长度为n的序列,要求能满足\(i+j=k\)并且\(a_i+a_j=a_k\)的三元组有m个。
首先 当三元组最多时 就是1,2,3,4,……这样的等差数列,maxx=\(\sum_{i=1}^n(n-1)/2\),m大于maxx时 输出-1,然后考虑删去多余的,从序列最后开始删,对于序列的最后一个值,可以减少的多元组为0到(n-1)/2,如果要删掉(n-1)/2个,那么相当于要删掉和这个有关所有三元组,那么取到最大值即可,注意多次取到最大值时差要超过n 防止出现还可以组成三元组的情况。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[5005];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=(i-1)/2;
    }
    if(m>sum){
        printf("-1\n");
        return;
    }else{
        for(int i=1;i<=n;i++){
            a[i]=i;
        }
        int now=n;
        m=sum-m;
        while(m){
            //printf("%d\n",m);
            int tmp=(now-1)/2;
            if(tmp<=m){
                a[now]=1e9-1e5*(n-now);
                m-=tmp;
            }else{
                a[now]=a[now-1]+a[2*m+1];
                m=0;
            }
            now--;
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.Kuroni and the Punishment
给n个数,可以进行一种操作,使得某个数+1或者-1,问使得所有数的gcd不为1的最少操作数
解 emmm 随机化  首先答案不会超过n,因为gcd为2的话 对于每个数最多进行一次操作。至少有一半的数最多只会加减1次(加减2次就超过n了),所以随机选一个x,有1/2的概率答案为x-1,x,x+1的素因子。随机取一定数量的x,贪心求即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
ll a[200005];
set<ll>s;
int n;
void cal(ll x)
{
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            s.insert(i);
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1){
        s.insert(x);
    }
}
ll sum(ll x)
{
    ll res=0;
    for(ll i=1;i<=n;i++){
        res+=min(x-a[i]%x,a[i]>=x?a[i]%x:x);
    }
    return res;
}
void work()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    random_shuffle(a+1,a+n+1);
    for(int i=1;i<=50;i++){
        cal(a[i]);
        cal(a[i]+1);
        cal(a[i]-1);

    }
    ll ans=n;
    for(auto x:s){
        ans=min(ans,sum(x));
    }
    printf("%lld\n",ans);
}
int main()
{
    srand(time(0));
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

G.Kuroni and Antihype
给你n个人,可以有两种操作,一种是个人加入组织,无收益。另一种是i邀请j,获得i的收益,要求i&j=0,问最大收益。
解 首先 如果不考虑这个限制,直接给边,每个边的边权为两点点权和,那么很简单可以得到答案是边权和-点权和。然后要加入这个限制,那么设定一个为0的人,这样这个人可以将所有人拉入组织,但无收益,这样相当于把第一种操作变成第二种,根据第二种跑最大生成树即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[500005];
int sum[500005];
int fa[500005];
int vis[500005];
ll ans=0;
int find(int x)
{
    if(fa[x]!=x){
        return fa[x]=find(fa[x]);
    }
    return x;
}
void cal(ll x,int y,int z)
{
    int y1=find(y);
    int z1=find(z);
    if(y1==z1)return;
    ans+=x*((vis[y1]?1:sum[y1])+(vis[z1]?1:sum[z1])-1);
    fa[y1]=z1;
    vis[y1]=1;
    vis[z1]=1;
}
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[a[i]]++;
        ans-=a[i];
    }
    for(int i=1;i<=200000;i++){
        fa[i]=i;
    }
    sum[0]++;
    for(int i=1<<18;i>=0;i--){
        for(int j=i;j;j=(j-1)&i){
            int k=j^i;
            if(sum[j]&&sum[k])cal(i,j,k);
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注