每日归档： 2022年10月29日

ECNU OJ 3031 二进制倒置

给定一个整数 n(0≤n≤10100)、将 n 的 334 位二进制表示形式（不包括开头可能的值为 0 的位，n=0 表示为 1 位 0）前后倒置，输出倒置后的二进制数对应的整数。

例如：n=10，其二进制表示为 (330 个 0)1010，倒置后为 0101，对应输出就是 5。

Input

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

接下来共 T 行整数，对应每个问题有 1 行，表示 n。

Output

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

然后对应每个问题在一行中输出结果。

#include <stdio.h>
#include <string.h>
typedef struct  {
    int cnt, v[101];
} BIGINT;

void DIV2(BIGINT *n)
{
    int carry = 0, i; //carry为进位
    if ( n->v[n->cnt -1] < 2) n ->cnt--, carry = 1;  //若最高位为1,
    for (i = n->cnt -1; i>= 0; i--) {				//从第二位开始
        int t = 10 * carry + n->v[i];	//加上上一位余数			
        n->v[i] = t/2; //每一位除以2
        carry = t%2; //余数作为下一位进位
    }
}

void MUL2ADD(BIGINT *n, int d)
{
    int carry=d, i;
    for (i = 0; i < n->cnt; i++){
        int t=carry + n->v[i] * 2; //每一位乘以2，并处理进位
        n->v[i] = t % 10; //若该数超过10,求个位数，否则就是该数本身
        carry = t / 10;	  //余数作为下一位进位
    }
    if (carry > 0) n->v[n->cnt++] = carry; //若循环完之后,carry大于0,进位
    
}

int main(void)
{
char line[102];
int i;
BIGINT n;
scanf("%sx", line);
n.cnt = strlen(line);
for ( i = 0; i < n.cnt; i++ ){
    n.v[i] = line[n.cnt - i - 1] - '0'; //数字倒置
    
}

int s[334], cnt = 0;
while (n.cnt > 0) 
    s[cnt++] = n.v[0] %2; //数字模2
    DIV2(&n);			  //数字除以2
}

for (i = 0; i < cnt; cnt++ ){
    MUL2ADD(&n, s[i]);
}

if (n.cnt == 0) n.cnt++; //若输入为0,做额外处理
for (i = n.cnt-1; i>=0; i--){
    printf("%d".n.v[i];
}
printf('\n');
}

 

ECNU OJ 2822 内存显示

一个 int 类型变量或 double 类型变量在连续几个字节的内存中存放。读取数值时，当数值中包含小数点时类型为 double，否则类型为 int。将读入的数值存放在 int 类型变量或 double 类型变量中。以十六进制格式（a-f 字母采用小写形式）输出相应变量的连续的每个字节的值。

读入的数据保证能在一个 int 类型或 double 类型变量中正确存放。

注意：int 类型变量和 double 类型变量所占字节数以及一个变量的几个字节的存放顺序与所用计算机的体系结构和编译系统有关。

Input

每一行包含一个数值

Output

每行对应一个数据，每个字节后面都要输出一个空格

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solveint(int n);
void solvedouble(double d);

int main()
{
    char s[31];
    while (~scanf("%s",s)){
        if (strchr(s,'.') == 0)
                solveint(atoi(s));
        else 
            solvedouble(atof(s));
        return 0;
    }
}

void solveint(int n)
{
    int c = sizeof(n);
    unsigned char *p=(unsigned char*) &n;
    while (c--)
        printf("%02x", *p++);
    putchar('\n');
}

void solvedouble(int d)
{
    int c = sizeof(d);
    unsigned char *p=(unsigned char*) &d;
    while (c--)
        printf("%02x", *p++);
    putchar('\n');
}

 

ECNU OJ 2893 数据密度

所有类型的数据在内存中都是以二进制的形式存放的。其中有些位是 1，而有些位是 0。例如：字符 A 的二进制表示 01000001 中有 2 位是 1，6 位是 0。设 sizeof(char) 为 1。

数据密度定义为一块内存数据中 1 的位的占比。

写程序计算一组字符的数据密度。

Input

第 1 行：整数 n (1≤n≤10)

第 2 行 ~ n+1 行：每行是个数范围为 1 ~ 120 的一组字符。一组字符中可能包含空格、制表符、汉字、字母、数字、标点符号。

Output

对于每一行中的一组字符，以最简分数形式在一行中输出其数据密度。

分数格式：分子 / 分母

#include <stdio.h>
#include <string.h>
void solve(char *s);
int gcd(int a, int b){
    return a ? gcd(b % a, a) : b ;
}

int main ()
{
    int T;
    scanf("%d", &T);
    while(T--){
        char s[121];
        gets(s);
        solve(s);
        return 0; 
    }
}

void solve(char *s)
{
    int s1  = 0, bytes=strlen(s), i, j;
    for (int i = 0; i < bytes; i++){
        unsigned char c= s[i]; //为了使用逻辑右移，定义为无符号字符类型
        for (j = 0; j < 8; j++){
            s1 += c % 2; //统计1的位数
            c>>=1; //逻辑右移
        }
    }
    int g = gcd(s1, bytes * 8);//最大公约数
    printf ("%d/%d", s1/g, bytes * 8 / g);

}

 

ECNU OJ 3059 极坐标排序

#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);
}
}

 

ECNU OJ 3055 字符频率

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

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

例如 :

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

A(a) B(b) C(c) D(d) E(e) F(f) G(g) H(h) I(i) J(j) K(k) L(l) M(m)
8.19 1.47 3.83 3.91 12.25 2.26 1.71 4.57 7.10 0.14 0.41 3.77 3.34
N(n) O(o) P(p) Q(q) R(r) S(s) T(t) U(u) V(v) W(w) X(x) Y(y) Z(z)
7.06 7.26 2.89 0.09 6.85 6.36 9.41 2.58 1.09 1.59 0.21 1.58 0.08

字符串 “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);
}

 

ECNU OJ 3036 按数据中1的位数排序

所有数据在内存中都是以二进制形式存放的，其中有一些位是 1，而另一些位是 0。

例如，整数 100 的二进制表示为 1100100，其中 1 的位数是 3；整数 15 的二进制表示为 1111，其中 1 的位数是 4；整数-15 的 64 位二进制表示为 1111111111111111111111111111111111111111111111111111111111110001，其中 1 的位数是 61。

现在有 N 个整数，要求按照 64 位二进制补码表示中 1 的位数从大到小进行排序。若两个数的二进制表示中 1 的位数相同，则按照数本身值由小到大排序。

例如：数 100,15,0,30,7,-15,100,-100 排序后的结果为 :

-15,-100,15,30,7,100,100,0。

Input

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

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

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

第 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);
}