CodeForces / 未解决

  • A-Ehab Fails to Be Thanos

    • 给出2n个数，输出前n个数的和不等于后n个数的和的任一序列
    • 解法，排序即可
    • #include<cstdio>
#include<queue>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1e6+10;


int a[maxn];

int main(){
	int n;
	cin>>n;
	long long sum=0;
	for(int i=1;i<=n*2;i++){
		scanf("%d" , &a[i]);
		sum+=a[i];
	}
	sort(a+1,a+n*2+1);
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=a[i];
	}
	if(sum-ans==ans){
		cout<<-1<<endl;
	}
	else {
		for(int i=1;i<=2*n;i++){
			printf("%d ", a[i]);
		}
	}
	return 0;
}

  • B-Ehab Is an Odd Person

    • 给出一个序列，若ai+aj为奇数，即可交换它们（可进行若干次交换）
    • 问能得到的字典序最小的序列（即让越小的数放在越前）
    • 显然，我们能得到以下结论：如果一个序列不是全是奇数或者全是偶数，那么这个序列就可以被任意排序，否则就不能被排序
    • 全奇全偶显然不能被排序；而只要奇偶参杂，那么任意的数都可以经过至多两次交换被换到任意位置（分类一下就能证明）
    • #include<cstdio>
#include<queue>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
const int maxn=1e6+10;
#define ll long long


int a[maxn];
int main(){
	int n;
	cin>>n; 
	int cnt=0;
	rep(i,1,n){
		scanf("%d", &a[i]);
		if(a[i]&1)++cnt;
	}
	if(cnt!=n&&cnt!=0){
		sort(a+1,a+n+1);
	}
	rep(i,1,n)printf("%d ", a[i]);
	return 0;
}

  • C-Ehab and a Special Coloring Problem

    • 给出n个空的位置，让在2~n的位置上填正整数（2<=n<=1e5）
    • 其中下标i，j互素的位置不能填相同的数，要使得序列中最大数最小化
    • 显然，要使得最大数最小化，那么就从cnt=1开始，使得所有不互素的位置上填上相同的数字
    • 按照素数筛法，我们将素数以及其倍数的位置上赋上cnt++即可
    • #include<cstdio>
#include<queue>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
const int maxn=1e6+10;
#define ll long long


int vis[maxn];
int main(){
	int n;
	cin>>n;
	int cnt=0;
	vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			vis[i]=++cnt;
			for(int j=i*2;j<=n;j+=i){
				vis[j]=cnt;
			}
		}
	}
	for(int i=2;i<=n;i++){
		printf("%d ", vis[i]);
	}
}

  • D-Ehab and the Expected XOR Problem

    • 构造一个序列
    • 序列满足
      1. 用于构造的数在1~2^n(n<=18)内
      2. 任意非空子段异或和不等于0或者给出的x
      3. 长度最大化
    • 想了半天，没有很好的思路
    • 但实际上，我们可以通过“子段”以及“异或”的性质想到需要用到前缀异或和
    • 由于前缀和的缘故，我们不再需要考虑连续的问题（前缀本身连续）
    • 而由于异或的缘故，我们不再需要考虑顺序的问题（异或满足交换律）
    • 所以我们让al⊕al+1⋯⊕ar=bl−1⊕br
    • 然后不等于0则等价于没有重复的数字出现
    • 不等于x等价于若取了i，则不取x^i
    • 最后再ai=bi⊕bi−1ai=bi⊕bi−1.还原即可
    • #include <iostream>
#include <vector>
using namespace std;
bool ex[(1<<18)];
int main()
{
    int n,x;
    scanf("%d%d",&n,&x);
    ex[0]=1;
    vector<int> v({0});
    for (int i=1;i<(1<<n);i++)
    {
        if (ex[i^x])
        continue;
        v.push_back(i);
        ex[i]=1;
    }
    printf("%d\n",v.size()-1);
    for (int i=1;i<v.size();i++)
    printf("%d ",(v[i]^v[i-1]));
}

  • 1174E – Ehab and the Expected GCD Problem

    • 定义p为（1~n）的全排列中的某一个排列
    • 定义gi为排列p的前i个数的gcd，也就是前缀gcd（1<=i<=n）
    • 定义f(p)为排列p所得到的gi中不同的数的个数
    • 求使得f(p)最大的p个数
    • 题解：https://codeforces.com/blog/entry/67388
    • #include <iostream>
using namespace std;
#define mod 1000000007
int n,dp[1000005][21][2];
int f(int x,int y)
{
    int tmp=(1<<x);
    if (y)
    tmp*=3;
    return n/tmp;
}
int main()
{
    scanf("%d",&n);
    int p=0;
    while ((1<<p)<=n)
    p++;
    p--;
    dp[1][p][0]=1;
    if ((1<<(p-1))*3<=n)
    dp[1][p-1][1]=1;
    for (int i=1;i<n;i++)
    {
        for (int x=0;x<=p;x++)
        {
            for (int y=0;y<=1;y++)
            {
                dp[i+1][x][y]=(dp[i+1][x][y]+1LL*dp[i][x][y]*(f(x,y)-i))%mod;
                if (x)
                dp[i+1][x-1][y]=(dp[i+1][x-1][y]+1LL*dp[i][x][y]*(f(x-1,y)-f(x,y)))%mod;
                if (y)
                dp[i+1][x][y-1]=(dp[i+1][x][y-1]+1LL*dp[i][x][y]*(f(x,y-1)-f(x,y)))%mod;
            }
        }
    }
    printf("%d",dp[n][0][0]);
}
  • https://codeforces.com/contest/1174/problem/F
  • F题待定

发表评论

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