首页 > 试题广场 >

继续xxx定律

[编程题]继续xxx定律

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

当n为3时，我们在验证xxx定律的过程中会得到一个序列，3，5，8，4，2，1，将3称为关键数，5，8，4，2称为覆盖数。现在输入n个数字a[i]，根据关键数与覆盖数的理论，我们只需要验证其中部分数就可以确定所有数满足xxx定律，输出输入的n个数中的关键数。如果其中有多个关键数的话按照其输入顺序的逆序输出。

输入描述:

    输入数据包含多个用例,每个用例首先包含一个整数n，然后接下来一行有n个整数a[i]，其中: 1<=n<=500, 1<a[i]<=1000

输出描述:

    请计算并输出数组a中包含的关键数，并按照其输入顺序的逆序输出,每个用例输出占一行。

示例1

输入

输出

3
15 7 3
7 15 3

算法知识视频讲解

263保洁小妹

一个哈希表cover[MAX]，cover[i]表示i是否被覆盖。初始化所有的0~MAX的整数均未被覆盖，从输入的数中取一个数，然后将它递推到1，途经的数cover[x]置为true(或者1)。再取一个输入的数，做同样的事情（倘若这个数本身已经被覆盖那就不用做了，取下一个数继续），循环到处理完输入的数为止。

输出的时候逆序遍历输入的数据，如果某个数没被覆盖，那就输出它

#include <stdio.h>
#define N 500
#define MAX 100000

int NextNum(int x)
{
    if(x%2==0) return x/2;
    else return (3*x+1)/2;
}

int main()
{
    int n, buf[N];
    bool cover[MAX];//i是否被覆盖
    while(scanf("%d", &n)!=EOF)
    {
        if(n<=0) break;
        for(int i=0; i<MAX; i++) cover[i]=false;
        for(int i=0; i<n; i++)
        {
            scanf("%d", &buf[i]);
            int x=buf[i];
            if(cover[x]==false)
            {
                while(x!=1)
                {
                    x=NextNum(x);
                    cover[x]=true;
                }
            }
        }
        bool isFirst=true;
        for(int i=n-1; i>=0; i--)
        {
            if(cover[buf[i]]==false)
            {
                if(isFirst) isFirst=false;
                else printf(" ");
                printf("%d", buf[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

发表于 2018-03-09 00:41:02 回复(1)

牛客啊牛客

最终AC代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int i, t, n;
    vector<int> ans;
    map<int, bool> mp;
    while(~scanf("%d", &n) && n){
        ans.clear();
        mp.clear();
        for(i=0; i<n; i++){
            scanf("%d", &t);
            if(mp[t] == false){
                ans.push_back(t); //将关键字保留
                while(t != 1){
                    if(t & 1) t = 3 * t + 1;
                    t >>= 1;
                    mp[t] = true; //标记非关键数
                }
            }    
        }
        t = 0; //标记是否输出空格
        for(i=ans.size()-1; i>=0; i--){
            if(mp[ans[i]] == false){ //这里再加一层判断 因为可能关键数可能在后面出现 前面某个数被误认为是关键数了
                if(t == 1) printf(" ");
                else t = 1;
                printf("%d", ans[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

这个题目，我是看着晕了，因为此题还和前面的题有联系，要想做出此题，还得看前面某题的题干：xxx定律
然后，测试用例给得也很奇葩：我最先以为给出的第一个数字除了代表后面输入的个数，还要用它去验证xxx定律，最终刷选出没在验证过程中出现的数字，而且本地测试时还通过了~~~

后来，提交后，第一个测试用例就错了。

我的思路是：用map标记在验证某个数t时出现的覆盖数，然后后面只要不是覆盖数，就可以进行xxx定律的验证。如果是关键数，则用vector存储。此外，有一点容易忽视，可能某个覆盖数先于关键数出现，那么这个覆盖数也被存储在vector中了，此时可以在输出时，再判断一下当前数是否是覆盖数，不是，则输出。

编辑于 2020-04-28 17:42:18 回复(0)

C/C++

斯巴达12138

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,tmp;
while(cin>>n){
if(n==0) return 0;
vector<int> v;
    for(int i=0;i<n;++i){
        cin>>tmp;
        v.push_back(tmp);
    }
    vector<int> v_cp(v.begin(),v.end());
    for(int i=0;i<v.size();++i){
        tmp=v[i];
        while(tmp!=1){
            if(tmp%2==0) tmp/=2;
            else tmp=(3*tmp+1)/2;
            auto f=find(v_cp.begin(),v_cp.end(),tmp);
            if(f!=v_cp.end()) v_cp.erase(f);
        }
    }
    for(int i=v_cp.size()-1;i>=0;--i){
        cout<<v_cp[i];
        if(i!=0) cout<<" ";
    }
cout<<endl;
}

    return 0;
}

发表于 2020-03-06 11:39:31 回复(0)

vic.dong

first,对所有数生成覆盖数;

second,逆序遍历所有数，输出非覆盖数。

#include <iostream>
#include <string.h>
using namespace std;
#define MaxN 500
#define MaxV 100000

void generate_cover_num(int k, int cover_num[])
{
	k = (0 == k % 2) ? k /= 2 : (3 * k + 1) / 2;
	while (1 != k && !cover_num[k]) { cover_num[k] = 1; k = ((k % 2) ? (3 * k + 1) : k) / 2; }
}

int main()
{
	int n = 0, a = 0, cnt = 0, cover_num[MaxV] = { 0 }, digits_list[MaxN] = {0};
	while (cin >> n && 0 != n)
	{
		cnt = 0; memset(cover_num, 0, MaxV * sizeof(int));
		while (n-- && cin >> digits_list[cnt]) generate_cover_num(digits_list[cnt++], cover_num);
		while (cnt--) if (!cover_num[digits_list[cnt]]) { ++n; if (n > 0) cout << ' '; cout << digits_list[cnt]; } cout << endl;
	}
	return 0;
}

发表于 2020-02-20 12:38:45 回复(0)

C/C++

areyoukidding7

//看了大部分人都用数组记录，我用set记录xxx经过的值。最后，反向遍历输入的数组，无法再set中查到的就输出。
#include<iostream>
#include<set>
using namespace std;

set<int> st;
int a[1001];

void xxx(int a){
    while(a!=1){
        if(a%2==0){a/=2;}
        else {a=(a*3+1)/2;}
        st.insert(a);
    }
}

int main(){
    int n,i,j;
    while(cin>>n){
        if(n==0){break;}
        st.clear();
        for(i=0;i<n;++i){
            cin>>a[i];
            xxx(a[i]);
        }
        bool is_first=true;
        for(i=n-1;i>=0;--i){
            if(st.find(a[i])==st.end()){
                if(is_first){cout<<a[i];is_first=false;}
                else{cout<<" "<<a[i];}
            }
        }
        cout<<endl;
    }
    
    return 0;
}

发表于 2019-03-12 22:21:28 回复(0)

Hesetone

题目不算难，每个值算到等于1为止，沿途所有数覆盖，最后没有

被覆盖的数就是关键数，不过我很好奇的是，题意中，a[i]的范围

是小于1000，为什么开数组的时候不开到10万就会报越界错误，

有大佬知道这个边界数值为什么是10万吗？毕竟卡在90.91%好久。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxsize 100005
#define nextsize 505
typedef long long ll;
using namespace std;
int n,v[nextsize];
bool a[maxsize];
void f(int m) {
    if(a[m]) return;
    while(m!=1) {
        if(m&1) m=(3*m+1)/2;
        else m/=2;
        a[m]=true;
    }
}
int main(int argc, char const *argv[]) {
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt","r",stdin);
#endif
    while(cin>>n&&!cin.eof()) {
        if(!n) break;
        memset(v,0,nextsize*sizeof(int));
        memset(a,false,maxsize*sizeof(bool));
        for(int i=0; i<n; i++) {
            cin>>v[i];
            f(v[i]);
        }
        int first=0;
        for(int i=n-1; i>=0; i--) {
            if(!a[v[i]]) {
                if(!first) first=1;
                else cout<<" ";
                cout<<v[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

发表于 2019-02-14 17:21:49 回复(2)

不爱说话的C.C君

import java.util.*;


public class Main {
	public static void main(String[] args) {
		ArrayList<Integer> cover = new ArrayList<>();
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			cover = new ArrayList<>();
			int n = in.nextInt();
			if (n == 0)
				break;
			int[] num = new int[n];
			for (int i = 0; i < n; i++) {
				num[i] = in.nextInt();
			}
			for (int i = 0; i < n; i++) {
				int n1= num[i];
				while(n1!=1){
					if(n1%2==0){
						n1=n1/2;
						if(n1!=1){
							if(cover.indexOf(n1)==-1){
								cover.add(n1);
							}
						}
					}else{
						n1=(n1*3+1)/2;
						if(n1!=1){
							if(cover.indexOf(n1)==-1){
								cover.add(n1);
							}
						}
					}
				}
			}
			int[] re = new int[n];
			int size =0;
			for(int i=0;i<n;i++){
				if(cover.indexOf(num[i])==-1){
					re[size++] = num[i];
				}
			}
			for(int i=size-1;i>=0;i--){
				if(i!=0){
					System.out.print(re[i]+" ");
				}else{
					System.out.println(re[i]);
				}
			}
		}
	}
}

发表于 2017-08-22 14:10:57 回复(0)

在思考的伊泽瑞尔

题目描述说的什么几罢

发表于 2023-03-11 21:41:47 回复(0)

有力量的小刺猬上岸了

我怎么看不懂呢题

发表于 2024-03-10 19:08:42 回复(0)

Java

早豆浆晚牛奶

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            int n = Integer.parseInt(s);
            if (n==0)break;
            String[] str = br.readLine().split(" ");
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(str[i]);
            }
            HashSet<Integer> coverset = new HashSet<>();
            ArrayList<Integer> outlist = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int t = a[i];

                while (t != 1) {
                    if (t % 2 == 0) {
                        t = t / 2;
                    } else {
                        t = (t * 3 + 1) / 2;
                    }
                    coverset.add(t);
                }

            }

            for (int i = 0; i < n; i++) {
                if (!coverset.contains(a[i]))
                    outlist.add(a[i]);
            }

            for (int i = outlist.size() - 1; i >= 0; --i) {
                System.out.print(outlist.get(i) + " ");
            }
            System.out.println();

        }
    }

}

发表于 2021-04-06 14:18:24 回复(0)

薛定谔的猫e

#include <iostream>
#include <cstring>
using namespace std;
int arr[101000] = {0};
int main(){
    int n;
    while(cin >> n){
        if(n == 0) break;
        memset(arr,0,sizeof(arr));
        int *temp = new int[n];
        for(int i = 0;i < n;i++)
            cin >> temp[i];
        for(int i = 0;i < n;i++){
            if(arr[temp[i]] == 0){
                int ch = temp[i];
                while(ch != 1){
                    if(ch % 2 == 1){
                        ch = (ch * 3 + 1) / 2;
                        arr[ch] = 1;
                    }else{
                        ch /= 2;
                        arr[ch] = 1;
                    }
                }
            }
        }
        for(int i = n - 1;i >= 0;i--){
            if(arr[temp[i]] == 0)
                cout << temp[i] << " ";
        }
        cout << endl;
    }
}

发表于 2021-03-10 21:21:34 回复(0)

crystalsssssssssssssssss


#include <iostream>
using namespace std;
#include <map>
map<int,int> m;
int f[500];
int main(){
    int n,x;
    while(cin>>n){
        if(n==0)break;
        for(int i=n-1;i>=0;i--){
            cin>>x;
            f[i]=x;
        }
        for(int i=0;i<n;i++){
        	int c=f[i];
         while(c>1){
           if(c%2==0){c/=2;m[c]=1;}
           else {
               c=3*c+1;
               c/=2;
               m[c]=1;
           }
       }	
		} 
       for(int i=0;i<n;i++){
           if(m[f[i]]!=1)cout<<f[i]<<" ";
       }
        cout<<endl;
    }
    return 0;
}

编辑于 2021-02-10 00:32:19 回复(0)

全世界的街里

题目意思理解错了，吐了，一直以为只要判断n

// 对于一个数 n，如果是偶数，就把 n 砍掉一半；如果是奇数，把 n 变成 3*n+ 1 后砍掉一半，直到该数变为 1 为止。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6;
const int maxa = 510;
bool hashTable[maxn];//false为覆盖数, true为关建数 
int a[maxa];
void func(int N) {
	while(N != 1) {
		if(N % 2 == 0){
			N = N / 2;
			hashTable[N] = false;
		} else {
			N = (3 * N + 1) / 2;
			hashTable[N] = false;
		}
	}
}
int main() {
	int N;
	while(cin >> N) {
		if(N == 0) break;
		memset(hashTable, true, sizeof(hashTable));//先假设全为关建数 
		for(int i = 0; i < N; ++i) {
			cin >> a[i];
			func(a[i]);//划去覆盖数 
		}
		for(int i = N - 1; i >= 0; --i) {
			if(hashTable[a[i]] == true)
				cout << a[i] << " "; 
		}
		cout << endl;
	}
	return 0;
}

发表于 2021-02-09 22:34:43 回复(0)

灭绝蒙萌

使用map，灰常简单

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

map<int,int> M;

int main(){
	int n,i,temp,a[505];
	while(cin>>n){
		M.clear();
		for(i=0;i<n;i++)
			cin>>a[i];
		for(i=0;i<n;i++){
			temp=a[i];
			while(temp!=1){
				if(temp%2==0)
					temp/=2;
				else
					temp=(3*temp+1)/2;
				M[temp]++;
			}
		}
		for(i=n-1;i>=0;i--){
			if(M[a[i]]==0)
				cout<<a[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

发表于 2020-04-05 20:03:06 回复(0)

VirgilG72

原来coverd要开这么大数组，一开始只开了1000，后面在debug的时候，发现tmp会不断变大。。然后给3000，10000,20000，直到50000，才够。。。

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	while(cin>>n) {
		int a[510];
		bool coverd[50000];
		for(int i=0; i<n; i++) {
			cin>>a[i];
			
		}
		for(int i=0; i<50000; i++) {
		
			coverd[i]=false;
		}
		
		for(int i=0; i<n; i++) {
			int tmp=a[i];
			if(coverd[tmp]==false) {
				while(tmp!=1) {

					if(tmp%2==0) {

						tmp=tmp/2;
						if(coverd[tmp]==true) break;
						coverd[tmp]=true;

					} else {

						tmp=(3*tmp+1)/2;
						if(coverd[tmp]==true) break;
						coverd[tmp]=true;
					}
				}
			}

		}
//			for(int i=0;i<n;i++){
//				cout<<coverd[a[i]]<<" ";
//			}

		for(int i=n-1; i>=0; i--) {
			if(!coverd[a[i]])
				cout<<a[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

发表于 2020-03-25 21:46:01 回复(0)

找不到工作的菜鸟

解题思路：为每个数设置一个标志位，也保存在二维数组中。对每一个元素求他的覆盖数，若覆盖数在数组中，将相应的标志位改为1。最后数组中标志为0的就是关键数。

#include<iostream>
using namespace std;
int main(){
    int n,a[2][500];
    while(cin>>n&&n!=0){
        for(int i=0;i<n;i++) {
            cin>>a[0][i];//输入序列
            a[1][i]=0;//初始化
        }
        for(int i=0;i<n;i++){
            int x=a[0][i];
            while(x!=1){
                if(x%2==0){
                    x=x/2;
                    for(int j=0;j<n;j++){//将覆盖数的标志改为1
                        if(x==a[0][j]) {a[1][j]=1;}
                    }
                }
                else{
                    x=(3*x+1)/2;
                    for(int j=0;j<n;j++){//将覆盖数的标志改为1
                        if(x==a[0][j]) {a[1][j]=1;}
                    }
                }
            }
        }
        //cout<<endl;
        for(int i=n-1;i>=0;i--){
            if(a[1][i]==0) cout<<a[0][i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

发表于 2020-03-03 16:49:44 回复(0)

C/C++

Schwarzer

运行时间29ms,比较长，方法基于上一题的xxx定律。首先节省时间，

#include <iostream>
#include<cmath>
using namespace std;
class specialnum
{
public:
    int value;
    int tag;
};
int judge2(int n)
{
    float t = log(n)/log(2);
    if(t==int(t)) return 1;
    else return 0;
}
int judge(int n,int p)
{
    if(n == 1)
    {
        return 0;
    }
    while(true)
    {
        if(n%2 == 0)
        {
            n = n /2;
        }
        else
        {
            n = n*3+1;
            n = n /2;
        }
        if(n==p)
        {
            return 1;
        }
        if(n == 1)
        {
            break;
        }
    }
    return 0;
}
int main()
{
    int n = 0;
    while(cin>>n&&n!=0)
    {
        specialnum *numbers = new specialnum[n];
        int index = 0;
        for(int i = 0;i<n;i++)
        {
            int tmp;cin>>tmp;
            if(judge2(tmp)==0)
            {
                numbers[index].value = tmp;
                numbers[index].tag=0;
                index++;
            }
        }
        for(int h = 0;h<index;h++)
        {
            for(int q = 0;q<index;q++)
            {
                if(q!=h)
                {
                    if(judge(numbers[h].value, numbers[q].value))
                    {
                        numbers[q].tag = 1;
                    }
                }
            }
        }
        for(int m = index - 1;m>=0;m--)
        {
            if(numbers[m].tag==0)
            {
                cout<<numbers[m].value<<" ";
            }
        }
        cout<<endl;
    }
}

排除2的整数次方的数，剩下的数组成一个判断序列，包含数值和一个tag。然后对每个数和剩余的数判断剩余的数字是否构成此数的覆盖数，如果构成将tag标签改写为1，执行共n(n-1)次。反向输出tag不为1的数字即可。

发表于 2019-10-10 22:14:45 回复(0)

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        inp=list(map(int,input().strip().split(' ')))
        list1=[n]
        result1=[]
        result2=[]
        for i in inp:
            if i not in result1:
                while i!=1:
                    if i%2==0:
                        i=i//2
                        result1.append(i)
                    else:
                        i=(i*3+1)//2
                        result1.append(i)
        for i in inp:
            if i not in result1:
                result2.append(str(i))
        print(' '.join(result2[::-1]))
    except:
        break

发表于 2019-08-22 13:46:07 回复(0)

咖啡糖66

#include <iostream>
#include <map>

using namespace std;

const int N =1000;
int a[N]={0};
bool isKey[N];
void init(){
for(int i=0;i<N;i++){
a[i]=0;
isKey[i]=true;
}
}

int main()
{
int n;
while(cin>>n){
if(n==0) break;
init();
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
if(!isKey[i]) continue;
map<int,int>mp;
int temp = a[i];

while(temp!=1){
if(temp%2==0) temp/=2;
else temp = (3*temp + 1)/2;
mp[temp]=1;
}
for(int i=0;i<n;i++){
if( mp[ a[i] ]==1 ) isKey[i] = false;
}
}
for(int i=n-1;i>0;i--){
if(isKey[i]) cout<<a[i]<<" ";
}
if(isKey[0]) cout<<a[0];
}
return 0;
}

发表于 2019-06-30 15:47:39 回复(0)

上单

#include <cstring>
#include <iostream>
using namespace std;
#define N 1000

int main(){
    int n,a[N],i,tmp,j;
    while (cin >> n){
        for(i=0;i<n;i++){
            cin >> a[i];
        }
        for(i=0;i<n;++i){
            if(a[i]!=0){
                tmp = a[i];
                while(tmp!=1){
                    if(tmp%2) tmp = (tmp*3+1)/2;
                    else tmp/=2;
                    for(j=0;j<n;++j){
                        if(a[j]==tmp){
                            a[j]=0;///覆盖值
                        }
                    }
                }    
            }
        }
        for(i=n-1;i>=0;--i){///逆序
            if(a[i]!=0){
                cout << a[i] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

发表于 2019-03-20 14:37:11 回复(0)