首页 > 其他分享 >Codeforces Round #828 (Div. 3)

Codeforces Round #828 (Div. 3)

时间:2022-10-21 23:46:36浏览次数:73  
标签:cout int tt pos Codeforces 因子 828 Div

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上,直接暴力枚举就好了。

image-20221021194002953

/*
确实使之前考虑因子的方法
但是感觉大家都没咋讲清楚我还是很懵
大概明白了就是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(){
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;
}
 

标签:cout,int,tt,pos,Codeforces,因子,828,Div
From: https://www.cnblogs.com/silky----player/p/16815093.html

相关文章

  • CF1735 C. Phase Shift (#824div.2)
    题目链接题意简述给你一个被加密后的字符串.字符串加密的规则是,字母表中所有二十六个字母围成一个圈,字符串中每个字母都被这个圈逆时针方向的上一个字母替代(这意味着......
  • Codeforces Round #756 (Div. 3) E1
    E1.EscapeTheMaze(easyversion)我们显然遍历根节点到叶结点的同时维护最短距离然后在return的时候看该点距离是否大于最近的朋友的距离要是大于的话我们显然可以......
  • Heidi and Library (hard) | CodeForces 802C最大流最小费用
    神仙题,想了两节ds课没想出来,跑到奇怪的犄角旮旯去了还是没法搞一个满意的模型看了洛谷黑题啊..释然了思路和细节在代码//LUOGU_RID:90857083#include<bits/stdc++.h......
  • Codeforces Round #760 E
    E.Singers'Tour我们显然可以推式子b[i]=a[i]+2a[i+1]+3a[i+1]....b[i+1]=na[i]+a[i+1]+2a[i+2]....这样b[i+1]-b[i]=-n*a[i]+(a[i]+a[i+1]+....+a[n])我们显然......
  • div 内容生成图片并下载
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="v......
  • Educational Codeforces Round 83 (Rated for Div. 2) C. Adding Powers(进制转换)
    https://codeforces.com/contest/1312/problem/C题目大意:给定一个长度为n的数组a,在给定一个底数k。一开始数组元素全部都是0,我们每一个时间i可以选择一个下标下的数字......
  • Educational Codeforces Round 138 (Rated for Div. 2) ABC(二分)
    只能说这场的出题人不适合我食用,ABC都读了假题,离谱啊~A.CowardlyRooks题目大意:给定一个棋盘n*n的大小,左下角的顶点在(1,1);给定了棋盘格上的m个棋子坐标。这m个棋子......
  • 「题解」Codeforces 1730F Almost Sorted
    给定一个长度为\(n\)的置换\(p\),以及一个正整数\(k\).对于一个置换\(q\),要求对于所有满足\(1\leqi<j\leqn\)的\(i,j\),有以下不等式成立:\[p_{q_i}\leqp_{q_j}+......
  • 用好 DIV 和 API,在前端系统中轻松嵌入数据分析模块
    在数字化转型潮流席卷各大行业的今天,越来越多的企业开始重视BI(商业智能)技术的部署和应用,期望从不断增长的数据资源中获得更多业务价值,从而提升利润、控制风险、降低成本。B......
  • Codeforces Round #762 (Div. 3) E
    E.MEXandIncrements我们一看数据n个数还要计算n+1一个mex显然不能暴力我们考虑后面的i可以由前面的贪心的做一次操作转移过来所以我们记录一个a数组放着多出来的......