首页 > 其他分享 >CSP历年复赛题-P1014 [NOIP1999 普及组] Cantor 表

CSP历年复赛题-P1014 [NOIP1999 普及组] Cantor 表

时间:2024-05-20 11:29:38浏览次数:23  
标签:cnt 题意 int P1014 枚举 Cantor NOIP1999

原题链接:https://www.luogu.com.cn/problem/P1014

题意解读:根据z字形遍历,求第n个数。

解题思路:

根据题意,遍历顺序如下图所示

观察得知,第i层的x/y的x+y = i + 1,并且

如果i是偶数,x从1开始枚举;如果i是奇数,x从i开始枚举

100分代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int i = 1;
    int cnt = 0;
    while(true)
    {
        if(i % 2 == 0)  //偶数从1/i开始枚举
        {
            for(int x = 1; x <= i; x++)
            {
                if(++cnt == n)
                {
                    cout << x << "/" << i + 1 - x;
                    return 0;
                }
            }
        }
        else //奇数从i/1开始枚举
        {
            for(int x = i; x >= 1; x--)
            {
                if(++cnt == n)
                {
                    cout << x << "/" << i + 1 - x;
                    return 0;
                }
            }
        }
        i++;
    }
}   

 

标签:cnt,题意,int,P1014,枚举,Cantor,NOIP1999
From: https://www.cnblogs.com/jcwy/p/18201527

相关文章

  • 洛谷题单指南-动态规划2-P1020 [NOIP1999 提高组] 导弹拦截
    原题链接:https://www.luogu.com.cn/problem/P1020题意解读:拦截系统发射导弹的高度依次不增,计算能拦截的最大导弹数以及需要几套拦截系统。解题思路:问题1:最多能拦截多少导弹?由于发射导弹高度不增,所以求一个最长不增子序列即可得到最大拦截数。方法一、O(n^2)做法:动态规划。采......
  • P1020 [NOIP1999 提高组] 导弹拦截
    链接:https://www.luogu.com.cn/problem/P1020这个题目一分为二:首先就是LIS:改下,改成最长不升子序列,复杂度:nlogn;然后用vector的贪心,复杂度:n^2(这里似乎可以二分降到nlogn,不过反正过了OwO!)被这个输入卡的好难受,建议用getline读取不确定的数题目:代码:#include<iostream>#incl......
  • SciTech-Mathmatics-RealAnalysis: Cantor-Schröder-Bernstein Theorem
    Cornell:https://www.cs.cornell.edu/courses/cs2800/2017fa/lectures/lec14-cantor.htmlUCLA:https://web.cs.ucla.edu/~palsberg/course/cs232/papers/bernstein.pdfhttps://artofproblemsolving.com/wiki/index.php/Schroeder-Bernstein_Theoremhttps://www.whitman.e......
  • SciTech-Mathmatics-Real Analysis-Cantor Set Theory + Bolzono-Weierstrass Theorem
    CantorSet,Priciple:1-1bi-directionalmappingtodeterminewhethertwosets(infiniteorfinite)AandBhavethesamesize.false:[0,1]~(0,+∞):闭区间[0,1]上全部的点作成的集合是不对等于\(Z^{+}\)正整数集上全部的点作成的集合。true:(0,1)~(......
  • P10149 [Ynoi1999] XM66F 题解
    分析考虑莫队。对于$a_i=k(l\lei\ler)$的下标集合$S_k$,当其加入一个新的下标$x$时,这个新下标对答案的贡献分两种情况。第一种,$x$最小。相邻从下标的间隔中产生的贡献是$\sum(|S_k|-i+1)\times(ans_{S_{k,i+1}}-ans_{S_{k,i}})$。画个图可以理解一下:第二中,$x$最......
  • P10141
    P10141题解正难则反正着,设\(dp(l,r)\)为合并出\([l,r]\)的概率,枚举大区间两端点合并(区间DP)复杂度\(O(n^4)\)反着,设\(dp(l,r)\)表示由\([1,n]\)分裂出\([l,r]\)的概率设大区间为\([i,j]\),中间点为\(k\)若\([i,k]>[k+1,j]\),\(dp(i,k)=\frac......
  • P10149 [Ynoi1999] XM66F题解
    题解首先,问题是静态的区间查询问题,一眼莫队。那么我们就需要考虑所需要维护的内容在区间扩增或者缩减时的变化如何快速维护。我们可以先写出对于区间\([l,r]\)来说,满足\(l\lei<j<k\ler\)的有序三元组\((i,j,k)\)数量的表达式,方便拆式子:\[\sum\limits_{i=l}^{r}......
  • 题解 LGP10144【[WC/CTS2024] 水镜】
    题解P10144【[WC/CTS2024]水镜】题目描述给定一个长度为\(n\)的正整数序列\(h_1,h_2,\cdots,h_n\),求满足以下所有条件的二元组\((u,v)\)的数量:\(1\leu<v\len\),且\(u,v\)为整数;存在一个正实数\(L\)以及一个长度为\((v-u+1)\)的序列\(r_u,r_{u+......
  • P10145 [WC/CTS2024] 线段树 题解
    Link纪念一下场切题。题意:给定一棵(分点不一定为中点)的线段树,给定若干个询问区间,问有多少个线段树上结点的集合,知道了这些结点对应的区间和就可以知道任何一个询问区间的和。从询问区间开始考虑。会发现可以把所有\(a_i\)分成若干个集合,只要知道每个集合的和就可以知道所有询......
  • 洛谷 P10145 [WC/CTS2024] 线段树 题解--zhengjun
    提供一种考场做法,在思路上和官方题解的差异蛮大的,虽然结果差不多。首先需要发现\([l,r)\)区间可以算出来的充要条件是:如果对于每个选中的节点\(u\),连无向边\((L_u,R_u)\),则当且仅当\(l\)和\(r\)连通时区间\([l,r)\)可以算出来。证明的话,用前缀和理解这些东西,分别考虑......