2016-2017 CT S03E07: Codeforces Trainings Season 3 Episode 7 - HackerEarth Problems Compilation 解题报告

2024-02-20 20:55:40

E

签到，我们贪心的解决问题，给第一个骑士找一匹战斗力最强的马，剩下的骑士和剩下的马按最大和最小组合，次小和次大组合以此类推，维护一个战斗力最大值跟第一个骑士和他的马合起来的战斗力毕竟就可以知道答案了。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

int n;
ll Ans,tmp;

int main(){
	n=input();
	for(int i=1;i<=n;i++){
		tmp=0x3f3f3f3f;
		for(int j=1;j<=n;j++)
			tmp=min(tmp,input());
		Ans=max(tmp,Ans);
	}
	printf("%lld\n",Ans);
}

B

签到，由题意易知字符串的长度只能为\(2^i\)，并且对于任意\(2*i\)和\(2*i+1\)(\(0\le i \le length/2\))的字符中必须有一个为P。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

int inv[100];
map <int,int> mp;

int main(){
	inv[0]=1;
	for(int i=1;;i++){
		inv[i]=inv[i-1]*2;
		mp[inv[i]]=1;
		if(inv[i]>100) break;
	}

	int T=input();

	while(T--){
		string s;
		cin>>s;
		if(s.length()==1){
			printf("YES\n");
		}else{
			if(mp[s.length()]==0) printf("NO\n");
			else{
				int Ans=1;
				for(int i=1;i<s.length();i+=2){
					if(s[i]!='P'&&s[i-1]!='P'){
						Ans=0;
					}
				}
				if(Ans) printf("YES\n");
				else printf("NO\n");
			}
		}
	}
}

C

我们可以通过组合数学来解决这个问题。对于一个火柴人，我们如果能确定它的身体,那么它的头和手我们可以分别通过\(C_{身体连接的点数}^{3}*C_{屁股连接的点数}^{2}\)来求得答案。但是仔细思考我们发现可能有点同时与身体和屁股相连，这时我们需要分类讨论一下。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const int N=207;
const ll mod=1e9+7;

vector <int> G[N];

int cnt[N*N];
PII e[N*N];
ll C[N][N],Ans=0;

void init(){
	C[0][0]=1;
	for(int i=1;i<N;i++) C[i][0]=C[i][i]=1;
	for(int i=2;i<N;i++){
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
}

ll c(int a,int b){
	if(b>a) return 0;
	else return C[a][b];
}

int main(){
	init();

	int n=input(),m=input();

	for(int i=1;i<=m;i++){
		e[i].fr=input(),e[i].sc=input();

		cnt[e[i].fr]++,cnt[e[i].sc]++;

		G[e[i].fr].pb(e[i].sc),G[e[i].sc].pb(e[i].fr);
	}

	for(int i=1;i<=m;i++){
		map<int,int> mp;
		mp.clear();
		for(auto v:G[e[i].fr]) mp[v]=1;
		for(auto v:G[e[i].sc]) mp[v]=1;

		int tmp=cnt[e[i].fr]+cnt[e[i].sc]-mp.size();

		int tmp1=cnt[e[i].fr]-tmp-1;
		int tmp2=cnt[e[i].sc]-tmp-1;

		for(int j=0;j<=min(tmp,3);j++){
			Ans=(Ans+c(tmp1,3-j)*c(tmp,j)%mod*c(tmp2+tmp-j,2)%mod)%mod;
		}

		for(int j=0;j<=min(tmp,2);j++){
			Ans=(Ans+c(tmp1,2-j)*c(tmp,j)%mod*c(tmp2+tmp-j,3))%mod;
		}
	}
	printf("%lld\n",Ans);
}

I

关于此题我们首先需要知道一些性质。

从\(a\)到\(b\)除了加减\(a\)和\(b\)自身，只能通过\(+2\)或者\(-2\)来调整数字且最多移动两次。
由1我们不难想到不会存在多解，因为不存在路径的分叉。

有了上面两条性质我们可以知道\(2\)是解决本题的关键。

我们可以分类讨论：

当\(a=2\)时，只有两种可能:

从\(2\)直接到\(b\)，此时需要满足\(b-2\)为质数。
从\(2\)到\(b+2\)再到\(b\)，此时需要满足\(b+2\)为质数即可。

当\(a \ne 2\)时，有三种可能：

\(a\)可以通过加若干次\(2\)到达\(b\)。
从\(a\)到\(2\)再回到\(a=2\)情况去讨论，此时需要满足\(a-2\)为质数。
从\(a\)到\(a+2\)再到\(2\)再回到\(a=2\)的情况去讨论，此时需要满足\(a+2\)为质数。

以上的讨论都围绕这一个问题素数测试，我们可以通过多种科技来测试素数。在此题中无论是米勒-拉宾素数测试还是根号复杂度的素数测试均可以通过所以数据。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

const long long S=20;
long long mult_mod(long long a,long long b,long long c){
    a%=c;
    b%=c;
    long long ret=0;
    while(b){
        if(b&1){ret+=a;ret%=c;}
        a<<=1;
        if(a>=c)a%=c;
        b>>=1;
    }
    return ret;
}
long long pow_mod(long long x,long long n,long long mod){
    if(n==1)return x%mod;
    x%=mod;
    long long tmp=x;
    long long ret=1;
    while(n){
        if(n&1) ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ret;
}
bool check(long long a,long long n,long long x,long long t){
    long long ret=pow_mod(a,x,n);
    long long last=ret;
    for(long long i=1;i<=t;i++){
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true;
        last=ret;
    }
    if(ret!=1) return true;
    return false;
}
bool isprime(long long n){
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;
    long long x=n-1;
    long long t=0;
    while((x&1)==0){x>>=1;t++;}
    for(long long  i=0;i<S;i++){
        long long a=rand()%(n-1)+1;
        if(check(a,n,x,t))
            return false;
    }
    return true;
}
long long factor[1000000];
long long tol;
long long gcd(long long a,long long b){
    if(a==0)return 1;
    if(a<0)return gcd(-a,b);
    while(b){
        long long t=a%b;
        a=b;
        b=t;
    }
    return a;
}
long long Pollard_rho(long long x,long long c){
    long long i=1,k=2;
    long long x0=rand()%x;
    long long y=x0;
    while(1){
        i++;
        x0=(mult_mod(x0,x0,x)+c)%x;
        long long d=gcd(y-x0,x);
        if(d!=1&&d!=x) return d;
        if(y==x0) return x;
        if(i==k){y=x0;k+=k;}
    }
}
void findfac(long long n){
    if(isprime(n)){
        factor[tol++]=n;
        return;
    }
    long long p=n;
    while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1);
    findfac(p);
    findfac(n/p);
}

vector<ll> Ans;

void print(){
    printf("%lld",Ans[0]);
    for(int i=1;i<Ans.size();i++){
        printf("->%lld",Ans[i]);
    }printf("\n");
}

int main(){
    ll a=input(),b=input();

    if(a==2){
        if(isprime(b-2)){
            printf("%lld->%lld\n",a,b);
        }else if(isprime(b+2)){
            printf("%lld->%lld->%lld\n",a,b+2,b);
        }else printf("Unlucky Benny\n");
    }else{
        Ans.clear();Ans.push_back(a);
        for(ll t=a+2;t<=b;t+=2)
            if(isprime(t)){
                Ans.push_back(t);
                if(t==b) print(),exit(0);
            }else break;
        
        Ans.clear(),Ans.push_back(a);
        if(isprime(a-2)){
            Ans.push_back(2);
            if(isprime(b-2)) Ans.push_back(b),print(),exit(0);
            if(isprime(b+2)) Ans.push_back(b+2),Ans.push_back(b),print(),exit(0);
        }

        if(isprime(a+2)){
            Ans.push_back(a+2);Ans.push_back(2);
            if(isprime(b-2)) Ans.push_back(b),print(),exit(0);
            if(isprime(b+2)) Ans.push_back(b+2),Ans.push_back(b),print(),exit(0);
        }
        
        printf("Unlucky Benny\n");
    }
}

D

直接用数据结构做容易超时。我们可以设一个函数\(f(x,y)\)，表示区间\([1,x]\)与区间\([1,y]\)的答案。那么对于题干中的询问就相当于询问\(f(r_1,r_2)-f(l_1-1,r_2)-f(r_1,l_2-1)+f(l_1-1,l_2-1)\)。对于求出若干个\(f(x,y)\)值我们可以用莫队来求。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

const int N=5e4+7;
int n,q,k;
int a[N];
struct Query{
	int l,r,id;
}qu1[N],qu2[N],qu3[N],qu4[N];

bool operator <(Query &a,Query &b) { return a.l/k==b.l/k? a.r<b.r:a.l/k<b.l/k; }

ll Ans[N];
int cnt1[N],cnt2[N];
ll Ans1[N],Ans2[N],Ans3[N],Ans4[N];


void Solve(Query qu[],ll Ans[]){
	memset(cnt1,0,sizeof cnt1);
	memset(cnt2,0,sizeof cnt2);

	k=ceil(pow(n,0.5));
	sort(qu+1,qu+1+q);

	int l=0,r=0;
	ll now=0;

	for(int i=1;i<=q;i++){
		while(l<qu[i].l) now+=cnt2[a[++l]],cnt1[a[l]]++;
		while(l>qu[i].l) now-=cnt2[a[l]],cnt1[a[l--]]--;
		while(r<qu[i].r) now+=cnt1[a[++r]],cnt2[a[r]]++;
		while(r>qu[i].r) now-=cnt1[a[r]],cnt2[a[r--]]--;
		Ans[qu[i].id]=now;	
	}
}

int main(){
	n=input();
	for(int i=1;i<=n;i++){
		a[i]=input();
	}

	q=input();
	for(int i=1;i<=q;i++){
		int l1=input(),r1=input(),l2=input(),r2=input();

		qu1[i]={r1,r2,i};
		qu2[i]={r1,l2-1,i};
		qu3[i]={l1-1,r2,i};
		qu4[i]={l1-1,l2-1,i};
	}

	Solve(qu1,Ans1);
	Solve(qu2,Ans2);
	Solve(qu3,Ans3);
	Solve(qu4,Ans4);

	for(int i=1;i<=q;i++){
		printf("%lld\n",Ans1[i]-Ans2[i]-Ans3[i]+Ans4[i]);
	}
}

码农公寓

E

B

C

I

D

相关文章