Codeforces 第 813 轮(第 2 部分)A - E2
文章Codeforces Round #813 (Div. 2) A - E2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A:一组长度为n 的排列,问交换多少次,能让前m个数变成[1,m]中的数
输出前 m 个数中有多少个比 m 大的就可以了
//-------------------------代码---------------------------- //#define int llconst int N = 1e5+10;int n,m; void solve(){ cin>>n>>m; int ans = 0; setq; fo(i,1,n) { int x;cin>>x; if(i <= m) { if(x > m) { ans ++ ; } } } cout< >n,n)// while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve();// {solve(); } return 0;} /*样例区 */ //------------------------------------------------------------
B:一组长度为n的数,让所有数的位置和值的lcm之和最大
位置大的和值大的lcm如果不是本身一般就是最大的。
知识:x和x+1互质。所以只要 将n 个数两两互换就可以了
需要注意,如果有奇数个数,第一个数只能是1,偶数个数,第一个数只能是2
//-------------------------代码---------------------------- //#define int llconst int N = 1e5+10;int n,m;int a[N];void solve(){ cin>>n; for(int i = n;i>=1;i-=2) { a[i] = i - 1;a[i-1] = i; } if(n % 2 == 1) a[1] = 1; else a[1] = 2; fo(i,1,n) cout<>t;while(t -- ) solve(); return 0;} /*样例区 */ //------------------------------------------------------------
C:n个数,问删除多少种数,可以使序列递增
从前往后遍历,如果当前数出现两次以上,并且不相邻,就要删掉所有数的种数
如果当前数比后面的数大,也要删掉所有数的种数
取一个删去种数的最大值就好了
前k 个数有多少种数怎么算?将所有数放到set里会自动去重,算set的大小就可以了
//-------------------------代码---------------------------- //#define int llconst int N = 1e5+10;int n,m;int a[N];void solve(){ cin>>n; int mx = 0; mapmp; set q; fo(i,1,n) { cin>>a[i]; mp[a[i]] ++ ; if(i >= 2 && mp[a[i]] >= 2 && a[i-1] != a[i]) mx = max(int(q.size()),mx); if(i >= 2 && a[i] < a[i-1]) mx = max((int)q.size(),mx); q.insert(a[i]); } cout< >n,n)// while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve();// {solve(); } return 0;} /*样例区 */ //------------------------------------------------------------
E1:(easy版) lcm的性质:必定是最大的数的倍数,数据范围一眼做法
题意:多组询问。lcm(i,j,k) >= i + j + k,问l 到 r 之间有多少满足条件的。l ,r <= 2e5。t <= 10
有一个性质:l 和 r 都是 1e5级别的,搜索三元组爆搜 要 n ^3,稍微优化:n^2 很难到 nlogn或者 n根号n。这里一眼可以确定要筛出某些数,在筛出来的数里搜了。
[l,r] 区间内三元组的数目是 组合数Cn3,就等于 len * (len - 1) * (len - 2) / 6
对于lcm(i,j,k) >= i + j + k,并不好直接判断,将大于等于号改成小于号:lcm(i,j,k) < i + j + k 。然后从最共的三元组数量找出满足条件的三元组数量即可
假设i,j,k中最大的数是 k ,那 lcm = 2 * k 或者 k 才满足条件 :比i + j + k 小。如果是 3k 的话 肯定要比 i + j + k 大
如果 lcm == k 。那肯定满足条件,三元组总数 - 1
如果 lcm == 2 * k 。那肯定是 k % i != 0 && k % j != 0。如果 满足 2 * k < i + j + k 也满足条件,三元组总数 - 1
只要枚举 所有 的2 * k ,并且找出它的因子 i ,j ,剪枝即可
ps:
1.lcm == 2 * k,如果 第二大的数 比 最大的数 的一半还小,那肯定不满足条件,可以减少对第一个数的搜索
2.找出每个数的因子是 o(n根号n)
//-------------------------代码----------------------------//#define int llconst int N = 4e5+10;int n,m;Vg[N];void solve(){// cin>>n>>m; int l,r;cin>>l>>r; int len = r - l + 1;; ll res = 1ll * len * (len - 1) * (len - 2) / 6; for(int i = l + 2;i<=r;i++) { V v; for(auto x:g[2*i]) { if(x < l) continue; if(i % x && x * 2 <= i) continue;//如果不是 i 的因子,说明它是 2 * i 的因子 ,要满足 lcm(i,j,k) < i + j + k 那它的大小至少要是 i 的一半, if(x >= i) break; for(auto y : g[2*i]) { if(y < l) continue; if(y >= x) break; if(i % x || i % y ) res -= 2 * i < x + y + i;//如果lcm = 2 * k,就要判断 else res -- ; //lcm = k,直接减 } } }}void main_init() { fo(i,1,200000) { for(int j = i;j<=400000;j+=i) { g[j].pb(i); } }}signed main(){ AC();clapping();TLE; cout< >n,n)// while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve();// {solve(); } return 0;}/*样例区*///------------------------------------------------------------
E2:hard版(t <= 1e5)树状数组+离线算法
我们把所有的循环 l 和 r 以及它是第几个询问,装进结构体
枚举[1,i] 以 r 为关键词,所有的 l 都是已经被计算过的
当枚举到当前询问的 r 的时候,l 就是一个特征值,不同的l 答案不一样
所以我们把所有的 i j k 的权值放入到最小的数 i 里,
ans[id] -= sum - query( l - 1)
//-------------------------代码----------------------------#define int llconst int N = 4e5+10;int n,m;Vv[N];V q[N];int tr[N];void add(int x,int v) { for(int i = x;i >n>>m; int t;cin>>t;fo(i,1,t) { int l,r;cin>>l>>r; q[r].pb({l,i});int len = r - l + 1; ans[i] = len * (len - 1) * (len - 2) / 6 ; } int sum = 0; for(int i = 1;i<=200000;i++) { for(auto x:v[i * 2]) { if(x >= i) break; if((i % x) && x * 2 <= i) continue; for(int y:v[i * 2]) { if(y >= x) break; if(i % x || i % y) { if(x + y + i > 2 * i) {sum ++ ;add(y,1); } } else { sum ++ ;add(y,1); } } } for(auto it : q[i]) { int l = it.first,id = it.second; ans[id] -= sum - qq(l-1); } } fo(i,1,t) { cout< >n,n)// while(cin>>n>>m,n,m)// int t;cin>>t;while(t -- ) solve();// {solve(); } return 0;}/*样例区*///------------------------------------------------------------
2. 本站积分货币获取途径以及用途的解读,想在本站混的好,请务必认真阅读!
3. 本站强烈打击盗版/破解等有损他人权益和违法作为,请各位会员支持正版!
4. 编程技术 > Codeforces 第 813 轮(第 2 部分)A - E2