洛谷刷题（普及-）：车站、拼数、Cantor 表、回文数、进制转换

记录洛谷刷题的过程qaq

---

[NOIP1998 提高组] 车站

题目描述

火车从始发站（称为第 $1$ 站）开出，在始发站上车的人数为 $a$，然后到达第 $2$ 站，在第 $2$ 站有人上、下车，但上、下车的人数相同，因此在第 $2$ 站开出时（即在到达第 $3$ 站之前）车上的人数保持为 $a$ 人。从第 $3$ 站起（包括第 $3$ 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 $(n-1)$ 站），都满足此规律。现给出的条件是：共有 $n$ 个车站，始发站上车的人数为 $a$ ，最后一站下车的人数是 $m$（全部下车）。试问 $x$ 站开出时车上的人数是多少？

输入格式

输入只有一行四个整数，分别表示始发站上车人数 $a$，车站数 $n$，终点站下车人数 $m$ 和所求的站点编号 $x$。

输出格式

输出一行一个整数表示答案：从 $x$ 站开出时车上的人数。

样例 #1

样例输入 #1

5 7 32 4
1

样例输出 #1

13
1

提示

对于全部的测试点，保证 $1\le a\le 20$，$1\le x\le n\le 20$，$1\le m\le 2\times 10^4$。

代码如下

#include
typedef long  long ll;
ll a,n,m,x,i,j,k,a1,a2,suma,sumb,sum,t,s;
int main(){
	while(scanf("%lld%lld%lld%lld",&a,&n,&m,&x)!=EOF){
		if(x==1||x==2)//由于当x=1或2或n是无需递推s，直接输出结果即可。
		{
			printf("%lld\n",a);
	 		return 0;
		}
		else if(x==3)
		{
			printf("%lld\n",2*a);
			return 0;
		}
		else if(x==n)
		{
			printf("%lld\n",m);
			return 0;
		}
		a1=1,a2=1,suma=0;
		for(i=1;i<=n-4;i++)//对于3
		{
			suma+=a1;
			sumb=suma-a1;
			t=a2,a2=a2+a1,a1=t;
		}
		s=(m-2*a-sumb*a)/suma;//suma*s+sumb*a+2*a=m  通过已知量suma、sumb、a求解s（第二
		a1=1,a2=1,suma=0;                                            //车站下车人数）
		for(i=1;i<=x-3;i++)//再求解当x时的suma和sumb
		{
			suma+=a1;
			sumb=suma-a1;
			t=a2,a2=a2+a1,a1=t;
		}
		printf("%lld\n",2*a+a*sumb+s*suma);//求解对应车站的人数
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

[NOIP1998 提高组] 拼数

题目描述

设有 $n$ 个正整数 $a_1\dots a_n$，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 $n$。

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$。

输出格式

一个正整数，表示最大的整数

样例 #1

样例输入 #1

3
13 312 343
1
2

样例输出 #1

34331213
1

样例 #2

样例输入 #2

4
7 13 4 246
1
2

样例输出 #2

7424613
1

提示

对于全部的测试点，保证 $1\le n\le 20$，$1\le a_i\le 10^9$。

代码如下：

#include
#include//数学函数库
#include//字符串处理函数库
struct shu
{
    char zifu[20];
}stu[25];

int compare(char list1[],char list2[])//自定义比较函数，注意与c++不同的是，即使结构体中的数组，也可用普通数组传递
{
    int i=0,j=0,flag=0,k1,k2;
    char a[50],b[50];
    strcpy(a,list1);//避免原数组受影响
    strcpy(b,list2);
    k1=strlen(a);k2=strlen(b);//字符串长度函数
    if(k1>k2)//先将两个字符串变成一样长，短的循环一下，到两个等长为止
        {
            while(k1>strlen(b))
            {
                strcat(b,b);//字符串连接函数
            }
            b[k1]='\0';
        }
    else if(k1<k2)
        {
            while(k2>strlen(a))
            {
                strcat(a,a);
            }
            a[k2]='\0';
        }
        //下面可以直接利用strcmp(a,b)比较，在此写出自定义的字符串的比较函数
        flag=strcmp(a,b);
    /*等价于：
    while((a[i]!='\0')||(b[j]!='\0'))//此时已经等长
    {
        if(a[i]==b[j]) {i++;j++;continue;}
        else
        {
            flag=a[i]>b[j]? 1:-1;
            break;
        }
    }
    */
    return flag;//大为1，小为-1，相等为0
}
int main()
{
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF){
	    for(i=1;i<=n;i++)
	    {
	        scanf("%s",stu[i].zifu);
	    }
	    for(i=1;i<n;i++)//经典的选择排序：
	    {
	        k=i;
	        for(j=i+1;j<=n;j++)
	        {
	            if(compare(stu[j].zifu,stu[k].zifu)>0) k=j;
	        }
	        if(k!=i)
	        {
	            strcpy(stu[0].zifu,stu[i].zifu);//字符串复制函数（会掩盖原先数组）
	            strcpy(stu[i].zifu,stu[k].zifu);
	            strcpy(stu[k].zifu,stu[0].zifu);
	        }
	    }
	    for(i=1;i<=n;i++)
	        printf("%s",stu[i].zifu);//依次输出，不必连接到一起，防止过长超出范围
	        printf("\n");
	}
	    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

[NOIP1999 普及组] Cantor 表

题目描述

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

$1/1$ , $1/2$ , $1/3$ , $1/4$, $1/5$, …

$2/1$, $2/2$ , $2/3$, $2/4$, …

$3/1$ , $3/2$, $3/3$, …

$4/1$, $4/2$, …

$5/1$, …

…

我们以 Z 字形给上表的每一项编号。第一项是 $1/1$，然后是 $1/2$，$2/1$，$3/1$，$2/2$，…

输入格式

整数$N$（$1\le N\le 10^7$）。

输出格式

表中的第 $N$ 项。

样例 #1

样例输入 #1

7
1

样例输出 #1

1/4
1

代码如下：

#include

int main()
{
    int n,k,s;            
    while(scanf("%d",&n) == 1)
    {    
        k=0;
        s=0;
        while(s<n)        
        {
            k++;
            s+=k;
        }
        if(k%2==1)        
            printf("%d/%d\n",s-n+1,k+n-s);    
        else
            printf("%d/%d\n",k+n-s,s-n+1);    
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

[NOIP1999 普及组] 回文数

题目描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个十进制数 $56$，将 $56$ 加 $65$（即把 $56$ 从右向左读），得到 $121$ 是一个回文数。

又如：对于十进制数 $87$：

STEP1：$87+78=165$
STEP2：$165+561=726$
STEP3：$726+627=1353$
STEP4：$1353+3531=4884$

在这里的一步是指进行了一次 $N$ 进制的加法，上例最少用了 $4$ 步得到回文数 $4884$。

写一个程序，给定一个 $N$（$2\le N\le 10$ 或 $N=16$）进制数 $M$（$100$ 位之内），求最少经过几步可以得到回文数。如果在 $30$ 步以内（包含 $30$ 步）不可能得到回文数，则输出 Impossible!。

输入格式

两行，分别是 $N$，$M$。

输出格式

如果能在 $30$ 步以内得到回文数，输出格式形如 STEP=ans，其中 $\text{ans}$ 为最少得到回文数的步数。

否则输出 Impossible!。

样例 #1

样例输入 #1

10
87
1
2

样例输出 #1

STEP=4
1

代码如下：

#include
#include
#include
#include 


int n, q[1000001], l, w[1000001], ans;
char s[1001];
void init() 
{
	int j = 0;
	for(int i = strlen(s) - 1; i >= 0 ; i--) 
	{
		if(s[i] >= '0' && s[i] <= '9') 
		{
			q[++j] = s[i] - '0';
		}
		else 
		{
			q[++j] = s[i] - 'A' + 10;
		} 
	}
}
void add(int a[], int b[]) 
{
	for(int i = 1; i <= l; i++)
	{
		a[i] += b[i];
		a[i + 1] += a[i] / n; 
		a[i] %= n;
	}
	if(a[l + 1] > 0) 
	{
		l++; 
	}
}
int f(int a[]) 
{
	int ln = l;
	int i = 1;
	int j = l;
	while(ln--)
	{
		if(ln < l / 2) 
		{
			break;
		}
		if(a[i] != a[j])
		{
			return 0; 
		}
		i++;
		j--;
	}
	return 1;
}
void turn(int a[]) 
{
	int j = 0;
	for(int i = l; i >= 1; i--) 
	{
		w[++j] = a[i]; 
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%s",&s);
	init(); 
	l = strlen(s);
	while(!f(q)) 
	{
		turn(q);
		add(q, w); 
		ans++;
		if(ans > 30) 
		{
			break;
		}
	}
	if(ans > 30)
	{
		printf("Impossible!"); 
	}
	else
	{
		printf("STEP=%d", ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

[NOIP2000 提高组] 进制转换

题目描述

我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所处位置为指数,以 $10$ 为底数的幂之和的形式。例如 $123$ 可表示为 $1\times 10^2+2\times 10^1+3\times 10^0$ 这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数,以 $2$ 为底数的幂之和的形式。

一般说来，任何一个正整数 $R$ 或一个负整数 $-R$ 都可以被选来作为一个数制系统的基数。如果是以 $R$ 或 $-R$ 为基数,则需要用到的数码为 $0,1,....R-1$。

例如当 $R=7$ 时,所需用到的数码是 $0,1,2,3,4,5,6$，这与其是 $R$ 或 $-R$ 无关。如果作为基数的数绝对值超过 $10$,则为了表示这些数码，通常使用英文字母来表示那些大于 $9$ 的数码。例如对 $16$ 进制数来说,用 $A$ 表示 $10$,用 $B$ 表示 $11$，用 $C$ 表示 $12$，以此类推。

在负进制数中是用 $-R $ 作为基数，例如 $-15$（十进制）相当于 $110001$ （$-2$进制），并且它可以被表示为 $2$ 的幂级数的和数：

$$110001=1\times (-2{)}^5+1\times (-2{)}^4+0\times (-2{)}^3+0\times (-2{)}^2+0\times (-2{)}^1+1\times (-2{)}^0$$

设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数。

输入格式

输入的每行有两个输入数据。

第一个是十进制数 $n$。
第二个是负进制数的基数 $-R$。

输出格式

输出此负进制数及其基数，若此基数超过 $10$，则参照 $16$ 进制的方式处理。

样例 #1

样例输入 #1

30000 -2
1

样例输出 #1

30000=11011010101110000(base-2)
1

样例 #2

样例输入 #2

-20000 -2
1

样例输出 #2

-20000=1111011000100000(base-2)
1

样例 #3

样例输入 #3

28800 -16
1

样例输出 #3

28800=19180(base-16)
1

样例 #4

样例输入 #4

-25000 -16
1

样例输出 #4

-25000=7FB8(base-16)
1

提示

【数据范围】
对于 $100\%$ 的数据，$-20\le R\le -2$，$|n|\le 37336$。

NOIp2000提高组第一题

代码如下：

#include
#include
#include
#include 


int change(int n,int b,char c[])
{
    int i=0,k;                                                                                                                                                   
    while(n!=0)
    {
        k=n%b;
        n/=b;
        if(k<0)
        {
        	k-=b;
        	n+=1;
        }//这里是负进制的重点
        if(k>9)
        	c[i] = (char)(k-10+'A');
        else 
        	c[i] = (char)(k+'0');
        i++;
    }
    return i-1;
}
int main()
{
    int a,n,i;
    char b[40];
    scanf("%d %d",&a,&n);
    printf("%d=",a);
    if(a==0)printf("0");
    for(i=change(a,n,b);i>=0;i--)
    	printf("%c",b[i]);
    printf("(base%d)",n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37