1.二进制数（10分）
题目描述：请编写一个程序，该程序对于读入的每一个正整数 n n n，打印出 n n n对应的二进制数字中所有 1 1 1的位置。二进制中最低位的位置为 0 0 0。
例如，正整数 13 13 13的二进制表示 ( 1101 ) (1101) (1101)中 1 1 1的位置是 0 0 0， 2 2 2， 3 3 3。
输入格式：测试数据包括多组数据。测试数据的第一行是一个正整数 d d d ( 1 ≤ d ≤ 10 ) (1≤d\le 10) (1≤d≤10)，表示测试数据的数量。其后有 d d d行，每一行是一个正整数 n n n ( 1 ≤ n ≤ 1 0 6 ) (1≤n≤10^6) (1≤n≤106)。
输出格式：输出的结果应当有 d d d行，对于每组测试数据，输出一行，是该组测试数据处理的结果。第 i i i行 ( 1 ≤ i ≤ d ) (1≤i\le d) (1≤i≤d)，应当包含该数据的二进制表示的 1 1 1的位置，位置是按递增顺序排序，两个位置中间用空格隔开。

输入样例：

1
13

输出样例：

0 2 3

遍历二进制中的每一位，输出为 1 1 1的每个位置。

#include<bits/stdc++.h>

using namespace std;
int T, x;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &x);
        int t = log2(x);
        for (int i = 0; i <= t; i++)
            if ((x >> i) & 1)
                printf("%d ", i);
        puts("");
    }
    return 0;
}

2.Quicksum(20分)
题目描述：checksum是一种扫描一个数据包并返回一个数值的算法。其思路在于，如果数据包被修改过，那么，checksum计算得到的值也会立即变化。所以，checksum常常用于检查数据传输的错误、证实文件内容的完整性及其它需要检查数据不被修改的场合。
在本题中，你将实现一个简单的checksum算法，即Quicksum算法。数据包的内容仅允许包含大写字母和空格，并且以大写字母开始和结束。空格和字母可以出现在任何其它的位置中，连续的空格也是允许的。
Quicksum的计算过程是计算数据包中每个字符的位置与该字符的值的乘积之和。空格的值为 0 0 0，字母的值就是它在字母表中的位置。A的值为 1 1 1，B的值为 2 2 2，以此类推，Z的值为 26 26 26。下面的两个例子是求“ACM”和“MID CENTRAL”的Quicksum值：

ACM:1*1+3*2+3*13=46
MID CENTRAL:1*13+2*9+3*4+4*0+5*3+6*5+7*14+8*20+9*18+10*1+11*12=650

输入格式：测试数据包括多组数据。每一行是一个字符串，表示一个数据包。每个数据包不能以
空格开始或结束，包含 1 ∼ 255 1\sim 255 1∼255个字符。输入数据的最后一行，是“#”，表示输入数据结束。
输出格式：对于每组测试数据，输出一行，输出对应数据包的Quicksum值。

输入样例：

ACM
MID CENTRAL
#

输出样例：

46
650

按照题目描述模拟即可。

#include<bits/stdc++.h>

using namespace std;

string a;

int main() {
    while (getline(cin, a), a[0] != '#') {
        int len = a.size(), ans = 0;
        for (int i = 0; i < len; i++) {
            if (a[i] == ' ')continue;
            ans += (a[i] - 'A' + 1) * (i + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

3.有多少个Fibonacci数?(30分)
题目描述：Fibonacci数的定义如下：
F 1 = 1 F_1=1 F1​=1
F 2 = 2 F_2=2 F2​=2
F n = F n − 1 + F n − 2   ( n ≥ 3 ) F_n=F_{n-1}+F_{n-2}\ (n ≥ 3) Fn​=Fn−1​+Fn−2​ (n≥3)
给出两个整数 a a a和 b b b，计算在区间 [ a ， b ] [a，b] [a，b]中有多少个Fibonacci数。
输入格式：测试数据包括多组数据。每组测试用例包含两个非负整数 a a a和 b b b，其中 a ≤ b ≤ 1 0 100 a≤b\le 10^{100} a≤b≤10100。输入以 a = b = 0 a=b=0 a=b=0结束。
输出格式：对于每组测试数据，输出一行，输出满足 a ≤ F i ≤ b a\le F_i≤b a≤Fi​≤b的Fibonacci数 F i F_i Fi​的数目。

输入样例：

10 100
1234567890 9876543210
0 0

输出样例：

5
4

由于小于等于 1 0 100 10^{100} 10100的Fibonacci数只有 474 474 474个，因此可以先将前 474 474 474个Fibonacci数打表，然后对于每个询问统计位于该区间的Fibonacci数的数量。由于数较大，需要用大数模板。

#include<bits/stdc++.h>

#define ll long long
using namespace std;

struct BigInt {
    const static ll mod = 1e18;
    const static int DLEN = 18;
    ll a[8];
    int len;

    BigInt() { memset(a, 0, sizeof(a)), len = 1; }

    BigInt(ll v) {
        memset(a, 0, sizeof(a)), len = 0;
        do { a[len++] = v % mod, v /= mod; } while (v);
    }

    BigInt(const char *s) {
        memset(a, 0, sizeof(a));
        int L = strlen(s);
        len = L / DLEN;
        if (L % DLEN) len++;
        int index = 0;
        for (int i = L - 1; i >= 0; i -= DLEN) {
            ll t = 0;
            int k = i - DLEN + 1;
            if (k < 0) k = 0;
            for (int j = k; j <= i; j++)t = t * 10 + s[j] - '0';
            a[index++] = t;
        }
    }

    BigInt operator+(const BigInt &b) const {
        BigInt res;
        res.len = max(len, b.len);
        for (int i = 0; i <= res.len; i++)res.a[i] = 0;
        for (int i = 0; i < res.len; i++) {
            res.a[i] += ((i < len) ? a[i] : 0) + ((i < b.len) ? b.a[i] : 0);
            res.a[i + 1] += res.a[i] / mod, res.a[i] %= mod;
        }
        if (res.a[res.len] > 0) res.len++;
        return res;
    }

    int cmp(const BigInt &b) {
        if (len != b.len) return len > b.len ? 1 : -1;
        for (int i = len; i >= 0; i--)if (a[i] != b.a[i]) return a[i] > b.a[i] ? 1 : -1;
        return 0;
    }

    void output() {
        printf("%lld", a[len - 1]);
        for (int i = len - 2; i >= 0; i--)printf("%018lld", a[i]);
        puts("");
    }
} F[500];

char s1[105], s2[105];
BigInt L, R;

inline int solve() {
    int l = 1, r = 474, x = 475, y = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        int t = L.cmp(F[mid]);
        if (!t) {
            x = mid;
            break;
        }
        t == 1 ? (l = mid + 1) : (x = mid, r = mid - 1);
    }
    l = 1, r = 474;
    while (l <= r) {
        int mid = (l + r) / 2;
        int t = R.cmp(F[mid]);
        if (!t) {
            y = mid;
            break;
        }
        t == 1 ? (y = mid, l = mid + 1) : (r = mid - 1);
    }
    return y - x + 1;
}

int main() {
    F[0] = BigInt(1), F[1] = BigInt(1);
    for (int i = 2; i <= 474; i++)F[i] = F[i - 1] + F[i - 2];
    while (scanf("%s%s", s1, s2), s1[0] != '0' || s2[0] != '0') {
        L = BigInt(s1), R = BigInt(s2);
        printf("%d\n", solve());
    }
    return 0;
}

4.Bubble Sort(30分)
Problem Description:Jack loves sorting
Do you know what BUBBLE SORT is? Probably it was the first algorithm you learned during your life as a programmer.Do you believe that quick sort is always faster than bubble sort? Let’s analyze it in detail.
We formulate the algorithm as follow:
Algorithm B (Bubble Sort).Keys K i , … , K N K_i,\dots,K_N Ki​,…,KN​ are rearanged in place;after sorting is complete the key will be in order, K i ≤ ⋯ ≤ K N K_i\le\dots\le K_N Ki​≤⋯≤KN​.
B1.[Initialize BOUND.] Set BOUND = N =N =N.
B2.[Loop on j j j]Set t = 0 t=0 t=0.Perfom step B3 for j = 1 , 2 , … , j=1,2,\dots, j=1,2,…, BOUND − 1 -1 −1,and then go to step B4.(if BOUND = 1 =1 =1,this means go directly to B4.)
B3.[Compare/exchange K j : K j + 1 K_j:K_{j+1} Kj​:Kj+1​] If K j > K j + 1 K_j>K_{j+1} Kj​>Kj+1​,interchange K j K_j Kj​, and K j + 1 K_{j+1} Kj+1​ and set t = j t=j t=j.
B4.[Any change?] If t = 0 t=0 t=0, terminate the algorithm.Otherwise set BOUND = t =t =t and return to step B2.
Each execution from B2 to B4 is called a pass. For example there are 5 5 5 keys which are 4 , 2 , 1 , 5 , 3 4,2,1,5,3 4,2,1,5,3.
Then the actions are as follow:
Initial:4 2 1 5 3
Pass 1:2 1 4 3 5
Pass 2:1 2 3 4 5
Pass 3:1 2 3 4 5
Soit totally takes 3 3 3 passes to complete the sorting.
Now give a sequences of integers,Jack wants to knows how many passes are needed using bubble sort.
Input:
The first line is an integer T T T, the number of test cases.
Each case consists of two lines.The frst line is an integer N N N, 1 ≤ N ≤ 10000 1 ≤ N ≤ 10000 1≤N≤10000.The second line are N N N positive integer no more than 1000000 1000000 1000000,indicating the N N N keys to sort.
Output:
For each case,print the number of passes needed.
Sample Input:

2
5
1 2 3 4 5
5
4 2 1 5 3

Sample Output:

1
3

题目大意是给定一个序列，求冒泡法排序需要排几轮。
由于数据规模为 1 0 4 10^4 104，且有多组数据，因此直接模拟会超时。
观察发现，对于序列上的某个数 K i K_i Ki​，如果存在 j < i j<i j<i使得 K j > K i K_j>K_i Kj​>Ki​，那么必然在一轮排序中有一个比 K i K_i Ki​大的数从 K i K_i Ki​前面移到了 K i K_i Ki​后面，使得 K i K_i Ki​前面比 K i K_i Ki​大的数的数量减少 1 1 1。而序列排好序的标志是对于序列中的每一个数，其前面都不存在比该数大的数。因此所需轮数为每个数前比该数大的数的数量的最大值加 1 1 1。统计数量可以利用树状数组维护。
时间复杂度为 O ( T N log ⁡ 1000000 ) O(TN\log 1000000) O(TNlog1000000)。

#include<bits/stdc++.h>

#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 1e6 + 10;

struct BIT {
    int t[N];
    int n;

    inline int ask(int k) {
        int ans = 0;
        for (int i = k; i; i -= lowbit(i))ans += t[i];
        return ans;
    }

    inline void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i))t[i] += v;
    }

    inline void init(int _n) {
        n = _n, memset(t, 0, sizeof(int) * (n + 5));
    }
} tr;

int T, n;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        tr.init(1000000);
        int mx = 0;
        while (n--) {
            int x;
            scanf("%d", &x);
            mx = max(mx, tr.ask(1000000) - tr.ask(x));
            tr.add(x, 1);
        }
        printf("%d\n", mx + 1);
    }
    return 0;
}

5.Zipper(60分）
题目描述：给出 3 3 3个字符串，确定第 3 3 3个字符串是否由前两个字符串中的字符组成。在第 3 3 3个字符事中，前两个字符串可以任意混合，但是每个字符串还是以原来的次序排列。例如，字符串“tcraete”由字符串“cat”和“tree”组成。
字符串A： cat
字符串B： tree
字符串C： tcraete
在这个例子中，第 3 3 3个字符串通过交错地采用前两个字符串中的字符构成。在下面第 2 2 2个例子中，“catrtee”由字符串“cat”和“tree”组成。
字符串A： cat
字符串B： tree
字符串C： catrtee
不可能由“cat”和“tree”组成“cttaree”。
输入格式：测试数据包括多组数据。输入数据的第 1 1 1行是一个正整数 T T T， 1 ≤ T ≤ 1000 1≤T≤1000 1≤T≤1000，表示有多少组测试数据。后续有 T T T行，每行代表一组测试数据。每组测试数据，包含有 3 3 3个字符串，用 1 1 1个空格将它们分开。第 3 3 3个字符串的长度是前两个字符串长度之和。前两个字符串的长度在 1 1 1到 200 200 200之间。
输出格式：对于每组测试数据，如果第 3 3 3个字符串由前两个字符串组成，则输出“Data set n: yes”；
如果不是，则输出“Data set n: no”，其中 n n n表示测试数据的编号，参见输出样例。
输入样例：

3
cat tree tcraete
cat tree catrtee
cat tree cttaree

输出样例：

Data set 1: yes
Data set 2: yes
Data set 3: no

设 f [ i ] [ j ] f[i][j] f[i][j]表示字符串 C C C的前 i + j i+j i+j个字符是否由字符串 A A A的前 i i i个字符和字符串 B B B的前 j j j个字符组成。
初始状态 f [ 0 ] [ 0 ] = 1 f[0][0]=1 f[0][0]=1。
如果 A [ i ] = C [ i + j ] A[i]=C[i+j] A[i]=C[i+j]那么存在转移方程：
f [ i ] [ j ] = f [ i ] [ j ] ∣ f [ i − 1 ] [ j ] f[i][j]=f[i][j]|f[i-1][j] f[i][j]=f[i][j]∣f[i−1][j]
同理，如果 B [ j ] = C [ i ] [ j ] B[j]=C[i][j] B[j]=C[i][j]，那么存在转移方程：
f [ i ] [ j ] = f [ i ] [ j ] ∣ f [ i ] [ j − 1 ] f[i][j]=f[i][j]|f[i][j-1] f[i][j]=f[i][j]∣f[i][j−1]
最后判断 f [ l e n A ] [ l e n B ] f[len_A][len_B] f[lenA​][lenB​]是否为 1 1 1。
时间复杂度为 O ( l e n A l e n B ) O(len_Alen_B) O(lenA​lenB​)。

#include<bits/stdc++.h>

using namespace std;
const int N = 205;
char a[N], b[N], c[N << 1];
int n, m, f[N][N], T, cse;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%s%s%s", a + 1, b + 1, c + 1);
        n = strlen(a + 1), m = strlen(b + 1);
        memset(f, 0, sizeof(f)), f[0][0] = 1;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++) {
                if (i && a[i] == c[i + j])f[i][j] |= f[i - 1][j];
                if (j && b[j] == c[i + j])f[i][j] |= f[i][j - 1];
            }
        printf("Data set %d: ", ++cse);
        puts(f[n][m] ? "yes" : "no");
    }
    return 0;
}