当前位置: 首页 > news >正文

CF1408F Two Different

CF1408F Two Different

挺好的一道思维题。

手玩几个例子之后发现以下性质:

1、直接变的话,只能同时把 \(2^k\) 个数变成一样的,次数大概是 \(2^{k - 1} \times k\)

2、零散的小堆可以向大堆借数。(初始值就是纯纯的干扰条件。。。)

3、考虑把性质 \(2\) 推广到极致:对于任意一个 \(n \in [2^k, 2^{k + 1})\),只需要先对前 \(2^k\) 处理一遍,再对后 \(2^k\) 处理一遍即可。具体的处理方法的话,找找下标规律就可以了(分治也可以)。估算一下操作次数不超过 \(2 \times (2 ^ {13} \times 13) = 212,992\)

时间复杂度 \(O(2n \log n)​\)

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l); i <= (r); ++ i)
#define G(i,r,l) for(int i(r); i >= (l); -- i)
using namespace std;
using ll = long long;
const int N = 3e4;
const int Q = 6e5;
int n, q;
int ans[Q][2];
void insert(int x, int y){++ q;ans[q][0] = x;ans[q][1] = y; 
}
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;int m = __lg(n) / __lg(2), r = 1 << m;F(i, 0, m - 1){int t = 1 << (i + 1);for(int j = 1; j <= r; j += t){F(k, j, j + t / 2 - 1){insert(k, k + t / 2);}}}int delta = n - r;if(delta == 0){cout << q << '\n';F(i, 1, q) cout << ans[i][0] << ' ' << ans[i][1] << '\n';}else{cout << q * 2 << '\n';F(i, 1, q) cout << ans[i][0] << ' ' << ans[i][1] << '\n';F(i, 1, q) cout << ans[i][0] + delta << ' ' << ans[i][1] + delta << '\n';}return fflush(0), 0;
}
http://www.hskmm.com/?act=detail&tid=24358

相关文章:

  • 数据结构 - 字典树 Trie
  • 激活函数实现
  • 漏洞赏金入门指南:从零开始的实战方法论
  • PMON failed to acquire latch 的报错及sqlplus / as sysdba 无法连接 - 详解
  • 2025CSP-S模拟赛58 比赛总结
  • 精读C++设计模式20 —— 结构型设计模式:桥接模式 - 详解
  • 用纯.NET开发并制作一个智能桌面机器人(六):使用.NET开发一个跨平台功能完善的小智AI客户端
  • 2025/10/4 总结
  • Qt处理Windows平板上摄像头
  • 你必须知道的TCP和UDP核心区别,快速搞懂这两大协议!
  • [swift 外部干涉法 extension]
  • 2025国庆Day3
  • 量子迁移计划启动:应对未来密码学挑战
  • HPE SPP 2025.09.00.00 - HPE 服务器固件、驱动程序和系统软件包
  • 详细介绍:Linux字符设备驱动开发全攻略
  • sql注入和xss漏洞
  • 数学 trick
  • 完整教程:精读C++20设计模式——行为型设计模式:解释器模式
  • js疑惑
  • 关于我
  • 20251004国庆模拟4
  • 珂朵莉树 ODT
  • 2025多校CSP模拟赛2
  • 详细介绍:深入了解linux网络—— 基于UDP实现翻译和聊天功能
  • Rewind: Codeforces Round 1055 (Div.1+Div.2)
  • 10.4模拟赛总结
  • 01.linux基础
  • 英语完形填空
  • 2025整体橱柜厂家TOP企业品牌推荐排行榜,云南昆明整体橱柜全瓷砖,开放式厨房,经济型,一站式无烟柴火灶,嵌入式,智能,多功能,全屋无烟柴火灶整体橱柜公司推荐
  • Centos7安装mysql8