ccpc2021哈尔滨站B、D、J、I ⽂章⽬录
B题
下⾯代码实测可以冲过去,数据的复杂度应该不能到达理论上的最坏情况。 如果不⾏,⽤bitset会快⼀点。
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int w[N];
int n;
int check(int x){
set<int>se;
int res=0;
for(int i=1;i<=n;i++){
if(w[i]>=x)continue;
if(se.find(x-w[i])==se.end()) se.insert(w[i]);
else{
res++;
se.clear();
}
}
return res*2;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
浙江同志网scanf("%d",&w[i]);
}
int ans=0;
for(int i=2;i<=200;i++){
ans=max(ans,check(i));
}
cout<<ans<<endl;
}
D题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
中国发展报告2010ll p,q;
void solve(ll &p,ll &q){
vector<int>pv;
ll ans_p=p,ans_q=q;
钛合金丝ll x=p;
int se[12]={};//存储被消去的数
while(x) pv.push_back(x%10),x/=10;
int plen=pv.size();
for(int i=0;i<(1ll<<plen);i++){
ll new_p=0;
memset(se,0,sizeof(se));
for(int j=0;j<plen;j++){
if((i&(1ll<<j))!=0){
new_p=new_p*10+pv[j];
}
else se[pv[j]]++;
}
if(new_p==0)continue;
ll g1=__gcd(p,q);
ll g2=__gcd(new_p,p/g1);
if(g1*g2!=p)continue;//不能整除
ll new_q=(q/g1)*(new_p/g2)/(p/g1/g2);//防⽌乘爆
if(new_q==0)continue;
x=q;
while(x){
--se[x%10];
x/=10;
}
x=new_q;
while(x){
现代汉语频率词典++se[x%10];
x/=10;
}
int flag=1;
for(int i=1;i<=9;i++){
if(se[i]!=0) flag=0;
}
if(flag==0)continue;
ans_p=min(ans_p,new_p);
ans_q=min(ans_q,new_q);
}
p=ans_p;
q=ans_q;
雅虎天盾}
int main(){
int t;
关敏卿
cin>>t;
while(t--){
cin>>p>>q;
solve(p,q);
cout<<p<<" "<<q<<endl;
}
return0;
}
E题
⾸先发现⼀个性质:
M没有取值,M有⼀种取值,M有⽆数种取值。
⾸先特判M有⽆数种取值的情况。
在特判⾸相是0的情况(这时所有数都是0,否则⽆解)特判结束后,算出M,再验证M即可