XTU oj 作业12

字数统计: 3.2k字   |   阅读时长≈ 15分

XTU-oj-作业12-2015年期末

这套题命名很有意思，A题题目是A开头，B题题目是B开头…这件事告诉我们要在痛苦中找寻美（手动狗头保命）。

A Alice and Bob

emmmmm,按照规律来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# include <stdio.h>

int main(){
    
    char A[10]; // 存储Alice的
    char B[10]; // 存储Bob的
    int K;
    scanf("%d",&K);
    while(K > 0){
        K--;
        scanf("%s",A);
        scanf("%s",B);
        if(A[0] == B[0])printf("Draw\n"); // 相同就平局
        else if(A[0] == 'r'&&B[0] == 's')printf("Alice\n");
        else if(A[0] == 'r'&&B[0] == 'p')printf("Bob\n");
        else if(A[0] == 's'&&B[0] == 'r')printf("Bob\n");
        else if(A[0] == 's'&&B[0] == 'p')printf("Alice\n");
        else if(A[0] == 'p'&&B[0] == 'r')printf("Alice\n");
        else if(A[0] == 'p'&&B[0] == 's')printf("Bob\n");
    }
    
    
    return 0;
}

B Buying Gifts

这道题目的话，就是按从小到大的顺序选择n个，但要注意选择的是差值最小的n个，那么肯定是在输入序列中连续的。那么我们先将输入的序列从小到大排列，然后以连续的n个数为一个序列的查找最小插值就好了。因为是差值相等选钱少，所以我们从后往前扫。

举个栗子:有10个要买5个，10个分别是19、13、12、11、10、9、7、5、4、3。我们先选择后五个9、7、5、4、3差值是6，然后我们在选10、9、7、5、4差值是6，然后选11、10、9、7、5差值是6，然后是12、11、10、9、7差值是5，然后13、12、11、10、9差值是4，然后19、13、12、11、10差值是9，故我们选择差值是4的。

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
#include<stdio.h>
int A[1001];

void down(int A[],int n);

int main(){
    int K;
    int i,j;
    scanf("%d",&K);
    while(K --){
        int n,m;
        int k;
        scanf("%d%d",&n,&m); // 输入
        for(i = 0; i < n; i ++){ // 输入序列
            scanf("%d",&k);
            A[i] = k;
        }
        down(A,n); // 排序
        int cnt = A[m - 1]-A[0]; // 初始的差值
        int p = 0; // 初始的选择位置
        int w; // 选中序列的差值
        for(i = 0; i + m - 1 < n; i ++){ // 开始查找
            w = A[i + m - 1] - A[i]; // 更新选中序列的差值
            if(w < cnt){
                cnt = w;
                p = i;
            }
        }
        int sum = 0; // 求和
        for(i = p; i < p + m; i ++){ // 求和
            sum = sum + A[i];
        }
        printf("%d %d\n",cnt,sum); // 输出
        for(i = 0; i < 1001; i ++){ // 初始化
            A[i] = 0;
        }
    }
}

void down(int A[],int n){ // 排序
    int i,j;
    int a;
    for(i = 0; i < n; i ++){
        for(j = 1; j < n -i; j ++){
            if(A[j - 1] > A[j]) {
                a = A[j-1];
                A[j-1] = A[j];
                A[j] = a;
            }
        }
    }
}

C Co-string

模拟一下查找的过程。详情看注释吧。

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
# include<stdio.h>
# include<string.h>
#define N 2011
char A[N];
int cnt[2]={0};//计数的数组
int main(){
    int i,j,l;
    int K;
    scanf("%d",&K);//样例个数
    while(K --){
        scanf("%s",A);
        int len = strlen(A);//数组的长度
        if(len%2 == 0){//如果数组长度为偶数
            int n = len/2;//数组长度的一半
            //printf("<==n==>%d\n",n);
            for(i = 1; i <= n; i ++){//“i”表示“co-string”字符串的一半长度
                for(l = 0; l < len; l ++){//“l”表示在哪个位置开始计数
                    cnt[0] = 0;
                    for(j = l; i+l < len&&j < i+l; j ++){//“j”表示下标，
                        if(A[j] == A[j + i]){
                                cnt[0] ++;
                        }
                        else{
                            cnt[0] = 0;//如果不相等也就说明在l为起点2*i长度的子字符串不满足题意所以之前所有的计数清零；
                            break;
                        }
                    }
                    if(cnt[0] > cnt[1]){
                        cnt[1] = cnt[0];
                    }
                }
            }
            printf("%d\n",2*cnt[1]);
        }
        else{
            int n = (len - 1)/2;
            for(i = 1; i <= n; i ++){
                for(l = 0; l < len; l ++){
                    cnt[0] = 0;
                    for(j = l; j < i+l&&j < len; j ++){
                        if(A[j] == A[j + i]) cnt[0] ++;
                        else{
                            cnt[0] = 0;
                            break;
                        }
                    }
                    if(cnt[0] > cnt[1]){
                        cnt[1] = cnt[0];
                    }
                }
            }
            printf("%d\n",2*cnt[1]);
        }
        for(i = 0; i < 2; i ++){
            cnt[i] = 0;
        }
    }
}

D Diamond

整体思路应该没问题，我稍微叙述一下我的代码吧。

分成了打印上下两部分，第一部分是第1行到第n行，第二部分是第n+1行到最后

有两个功能，第一个是输出x个空格(print1(x))，第二个是两个字符的对称输出。比如：’D’到’B’就是DCBCD

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
#include<stdio.h>
void print1(int n)
{
    for(int i  = 0; i < n; i++)
        printf(" ");
}
void print2(int n,int m)
{
    for(int i = 0; i < m; i++)
        printf("%c",'A'+n-i-1);
    for(int i = m-1; i > 0; i--)
        printf("%c",'A'+n-i);
    printf("\n");
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            print1(n-i-1);
            print2(n,i+1);
        }
        for(int i = n-2; i >= 0; i--)
        {
            print1(n-i-1);
            print2(n,i+1);
        }
    }
    return 0;
}

E Enquiry

对要搜索的队列开始搜索，如果如果发现不一样就加一。代码中用男女不同是每个元素相减，如果是同一性别就为0，不是就是7.

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
#include <stdio.h>
#include <string.h>

char C[10011]; // 记录队列
int a[1001][2]; // 记录每次查询的区间
int cnt[1001]; // 记录每次查找的数据
// 
int abs(int n){ // 取绝对值
    if(n < 0) return -n;
    else return n;
}

int main (){
    int n;
    int K;
    scanf("%d",&K);
    while(K --){
        int i,j;
        scanf("%s",C);
        scanf("%d",&n);
        int len = strlen(C); // 人数
        
        for(i = 0; i < n; i ++){ // 输入区间
            scanf("%d%d",&a[i][0],&a[i][1]);
        }
        
        for(i = 0; i < n; i ++){ // 开始搜索查找
            for(j = a[i][0]-1; j < a[i][1]-1; j ++){ // 在区间内查找
                int k = abs(C[j] - C[j +1]); // 每个元素做差，如果等于7说明不一样
                if(k == 7) cnt[i] ++; // 那就相邻不同加一
            }
            printf("%d\n",cnt[i]); // 输出
        }
        for(i = 0; i < n; i ++){ // 初始化
            cnt[i] = 0;
        }
    }
}

F Flawless Prime

模拟一下去最高位的过程，然后判断是不是素数就好，这里判断素数无需打表直接用暴力判断就好。注意前导零。

代码中我们用一个计数器cnt，如果每次去完最高位，满足没有前导零且是一个素数，那我们就将cnt++。最后如果计数器的值为n的位数-1就说明所有去高位的过程都满足上述两个条件，就输出Yes，否则输出No

注意：这里的n最大是10位需要开__int64。

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
#include <stdio.h>

int s(int n){//是否是素数 
    int i,j;
    if(n == 1) return 0; 
    for(i = 2; i*i <= n; i ++){
        if(n%i == 0) return 0;
    }
    return 1;
}

int ws(int n){//n有多少位 
    int cnt = 0;
    while(n > 0){
        n /= 10;
        cnt ++;
    }
    return cnt;
}

int nc(int n){//10的n次方 
    int cnt = 1;
    while(n > 0){
        cnt *= 10;
        n --;
    }
    return cnt;
}

int main(){
    int K;
    scanf("%d",&K);

    while(K --){

        __int64 n;
        scanf("%I64d",&n);
        
        int t = s(n); //是否是素数
        int W = ws(n);//判断有多少位 
        int w,l,l2,m;
        int cnt = 0;//计数 

        while(n > 0){
            
            w = ws(n);//w为n有多少位 
            l = nc(w-1);//10的w-1次 
            l2 = nc(w-2);//10的w-2次
            n = n%l;//n去掉最高位 
            t = s(n);//n现在是否为素数 
            m = n/l2;//n去掉最高位后是否有前导0 

            if(t&&m != 0) cnt++; // 如果是素数并且没有前导0，计数器加一
        }
        if(cnt == W-1)printf("Yes\n");//如果计数和起初n的位数-1相同说明是否则不是 
        else printf("No\n");
    }

    return 0;
}

G GCD

这道题中提到与6互素的个数。我们分析一下，6的因子是2和3，要和6互素也就是和6求公约数不能是2或3或6，也就是这个数不能被2或3或6整除。

我们之前接触过一道Alice and Bob的题目其中有提过一个数学知识，n与m取商得到的是1-n中能被m整除的个数。

应用这个知识点，再加上容斥原理（也就是取两个集合并集中元素的个数。举个例子，求集合A和集合B并集的元素个数，也就是|A|+|B|-|A∩B|）。对于这道题就是先求1到n中满足与6互素的个数，也就是n-(n中能被2整除的个数+n中能被3整除的个数-n中能被6整除的个数)。然后n到m中满足条件的个数就是用1到m的个数-（1到(n-1)的个数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>

int gcd(int n){
    int n1,n2,n3;
    int a;
    n1 = n/2;
    n2 = n/3;
    n3 = n/6;
    a = n - (n1 +n2 -n3);
    return a;
}

int main(){
    int K;
    scanf("%d",&K);
    int n,m;
    while(K --){
        scanf("%d%d",&n,&m);
        n = gcd(n-1);
        m = gcd(m);
        printf("%d\n",m - n);
    }
}

H Homework

这是oj里面我最爱的一道题，没有之一。它和我一同见证了4点钟的湘大（不要问我为啥起的那么早，因为我没睡。也不要觉得我好菜，自信点我就是很菜），这道题对于你们来说是一道平平无奇的第八题，但对于我来说是满满的成就感……

好了废话不多说了…

这道题目所设计的内容就是你们平时分作业的计算公式，也就是为什么我们会提醒你们早做题。

这道题思路，我们首先创建两个结构体，一个储存输入的数据(student)，一个储存最后要输出的数据(student2)。student里面有题号、学号、排名两个信息；student2里面有学号和排名（分数）两个信息。因为输入的数据是多条的所以我们用一个数组来储存多条信息，命名为all[]，输出也是命名为zcj[]。

然后将每一次的输入存到all里面，并将输入的排名转化为单题分数，每次输入完后更新zcj的数据，更新时如果学号在前面出现过就把成绩加到相应的分数，如果没出现过，就把学号填入zcj数组。

在所有数据输入完之后，我们进行排序操作，先按排名得分排序，然后算分，之后再将统一分数的按学号排序。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <math.h>

int pblem[222];

struct student {//输入时的结构体 
    int ProblemID;
    __int64 StudentID;
    int rank;
};

struct student2{//输出时的结构体 
    __int64 StudentID;
    int rank;
};

struct student all[111111];
struct student2 zcj[555];

void putout(struct student2 p);//输出函数
void swap(struct student2*p1,struct student2*p2);//交换函数；
void swap2(struct student2*p1,struct student2*p2);//交换函数；

int main(){
    int i = 0,j;
    int sn = 0;//记录有多少学生 
    int np = 1;//记录题目的个数
    while(scanf("%d%I64d%d",&all[i].ProblemID,&all[i].StudentID,&all[i].rank)!=EOF){
        int *r;//定义指针 指向每一个排名（rank）
        r  = &all[i].rank;//把排名换成积分 
        if(*r >= 1 && *r <= 12) *r = 32;
        else if(*r <= 24 && *r >= 13) *r = 16;
        else if(*r <= 48 && *r >= 25) *r = 8;
        else if(*r <= 96 && *r >= 49) *r = 4;
        else if(*r <= 192 && *r >= 97) *r = 2;
        else *r = 1;
        
        pblem[0] = all[0].ProblemID;
        
        sn ++;//记录有多少学生 
        np ++;//记录题目的个数 
        for(j = 0; j < np; j ++){//记录题号并计算多少道题 
            pblem[np] = all[i].ProblemID;
            if(all[i].ProblemID == pblem[j]){
                pblem[np] = 0;
                np --;
            }
        }
        zcj[sn].StudentID = all[i].StudentID;
        zcj[sn].rank = all[i].rank;
        for(j = 1; j < sn; j ++){//记录号并计算多少道题  
            if(all[i].StudentID == zcj[j].StudentID){
                zcj[j].rank = zcj[j].rank +all[i].rank;
                zcj[sn].StudentID = 0;
                sn --;
            }
            
        }
        
        i ++;
    } 
    for(i = sn; i > 1; i --){//然后按成绩排序 
        for(j = 1; j < i; j ++){
            swap(&zcj[j],&zcj[j +1]);
        }
    }
    
    int zf = zcj[1].rank;//记录总分 
    
    for(j = 1; j <= sn; j ++){//求每人最终成绩 
        int *ra = &zcj[j].rank;
        *ra = roundf(100 + log(1.0 + ((double)*ra-zf)/zf)*10);
    }
    int judge;
    int k;
    for(i=1;i<sn;i++)
    {
        k = i;
        while(zcj[i].rank==zcj[i+1].rank)
        {
            i++;
        }
        
        judge = 1;
        while(judge)
        {
            judge = 0;
            for(j=k;j<i;j++)
            {
                if(zcj[j].StudentID>zcj[j+1].StudentID)
                {
                    swap2(&zcj[j],&zcj[j+1]);
                    judge = 1;
                }
            }
        }
    }
    
    
    for(j = 1; j <= sn; j ++){//输出 
        putout(zcj[j]);
    }
    
}

void swap(struct student2*p1,struct student2*p2){
    struct student2 p;
    if(p2->rank > p1->rank){
        p = *p1;
        *p1 = *p2;
        *p2 = p;
    }
}

void swap2(struct student2*p1,struct student2*p2){
    struct student2 p;
    if(p2->StudentID < p1->StudentID){
        p = *p1;
        *p1 = *p2;
        *p2 = p;
    }
}

void putout(struct student2 p){
    printf("%I64d %d\n",p.StudentID,p.rank);
}
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

XTU 计算机小白一个
不定期在博客分享自己的学习笔记
如有不足，请各位大佬批评谅解