CF Round # 295 (Div. 1)题解
CF 521 A. DNA Alignment
假设字符串中的(A,G,C,T)个数分别为(a,g,c,t)。你构造出的个数分别为(aprime,bprime,cprime,dprime)。
则(ρ(s,t)=a*aprime+g*gprime...)，可以发现最优解一定是让(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)讨论在后面最近的(+)在哪？
/*
{
######################
# 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)，然后乘法就转换成了加法。
/*
{
######################
# 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
...