Midterm Exam

第一次期中考试，我也是狠狠的爆零了
其实题目不是很难，回过头来看，补题的时候都是交一两发就过了
考试和状态，策略的关系很大，算是我的老毛病了，唉

补题补了一天，终于在晚上的时候全部写完了，我还是需要狠狠的训练啊
加练

Index

• Index
• A
• B
• C
• D
• E
• F
• G
• H

A

• 1589

我看到这个题目的第一眼就有思路了，二分+递归应该就可以写出来，但是我觉得我递归的底子不是很扎实，就跳了这个题，但是这个题其实真的不难
蒟蒻也是在补题的时候两遍过了

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

#define N 1000010

char num[N];

int solve(char *num, int len) {
    int index = len - 1;
    for (int i = 0; i < len / 2; i++) {
        if (num[i] != num[index--]) {
            return len;
        }
    }
    if (len % 2 == 0) {
        return solve(num, len / 2);
    } else {
        return len;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", num);
        int len = strlen(num);
        printf("%d\n", solve(num, len));
    }
    return 0;
}

B

• 1590

代码实现过于复杂出了纰漏，而且我理解错了题意(我的天！)，补题时优化了一下逻辑就过了

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

void swap(char *a,char *b){
    char temp=*a;
    *a=*b;
    *b=temp;
}

void trans(char *str,int k){
    for(int i=0;i<k/2;i++){
        swap(&str[i],&str[k-i-1]);
    }  
}

int main()
{
    char str[1110];
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%s", str);
        int len = strlen(str);
        int k;
        scanf("%d", &k);
        for(int i=0;i<len;i+=2*k){
            if(i+k<len){
                trans(str+i,k);
            }else{
                trans(str+i,len-i);
            }
        } 
        printf("%s\n", str);
    }
    return 0;

}

C

• 1591

考试的时候最先开始写的题目，我觉得不难，简单的字符串转化，但是交上去一直过不了，补题时才发现我漏了个小细节(哭)，而且可以直接二进制输出，我手打了一个函数来实现，就是这里出了漏子

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

char str[100];
int num[100];

int main() {
    while (fgets(str, sizeof(str), stdin) != NULL) {
        if (str[0] == '#') {
            int len = strlen(str);
            if (str[len - 1] == '\n') {
                str[len - 1] = '\0'; 
                len--;
            }
            for (int i = 0; i < len; i++) {
                if ((int)str[i] > 96) {
                    num[i] = str[i] - 87;
                } else {
                    num[i] = str[i] - 48;
                }
            }
            int ans = 0;
            for (int i = 1; i < len; i += 2) {
                ans += num[i] * 16 + num[i + 1];
                printf("%d", ans);
                ans = 0;
                if (i != len - 2) {
                    printf(",");
                }
            }
        }else{
            char a[2]={0};
            int len=strlen(str);
            if (str[len - 1] == '\n') {
                str[len - 1] = '\0'; 
                len--;
            }
            int j=0;
            for(int i=0;i<3;i++){
                while(str[j++]!=' '&&str[j-1]!='\0'){
                    num[i]=num[i]*10+str[j-1]-'0'; 
                }
            }
            printf("#");
            for(int i=0;i<3;i++){
                printf("%02x",num[i]);
            }
        }
        printf("\n");
        memset(str, 0, sizeof(str));
        memset(num, 0, sizeof(num));
    }
    return 0;
}

D

• 1592

考试的时候看都没看这个题，这个题面描述比较抽象，问了别人才明白这就是一个简单的马尔科夫链，推出公式就出来了

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;
        if (x == 0) {
            cout << "0" << endl;
            continue;
        }
        if (y == 0) {
            cout << "1" << endl;
            continue;
        }
        int num = x;
        int den = x + y;
        int g = gcd(num, den);
        num /= g;
        den /= g;
        if (num == den) {
            cout << "1" << endl;
        } else {
            cout << num << "/" << den << endl;
        }
    }
    return 0;
}

E

• 1593

这也是一个题面描述抽象的，也是问了大佬才明白这个题是什么意思
蒟蒻也是想出了O(N)复杂度的算法(仅剩的自豪，大哭)

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

#define N 10000010

typedef struct{
    int value;
    int index;
}Num;

Num num[N];

int cmp(const void *a,const void *b){
    // return *(int *)a-*(int *)b;
    return ((Num *)a)->value-((Num *)b)->value;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            scanf("%d",&num[i].value);
            num[i].index=i;
        }
        qsort(num,n,sizeof(Num),cmp);
        int cnt=0;
        for(int i=0;i<n;i++){
            if(num[i].index>num[i+1].index||num[i].index+1!=num[i+1].index){
                cnt++;
            }
        }
        if(cnt<=m){
            puts("YES");
        }else{
            puts("NO");
        }
    }
    return 0;
}

F

• 1594

这是一个博弈论经典理论，得出结论即可解题

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int t, n, m;
        cin >> t >> n >> m;
        if (t == 1) { 
            if (n % (m + 1) == 0) {
                cout << "Bad" << endl;
            } else {
                cout << "Nice" << endl;
            }
        } else { 
            if (n % (m + 1) == 0) {
                cout << "Nice" << endl;
            } else {
                cout << "Bad" << endl;
            }
        }
    }
    return 0;
}

G

• 1595

我觉得这里面最简单的一道题，但可惜没时间写这道题了

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

char map[1010][10010];
char str[1010];

int main()
{
    scanf("%s", str);
    int len = strlen(str);
    int w;
    scanf("%d", &w);
    int i=0,k=0,index=0;
    while(i<len){
        index++;
        for(int j=0;j<w&&(i<len);j++){
            map[j][k]=str[i++];
        }
        k+=w-1;
        int x=w-1;
        for(int j=0;j<w-2&&(i<len);j++){
            int y=i-index*w+index;
            map[--x][y]=str[i++];
        }
    }
    for(i=0;i<1010;i++){
        for(int j=0;j<10010;j++){
             if(map[i][j]){
                 printf("%c",map[i][j]);
             }
         }
    }
    printf("\n");
    return 0;
}

H

• 1596

签到题，我没做出来······
事实上确实是签到题，但是我看到这道题的时候心态比较乱，而且好多人都把这道题写出来了，哎

#include<stdio.h>

typedef long long ll;

ll genLeft(ll n){
    return n*(n-1)/2+1;
}
ll genRight(ll n){
    return n*(n+1)/2;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        ll left=genLeft(n);
        ll right=genRight(n);
        left=((left%m==0)?left:left+m-left%m);
        right=right-right%m;
        ll ans=(right-left)/m+1;
        printf("%lld\n",ans);
    }
    return 0;
}

这里寻找个数时还有另一种思路

#include<stdio.h>

typedef long long ll;

ll genLeft(ll n){
    return n*(n-1)/2+1;
}
ll genRight(ll n){
    return n*(n+1)/2;
}
ll solve(ll n, ll m) {
    ll left = genLeft(n);
    ll right = genRight(n);
    ll a = ((left + m - 1) / m )* m;
    ll b = right / m * m;
    return (b - a) / m + 1;
}

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

    while (T--) {
        ll n, m;
        scanf("%lld %lld", &n, &m);
        printf("%lld\n", solve(n, m));
    }

    return 0;
}