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

第21题

一个人站在坐标（0，0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（___ , ___）。

第22题

如下图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）。现在要使得所有的格子中的数字都变为 0，至少需要_____次操作。

第23题

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int t[256];
    char s[10];
    int i;
    scanf("%s", s);
    for(i = 0; i < 256; i++) t[i] = 0;
    for(i = 0; i < strlen(s); i++) t[s[i]]++;
    for(i = 0; i < strlen(s); i++)
        if(t[s[i]] == 1) {
            cout << s[i] << endl;
            return 0;
        }
    cout << "no" << endl;
    return 0;
}

输入：

xyzxyw

输出：（ ）

第24题

#include <stdio.h>
int g(int m, int n, int x) {
    int ans=0;
    int i;
    if(n == 1)
        return 1;
    for(i = x; i <= m / n; i++)
        ans += g(m - i, n - 1, i);
    return ans;
}
int main()
{
    int t, m, n;
    scanf("%d%d", &m, &n);
    printf("%d
", g(m, n, 0));
    return  0;
}

输入：

7 3

输出：（ ）

第25题

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string ch;
    int a[200];
    int b[200];
    int n, i, t, res;
    cin >> ch;
    n = ch.length();
    for(i = 0; i < 200; i++) b[i] = 0;
    for(i = 1; i <= n ; i++) {
        a[i] = ch[i-1] - '0';
        b[i] = b[i-1] + a[i];
    }
    res = b[n];
    t = 0;
    for(i = n; i > 0; i--) {
        if(a[i] == 0) t++;
        if(b[i-1] + t < res) res = b[i-1] + t;
    }
    cout << res << endl;
    return 0;
}

输入：

1001101011001101101011110001

输出：（ ）

第26题

#include <iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int x = 1;
    int y = 1;
    int dx = 1;
    int dy = 1;
    int cnt = 0;
    while(cnt != 2) {
        cnt = 0;
        x = x + dx;
        y = y + dy;
        if(x == 1 || x == n) {
            ++cnt;
            dx = -dx;
        }
        if(y == 1 || y == m) {
            ++cnt;
            dy = -dy;
        }
    }
    cout << x << " " << y << endl;
    return  0 ;
}

1）输入：

4 3

输出：（ ）

2）输入：

2017 1014

输出：（ ）

第27题

（快速幂）请完善下面的程序，该程序使用分治法求 x^p mod m 的值。

输入：三个不超过 10000 的正整数 x, p, m。

输出：x^p mod m 的值。

提示：若 p 为偶数，x^p = (x²)^p/2；若 p 为奇数，x^p = x  (x²)^(p-1)/2。

#include <iostream>
using namespace std;
int x, p, m, i, result;
int main()
{
    cin >> x >> p >> m;
    result = ①;
    while(②)
    {
        if(p % 2 == 1)
            result = ③;
        p /= 2;
        x = ④;
    }
    cout << ⑤ << endl;
    return  0 ;
}

第28题

（切割绳子）有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。

输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过 10^6的正整数，表示每条绳子的长度，第三行是一个不超过 10^8 的正整数 m。

输出 ：绳段的最大长度，若无法切割，输出 Failed。

#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int  len[100]; //绳子长度
int main()
{
    cin >> n;
    count = 0;
    for (i = 0; i < n; i++) {
        cin >> len[i];
        ①;
    }
    cin >> m;
    if (②) {
        cout << "Failed" << endl;
        return 0;
    }
    lbound = 1 ;
    ubound = 1000000 ;
    while (③) {
        mid = ④;
        count =0 ;
        for (i = 0; i < n; i++ )
            ⑤;
        if (count < m)
            ubound = mid - 1 ;
        else
            lbound = mid ;
    }
    cout << lbound << endl;
    return 0;
}