首页 > 试题广场 >

不一样的逆序数

[编程题]不一样的逆序数

热度指数：2365 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团最近对逆序数（将一个数字逐位逆序，例如1234的逆序数为4321，1100的逆序数为11）特别感兴趣，但是又觉得普通的逆序数问题有点太乏味了。

于是他想出了一个新的定义：如果一个数的4倍恰好是它的逆序数，那么称这两个数是新定义下的逆序对。

接下来给定一正整数n，问：不超过n的正整数中有多少对新定义下的逆序对？

输入描述:

单组输入。

输入一个正整数n，n<1e7。

输出描述:

第一行输出在不超过n的前提下有多少对逆序数，接下来每一行输出一对逆序数，以空格分隔。如果有多组逆序数，按照第一个数升序输出。

如果没有一对逆序数则直接输出0即可。

示例1

输入

输出

1
2178 8712

算法知识视频讲解

啊坡糍嘚

n=int(input())
s=0
mylist=[]
for m in range(1,int(n/4+1)):
m=str(m)
m2=int(m[-1::-1]) #逆序数
m=int(m)
if m2==4*m:
s+=1
mylist.append(m)
mylist.append(m2)
if s==0:
print(0)
else:
print(s)
for i in range(0,len(mylist),2):

print(mylist[i],mylist[i+1],sep=' ')

给用python的兄弟们做下参考，看大佬们都用java等。我看不懂😥，希望对有和我一样用python的有点用

发表于 2021-03-28 15:29:56 回复(0)

pein531

很简单，第一对逆序对就是2178和8712，从它开始往n遍历，检查每个数的4倍是否是它的逆序数。但需要注意的是，对于某个数num，如果它的4倍大于n了，那即使它能和它的4倍组成逆序对也不符合题意，因此我们的遍历不用到n，只需要到n/4即可。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        if(n < 2178){
            System.out.println(0);
        }else{
            int num = 2178;
            int count = 0;
            ArrayList<String> res = new ArrayList<>();
            while(num <= n / 4){
                int revNum = reverse(num);
                if(4*num == revNum){
                    count ++;
                    res.add(num + " " + revNum);
                }
                num ++;
            }
            System.out.println(count);
            for(int i = 0; i < res.size(); i++)
                System.out.println(res.get(i));
        }
    }
    // 对数字num进行逆序
    private static int reverse(int num){
        int res = 0;
        while(num > 0){
            res = res*10 + num%10;
            num /= 10;
        }
        return res;
    }
}

发表于 2021-03-01 21:15:35 回复(0)

苦逼的90后

用了一波函数来实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine().trim())/4;
        List<int[]> list=new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            int ren=Integer.parseInt(new StringBuilder().append(i).reverse().toString());
            if (i*4==ren){
                list.add(new int[]{i,ren});
            }
        }
        System.out.println(list.size());
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i)[0]+" "+list.get(i)[1]);
        }
    }
}

发表于 2021-06-06 17:46:09 回复(0)

Python

非得色

n = str(input())

x = 0
x4 = 0
arr = []

for i in range(int(n)):
    re = int(str(i)[::-1])
    if i*4 == re and i != 0:
        x = (str(i) + " " + str(re))
        arr.append(x)
    else:
        i += 1

ans = 0
for x in arr:
    ans = ans+1
    print(ans)
    print(arr[ans-1])

发表于 2023-03-23 18:47:04 回复(0)

三减一

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

int main() {
long n;
cin>>n;
int count=0;
vector<vector<int>> s;
for(long i=1;i<n;i++)
{
long a=i;
long ans=0;
while(a>0)
{

int p=a%10;
ans=ans*10+p;
a=a/10;
}
if(i*4==ans&&ans<=n){
count++;
vector<int> a;
a.push_back(i);
a.push_back(ans);
s.push_back(a);
}

}
cout<<count<<endl;
for(int i=0;i<s.size();i++)
{
for(int j=0;j<2;j++)
cout<<s[i][j]<<" ";

cout<<endl;
}



}
// 64 位输出请用 printf("%lld")

发表于 2023-03-13 00:13:31 回复(0)

牛客209749188号

链接：https://www.nowcoder.com/questionTerminal/b7536a2ffb1947e4930d12ece2f838b4?f=discussion
来源：牛客网

#include<bits/stdc++.h>
using namespace std;
vector<string> path;
bool check(int a,int b)
{
    string tmp1=to_string(a);
    string tmp2=to_string(b);
    while(tmp2.back()==' ')
        tmp2.pop_back();
    if(tmp1.size()!=tmp2.size())
        return false;
    int i=0,j=tmp1.size()-1;
    while(i<tmp1.size())
    {
        if(tmp1[i]!=tmp2[j])
            return false;
        i++,j--;
    }
    path.push_back(tmp1+' '+tmp2);
    return true;
}
    
int main()
{
    int n=0;
    cin>>n;
    if(n<8712)
    {
        cout<<"0"<<endl;
        return 0;
    }
    int res=0;
    for(int i=2178;i<=n;++i)
    {
        if(4*i<=n &&check(i,4*i))
        {
            res++;
        }
    }
    cout<<res<<endl;
    for(auto&s:path)
        cout<<s<<endl;
   return 0;
}

发表于 2022-04-01 17:06:50 回复(0)

代码需要写注释？

这题是找规律题，其实很好推，分头想，如果要想满足逆序对，假设i为首个数则i*4<=9必须的
所以首只能是1-2同如果首是1那么尾部就是4，但是4*4=16无法往前推出1，所以只能是2，那么同理
可以推出尾部只能是8，一次可推出第二位一定是1倒数第二位一定是7，那么中间位一定是9，只要满足
情况小于n则一定是中间插入9即可，就是个数学找规律题


import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        StringBuilder s = new StringBuilder("2178");
        LinkedHashMap<String,String> m = new LinkedHashMap<>();
        while (n>=Integer.parseInt(new StringBuilder(s).reverse().toString())){
            m.put(s.toString(),new StringBuilder(s).reverse().toString());
            s.insert(2,"9");
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(m.size()));
        if(m.size()==0){
            bw.flush();return;
        }
        bw.newLine();
        for (String s1 : m.keySet()) {
            bw.write(s1+" "+m.get(s1));
            bw.newLine();
        }
        bw.flush();
    }
}

发表于 2022-03-25 21:14:14 回复(0)

不投降

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n < 8712) System.out.println(0);
        else{
            if(n <= 10000){
                System.out.println(1);
                System.out.println(2178 + " " + 8712);
            }
            else{
                int index = 1;
                List<String> ans = new ArrayList<>();
                ans.add("2178");
                ans.add("8712");
                //System.out.println(1);
                //System.out.println(2178 + " " + 8712);
                for(int i = 2501;i <= n / 4;i++){
                    String s1 = String.valueOf(i);
                    String s2 = String.valueOf(i * 4);
                    StringBuffer buffer = new StringBuffer(s1);
                    String s3 = buffer.reverse().toString();
                    if(s3.equals(s2)){
                        index++;
                        ans.add(s1);
                        ans.add(s2);
                    }
                }
                System.out.println(index);
                for(int i = 0;i < ans.size();i++){
                    System.out.print(Integer.valueOf(ans.get(i)) + " ");
                    if(i % 2 == 1) System.out.println();
                }
            }

        }
    }
}

发表于 2022-03-24 22:29:12 回复(0)

Python

Ivan_2021

n = int(input())
ans = []
for num1 in range(2178, int(n/4)+1):
    num2 = int(str(num1)[::-1])
    if num1*4 == num2:
        ans.append(num1)
print(len(ans))
for i in ans:
    print(i, i*4)

一道奇怪的题。。。。

发表于 2021-09-29 22:08:53 回复(0)

C/C++

liangchao_jiezi

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    long long x;
    cin>>x;
    vector<long long> vec;
    for(long long i=1;i<=x/4;i++){
        string s1=to_string(i);
        string s2=to_string(4*i);
        reverse(s2.begin(),s2.end());
        if(s1==s2){
            vec.push_back(i);
            vec.push_back(4*i);
        }
    }
    if(vec.size()==0) cout<<0;
    else{
        cout<<vec.size()/2<<endl;
        for(int i=0;i<vec.size();i+=2){
            cout<<vec[i]<<" "<<vec[i+1]<<endl;
        }
    }
}

编辑于 2021-08-14 17:20:50 回复(0)

hit_zt

正经代码我就不放了，放个投机取巧的答案：

可以证明：87(n个9)12 = 21(n个9)78*4

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        int res = 0;
        if(num>8711&&num<87912){
            res=1;
            sb.append(2178 +" "+ 8712 + "\n");
        }
        else if(num>87911 && num<879912){
            res=2;
            sb.append(2178 +" "+ 8712 + "\n");
            sb.append(21978 +" "+ 87912 + "\n");
        }
        else if(num>879911 && num<8799912){
            res=3;
            sb.append(2178 +" "+ 8712 + "\n");
            sb.append(21978 +" "+ 87912 + "\n");
            sb.append(219978 +" "+ 879912 + "\n");
        }
        else if(num>8799911 && num<87999912){
            res=4;
            sb.append(2178 +" "+ 8712 + "\n");
            sb.append(21978 +" "+ 87912 + "\n");
            sb.append(219978 +" "+ 879912 + "\n");
            sb.append(2199978 +" "+ 8799912 + "\n");
        }
        System.out.println(res);
        System.out.println(sb.toString());
    }
}

发表于 2021-04-03 17:45:41 回复(0)

不偷不抢安度因_

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    if (n < 2178) {
        cout << 0;
        return 0;
    } else if (n < 10001) {
        cout << 1 << '\n' << "2178 8712" << endl;
        return 0;
    }
    vector<pair<int, int>> res{{2178, 8712}};
    for (int i = 10002; i <= n / 4; i += 4) {
        string a = to_string(i);
        string b = to_string(i * 4);
        reverse(a.begin(), a.end());
        if (a == b) {
            res.push_back({i, i * 4});
        }
    }
    int len = res.size();
    cout << len << '\n';
    //cout << 2178 << ' ' << 8712;
    for (int i = 0; i < len; ++i) {
        cout << res[i].first << ' ' << res[i].second << '\n';
    }
     
    return 0;
}

发表于 2021-03-02 16:37:14 回复(0)