CodeForces - 1469D Ceil Divisions(构造+思维)

题目链接：点击查看

题目大意：给出一个初始时 a i = i a_i=i ai​=i 的序列，现在要求操作最多不超过 $n+5$ 次，使得最终序列有 $n-1$ 个 $1$ 和 $1$ 个 $2$，每次操作可以执行：
a x = ⌈ a x a y ⌉ a_x = \left\lceil \frac{a_x}{a_y} \right\rceil ax​=⌈ay​ax​​⌉

题目分析：正解是辗转求根号，因为 $n$ 的上限是 $2e5$，辗转求根号的话最多需要执行五次，对于每次 ( n , n ) (\sqrt{n},n) (n ​,n) 之间的所有数（注意是开区间），都执行操作 $(i,i+1)$，最后执行两次 ( n , n ) (n,\sqrt{n}) (n,n ​) 就可以将 ( n , n ] (\sqrt{n},n] (n ​,n] 内的数都变成 $1$ 了，然后 $i=1$ 和 $i=2$ 两个数不需要操作，所以最终的操作次数是 $n-2+5=n+3$ 次

比赛的时候想了一种难写的假算法，后来优化成了好写一点的真算法，不过还是比正解稍微麻烦一点，也来记录一下吧

一开始想的是，多出来的五次操作和 $2e5$ 的 $5$ 会不会有关系，于是将数列中的几个特殊的数字拿出来：$10,100,1000,10000,100000,n$ ，发现可以先将 $n$ 和 $100000$ 操作得到 $2$，然后整个数列从后往前依次操作最终得到 $10,10,10,10,10$，然后再从前往后依次操作得到 $1,1,1,1,10$ ，最后对剩下的 $10$ 和 $2$ 辗转操作就可以将 $10$ 最终变成 $1$ 了，有兴趣的朋友可以自己算一下复杂度，经过计算这样是 $n+6$ 次的

考虑优化呗，为什么会多出一次呢？因为最后是需要让 $10$ 对 $2$ 辗转相除，显然最后剩下的这个数是 $2$ 的幂次更优一些，所以之后又考虑了 $8$ 进制和 $16$ 进制，忽然发现 $16$ 进制竟然是可行的

思路还是同上，只不过优化了不少细节，比如拿出来的几个特殊数字是（从大到小排）： n , ⌈ n 16 ⌉ , ⌈ n 1 6 2 ⌉ , ⌈ n 1 6 3 ⌉ ⋯ n,\left\lceil \frac{n}{16} \right\rceil,\left\lceil \frac{n}{16^2} \right\rceil,\left\lceil \frac{n}{16^3} \right\rceil \cdots n,⌈16n​⌉,⌈162n​⌉,⌈163n​⌉⋯，只要保证最后一个数大于 $1$ 即可，因为如果等于 $1$ 的话就会死循环了。经过计算 $2e5$ 内这样最多同时会被选出 $5$ 个这样的数，同样是 $1$ 和 $2$ 无需操作，这样除去这五个数后，其他的数都变成 $1$ 只需要花费 $n-5-2=n-7$ 次操作

然后五个数相邻互除，最坏变成 $16,16,16,16,x$，这里的 $x$ 不一定是 $16$，但一定是一个小于等于 $16$ 的数，最坏会有五个数，此时需要花费四次操作数，目前用了 $n-7+4=n-3$ 次操作

然后还是固定第一个 $16$，其余的数都与这个数操作，变成 $16,1,1,1,1$，又花费了四次操作，现在用掉了 $n-3+4=n+1$ 次操作

最后让 $16$ 和 $2$ 辗转相除四次，将 $16$ 变成 $1$ 就好了，最终花费是 $n+1+4=n+5$ 次操作

我的思路很繁琐对吧，所以第二种解法是写给自己看的，所以说我到底是菜呢还是不菜呢？

代码：
$n+3$

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
template<typename T>
inline void read(T &x)
{T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f;
}
template<typename T>
inline void write(T x)
{if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');
}
const int inf=0x3f3f3f3f;
const int N=1e6+100;
bool ban[N];
int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;read(n);vector<pair<int,int>>ans;while(n>2){int t=ceil(sqrt(n));for(int i=t+1;i<n;i++) ans.emplace_back(i,i+1);ans.emplace_back(n,t),ans.emplace_back(n,t);n=t;}write(ans.size()),putchar('\n');for(auto it:ans) write(it.first),putchar(' '),write(it.second),putchar('\n');}return 0;
}

$n+5$

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
template<typename T>
inline void read(T &x)
{T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f;
}
template<typename T>
inline void write(T x)
{if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');
}
const int inf=0x3f3f3f3f;
const int N=1e6+100;
bool ban[N];
int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;read(n);memset(ban,false,n+5);vector<pair<int,int>>ans;vector<int>node;int temp=n;while(temp!=1){node.push_back(temp);ban[temp]=true;temp=(temp+15)/16;}for(int i=3;i<=n;i++) if(!ban[i]) ans.emplace_back(i,n);//多余的都变成1for(int i=1;i<(int)node.size();i++) ans.emplace_back(node[i-1],node[i]);//都变成16if(node.back()==1||node.back()==2) node.pop_back();//特判1和2不需要操作for(int i=(int)node.size()-1;i>0;i--) ans.emplace_back(node[i],node[i-1]);//除了n全变成1for(int i=1;i<=4;i++) ans.emplace_back(n,2);write(ans.size()),putchar('\n');for(auto it:ans) write(it.first),putchar(' '),write(it.second),putchar('\n');}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！