Codeforces Round #828 (Div. 3)
1.Problem - D - Codeforces
只要找有因子2的个数即可。只要因子个数是大于等于n的即可。
void slove(){
cin >> n;
fel(i,1,n) cin >> a[i];
int sum = 0, ans = 0;
fel(i,1,n){
while(a[i] % 2 == 0){
a[i] /= 2;
sum++;
}
}
if(sum >= n){
cout << 0 <<endl;
return;
}
vector<int>w(n+1);
fel(i,1,n){
int t = i,ww =0;
while(t%2==0){
t/=2;
ww++;
}
w[i] = ww;
}
sort(w.begin()+1, w.begin()+1+n,greater<int>());
fel(i,1,n){
if(sum<n){
sum+=w[i];
ans++;
}
if(sum >= n){
cout << ans <<endl;
return;
}
}
cout << -1 << endl;
}
2.Problem - E1 - Codeforces
首先是考虑到因子上面。首先是一个结论1e9以内的最多只有1334个因子。1e18以内的因子最多1e5左右。
所以就可以直接考虑枚举因子分到x, y上,直接暴力枚举就好了。
/*
确实使之前考虑因子的方法
但是感觉大家都没咋讲清楚我还是很懵
大概明白了就是1e9以内的最多因子就只有1334个
1e18也就只有1e5个左右所以直接考虑dfs考虑x和y中某个数分配某个因子即可。
*/
int a,b,c,d,flag,ansx,ansy;
map<int,int>mp;
vector<pair<int,int> >tt;
void init(int x){
for(int i = 2; i*i <= x; i++){
while(x%i==0){
x /= i;
mp[i]++;
}
}
if(x) mp[x]++;
}
void dfs(int ind, int x, int y){//x,y是因子的乘积
if(ind == tt.size()){
int t1=(a / x + 1)*x;
int t2=(b / y + 1)*y;
if(t1<=c&&t2<=d){
flag = 1;
ansx = t1;
ansy = t2;
}
return;
}
//然后就是考虑把因子分别分到两个数里面
int p = tt[ind].first, cnt = tt[ind].second;
int poww = pow(p,cnt);
int res = 1;
for(int i = 0; i<=cnt; i++){
dfs(ind + 1,x*res, y*poww/res);
res *= p;
}
}
void slove(){
cin >> a >> b >> c >> d;
tt.clear();
flag = 0;
mp.clear();
init(a);
init(b);
for(auto p : mp){
tt.pb(p);
}
dfs(0,1,1);
if(flag){
cout<< ansx << " " << ansy <<endl;
}
else{
cout << -1 << " " << -1 <<endl;
}
}
3.Problem - F - Codeforces
要使mex是大于med的发现这种情况是很少的,所以考虑去求这种情况,这种情况只有当0-x都在在这个区间内,但是x不再这个区间内。
再考虑这个区间的中位数如果他的区间长度小于2*x很明显他的中位数一定是小于x的。发现只有这种情况是有可能发生mex > med的。
所以考虑求这种情况就可以了。
void slove(){标签:cout,int,tt,pos,Codeforces,因子,828,Div From: https://www.cnblogs.com/silky----player/p/16815093.html
cin >> n;
fel(i,0,n) pos[i] = 0;//初始化pos[n]使他不能加
fel(i,1,n) cin >> a[i], pos[a[i]] = i;
int l = pos[0],r = pos[0], ans = 0;
for(int i = 1; i <= n; i++){
if(i!=n&&l<=pos[i]&&r>=pos[i]) continue;//已经算过
int len = 2 * i;
if(len>=r-l+1){
if(pos[i] > r){
for(int j = r; j < pos[i]; j++){
int k = max(1ll, j - len + 1);
ans += max(1ll*0,l - k + 1);
}
}
else{
for(int j = pos[i] + 1; j <= l; j++){
int k = min(n,len + j - 1);
ans += max(1ll*0,k - r + 1);
}
}
}
l = min(l,pos[i]);
r = max(r,pos[i]);
}
cout << ans << endl;
}