NOIP第十九届全国青少年信息学奥林匹克联赛初赛试题[2013提高组]

第21题

某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1，s2，, ， sn，均为 0 或 1。该系统每次随机生成 n 个数 a1，a2，, ， an，均为 0 或 1，请用户回答 （s 1a1+s 2 a2+… +s n an）除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问 答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。 例如，当 n=4 时，有人窃听了以下 5 次问答：

就破解出了密码 s1= _ ， s2= _ ，s3= _， s4= _。(结果之间用空格隔开即可）

第22题

现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概率 地随机跳到 1，2，, ， k 号荷尔蒙叶之一上，直至跳到 1 号荷叶为止。当 n=2 时，平均一 共跳 2 次；当 n=3 时，平均一共跳 2.5 次。则当 n=5 时，平均一共跳 _____次。

第23题

#include <iostream>
#include <string>
using namespace std;
int main() {
    string str;
    cin>>str;
    int n = str.size();
    bool isPlalindrome = true;
    for (int i = 0;i < n/2;i++) {
        if (str[i] != str[n-i-1]) isPlalindrome = false;
    }
    if (isPlalindrome)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

输入：

abceecba

输出：________

第24题

#include <iostream>
using namespace std;
int main(){
    int a, b, u, v, i, num;
    cin>>a>>b>>u>>v;
    num = 0;
    for (i = a;i <= b;i++)
        if (((i % u) == 0) || ((i % v) == 0))
            num++;
    cout<<num<<endl;
    return 0;
}

输入：

1 1000 10 15

输出：________

第25题

#include <iostream>
using namespace std;
int main(){
    const int SIZE = 100;
    int height[SIZE], num[SIZE], n, ans;
    cin>>n;
    for (int i = 0;i < n;i++) {
        cin>>height[i];
        num[i] = 1;
        for (int j = 0;j < i;j++) {
            if ((height[j] < height[i]) && (num[j] >= num[i]))
                num[i] = num[j]+1;
        }
    }
    ans = 0;
    for (int i = 0;i < n;i++) {
        if (num[i] > ans) ans = num[i];
    }
    cout<<ans<<endl;
}

输入：

8

3 2 5 11 12 7 4 10

输出：________

第26题

#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 100;
int n, m, p, a[SIZE][SIZE], count;
void colour(int x, int y){
    count++;
    a[x][y] = 1;
    if ((x > 1) && (a[x - 1][y] == 0)) colour(x - 1, y);
    if ((y > 1) && (a[x][y - 1] == 0)) colour(x, y - 1);
    if ((x < n) && (a[x + 1][y] == 0)) colour(x + 1, y);
    if ((y < m) && (a[x][y + 1] == 0)) colour(x, y + 1);
}
int main(){
    int i, j, x, y, ans;
    memset(a, 0, sizeof(a));
    cin>>n>>m>>p;
    for (i = 1;i <= p;i++) {
        cin>>x>>y;
        a[x][y] = 1;
    }
    ans = 0;
    for (i = 1;i <= n;i++)
        for (j = 1;j <= m;j++)
            if (a[i][j] == 0) {
                count = 0;
                colour(i, j);
                if (ans < count)
                    ans = count;
            }
    cout<<ans<<endl;
    return 0;
}

输入：

6 5 9

1 4

2 3

2 4

3 2

4 1

4 3

4 5

5 4

6 4

输出：________

第27题

（序列重排）全局数组变量 a 定义如下： 

const int SIZE=100; 

int a[SIZE],n; 

它记录着一个长度为 n 的序列 a[1] ，a[2] ，, ， a[n] 。现在需要一个函数，以整数 p(1 ≤p≤ n) 为参数， 实现如下功能： 将序列 a 的前 p 个数与后 n-p 个数对调， 且不改变这 p 个数（或 n-p 个数）之间的相对位置。例如，长度为 5 的序列 1， 2，3，4，5，当 p=2 时重排结果为 3，4， 5，1，2。有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n) 、空间复杂度为 O(n) ：

void swap1(int p){
int i, j, b[SIZE];
    for (i = 1;i <= p;i++)
        b[①] = a[i];
    for (i = p + 1;i <= n;i++)
        b[i - p] = a[i];
    for (i = 1;i <= n;i++)
        a[i] = b[i];
}

我们也可以用时间换空间，使用时间复杂度为O(n^2)、空间复杂度为 O(1) 的算法：

void swap2(int p){
    int i, j, temp;
    for (i = p + 1;i <= n;i++) {
        temp = a[i];
        for (j = i;j >=②;j--)
            a[j] = a[j - 1];
        ③ = temp;
        }
}

事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1)：

void swap3(int p){
    int start1, end1, start2, end2, i, j, temp;
    start1 = 1;
    end1 = p;
    start2 = p + 1;
    end2 = n;
    while (true) {
        i = start1;
        j = start2;
        while ((i <= end1) && (j <= end2)) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j++;
        }
        if (i <= end1)
            start1 = i;
        else if (④) {
            start1 =⑤;
            end1 =⑥;
            start2 = j;
        }else
            break;
    }
}

第28题

（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子 序列并列最长，输出任意一个即可。例如，序列“ 1 1 2 3 2 3 2 3 3 1 1 1 3 1 ”中，有 两段满足条件的最长子序列，长度均为 7，分别用下划线和加粗斜体标出。

#include <iostream>
using namespace std;
int main(){
    const int SIZE = 100;
    int n, i, j, a[SIZE], cur1, cur2, count1, count2,
    ans_length, ans_start, ans_end;
    //cur1, cur2 分别表示当前子序列中的两个不同整数
    //count1, count2 分别表示 cur1, cur2 在当前子序列中出现的次数
    cin>>n;
    for (i = 1;i <= n;i++)
        cin>>a[i];
    i = 1;
    j = 1;
    //i, j 分别表示当前子序列的首尾，并保证其中至多有两个不同整数
    while ((j <= n) && (a[j] == a[i]))
        j++;
    cur1 = a[i];
    cur2 = a[j];
    count1 =①;
    count2 = 1;
    ans_length = j - i + 1;
    while (j < n) {
        j++;
        if (a[j] == cur1)
            count1++;
        else if (a[j] == cur2)
            count2++;
        else {
            if (a[j - 1] ==② ) {
                while (count2 > 0) {
                    if (a[i] == cur1)
                        count1--;
                    else
                        count2--;
                    i++;
                }
                cur2 = a[j];
                count2 = 1;
            }else {
                while (count1 > 0) {
                    if (a[i] == cur1)
                        ③ ;
                    else
                        ④ ;
                    i++;
                }
                ⑤ ;
                count1 = 1;
            }
        }
        if (ans_length < j - i + 1) {
            ans_length = j - i + 1;
            ans_start = i;
            ans_end = j;
        }
    }
    for (i = ans_start;i <= ans_end;i++)
        cout<<a[i]<<' ';
    return 0;
}