一、基礎練習

1.fib數列

題目

題目鏈接

Fibonacci數列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1，當n比較大時，Fn也非常大，現在我們想知道，Fn除以10007的余數是多少，

資料規模與約定

1 <= n <= 1,000,000，

解題思路

很明顯，資料規模并不大，O(n)時間復雜度便可解決，

但如果資料規模非常龐大，我們可以利用到下面這張圖的矩陣遞推公式再根據矩陣快速冪解決：

解題代碼

解法一(簡單遞推)：時間復雜度O(n)

適用于資料量少于10^8的情況

#include <stdio.h>
const int MOD = 10007;
int main() {
    int n;
    scanf("%d", &n);
    int a=1,b=1;
    if(n<=2)printf("1");
    else{
        int tmp;
				int i;
        for(i=3;i<=n;i++) {
            tmp = b;
            b = (a+b)%MOD;
            a = tmp;
        }
        printf("%d",b);
    }
    return 0;
}

解法二(矩陣快速冪)：時間復雜度O(logn)

適用于資料量大于10^8的情況

//
// Created by Alone on 2021/11/19.
//
#include <bits/stdc++.h>
using namespace std;

typedef long long ll ;

//TODO To design a matrix class to solve this problem
class Matrix{
    ll** date;
    int m;
    int n;
public: static const int MOD;
public:
    Matrix(ll** rec,int n,int m):date(rec),n(n),m(m){}//C format to init
    Matrix():date(NULL),m(0),n(0){} //aefault
    Matrix(Matrix& b):n(b.n),m(b.m){//copy struct
        assert(b.date!=NULL && b.n>0 && b.m>0);
        date = new ll*[n];
        copy(b.date,b.date+n,date);
        for(int i=0;i<n;i++){
            date[i] = new ll[m];
            copy(b.date[i],b.date[i]+m,date[i]);
        }
    }
    ~Matrix(){//destruct
        assert(date!=NULL && n>0 && m>0);
        for (int i = n-1; i >=0 ; --i) {
            delete [] date[i];
        }
        delete[] date;
    }
    Matrix& operator*(Matrix& b){//TODO operator* to overload
        assert(b.date!=NULL && date!=NULL && m==b.n);
        ll tmp[n][b.m];
        for(int i=0;i<n;i++){
            for(int j=0;j<b.m;j++){
                ll sum = 0;
                for(int k=0;k<m;k++){
                    sum = (sum + date[i][k]*b.date[k][j])%MOD;
                }
                tmp[i][j] = sum;
            }
        }
        this->m = b.m;
        for(int i=0;i<n;i++){
            for (int j = 0; j < m; ++j) {
                date[i][j] = tmp[i][j];
            }
        }
        return *this;
    }
    void init(){//TODO initialized to unit matrix
        assert(date!=NULL && n>0 && m>0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if(i==j)date[i][j] = 1;
                else date[i][j] = 0;
            }
        }
    }
    void quickPow(ll c){//TODO quick pow for matrix
        if(c==1||c<0)return;
        if(c==0){
            init();
            return;
        }
        Matrix tmp(*this);
        init();
        while (c){
            if(c&1)
                *this = *this * tmp;
            c >>= 1;
            tmp = tmp*tmp;
        }
    }
    void print(){//TODO to print this matrix
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout<<date[i][j]<<' ';
            }
            cout<<endl;
        }
    }
    int get(int x,int y){//TODO provide access to the outside
        assert(date!=NULL && x<n && y<m);
        return date[x][y];
    }
};
const int Matrix::MOD = 1007;//TODO set the factor for mod operation

int main(){
    ll c;
    cin>>c;
    ll** matrix = new ll*[2];
    matrix[0] = new ll[2]{1,1};
    matrix[1] = new ll[2]{1,0};
    Matrix mat(matrix,2,2);
    mat.quickPow(c-1);

    ll** res = new ll*[2];
    res[0] = new ll[1]{1};
    res[1] = new ll[1]{1};
    Matrix fib(res,2,1);
    Matrix ret(mat*fib);
    cout<<ret.get(1,0);
    return 0;
}

2.閏年判斷

題目

題目鏈接

解題思路

只要挑選處閏年即可，閏年有個判斷方式將其判斷：

關于閏年的解釋：

1. 普通年份能被4整除，且不能被100整除的，是閏年，（ 如2004年就是閏年）
2. 世紀年份能被400整除的是閏年，（ 如2000年是閏年，1900年不是閏年）

如果年份是閏年，那么它的二月份就會比平常多1天，

解題代碼

#include<stdio.h>
int main(){
    int n;
    const char* res[]= {"no","yes"};
    scanf("%d",&n);
    int index = 0;
    if(n%400==0||(n%4==0&&n%100!=0))
        index = 1;
    fputs(res[index],stdout);
    return 0;
}

3. 數列特征

題目

題目鏈接

解題思路

求一個陣列的最大值和最小值以及所有數字的和，，

解題代碼

#include<iostream>
#include<algorithm>
#include<limits>
using namespace std;
int main(){
    int n;
    cin>>n;
    int nums[n];
    int mx=INT_MIN,mn=INT_MAX,sum = 0;
    for(int i=0;i<n;i++){
        cin>>nums[i];
        mx = max(mx,nums[i]);
        mn = min(mn,nums[i]);
        sum += nums[i];
    }
    printf("%d\n%d\n%d",mx,mn,sum);
    return 0;
}

4.查找整數

題目

題目鏈接

解題思路

按照題目意思來就行，直接查找第一次出現的位置即可，

解題代碼

解法一：C風格

#include <iostream>
using namespace std;

int main(){
    int n,target;
    int res = -1;
    cin>>n;
    int nums[n];
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    cin>>target;
    for (int i = 0; i < n; ++i) {
        if(nums[i]==target){
            res = i+1;
            break;
        }
    }
    cout<<res;
    return 0;
}

解法二：C++風格

由于C++98不支持lamda運算式，所以需要把傳入的函式單獨寫出來了，

#include <bits/stdc++.h>
using namespace std;
void input(int& a){cin>>a;}
int main(){
    int n,target,res;
    cin>>n;
    int nums[n];
    for_each(nums,nums+n,input);
    cin>>target;
    res = find(nums,nums+n,target)-nums+1;
    if(res>n)
        res = -1;
    cout<<res;
    return 0;
}

C++11風格

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,target;
    int res;
    cin>>n;
    int nums[n];
    for_each(nums,nums+n,[](int& a){cin>>a;});
    cin>>target;
    res = find(nums,nums+n,target)-nums+1;
    if(res>n)
        res = -1;
    cout<<res;
    return 0;
}

5.楊輝三角形

題目

題目鏈接

解題思路

根據楊輝三角的性質來做，對于楊輝三角第 i 行、第 j 列的元素，我們用 dp[i][j] 來進行表示，那么有以下關系：
d p [ i ] [ j ] = { d p [ i ? 1 ] [ j ] + d p [ i ? 1 ] [ j ? 1 ] ( 0 < j < m ) 1 ( j = 0 , j = m ) dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]+dp[i-1][j-1](0<j<m) \\ 1\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(j=0,j=m) \end{array} \right. dp[i][j]={dp[i?1][j]+dp[i?1][j?1](0<j<m)1(j=0,j=m)?

解題代碼

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int nums[n][n];
    memset(nums,0,sizeof(nums));
    int cnt = 1; //表示該層有多少列需要更新
    for(int i=0;i<n;i++,cnt++){
        for(int j=0;j<cnt;j++){
            if(j==0||j==n-1)
                nums[i][j] = 1;
            else
                nums[i][j] = nums[i-1][j]+nums[i-1][j-1];
        }
    }
    //列印結果
    cnt = 1;
    for (int i = 0; i < n; ++i,++cnt) {
        for (int j = 0; j < cnt; ++j) {
            printf("%d ",nums[i][j]);
        }
        printf("\n");
    }
    return 0;
}

6.數列排序

題目

題目鏈接

解題思路

排序演算法，有很多，有冒泡/插入/選擇/基數/基爾/快速/堆/歸并/桶排序等等等，這些大概是10大必會的排序，其中以快排運用最廣，而快排，又分幾種實作方式，大概分兩類，基于比較的挖坑填補實作，以及直接基于比較的交換實作，我這里手寫的快排用的是交換實作，

解題代碼

#include <bits/stdc++.h>
using namespace std;
//快速排序
void qsort(int* nums, int l, int r) {
    if (l >= r)return;
    int tl = l, tr = r;
    int cmp = nums[(l + r) / 2];
    while (tl <= tr) {
        while (nums[tl] < cmp)tl++;
        while (nums[tr] > cmp)tr--;
        if (tl <= tr) {
            swap(nums[tl], nums[tr]);
            tl++;
            tr--;
        }
    }
    qsort(nums, l, tr);
    qsort(nums, tl, r);
}
//快排入口
void quickSort(int* nums, int len) {
    qsort(nums, 0, len - 1);
}

int main(){
    int n;
    cin>>n;
    int nums[n];
    for (int i = 0; i < n; ++i) {
        cin>>nums[i];
    }
    quickSort(nums,n);
    for (int i = 0; i < n; ++i) {
        cout<<nums[i]<<' ';
    }
    return 0;
}

7.演算法訓練 P0701 單詞變復數

題目

題目鏈接

題目詳解

簡單明了的三種分類討論，我這里實作一個專門判斷是否以某個字符結尾的函式，然后一切就引刃而解了，

解題代碼

完全的純種C優質代碼：

#include <stdio.h>
#include <string.h>
#define false 0
#define true 1
typedef unsigned char bool;
//TODO 判斷字串是否以某個字串結尾
bool endWith(char* s,int n,const char* cmp,int m){
    int cnt ;//用于反向記錄有多少個字符相同
    for (cnt = 0; n-1-cnt >=0&& m-1-cnt>=0 ; ++cnt) {
        if(s[n-1-cnt]!=cmp[m-1-cnt])
            return false;
    }
    return cnt == m;
}
//TODO 判斷是否是元音字母
inline bool isvowel(char ch){
    return ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u';
}
int main(){
    char s[50];
    gets(s);
    int n = strlen(s);
    //TODO 三種情況
    if(endWith(s,n,"s",1)||endWith(s,n,"z",1)||
    endWith(s,n,"x",1)||endWith(s,n,"ch",2)||endWith(s,n,"sh",2)){
        strcat(s,"es");
    } else if(endWith(s,n,"y",1)&&n-2>=0&&!isvowel(s[n-2])){
        s[n-1] = 0;
        strcat(s,"ies");
    }else{
        strcat(s,"s");
    }
    fputs(s,stdout);
    return 0;
}

8.演算法訓練 P0702 實作strcmp

題目

題目鏈接

解題思路

• 由于我平時是比較對原始碼感興趣的，所以本人也比較喜歡寫這種造輪子的題目，

strcmp的比較無非就是三種情況：

1. 完全匹配，如"abc",“abc”
2. 部分匹配，如"abcd",“abf”
3. 單方面完全匹配，如"abcd",“ab”

而計算差值的時候我們就需要對以上三種情況進行思考，

接下來結合代碼應該就非常好理解了，

解題代碼

#include <stdio.h>
int strcmp(const char* s1,const char* s2){
    int i = 0;
    int ret = 0;
    //TODO 跳出回圈后無非就三種情況：1.完全匹配 2.部分匹配 3.單方面完全匹配
    while (s1[i]!=0&&s2[i]!=0){
        if(s1[i]!=s2[i]){
            ret = s1[i] - s2[i];
            break;
        }
        i++;
    }
    //TODO 處理單方面完全匹配的情況
    if((s1[i] == 0&&s2[i] != 0)||(s1[i] != 0&&s2[i] == 0))
        ret = s1[i]==0?-s2[i]:s1[i];
    return ret;
}
int main(){
    char s1[1005],s2[1005];
    gets(s1);
    gets(s2);
    printf("%d",strcmp(s1,s2));
    return 0;
}

9.試題 演算法訓練 P0703 反置數

題目

題目鏈接

解題思路

我認為有至少兩種解題思路：

1. 按照題目給的程序進行模擬，這個程序其實也很簡單，直接就寫兩個函式就可以解決問題：
   一個用于去掉后綴0的函式以及一個用于把整數的數值反轉的函式，這個方法非常好寫，也很快，但如果數字很大就沒法了，
2. 通過字串模擬加法程序，恰好字串大數加減的正常程序就是先反轉再加減的，而這題正好就是需要反向加減，所以完全可以用字串模擬大數加減解決，但我們需要對字串前后的0進行處理，否則不符合列印要求，（正好后面還有大數加減的題目，我就偷個懶用它了）

解題代碼

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

char sum[20];

//TODO 處理尾部的0，長度引數傳入指標，方便同時修改長度
void solveBack(char *s, int *l) {
    int cnt = 0;
    int n = l == NULL ? strlen(s) : *l;
    while (n - cnt - 1 >= 0) {
        if (s[n - cnt - 1] == '0') {
            s[n - cnt - 1] = 0;
            if (l != NULL)(*l)--;
        } else break;
        cnt++;
    }
}

//TODO 處理前面的0
char *solvePre(char *s, int *l) {
    int cnt = 0;
    int n = l == NULL ? strlen(s) : *l;
    while (cnt < n) {
        if (s[cnt] == '0') {
            s[cnt] = 0;
            if (l != NULL)(*l)--;
        } else break;
        cnt++;
    }
    return s + cnt;
}

int main() {
    char s1[10], s2[10];
    scanf("%s %s", s1, s2);
    //TODO 直接的大數相加即可
    int n1 = strlen(s1), n2 = strlen(s2);
    solveBack(s1, &n1);
    solveBack(s2, &n2);
    int maxS = n1 > n2 ? n1 : n2;
    int up = 0;
    int a1, a2;
    int index = 0;
    //TODO 大數加減的邏輯部分
    for (int i = 0; i < maxS; ++i) {
        a1 = i < n1 ? s1[i] - '0' : 0, a2 = i < n2 ? s2[i] - '0' : 0;
        int base = up + a1 + a2;
        up = base / 10;
        sum[index++] = base % 10 + '0';
    }
    while (up) {
        sum[index++] = up % 10 + '0';
        up /= 10;
    }
    sum[index] = 0;
    solveBack(sum, NULL);
    char *ret = solvePre(sum, NULL);
    puts(ret);
    return 0;
}

10.試題 演算法訓練 P0704 滿足條件的回文數和質數

題目

題目鏈接

解題思路

分離連個邏輯函式即可簡單實作功能：

1. 判斷是否為質數，
2. 判斷是否是回文數，

這兩個數的判斷都有多種方法進行，這里不過多贅述，

我用的都是最質樸的方法進行判斷，

解題代碼

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

bool isPrim(int n){
    if(n<2)return false;
    if(n==2)return true;
    if(n%2==0)return false;//為偶數比不可能為質數
    for (int i = 2; i*i <= n ; ++i) {
        if(n%i==0)
            return false;
    }
    return true;
}
bool isPal(int n){
    char s[10];
    sprintf(s,"%d",n);
    int l=0,r = strlen(s)-1;
    while (l<r){
        if(s[l]!=s[r])
            return false;
        l++;
        r--;
    }
    return true;
}
int main() {
    int min,max;
    scanf("%d %d",&min,&max);
    for (int i = min; i < max; ++i) {
        if(isPal(i)&&isPrim(i))
            printf("%d ",i);
    }
    return 0;
}

11.試題 演算法訓練 P0601 實作洗掉字符函式

題目

題目鏈接

解題思路

如果這題只是為了解題，那么很簡單，直接碰到這個字符就不列印即可，

如果是為了實作這個洗掉給定字符的函式功能，我有兩種思路：

1. 如果不創建新的記憶體進行洗掉，那么最直觀的方法就是一個一個字符的來進行洗掉操作，如果等于這個字符，那么直接進行一輪洗掉后的平移，時間復雜度較高，最壞為O(n^2)，當然可以優化為O(n)級別的，那就是我們采取給整個陣列賦值的思路，從左到右掃描賦值，如果等于對應字符，那么就跳過不賦值，最后在后面加個 ‘\0’ 即可，
2. 如果創建新記憶體進行，那么很簡單的就可以實作O(n)級別的，

解題代碼

解法一：只為解題的解題(適合真正比賽時)

#include <stdio.h>
int main() {
    char s[100];
    gets(s);
    char target = getchar();
    int i = 0;
    while (s[i]!=0){
        if(s[i]!=target){
            putc(s[i],stdout);
        }
        i++;
    }
    return 0;
}

解法二：從左到右的掃描更新法 O(n) （使用于面試官問你后，你的回答）

#include <stdio.h>

int main() {
    char s[100];
    gets(s);
    char target = getchar();
    int i = 0;
    //TODO 洗掉邏輯處理
    int index = 0;
    while (s[i]!=0){
        if(s[i]!=target){
            s[index++] = s[i];
        }
        i++;
    }
    s[index] = 0;
    //
    puts(s);
    return 0;
}

12.試題 演算法訓練 P1103 復數加減乘除類的設計

題目

編程實作兩個復數的運算，設有兩個復數 和 ，則他們的運算公式為：

要求：（1）定義一個結構體型別來描述復數，
　　（2）復數之間的加法、減法、乘法和除法分別用不用的函式來實作，
　　（3）必須使用結構體指標的方法把函式的計算結果回傳，
　　說明：用戶輸入：運算子號(+,-,*,/) a b c d.
　　輸出：a+bi，輸出時不管a,b是小于0或等于0都按該格式輸出，輸出時a,b都保留兩位，

輸入：

• 2.5 3.6 1.5 4.9
  輸出：
• 1.00±1.30i

解題思路

• 把高中那套負數加減乘除的公式套用進去即可！

這里C的話可用函式式的面向的物件實作，C++的話用一個類多載所有的運算子即可，

解題代碼

#include <bits/stdc++.h>
struct complex{
    double x,y;
    complex(double x,double y):x(x),y(y){}
    complex():x(0),y(0){}
    //TODO overload operator+ to redefine +
    complex operator+(complex& src){
        double tx = x+src.x;
        double ty = y+src.y;
        return complex(tx,ty);
    }
    //TODO overload operator- to redefine -
    complex operator-(complex& src){
        double tx = x - src.x;
        double ty = y- src.y;
        return complex(tx,ty);
    }
    //TODO overload operator* to redefine *
    complex operator*(complex& src){
        double tx = x*src.x - y*src.y;
        double ty = x*src.y + y*src.x;
        return complex(tx,ty);
    }
    //TODO overload operator* to redefine /
    complex operator/(complex& src){
        double t = src.x*src.x + src.y*src.y;
        double tx = (x*src.x+y*src.y)/t;
        double ty =(src.x*y-x*src.y)/t;
        return complex(tx,ty);
    }
};

int main() {
    char op;double x1,y1,x2,y2;
    scanf("%c %lf %lf %lf %lf",&op,&x1,&y1,&x2,&y2);
    complex a(x1,y1);
    complex b(x2,y2);
    complex res;
    //TODO What operations are performed according to your choice
    switch (op) {
        case '+':
            res = a+b;
            break;
        case '-':
            res = a-b;
            break;
        case '*':
            res = a*b;
            break;
        case '/':
            res = a/b;
            break;
    }
    //TODO print the result by two decimal places
    printf("%.2lf+%.2lfi",res.x,res.y);
    return 0;
}

13.試題 演算法訓練 洗掉陣列零元素

題目

題目鏈接

解題思路

這和之前的洗掉字符的題目沒有任何的本質區別，就是直接通過一個指標從左到右遍歷，而另一個指標從左到右更新，

代碼即是思路，

解題代碼

#include <bits/stdc++.h>
//TODO 洗掉陣列指定的值，然后洗掉后的陣列長度
int remove_nums(int* nums,int len,int val){
    int index = 0;
    int i = 0;
    while (i<len){
        if(nums[i]!=val){
            nums[index++] = nums[i];
        }
        i++;
    }
    return index;
}
int main() {
    int n;
    std::cin>>n;
    int nums[n];
    for (int i = 0; i < n; ++i) {
        std::cin>>nums[i];
    }
    int res_len = remove_nums(nums,n,0);
    printf("%d\n",res_len);
    for (int j = 0; j < res_len; ++j) {
        printf("%d ",nums[j]);
    }
    return 0;
}

14.試題 演算法訓練 大整數加法

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

任意輸入兩個正整數a,b，求兩數之和，（注：本題會輸入超過32位整數限制的大整數）

樣例輸入

4611686018427387903 4611686018427387903

樣例輸出

9223372036854775806

資料規模和約定

1=<a,b<=4611686018427387903

解題思路

由于前面都用到了大整數加法，所以直接拿前面的代碼來用了，具體實作思路也很簡單，就是一個加法的模擬程序，一般來說三步走：

1. 把陣列逆置，
2. 用另一個陣列計算答案，注意要分進位和本位進行模擬運算，
3. 如果最后的進位不為0，則繼續往前加法，

解題代碼

#include <stdio.h>
#include <string.h>
#include <algorithm>
//TODO 洗掉陣列指定的值，然后洗掉后的陣列長度
char sum[50] = {0};
void reverse(char* s,int len){
    int i = 0,j = len-1;
    while (i<j){
        std::swap(s[i],s[j]);
        i++;j--;
    }
}
int main() {
    char a[50],b[50];
    scanf("%s %s",a,b);
    //TODO 1.reverse
    int na = strlen(a);reverse(a,na);
    int nb = strlen(b);reverse(b,nb);
    //TODO 2.calculate
    int maxL = na>nb?na:nb;
    int up = 0,base,ta,tb,i;
    for (i = 0; i < maxL; ++i) {
        ta = i<na?a[i]-'0':0;
        tb = i<nb?b[i]-'0':0;
        base = ta+tb+up;
        up = base/10;
        sum[i] = base%10+'0';
    }
    while (up){
        sum[i++] = up%10+'0';
        up /= 10;
    }
    //TODO Print
    for (int j = i-1; j >=0 ; --j) {
        putc(sum[j],stdout);
    }
    return 0;
}

15.試題 演算法訓練 最小乘積(基本型)

題目

資源限制

時間限制：1.0s 記憶體限制：512.0MB

問題描述

給兩組數，各n個，
　　請調整每組數的排列順序，使得兩組資料相同下標元素對應相乘，然后相加的和最小，要求程式輸出這個最小值，
　　例如兩組數分別為:1 3　　-5和-2 4 1

那么對應乘積取和的最小值應為：
　　(-5) * 4 + 3 * (-2) + 1 * 1 = -25

輸入格式

第一個行一個數T表示資料組數，后面每組資料，先讀入一個n，接下來兩行每行n個數，每個數的絕對值小于等于1000，
　　n<=8,T<=1000

輸出格式

一個數表示答案，

樣例輸入

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

樣例輸出

-25
6

解題思路

根據題目意思，很明顯，我們把陣列的位置，一個排成從小到大，一個排成從大到小，對應相乘即可，

解題代碼

#include <iostream>
#include <algorithm>
int nums1[10];
int nums2[10];
int main() {
    int n;
    std::cin>>n;
    //TODO 思路：一個陣列從小到大排序，一個陣列從大到小排序，最后輸出它們的對應乘積即可
    while (n--){
        int c;
        std::cin>>c;
        for (int i = 0; i < c; ++i) {
            std::cin>>nums1[i];
        }
        std::sort(nums1,nums1+c);
        for (int i = 0; i < c; ++i) {
            std::cin>>nums2[i];
        }
        std::sort(nums2,nums2+c,std::greater<int>());
        int sum = 0;
        for (int i = 0; i < c; ++i) {
            sum += nums1[i]*nums2[i];
        }
        std::cout<<sum<<'\n';
    }
    return 0;
}

16.試題 演算法訓練 矩陣運算

題目

資源限制

時間限制：1.0s 記憶體限制：512.0MB

問題描述

給定一個n*n的矩陣A，求A+AT的值，其中AT表示A的轉置，

輸入格式

輸入的第一行包含一個整數n，1<=n<=100，
　　接下來n行，每行n個整數，表示A中的每一個元素，每個元素的絕對值不超過10000，

輸出格式

輸出n行，每行n個整數，用空格分隔，表示所示的答案，

樣例輸入

3
1 2 3
4 5 6
7 8 9

樣例輸出

2 6 10
6 10 14
10 14 18

解題思路

這里直接用二維陣列存下矩陣然后得到另一個轉置矩陣再相加即可，

我一般碰到這類關于某種資料型別的運算，我喜歡把它們抽象為類，然后再進行計算，所以我這題是設計了一個mat類，里面多載了加法等，

解題代碼

#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
struct Mat{
    int** nums;
    int n;
    Mat(int** src,int n):nums(src),n(n){}
    Mat(int n):n(n){
        nums = new int*[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = new int[n];
            //TODO 把輸入程序放到初始化里面來了
            for (int j = 0; j < n; ++j) {
                cin>>nums[i][j];
            }
        }
    }
    Mat get_transform(){
        int** t_nums = new int*[n];
        for (int i = 0; i < n; ++i) {
            t_nums[i] = new int[n];
            for (int j = 0; j < n; ++j) {
                t_nums[i][j] = nums[j][i];//TODO 轉置賦值程序
            }
        }
        return Mat(t_nums,n);
    }
    //TODO 多載加法
    Mat& operator+(Mat& src){
        assert(src.n==n&&nums!=NULL&&src.nums!=NULL);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                nums[i][j] += src.nums[i][j];
            }
        }
        return *this;
    }
    void print(){
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                printf("%d ",nums[i][j]);
            }
            putc('\n',stdout);
        }
    }
};
int main() {
    int n;
    cin>>n;
    Mat a(n);
    Mat b = a.get_transform();
    (a+b).print();
    return 0;
}

17.試題 演算法訓練 百雞百錢

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

我國古代數學家張丘建在《算經》一書中提出的數學問題：雞翁一值錢五，雞母一值錢三，雞雛三值錢一，百錢買百雞，問雞翁、雞母、雞雛各幾何？

輸出格式

滿足條件的雞翁、雞母和雞雛的只數，中間空格隔開，每種情況輸出到一行，
　　例如 ：
　　0 25 75
　　4 18 78

解題分析

純純的用代碼解方程，分析草稿如下圖：

解題代碼

#include <iostream>
using namespace std;

int main() {
    for (int i = 0; i <= 14 ; ++i) {
        for (int j = 0; j <= 25; ++j) {
            if(7*i+4*j==100){
                printf("%d %d %d\n",i,j,100-i-j);
            }
        }
    }
    return 0;
}

18.試題 演算法訓練 資料傳遞加密

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

某個公司傳遞資料，資料是四位整數，在傳遞程序中需要進行加密的，加密規則如下：每位數字都加上5,然后除以10的余數代替該位數字，再將新生成資料的第一位和第四位交換，第二位和第三位交換，要求輸入4位整數，輸出加密后的4位整數，比如：輸入一個四位整數1234，則輸出加密結果為9876，

樣例輸入

1234

樣例輸出

9876

題目決議

• 只需要進行兩個程序：

1. +5除以10得到余數替換每一位，
2. 交換資料（第一位和第四位交換，第二位和第三位交換），

解題代碼

#include <iostream>
#include <cstring>
using namespace std;
//TODO 替換操作
void replace(char* s){
    int i =0,data;
    while (s[i]!=0){
        data = s[i] - '0';
        s[i] = (data+5)%10 + '0';
        i++;
    }
}
//TODO 交換操作
void swap(char* s){
    int i=0,j = strlen(s)-1;
    char tmp;
    while (i<j){
        tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        i++,j--;
    }
}

int main() {
    char s[10];
    gets(s);
    replace(s);
    swap(s);
    puts(s);
    return 0;
}

二、演算法提高

19. 試題 演算法提高 心形

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

根據給出的最大寬度，輸出心形（注意空格，行末不加多余空格），

輸入格式

一行一個整數width，表示最寬的一行中有多少個“*”，

輸出格式

若干行表示對應心形，注意為讓選手更清晰觀察樣例，樣例輸出中用“-”表示空格，請選手在提交的程式中不要輸出“-”，

樣例輸入

13

樣例輸出

資料規模和約定

width總是4的倍數加一，且width >= 13，

題目決議

這種列印型別題目要學會逐一找規律剖析！

在我的寫法里面，這個心形能夠解分為三個部分：(如下圖)

首先我們需要確認一個元素的組成長度！本題輸入的就是第二部分的長度，比如樣例的13，而我們發現每個部分由兩個字符構成，所以我們下面的討論都是以兩個字符為單位，而拆分成不同的元素種類的話也只有兩種：1. " "(兩個空格)稱為空白元素 2. " *"(一個空格一個星)稱為星元素，

以下所有用到的 n 均表示輸入的變數值，

一、第一部分

關于第一部分我還是分為三個部分進行每一行的列印：

1. 左邊的空白元素：它的起始長度很明顯就是第一部分的深度，而第一部分的深度 = ((n-1)/2)/2，
   后續這部分元素都以每次遞減一個的趨勢，
2. 中間的空白元素：它的起始長度應該從第一部分的底層往上推，你發現從最底層長度為1開始，每層+2，
   *所以起始元素長度為：1+(deep-1)2 ，而后續以每次遞減2個的趨勢，
3. 星元素：這個算是兩個部分并作一個部分，因為這兩個部分沒有任何區別，一個在左邊空白和中間空白的中間，而另一個在最右邊，從1個開始往下遞增，每次遞增兩個，

二、第二部分

第二部分就沒有那么多彎彎繞繞了，直接 n 是多少就列印多少個星，

三、第三部分

第三部分分為兩部分：

1. 左邊的空白元素：從1開始往下遞增，
2. 右邊的星元素：從n-1往下遞減兩個元素，

當星元素遞減為1個的時候結束！

解題代碼

AC圖片：

#include <iostream>
using namespace std;
//TODO 用于列印n個“  ”
void print1(int n){
    for (int i = 0; i < n; i++)
    {
        putc(' ',stdout);
        putc(' ',stdout);
    }
}
//TODO 用于列印n個" *"
void print2(int n){
    for (int i = 0; i < n; i++)
    {
        putc(' ',stdout);
        putc('*',stdout);
    }
}

int main(){
    int n;cin >> n;
    int deep = (n-1)/4;
    int p1 = deep;
    int p2 = 1;
    int p3 = 1+2*(deep-1);
    //TODO 第一部分的列印
    for (int i = 0; i < deep; i++)
    {
        print1(p1);
        print2(p2);
        print1(p3);
        print2(p2);
        p1 -= 1;
        p2 += 2;
        p3 -= 2;
        putc('\n',stdout);
    }
    //TODO 第二部分列印：最簡單的純一行
    print2(n);
    putc('\n',stdout);
    //TODO 第三部分列印
    int n1 = 1,n2 = n-2;
    while (n2>=1){
        print1(n1);
        print2(n2);
        n1++;
        n2-=2;
        putc('\n',stdout);
    }
    return 0;
}

20.試題 演算法提高 字串查找

題目

資源限制

時間限制：1.0s 記憶體限制：512.0MB

問題描述

給定兩個字串a和b，查找b在a中第一次出現的位置，
　　如a=“hello world”，b=“world”時，b第一次出現是在a的第7個字符到第11個字符，按照C++的習慣，位置從0開始編號，所以b在a中第一次出現的位置為6，

輸入格式

輸入包括兩行，分別為兩個字串a和b，字串中可能含有空格，字串的長度不超過500，請注意讀入一行字串的方法，

輸出格式

輸出b在a中第一次出現的位置，如果b沒有在a中出現，則輸出-1，

樣例輸入

hello world
world

樣例輸出

6

樣例輸入

hello world
tsinsen

樣例輸出

-1

題目鏈接

題目決議

不知道是不是這道題的緣故，好像只能提交一個函式體內的代碼，不能提交完整代碼！

所以我都AC代碼如下所示：

int n = 0;while (b[n]!=0)n++;//計算b的長度
    int i=0,j;
    while (a[i]!=0){
        j = 0;
        while (b[j]!=0){
            if(a[i+j]!=b[j]){
                break;
            }
            j++;
        }
        if(j==n){
            return i;
        }
        i++;
    }
    return -1;

AC截圖：

解題代碼

其實本題我是想拿來練練kmp演算法的，奈何只能寫部分代碼塊進行提交，連函式都不能寫，所以只好作罷，

實際直接呼叫語言的內部函式庫的話，可以像下面這樣：

C version

#include <string.h>
#include <stdio.h>
int main() {
    char s1[100],s2[100];
    gets(s1);
    gets(s2);
    char* res = strstr(s1,s2);
    if(res==NULL){
        printf("-1");
    }
    else{
        printf("%d",res-s1);
    }
   return 0;
}

cpp version

#include <iostream>
#include <string>
int main() {
   using namespace std;
   string s1,s2;
   getline(cin,s1);
   getline(cin,s2);
   cout<<int(s1.find(s2));
   return 0;
}

21.試題 演算法提高 校門外的樹

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米，我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數 軸上的每個整數點，即0，1，2，……，L，都種有一棵樹，
　　由于馬路上有一些區域要用來建地鐵，這些區域用它們在數軸上的起始點和終止點表示，已 知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分，現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走，你的任務是計算將這些樹 都移走后，馬路上還有多少棵樹，

輸入格式

輸入檔案的第一行有兩個整數L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開，接下來的M行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點 和終止點的坐標，

輸出格式

輸出檔案包括一行，這一行只包含一個整數，表示馬路上剩余的樹的數目，

樣例輸入

500 3
150 300
100 200
470 471

樣例輸出

298

資料規模和約定

對于20%的資料，區域之間沒有重合的部分；
　　對于其它的資料，區域之間有重合的情況，

題目鏈接

解題思路

這題藍橋杯平時訓練的時候，只能說是寫爛了，，這題本可以按照首尾區間 =1 +1 的方式來處理，但是由于本題是洗掉區間內的元素后不能重復洗掉的情況，所以目前我只能想到用直接暴力的覆寫法😂

直接暴力的覆寫：

每次給定區間后，我們就把這個區間的樹砍掉，如果樹已經被砍（值為0），則沒變化，

解題代碼

#include <bits/stdc++.h>

void solve(bool & t){
    if(t==1)t = 0;
}
int main()
{
    using namespace std;
    int n,m,l,r;
    cin>>n>>m;
    bool nums[n+1];
    fill(nums,nums+n+1,1);
    while (m--){
        cin>>l>>r;
        for_each(nums+l,nums+r+1,solve);
    }
    cout<<accumulate(nums,nums+n+1,0);
    return 0;
}

22.試題 演算法提高 第二大整數

題目

資源限制

時間限制：1.0s 記憶體限制：512.0MB

問題描述

撰寫一個程式，讀入一組整數（不超過20個），當用戶輸入0時，表示輸入結束，然后程式將從這組整數中，把第二大的那個整數找出來，并把它列印出來，說明：（1）0表示輸入結束，它本身并不計入這組整數中，（2）在這組整數中，既有正數，也可能有負數，（3）這組整數的個數不少于2個，
　　輸入格式：輸入只有一行，包括若干個整數，中間用空格隔開，最后一個整數為0，
　　輸出格式：輸出第二大的那個整數，
　　輸入輸出樣例

樣例輸入

5 8 -12 7 0

樣例輸出

7

題目鏈接

解題分析

如果僅僅只是為了解題，那么這題最簡單的方式肯定是直接存下資料排序即可，

當然這道題的正統解法應該是，通過兩個變數進行更新即可，

解題代碼

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int first=INT_MIN,second=INT_MIN,val;
    cin>>val;
    while (val!=0){
        if(val>first){//TODO 有型別于傳遞性的關系，所以注意傳遞下去
            second = first;
            first = val;
        }else if(val>second){
            second = val;
        }
        cin>>val;
    }
    cout<<second;
    return 0;
}

三、歷屆試題

23.四平方和【第七屆】【省賽】【C組】

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

四平方和定理，又稱為拉格朗日定理：
　　每個正整數都可以表示為至多4個正整數的平方和，
　　如果把0包括進去，就正好可以表示為4個數的平方和，

比如：
　　5 = 0^2 + 0^2 + 1^2 + 2^2
　　7 = 1^2 + 1^2 + 1^2 + 2^2
　　（^符號表示乘方的意思）

對于一個給定的正整數，可能存在多種平方和的表示法，
　　要求你對4個數排序：
　　0 <= a <= b <= c <= d
　　并對所有的可能表示法按 a,b,c,d 為聯合主鍵升序排列，最后輸出第一個表示法

程式輸入為一個正整數N (N<5000000)
　　要求輸出4個非負整數，按從小到大排序，中間用空格分開

例如，輸入：
　　5
　　則程式應該輸出：
　　0 0 1 2

再例如，輸入：
　　12
　　則程式應該輸出：
　　0 2 2 2

再例如，輸入：
　　773535
　　則程式應該輸出：
　　1 1 267 838

資源約定：
　　峰值記憶體消耗（含虛擬機） < 256M
　　CPU消耗 < 3000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多余內容，

所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
　　注意：不要使用package陳述句，不要使用jdk1.7及以上版本的特性，
　　注意：主類的名字必須是：Main，否則按無效代碼處理，

題目決議

• 讀完題后，很多人肯定馬上能想到用四個for回圈的暴力法，沒錯，根據題意，這題就是可以用暴力法解，，，

并對所有的可能表示法按 a,b,c,d 為聯合主鍵升序排列，最后輸出第一個表示法，

對于以上這句話，你可以理解為，題目要你從四個for回圈的正常順序里面找到第一個符合要求的答案，很多人可能就是沒搞清楚這個說明的關鍵所在，所以直接能用下面這段代碼暴力秒了，，，當然也不是直接的一個判斷就秒，而需要對每層回圈進行判斷是否已經超出表示范圍，然后排除，

#include<cstdio>
#include<cmath>
#define LL long long 
using namespace std;
LL n;
int main(){
	scanf("%lld",&n);
	LL m = sqrt(n);//確定范圍 
	for(LL i=0 ;i<=m ;i++){
		if(i*i<=n)
		for(LL j=i ;j<=m ;j++){
			if(i*i+j*j<=n)
			for(LL k=j ;k<=m ;k++){
				if(i*i+j*j+k*k<=n)
				for(LL x=k ;x<=m ;x++){
					if((i*i+j*j+k*k+x*x)==n){
						printf("%lld %lld %lld %lld\n",i,j,k,x);
						return 0;
					}
				}
			}
		}
	}
	
	return 0;
}

當然這樣暴力的方法，當然不是這道題的真正意義，雖然也能夠通過

像這種幾個for回圈找某個數的題目，大概有以下三類優化方法：

1. 二分搜索優化其中一層for回圈
2. 雙指標優化兩層for回圈（只適用于不重復下標選擇的組合，所以不適用本題）
3. 哈希表提前存盤答案進行優化（只適用于下標選擇可以重復的情況，所以正好適用于本題）

很明顯我們如果想真正做這類題，正統的方法應該是第三種，我們需要一個哈希表映射值和下標來方便拿取答案，我們可以用STL里面的哈希表用int映射pair是可以的，但效率不夠好，由于本題的資料范圍其中的值不會太大，所以完全可以用最原始的陣列充當哈希表來使用，平時我們在競賽題中你用哈希表來映射多元的東西，能不用STL就不用，因為查找和遍歷的效率太慢了，

解題代碼

兩個陣列充當哈希表進行提前存盤映射，來把4個for優化為2個for，

#include <bits/stdc++.h>
using namespace std;
int x1[5000000],x2[5000000];
int main()
{
    memset(x1,-1,sizeof(x1));
    int n;
    cin>>n;
    for (int i = 0; i*i <= n; ++i) {
        for (int j = 0; j*j <= n; ++j) {
         //TODO 小細節：先判斷是否大于n在進行陣列訪問(否則可能會產生下標越界訪問)
            if((i*i+j*j)<=n&&x1[i*i+j*j]==-1){
                x1[i*i+j*j] = i;
                x2[i*i+j*j] = j;
            }
        }
    }
    for (int i = 0; i*i <= n; ++i) {
        for (int j = 0; j*j <= n; ++j) {
            int target = n-(i*i+j*j);
            if(target<0) break;
            if(x1[target]!=-1){
                printf("%d %d %d %d",i,j,x1[target]>x2[target]?x2[target]:x1[target],
                        x2[target]>x1[target]?x2[target]:x1[target]);
                return 0;
            }
        }
    }
    return 0;
}

提交代碼的效率：

24.歷屆真題 錯誤票據【第四屆】【省賽】【B組】

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

某涉密單位下發了某種票據，并要在年終全部識訓，

每張票據有唯一的ID號，全年所有票據的ID號是連續的，但ID的開始數碼是隨機選定的，

因為作業人員疏忽，在錄入ID號的時候發生了一處錯誤，造成了某個ID斷號，另外一個ID重號，

你的任務是通過編程，找出斷號的ID和重號的ID，

假設斷號不可能發生在最大和最小號，

要求程式首先輸入一個整數N(N<100)表示后面資料行數，
　　接著讀入N行資料，
　　每行資料長度不等，是用空格分開的若干個（不大于100個）正整數（不大于100000）
　　每個整數代表一個ID號，

要求程式輸出1行，含兩個整數m n，用空格分隔，
　　其中，m表示斷號ID，n表示重號ID

例如：
　　用戶輸入：
　　2
　　5 6 8 11 9
　　10 12 9

則程式輸出：
　　7 9

再例如：
　　用戶輸入：
　　6
　　164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
　　172 189 127 107 112 192 103 131 133 169 158
　　128 102 110 148 139 157 140 195 197
　　185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
　　149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
　　113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119

則程式輸出：
　　105 120

資源約定：
　　峰值記憶體消耗 < 64M
　　CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多余內容，

所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，

注意: main函式需要回傳0
　　注意: 只使用ANSI C/ANSI C++ 標準，不要呼叫依賴于編譯環境或作業系統的特殊函式，
　　注意: 所有依賴的函式必須明確地在源檔案中 #include ， 不能通過工程設定而省略常用頭檔案，

提交時，注意選擇所期望的編譯器型別，

題目鏈接

題目決議

讀完題后，我們發現，它的輸入，我們需要格外注意一下，因為是以行輸入，而每行要輸入的資料是多少也沒告訴你，所以很多人可能會被這個給難到，而實際的解題程序并不復雜，只需要創建一個陣列用它的下標將每個你輸入的值進行記錄，然后如果重復記錄則就是第二個輸出，在輸入的途中，你將他的最小值和最大值給記錄下來，最后再遍歷一遍陣列即可得到中間缺的那個數！

具體陣列的細節操作：

1. 我為了節省空間用的是位陣列bitset，
2. 為了防止輸入的數字有負數，我們對輸入值和陣列下標的映射加一個偏移量，使得結果為正數，

具體的輸入操作細節：

1. 我用的getline得到每一行的資料，然后存放到stringsteam類里面，
2. 通過stringstream類再次進行每一行資料的輸入操作，
3. 最后需要注意的兩個細節：
   一、cin輸入的時候在輸入緩沖區會留下一個換行符沒有讀取 '\n'，而getline對于資料讀取是碰到換行符就結束，所以在用getline讀取一行之前我們需要掉用cin.ignore()把換行符給處理掉，否則會導致getline無法讀入資料！
   二、stringsteam類每次讀入且完全被寫出的時候，需要重新呼叫clear()來重繪緩沖區才能夠進行下一次的讀入寫出！

解題代碼

解題效率：

#include <bits/stdc++.h>
using namespace std;
bitset<1000000>nums; //TODO bitset兼顧記憶體和性能的利器
int gap = 500000;   //TODO 取的偏移量
int main()
{
    int a,b;
    ios::sync_with_stdio(false);//TODO 取消和stdio的緩沖區同步
    int n;cin>>n;
    cin.ignore();       //TODO 清除緩沖區'\n'
    int nmax=INT_MIN,nmin=INT_MAX;
    stringstream ss;    //TODO 用于存下一行資料進行輸入
    string s;          
    while (n--){
        int val;
        getline(cin,s);//TODO 讀取一行資料放入s
        ss<<s;              //TODO 將s里的資料輸入到ss
        while(ss>>val){     //TODO ss開始輸入
            if(!nums[val+gap])
                nums[val+gap] = 1;
            else{
                b = val;
            }
            nmax = max(nmax,val);
            nmin = min(nmin,val);
        }
        ss.clear();         //TODO 細節clear，因為讀完后在ss內部留下結束信號
    }
    for (int i = nmin; i <= nmax; ++i) {
        if(!nums[i]){
            a=i;
            break;
        }
    }
    cout<<a<<' '<<b;
    return 0;
}

25. 歷屆真題 密碼發生器【第三屆】【省賽】【本科組】

題目

資源限制

時間限制：1.0s 記憶體限制：256.0MB

在對銀行賬戶等重要權限設定密碼的時候，我們常常遇到這樣的煩惱：如果為了好記用生日吧，容易被破解，不安全；如果設定不好記的密碼，又擔心自己也會忘記；如果寫在紙上，擔心紙張被別人發現或弄丟了…

這個程式的任務就是把一串拼音字母轉換為6位數字（密碼），我們可以使用任何好記的拼音串(比如名字，王喜明，就寫：wangximing)作為輸入，程式輸出6位數字，

變換的程序如下：

第一步. 把字串6個一組折疊起來，比如wangximing則變為：
　　wangxi
　　ming

第二步. 把所有垂直在同一個位置的字符的ascii碼值相加，得出6個數字，如上面的例子，則得出：
　　228 202 220 206 120 105

第三步. 再把每個數字“縮位”處理：就是把每個位的數字相加，得出的數字如果不是一位數字，就再縮位，直到變成一位數字為止，例如: 228 => 2+2+8=12 => 1+2=3

上面的數字縮位后變為：344836, 這就是程式最終的輸出結果！

要求程式從標準輸入接收資料，在標準輸出上輸出結果，

輸入格式為：第一行是一個整數n（<100），表示下邊有多少輸入行，接下來是n行字串，就是等待變換的字串，
　　輸出格式為：n行變換后的6位密碼，

例如，輸入：
　　5
　　zhangfeng
　　wangximing
　　jiujingfazi
　　woaibeijingtiananmen
　　haohaoxuexi

則輸出：
　　772243
　　344836
　　297332
　　716652
　　875843，

題目鏈接

題目決議

非常簡單的模擬題，，

按照下面兩步走即可：

1. 以6為長度進行串聯，直接以6為長度取模相加即可，
2. 縮位處理函式，簡單的不斷各位相加即可，

解題代碼

解題效率：

#include <bits/stdc++.h>
using namespace std;
int res[6]; //TODO 所有的6位數字全用它來存

inline int handle(int x){//TODO 處理每個數字最后變成一位數
    if(x<10)
        return x;
    int sum = 0;
    while (x){
        sum += x%10;
        x /= 10;
    }
    return handle(sum);
}
//TODO 處理每個字串
void solve(string& s){
    memset(res,0,sizeof(res));
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        res[i%6] += s[i];
    }
    for (int i = 0; i < 6; ++i) {
        cout<<handle(res[i]);//列印答案
    }
    cout<<'\n';
}
int main()
{
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    string s;
    while(n--){
        cin>>s;
        solve(s);
    }
    return 0;
}