CF Round # 295 (Div. 1)题解

2023-11-19 14:54:34

CF Round # 295 (Div. 1)题解

CF 521 A. DNA Alignment

假设字符串中的 A , G , C , T A,G,C,T A,G,C,T个数分别为 a , g , c , t a,g,c,t a,g,c,t。你构造出的个数分别为 a ′ , b ′ , c ′ , d ′ a\prime,b\prime,c\prime,d\prime a′,b′,c′,d′。

则 ρ ( s , t ) = a ∗ a ′ + g ∗ g ′ . . . ρ(s,t)=a*a\prime+g*g\prime... ρ(s,t)=a∗a′+g∗g′...，可以发现最优解一定是让 max ⁡ { a , g , c , t } \max\{a,g,c,t\} max{a,g,c,t}乘上一个数。

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int main(){
	int n;
	string s;
	cin>>n>>s;
	LL rest=1;
	map<char,int> cnt;
	rep(i,n) cnt[s[i]]++;
	vector<int> v;
	for(auto ite=cnt.begin();ite!=cnt.end();ite++){
		v.PB(ite->SEC);
	}
	sort(ALL(v));
	reverse(ALL(v));
	int x=0;
	rep(i,v.size())
		if(v[i]==v[0]) ++x;
	rb(i,1,n)
		rest=rest*x%(int)(1e9+7);
	cout<<rest<<endl;	
	return 0;
}

CF 521 B. Cubes

搞一个set存放当前可行的方块，贪心即可。

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
map<mp,int> M;
int m;
const int MAXN=1e5+20;
int x[MAXN],y[MAXN];
vector<int> v[MAXN],up[MAXN];
int oc[MAXN];
set<int> can;
const int MOD=1e9+9;
int stand[MAXN];
void erase(int x){
	can.erase(x);
	for(auto it:up[x]){
		v[it].erase(lower_bound(ALL(v[it]),x));
	}
	if(v[x].size()==1){
		oc[v[x][0]]--;
		if(oc[v[x][0]]==0){
//			cout<<"In"<<v[x][0]<<endl;
			can.insert(v[x][0]);
		}
	}
	for(auto it:v[x]){
		up[it].erase(lower_bound(ALL(up[it]),x));
	}
	for(auto it:up[x]){
		if(v[it].size()==1){
			oc[v[it][0]]++;
			if(can.find(v[it][0])!=can.end())
				can.erase(v[it][0]);
		}
	}
}
int main(){
	scanf("%d",&m);
	rb(i,1,m) scanf("%d%d",&x[i],&y[i]),M[II(x[i],y[i])]=i;
	rb(i,1,m){
		rb(j,-1,1)
			if(M.find(II(x[i]+j,y[i]-1))!=M.end()) v[i].PB(M[II(x[i]+j,y[i]-1)]),up[M[II(x[i]+j,y[i]-1)]].PB(i);
	}
	rb(i,1,m) sort(ALL(v[i])),sort(ALL(up[i]));
	rb(i,1,m) stand[i]=v[i].size();
	rep(i,m) can.insert(i+1);
	rb(i,1,m) if(stand[i]==1){
		oc[v[i][0]]++;
		if(can.find(v[i][0])!=can.end()){
//			cout<<"Er"<<i<<' '<<v[i][0]<<endl;
			can.erase(v[i][0]);
		}
	}
	LL rest=0;
	rb(i,1,m){
		rest=rest*m%MOD;
		int ban;
//		cout<<can.size()<<endl;
		if(i&1){
			auto ite=can.end();
			ban=*(--ite);
		}
		else{
			ban=*can.begin();
		}
//		cout<<i<<' '<<ban<<endl;
		erase(ban);
		rest+=ban-1;
	}
	cout<<rest%MOD<<endl;
	return 0;
}

CF 521 C. Pluses everywhere

对于每一个 a i a_i ai​讨论在后面最近的 + + +在哪？

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MOD=1e9+7;
int n,k;
LL quick(LL A,LL B){
	if(B==0) return 1;
	LL  tmp=quick(A,B>>1);
	tmp*=tmp;
	tmp%=MOD;
	if(B&1)
		tmp*=A,tmp%=MOD;
 	return tmp;
}
int fact[100000+20],invfact[100000+20];
int suf[100000+20];
int tot;
int rest=0;
LL c(int A,int B){
	if(B==0) return 1;
	if(B<0) return 0;
	if(A<B) return 0;
	return 1ll*fact[A]*invfact[A-B]%MOD*invfact[B]%MOD;
}
int main(){
	scanf("%d%d",&n,&k);
	string s;
	cin>>s;
	rl(i,n-1,1)	
		suf[i]=suf[i+1]+(s[i-1]-'0');
	fact[0]=1;
	rb(i,1,n){
		fact[i]=1ll*fact[i-1]*i%MOD;
	}
	invfact[n]=quick(fact[n],MOD-2);
	rl(i,n-1,0)
		invfact[i]=1ll*invfact[i+1]*(i+1)%MOD;
	tot=0;
	int bad=0,ten=1;
	rb(i,1,n-2){
		tot-=bad;
		tot+=MOD;
		tot%=MOD;
		tot=10ll*tot%MOD;
		bad+=1ll*ten*(s[n-1-i]-'0')%MOD;
		bad%=MOD;
		ten=10ll*ten%MOD;
		(tot+=suf[i+1])%=MOD; 
		(rest+=1ll*tot*c(n-2-i,k-2)%MOD)%=MOD;
	}
	int tmp=0;
	rb(i,1,n-1){
		tmp=10ll*tmp%MOD;
		(tmp+=(s[i-1]-'0'))%=MOD;
		(rest+=1ll*tmp*c(n-1-i,k-1)%MOD)%=MOD;
	}
	int z=1;
	tmp=0;
	rb(i,1,n){
		(tmp+=1ll*(s[n-i]-'0')*z%MOD)%=MOD;
		z=10ll*z%MOD;
		(rest+=1ll*tmp*c(n-1-i,k-(i!=n))%MOD)%=MOD;
	}
	cout<<rest<<endl;
	return 0;
}

CF 521 D. Shop

对于每一个数取 ln ⁡ \ln ln，然后乘法就转换成了加法。

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int k,n,m; 
const int MAXN=1e5+20;
vector<mp> as[MAXN],ad[MAXN];
vector<pair<double,int> > mu;
int a[MAXN],ty[MAXN];
double best,tmpanswer;
deque<int> TMP;
deque<int> answer;
bool cmp(int A,int B){
	return ty[A]<ty[B];
}
void Assign(){
	if(best>tmpanswer) return;
	answer=TMP;
	best=tmpanswer;
}
int main(){
	scanf("%d%d%d",&k,&n,&m);
	rb(i,1,k) scanf("%d",&a[i]);
	rb(i,1,n){
		int ti,ii,bi;
		scanf("%d%d%d",&ti,&ii,&bi);
		ty[i]=ti;
		if(ti==1) as[ii].PB(II(bi,i));
		else if(ti==2) ad[ii].PB(II(bi,i));
		else mu.PB(II(log(double(bi)),i));
	}
	best=-1;
	tmpanswer=0.0;
	sort(ALL(mu));
	reverse(ALL(mu));
	rb(i,1,k) sort(ALL(as[i])),reverse(ALL(as[i]));
	priority_queue<pair<double,int> > pq;
	rb(i,1,k){
		if(!as[i].empty()&&as[i][0].FIR>a[i]) ad[i].PB(II(as[i][0].FIR-a[i],as[i][0].SEC));sort(ALL(ad[i]));
		reverse(ALL(ad[i]));
		tmpanswer+=log(double(a[i]));
		LL sum=a[i];
		for(auto it:ad[i]){
			pq.push(II(log(double(sum+it.FIR))-log(double(sum)),it.SEC));
			sum+=it.FIR;
		}
	}
	if(pq.size()+mu.size()<=m){
		while(!pq.empty()) answer.PB(pq.top().SEC),pq.pop();
		for(auto it:mu) answer.PB(it.SEC);
	}
	else{
	while(m>mu.size()){
		TMP.push_front(pq.top().SEC);
		tmpanswer+=pq.top().FIR;
		pq.pop();
		--m;
	}
	double M=0.0;
	rep(i,m) M+=mu[i].FIR;
	rep(i,m) TMP.PB(mu[i].SEC);
	rl(i,m-1,0){
		tmpanswer+=M;
		Assign();
		tmpanswer-=M;
		if(pq.empty()) break;
		TMP.POB();
		TMP.push_front(pq.top().SEC);
		tmpanswer+=pq.top().FIR;
		pq.pop();
		M-=mu[i].FIR;
	}
	Assign();
	}
	sort(ALL(answer),cmp);
	cout<<answer.size()<<endl;
	for(auto it:answer) printf("%d ",it);
	return 0;
}

CF 521 E. Cycling City

…

上一篇：机器学习系列：大规模机器学习(Large Scale Machine Learning)


下一篇：295. Find Median from Data Stream