分类： OJ算法刷题

#include <stdio.h>

int slection_sort(int array[], int n)
{
    for (int i = 0; i < n; i++){
        int min_index = i;
        for (int j = i + 1; j < n; j++)
            if (array[j] < array[min_index]){
                min_index = j;
            }
        swap(array[i], array[min_index]);
    }
}

Input

第一行：一个整数 T （0 < T <= 100 ），表示有 T 组测试数据。

第 2 行- T+1 行：每行输入两个正整数 x 和 y，（0 ≦x, y ≦1000000 ）。两个整数之间有一个空格。

Output

对每组测试数据，输出一行。

int main()
{
    int t,x,y,z,q;
    scanf(“%d”,&t);
    while(t–)
    {
        scanf(“%d %d”,&x,&y);
        z=0;
        for(q=0;q<32;q++)
        {
            if((x%2)!=(y%2))
            z++;
            x>>=1;
            y>>=1;
            }
        printf(“%d\n”,z);
    }
    return 0;
}

Input

第 1 行：整数 T (1≤T≤10) 为问题数。

第 2 ∽ T+1 行：每一个问题中要转换的十进制数 N (0≤N≤1 000 000)。

Output

对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等），然后在一行中输出对应的二进制与十六进制，用空格隔开。十六进制中 10 用 A 表示，依次类推。

#include <iostream>
#include <stdio.h>
using namespace std;
int t=0;
char hex_list[36]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
void solve(int num);
int main ()
{
    int T;
    scanf("%d", &T);
    while(T--){
        int num;
        cin >> num;
        solve(num);
    }
}

int convert(int p, int from, int *to)
{
    int i=0;
    do {
        to[i++] = from  % p;
        from /= p;
       
    } while ( from > 0 );

    return i;

}
void solve(int num)
{
    int bin[1000], hex[1000];

    int i = convert(2,num,bin);
    int j = convert(16,num,hex);
    int reverse_bin[1000];
    int reverse_hex[1000];

    printf("case #%d\n", t++); 
    for (int k = 0; k < i; k++){
        reverse_bin[k] = bin[i - k - 1];
    }
    for (int k = 0; k < j; k++){
        reverse_hex[k]= hex[j - k - 1]; 
    }

    for (int k = 0; k < i; k++) cout << reverse_bin[k];
    cout << ' ';
    for (int k = 0; k < j; k++) cout << hex_list[reverse_hex[k]];
    cout << endl;
    
}

Input

输入一个正整数 T。表示测试数据的组数。

每个测试实例包含两个整数 N(32 位整数) 和 R （2<=R<=36).

Output

为每个测试实例输出转换后的数，每个输出占一行。如果 R 大于 10，则对应的数字规则参考 16 进制（比如，10 用 A 表示 ,16 用 G 表示等等）。

#include<iostream>
using namespace std;
long int n,r;
char a[36]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int work(long int n)
{
    if(n<r)
    {
       cout<<a[n];
       return n;
    }
    else
    {
       work((n-n%r)/r);
       cout<<a[n%r];
    }
}

void work2(long int n)
{
    int z[100], num=0;
    do {
        z[num++] = n % r;
        n = n / r;
    } while (n != 0);

    for (int i= num - 1; i>=0; i--){
        cout << a[z[i]];
    }

}
int main()
{
    long int t,i,j;
    bool check=0;
    cin>>t;
    for(i=0;i<t;i++)
    {
       check=0;
       cin>>n>>r;
       j=0;
       if(n<0)
       {
         check=1;
         n=-n;
         cout<<'-';
       }
       work2(n);
       cout<<endl;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct point
{
   double x, y;
   double p, angle;
};

struct point s[1000];

int cmp (const void * a, const void *b)
{
    struct point p1, p2;
    p1 = *(struct point *)a;
    p2 = *(struct point *)b;
    
    if (p1.angle > p2.angle) return 1;				//极角大的排在后
    else if (fabs( p1.angle - p2.angle ) < 1e-10)   //极角相同
        if (p2.p > p1.p )return 1;                  //按极径大的放在前
    return -1;
}
int main (void)
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
    scanf( "%lf%lf", &s[i].x, &s[i].y);
    s[i].p  = sqrt ( s[i].x * s[i].x + s[i].y * s[i].y ); //计算极径
    int t;
    t = atan2( s[i].y, s[i].x );                          //计算极径的反正切
    if (t < 0 ) s[i].angle = 2 * M_PI + t;				  //由于atan2()返回值为(-π,π]，所以要把负值加2π
    else s[i].angle = t;								  //正值不变
    qsort ( s, n ,sizeof(s[0]), cmp );
    for (int i=0; i<n; i++)
        printf("(%.4f,%.4f)\n", s[i].p, s[i].angle);
}
}

设 26 个英文字母，每个字母都对应一个使用频率，同一个字母的大小写使用频率相同。

现给定一个由 26 个英文字母构成的字符串，请将字符串按照字母使用频率由大到小重排，使用频率大的字母排在前面，使用频率小的字母排在后面，如果使用频率相同则按照字母顺序表排列，小写字母排在大写字母前面，即 a->A->b->B->c->C-d->D->……->z->Z。

例如 :

26 个字母的使用频率如下表 :

字符串 “Thisisaexample” 重排后为 “eeTaaiisshlmpx”

字符串 “AertrtsaBereDET” 重排后为 “eeeEttTaArrrsDB”。

Input

第 1 行：一个整数 T (1≤T≤10) 为问题数。

对于每个问题，有 2 行数据，按如下格式输入：

第 1 行输入 26 个浮点数，分别表示 26 个英文字母 A(a)～Z(z) 的使用频率；

第 2 行输入一个字符串，字符串长度不超过 100 个字符，字符串由 26 个英文字母构成。

Output

对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等）。

然后对应每个问题在一行中输出重排后的字符串。

#include <stdio.h>
#include <algorithm>
double p[27];

int cmp(const void * a, const void * b)
{
    char ch1, ch2; //待比较字符
    int p1, p2; //p1,p2 为ch1, ch2 在字母表中的序号
    ch1=*((char *)a);
    ch2=*((char *)b);
    if (ch1 >= 'a' && ch1 <= 'z') p1 = ch1 - 'a'; else p1 = ch1 - 'A';
    if (ch2 >= 'a' && ch2 <= 'z') p1 = ch2 - 'a'; else p2 = ch2 - 'A';
    
    if(p[p1] < p[p2])  return -1; // 按字母频率排序
    else if (p[p1] == p[p2])      // 字母使用频率相同
        if (p1 == p2)
            return ch2 - ch1; //相同字母，降序排列，即小写在大写前面
        else return p1 - p2; //不同字母，但使用频率相同，按字母表顺序排列
    else return 1;

}

int main (void)
{
    for (int i =0; i < 26; i++)
        scanf("%lf",&p[i]);
    char str[101];
    scanf("%s", str);
    
    qsort(str, strlen(str),sizeof(str[0]), cmp);
    printf("%s\n", str);
}

Input

第 1 行：整数 T (1≤T≤10) 为问题数

第 2 行：第一个问题中的 N(1≤N≤10000)

第 3 行：N 个待排序的数 (-10¹⁸≤数≤10¹⁸)，每两个数之间由一个空格分隔。

第 4 ∽T*2+1 行：后面问题的数据，格式与第一个问题相同。

Output

对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等），然后在一行中输出排序后的数。格式为：以一个空格分隔每两个数。最后一个数后面没有空格。

#include 
#include 
#include 
struct data
{
    long long int a; //整数
    int number; //64位二进制补码中1的位数
};

int cmp (const void *a, const void *b)
{
    struct data d1, d2;
    d1 = *((struct data *)a);
    d2 = *((struct data *)b);
    if (d2.number != d1.number)
        return d2.number - d1.number; //降序排列
    else{
        if (d1.a < d2.a) // 因为cmp返回值为int 而 a为long long 所以不能直接相减 
            return -1;
        else 
            return 1;
    }
}
int main (void)
{   
    int n;
    struct data p[1000];
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%I64d", &p[i].a);
        int d=1;
        p[i].number = 0;
        for (int t=0; t<64;t++){
            if(p[i].a & d)
                p[i].number++;
            d = d << 1;
        }
    }
    int i;
    qsort(p,n, sizeof(p[0]), cmp);
    for (i = 0; i < n - 1; i++)
        printf("%I64d ",p[i].a);
    printf("%l64d\n",p[i].a);
}

Input

第 1 行：整数 T (1≤T≤10) 为问题数

第 2 行：第一个问题的整数 N （1≤N≤1000）

第 3 ∽ N+2 行：第一个问题的每行的数据 ai 和表示行结束的标志-1, 1≤数据个数≤50。0≤ai≤10^9, 数据之间由一个空格分隔。

后面是第 2 ∽ T 个问题的数据。格式与第一个问题相同。

Output

对于每个问题，输出排序后的结果。

格式为：每行输出一行数据，数据之间有一个空格。

#include <stdio.h>

int line_data[1000][51];

//首先比较行中第一个数的值，将第一个数大的行排在前边
//如果第一个数相等，按照第二个数的值排序
//若某行没有第二个数的话，该行排在后边
//如果第二个数还是相等，则比较第三个数，以此类推

int cmp(cont void *a, const void *b)
{
    int *s1 = (int *a);
    int *s2 = (int *b);
    while (*s1 != -1 && s2 != -1 && *s1 = *s2){ //若相等比较下一个，
                                                //若不等，跳出循环
                                                //若为-1，亦跳出循环
        s1++;
        s2++;
    }
    return *s2 - *s1; //跳出循环后，降序排列

}
int main(void)
{
    int n;
    scanf("%d", &n);
    for ( int k = 0; k < n; k++ ){
        int j = 0;
        while(scanf("%d", &line_data[k][j]) && line_data[k][j] != -1){
            j++;
        }        
    }

    qsort(line_data,n, sizeof(line_data[0]), cmp);
    for (int k =0; k < n; k++){
        for ( int j = 0; line_data[k][j+1] != -1; j++ )
            printf("%d ", line_data[k][j]);
        printf("%d", line_data[k][j]);
    }

}

Input

每组数据由 2 行组成，第 1 行为字母顺序（26 个大写字母），第 2 行是需要排序的一组字符串（只含大小写字母，长度不大于 20）。

数据不多于 100 组。需要排序的一组字符串中包含的字符串个数至少 1 个，至多 100 个。

Output

对于每一组数据，输出排序后的字符串。字符串之间输出一个空格，最后一个字符串后面没有空格，而是输出一个换行符。

#include <stdio.h>

int p[26];
//按给定的字母循序对字符串排序，如果第一个字符相等，则比较第二个字符

int cmp (const void *a, const void *b)
{
    char *s1, *s2; //s1,s2用来遍历字符串
    char ch1, ch2; //ch1，ch2用来指向对应的大写字母
    s1 = (char *)a; 
    s2 = (char *)b;

//--------------------------------重要---------------------------------
    while (*s1 && *s2){
        ch1 = (*s1) >= 'a' ? *s1 - 'a' + 'A' : *s1; // 转化为大写
        ch2 = (*s2) >= 'a' ? *s2 - 'a' + 'A' : *s2; 

        if (p[ch1-'A'] != p[ch2-'A'])   //字符不相等，按顺序表比较
            return p[ch1-'A'] - p[ch2-'A']; //升序
        else { //字符相等，进入下个字符比较
            s1++; s2++;
        }

        if (*s1 == 0) //第一个字符串结束，而第二个未结束则，第一个字符串在前
            return -1;
        else          //第一个字符串未结束，而第二个结束，第一个字符串在后
            return 1;
//--------------------------------重要---------------------------------
    }
}


int main(void)
{

    char s[27];

    while(~scanf("%s\n",s)){   //读入字母顺序表
        for (int i = 0; i < 26; i++)
            p[s[i]-'A'] = i;
        
        char str[2200];
        char a[100][21];

        gets(str);
        int count = 0;
        int i = 0;
//--------------------------------重要---------------------------------
        while (true){ //根据空格分割出每个字符串，把字符串存储在二维数组
            int j = 0;
            while (str[i]!= ' ' && str[i])
                a[count][j++] = str[i++];
            a[count][j] = '\0';
            count++;  //统计字符串个数
            if (!str[i])
                break;
            else
                i++;
        }
//--------------------------------重要---------------------------------
        qsort(a, count, sizeof(a[0]), cmp);
        // qsort(首地址，排序的字符创个数，每一个数组元素大小，比较函数)
        for (int i = 0; i < count - 1; i++)
            printf("%s ", a[i]);
        printf("%s\n", a[i]);
    }
}

3-1 得分 (UVa 1585)

题目：有一个客观的测试结果，如“OOXXOXXOOO”，一个“O”表示一个问题的正确答案，一个“X”表示一个错误的答案。这个测试的每个问题的分数是由它自己计算的，例如，第10个问题的得分是3，它是由它自己和它的前两个连续的O得到的。
因此，“OOXXOXXOOO”的分数是由“1 + 2 + 0 + 0 + 1 + 0 + 0 + 1 + 2 + 3”计算得到的10。
你要编写一个计算测试结果分数的程序。

提示：用一个flag标记是否是O开头

#include <iostream>
using namespace std;

int main(void)
{
    string str;
    cin >> str;
    int len = str.length();
    bool start = false;
    int count = 0;
    int sum = 0;
    for (int i = 0; i < len; i++){
        if (str[i] == 'O'){
            start = true;
            count++;
        } else if (str[i] == 'X') {
            start = false;
            count = 0;
        }
        if (start) {
            sum += count;
        }
    }
}

3-2分子量 (UVa 1586)

题目大意：给出一种物质的分子式（不带括号），求分子量。本题中分子式只包含4种原子，分别为C、H、O、N，

原子量分别为12.01,1.008,16.00,14.01

提示：用数组保存四种原子的分子量，用flag标记当前位是字母还是数字。如果是数字，超过一位的，把每一位的数值从字符串中提取出来。用数组保存每一位的分子量。

#include <stdio.h>
#include <string.h>
#include <ctype.h>
float ans[100];
float mass[] = {12.01, 1.008, 16.00, 14.01};
char str[10];
int len;
int num(int pos, int len)//pos为数字开始的位置，len为分子式长度
{
    int temp;
    for (int i=pos;i<len;i++){ //获取数字长度，并存储到temp
        if(isdigit(str[i])){
            temp=i;
        } else {
            break;
        }
    }

    int n = 0;
    for (int i=pos; i <=temp;i++){ //根据每一十进制位计算分子量
        n = n * 10 +  (str[i] - '0');
    }
    return n - 1; //注意减一是因为最后计算的时候，字母本身占一倍 
  
}

int main(void)
{
    int flag = 0; 
    scanf("%s", str);
    len = strlen(str);
    for (int i = 0; i < len; i++){
        if (str[i] == 'C'){
            ans[i]=mass[0];
        }
        if (str[i] == 'H'){
            ans[i]=mass[1];
        }
        if (str[i] == 'O'){
            ans[i]=mass[2];
        }
        if (str[i] == 'N'){
            ans[i]=mass[3];
        }
        if(isdigit(str[i])&&flag==0){ //初始状态flag = 0，直接进入if判断 
            ans[i]=ans[i-1] * num (i, len); //若该位为数字，则计算数字乘以前面元素的分子量
            flag = 1; //做标记，表示计算数字，下次循环忽略此if判断
        } 
        if (isalpha(str[i])){ //若该位为字母，则标记flag = 0复位，方便下次循环进入上面if判断
            flag = 0;
        }
    }
    
    float sum = 0;
    for (int i = 0; i<len;i++){
       sum+=ans[i];
    }
    printf("%.3f\n",sum);
    return 0;
}

3-3 数数字(UVa1225)

#include <iostream>
using namespace std;

int main(void)
{
    int sum[10] = {}; //sum[i]表示数字i的个数
    for (int i = 1; i <= 10000; i++){
        int j = i;
        while (j > 0){
            int k;
            k = j % 10; //获取个位
            sum[k]++;   //个位数字的个数加一
            j /= 10;    //下一位
        }
    }

    for  (int i = 0; i < 10; i++){
        cout << i <<  "  : "  << sum[i] << endl;
    }
}

#include  <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

using namespace std;

char str[104];

int main(void)
{
    int n;
    while (~scanf("%d",&n))
        while (n--){
            scanf("%s", str);
            int len = strlen(str);
            for(int k, i = 1; i < len; i++){
                if (len % i == 0 ) //若子串长度能够整除母串
                    for (k = i; k < len; k++) //开始匹配
                        if (str[i] != str[k%i]) //如果不能匹配
                            break; //则跳出
                if (len == i) {//若全部匹配 
                    cout << i;
                    break;
                }
            }
            if (n) cout << endl;
    }
}

#include<stdio.h>  
#include<cstring>  
#include<algorithm>  
#include <iostream>
#define HardBoy main()  
#define ForMyLove return 0;  
using namespace std;  
const int MYDD = 1103+1e4;  
  
int HardBoy {  
    int quotient[MYDD];  
    int remainder[MYDD];  
    int u[MYDD];  
    int n, m, t;  
      
    while(scanf("%d %d", &n, &m) != EOF) {  
        t = n;/*3000以内*/  
        memset(quotient, 0, sizeof(quotient));  
        memset(u, 0, sizeof(u));  
        int cnt = 0;  
        quotient[cnt++] = n/m;  
        n %= m;
        //n为余数,循环前数组u[]被置0，!u[n]为真，进入循环
        while(!u[n] && n) { //u[n] == 0 

            //debug:cout << "before n= " << n << endl;
            u[n] = cnt;
            //一开始数组u[n] = cnt == 0,!u[n]为真，持续循环
            //之后cnt > 0，每次循环,u[n]被赋正值
            //直到循环至n重复出现，即出现循环节,这时u[n]已经被赋值为正值，!u[n]为假,跳出循环
            //debug:cout << "u[n]= " << cnt <<endl;
            remainder[cnt] = n;  //记录余数
            //debug:cout << "reamainder= " << n << endl;
            quotient[cnt++] = 10*n/m;  //记录商
            //debug:cout << "quotient= " << 10*n/m << endl;
            n = 10*n%m;  
            //debug:cout << "after n= " << n << endl;

            //debug:cout << endl; 
        }  
  
        printf("%d/%d = %d.", t, m, quotient[0]);  
        for (int i = 1 ; i < cnt && i <= 50 ; i++) {  
            if (n && remainder[i] == n) printf("(");  
            /*存在循环节->开始存在余数相同的位置*/  
            printf("%d",quotient[i]);  
        }  
        if (!n) printf("(0");
        //余数为零
        if (cnt > 50) printf("...");  
        printf(")\n");  
        printf("   %d = number of digits in repeating cycle\n\n",!n? 1:cnt-u[n]);  
  
    }  
    ForMyLove  
}

#include <stdio.h>  
#include <string.h>  
  
char a[100005], b[100005];  
int main() {  
    while (~scanf("%s%s", a, b)) {  
        int star = 0, lenb = strlen(b), lena = strlen(a);  
        for (int i = 0; i < lenb; i ++) {  
            if (a[star] == b[i])  
                star ++;  
            if (star == lena) {  
                printf("Yes\n");  
                break;  
            }  
        }  
        if (star != lena)  
            printf("No\n");  
    }  
    return 0;  
}