首页 › 题库 › 信息学奥赛 › 信息学奥赛-入门级

信息学奥赛-入门级 题库

共 1088 道题 ,第 39 / 55 页 · 按题型筛选,点「查看答案」核对解析
761 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

插入排序


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

int n, q, a[8005], b[8005], num, x, v, ans;

int main() {
    scanf("%d%d", &n, &q);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    
    // 计算每个数在数组中的排位
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (i == j || a[j] < a[i] || a[j] == a[i]) {
                b[i]++;
            } else {
                b[j]++;
            }
        }
    }
    
    for (int i = 0; i < q; i++) {
        scanf("%d", &num);
        
        if (num == 1) {
            scanf("%d%d", &x, &v);
            
            for (int i = 1; i <= n; i++) {
                if (i == x) {
                    continue;
                }
                
                // 根据条件更新排位
                if ((a[i] < a[x] || (a[i] == a[x] && i < x)) && 
                    (a[i] > v || (a[i] == v && i > x))) {
                    b[i]++;
                    b[x]--;
                } else if ((a[i] > a[x] || (a[i] == a[x] && i > x)) && 
                           (a[i] < v || (a[i] == v && i < x))) {
                    b[i]--;
                    b[x]++;
                }
            }
            
            a[x] = v;
        }
        
        if (num == 2) {
            scanf("%d", &x);
            printf("%d\n", b[x]);
        }
    }
    
    return 0;
}


题目详情
762 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

网络连接


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

map<string, int> vis;
int n;

bool check(char s[]) {
    int a = -1, b = -1, c = -1, d = -1, e = -1;
    // 尝试读入,保存至变量中
    int t = sscanf(s, "%d.%d.%d.%d:%d", &a, &b, &c, &d, &e);
    
    // 必须读入5个部分才可能合法
    if (t != 5) return 0;
    
    // 检查各部分数值范围
    if (a < 0 || a > 255) return 0;
    if (b < 0 || b > 255) return 0;
    if (c < 0 || c > 255) return 0;
    if (d < 0 || d > 255) return 0;
    if (e < 0 || e > 65535) return 0;
    
    // 格式化后与原字符串对比,确保无冗余格式
    char s2[35];
    sprintf(s2, "%d.%d.%d.%d:%d", a, b, c, d, e);
    
    int lens = strlen(s);
    for (int i = 0; i < lens; i++) {
        if (s[i] != s2[i]) {
            return 0;
        }
    }
    
    return 1;
}

int main() {
    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        char op[1005], ad[1005];
        cin >> op >> ad;
        string t(ad);
        
        if (op[0] == 'S') {  // 服务机操作
            if (!check(ad)) {
                cout << "ERR" << endl;  // 地址不合法
            } else if (vis.count(t) != 0) {
                cout << "FAIL" << endl;  // 已存在该服务机
            } else {
                cout << "OK" << endl;    // 注册成功
                vis[t] = i;             // 记录编号
            }
        } else {  // 客户机操作
            if (!check(ad)) {
                cout << "ERR" << endl;  // 地址不合法
            } else if (vis.count(t) == 0) {
                cout << "FAIL" << endl;  // 找不到对应服务机
            } else {
                cout << vis[ad] << endl;  // 输出对应服务机编号
            }
        }
    }
    
    return 0;
}


题目详情
763 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

小熊的果篮


答案与解析
参考答案
#include <bits/stdc++.h>
#define INF 200010
using namespace std;

int n;
set<int> s1, s2;  // 存储两种下标的集合

int main() {
    scanf("%d", &n);
    s1.clear();
    s2.clear();
    
    int q;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &q);
        if (q) {
            s1.insert(i);  // q为1时插入s1
        } else {
            s2.insert(i);  // q为0时插入s2
        }
    }
    
    // 插入INF防止set为空时操作出错
    s1.insert(INF);
    s2.insert(INF);
    
    int nw = 0;
    // p表示当前要操作的集合:0为s1,1为s2(选择最小下标的集合)
    bool p = (*s1.begin() < *s2.begin()) ? 0 : 1;
    
    // 循环处理,直到当前操作的集合只剩下INF(size > 1表示还有有效元素)
    while ((!p && s1.size() > 1) || (p && s2.size() > 1)) {
        if (!p) {  // 处理s1
            nw = *s1.upper_bound(nw);  // 找nw之后的下一个元素
            
            if (nw == INF) {  // 已遍历完当前轮次,从头开始
                nw = 0;
                // 重新选择下一轮的起始集合
                p = (*s1.begin() < *s2.begin()) ? 0 : 1;
                puts("");
                continue;
            }
            
            printf("%d ", nw);  // 输出并从集合中删除
            s1.erase(nw);
            p = !p;  // 切换到另一个集合
        } else {  // 处理s2(逻辑同上)
            nw = *s2.upper_bound(nw);
            
            if (nw == INF) {
                nw = 0;
                p = (*s1.begin() < *s2.begin()) ? 0 : 1;
                puts("");
                continue;
            }
            
            printf("%d ", nw);
            s2.erase(nw);
            p = !p;
        }
    }
    
    puts("");  // 处理最后一个果篮的换行
    
    // 输出剩余集合中的元素(每行一个)
    while (s1.size() > 1) {
        printf("%d\n", *s1.begin());
        s1.erase(*s1.begin());
    }
    while (s2.size() > 1) {
        printf("%d\n", *s2.begin());
        s2.erase(*s2.begin());
    }
    
    return 0;
}


题目详情
764 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

优秀的拆分(power)


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

/*
定义:分解为了若干个不同的 2 的正整数次幂
性质:是偶数,奇数不存在优秀的拆分

思路:
如果n是偶数,将n进行进制转换
10 -> 1010
*/
int a[110],n,k = 0;//k表示a数组的下标

int main(){
    cin>>n;
    //特判奇数的情况
    if(n % 2 != 0){
        cout<<-1;
        return 0;
    }

    //进制转换
    int t = 1;//表示2的次方
    while(n != 0){
        if(n % 2 != 0){
            k++;
            a[k] = t;
        }
        t = t * 2;
        n = n / 2;
    }

    //逆序输出结果
    for(int i = k;i >= 1;i--){
        cout<<a[i]<<" ";
    }
    return 0;
}


题目详情
765 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

直播获奖( live)


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

/*
1.获奖人数为k = max(1, int(p × w%))
2.选手的成绩均为不超过 600 的非负整数
思路:使用数组统计每个分值得分的人数
从大到小统计出k个人,最后一次循环对应的分值就是要求的获奖分数
*/
int a[610];
int n,w,x;

int main(){
    scanf("%d%d",&n,&w);
    int k;//获奖人数
    int ans;//统计人数
    //读入n个人的分数,读一个算一个
    for(int i = 1;i <= n;i++){
        scanf("%d",&x);
        a[x]++;//统计每个分值对应的人数
        //计算获奖人数
        k = max(1,int(i * w / 100.0));
        ans = 0;
        //从最高分的人数向下统计出>=k个人
        for(int j = 600;j >= 0;j--){
            if(ans + a[j] < k) ans += a[j];//+=
            else{
                printf("%d ",j);
                break;
            }
        }
    }
	return 0;
}


题目详情
766 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

表达式(expr)


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

/*
取反某一个操作数的值时,原表达式的值为多少
思路:
1.读入表达式,将表达式建成二叉树
2.计算出表达式的值
3.深搜,求出哪些结点的值修改后对结果有影响
*/
const int N = 1e6 + 10;
struct node{
    int to,next;
}a[N];//邻接表
int pre[N],k;//存储以每个点为起点的最后一条边的编号
int num[N];//存储二叉树每个结点的值
char c[N];//存储操作符
int m;//表示c数组的下标
bool f[N];//标记哪些点的值修改后对结果有影响
int n;
string s,w;//w用来存储每个操作数的下标
stack<int> st;//用于计算后缀表达式

//建边
void add(int u,int v){
    k++;
    a[k].to = v;
    a[k].next = pre[u];
    pre[u] = k;
}

//深搜求哪些结点的值修改后对结果有影响
void dfs(int x){
    f[x] = true;
    if(x <= n) return;//如果是叶子结点
    if(c[x] == '!') dfs(a[pre[x]].to);
    else{
        int n1 = a[pre[x]].to,n2 = a[a[pre[x]].next].to;
        if(c[x] == '&'){
            if(num[n1] == 1) dfs(n2);
            if(num[n2] == 1) dfs(n1);
        }else if(c[x] == '|'){
            if(num[n1] == 0) dfs(n2);
            if(num[n2] == 0) dfs(n1);
        }
    }
}

int main()
{
    getline(cin,s);
    cin>>n;
    for(int i = 1;i <= n;i++){
        scanf("%d",&num[i]);
    }

    //分析表达式,建树
    int x,y;
    m = n;
    for(int i = 0;i < s.size();i++){
        if(isdigit(s[i])){
            w = w + s[i];
            //如果连续数字结束
            if(i==s.size()-1||!isdigit(s[i+1])){
                st.push(atoi(w.c_str()));//将操作数的下标入栈
                w = "";
            }
        }else if(s[i] == '!'){
            //如果是取反操作符
            m++;
            c[m] = s[i];//操作符的编号是m
            x = st.top();//取栈顶元素来运算
            st.pop(); //出栈
            //建边
            add(m,x);
            num[m] = !num[x];
            st.push(m);
        }else if(s[i] == '&' || s[i] == '|'){
            //如果是& |操作符
            m++;
            c[m] = s[i];
            //取2个操作数
            x = st.top();
            st.pop();
            y = st.top();
            st.pop();
            //建边
            add(m,x);
            add(m,y);
            //计算结点的值
            if(s[i] == '&') num[m] = num[x] & num[y];
            else if(s[i] == '|') num[m] = num[x] | num[y];

            st.push(m);
        }
    }

    int ans = num[st.top()];
    //cout<<ans;
    //深搜求哪些结点的值修改后对结果有影响
    dfs(st.top());//从根开始深搜

    //q次询问
    int q;
    cin>>q;
    while(q--){
        scanf("%d",&x);
        if(f[x]==true) printf("%d\n",!ans);
        else printf("%d\n",ans);
    }

    return 0;
}


题目详情
767 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

方格取数(number)


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
/*
左上角走到右下角
每一步只能向上、向下或向右走一格
不能重复经过已经走过的方格

计算的结果,要用long long
*/
const int N = 1010;
int a[N][N];//读入的每个点的值
typedef long long LL;
LL f[N][N];
int n,m;

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            scanf("%d",&a[i][j]);
        }
    }

    /*
    DP求出走到每个点经过的数字和的最大值
    一列一列求,对于每一列而言,要求从上向下走到每个点经过的数字和的最大值
    也要求从下向上走到每个点经过的数字和的最大值
    */
    memset(f,-0x7f,sizeof(f));

    LL ma;//走到每个格子经过的数字和最大
    f[1][0] = 0;
    for(int j = 1;j <= m;j++){
        //从上向下求
        ma = -1e18;
        for(int i = 1;i <= n;i++){
            ma = max(ma,f[i][j-1]) + a[i][j];
            f[i][j] = max(f[i][j],ma);
        }

        //从下向上求
        ma = -1e18;
        for(int i = n;i >= 1;i--){
            ma = max(ma,f[i][j-1]) + a[i][j];
            f[i][j] = max(f[i][j],ma);
        }
    }

cout<<f[n][m];
return 0;
}


题目详情
768 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

T1 扑克牌

答案与解析
参考答案
#include <iostream>
#include <set>
using namespace std;


int main() {
    int n;
    cin >> n;
    set<string> st;
    while (n--) {
        string s;
        cin >> s;
        st.insert(s);
    }
    cout << 52 - st.size() << endl;
    return 0;
}

题目给出已有的牌,要求计算最少需要补充多少张牌才能凑齐一副完整的扑克牌(52张)。给出的扑克牌可能包含重复的牌(即花色和点数都相同的牌),因此需要去重后计算缺失的牌数。

题目详情
769 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

T2 地图探险

答案与解析
参考答案
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e3 + 5;

int n, m, k, x, y, d, dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
char mp[N][N];
bool vis[N][N];


int main() {
    int t;
    cin >> t;
    while (t--) {
        memset(vis, false, sizeof (vis));
        cin >> n >> m >> k >> x >> y >> d;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> mp[i][j];

        vis[x][y] = true;
        while (k--) {
            int nx = x + dir[d][0], ny = y + dir[d][1];
            if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) {
                d = (d + 1) % 4;
                continue;
            }
            x = nx, y = ny;
            vis[nx][ny] = true;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (vis[i][j] == true)
                    ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

需要的变量 / 数组

描述机器人状态需要的3个变量:

x:位置。

y:位置。

d:朝向(0~3)。

vis数组:

当机器人走过[x, y],vis[x][y] = true。

dir数组:

dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}。

[x + dir[d][0], y + dir[d][1]]表示当机器人朝向为d时往前走一步之后的位置。

d = 0: 右 (0, 1)。

d = 1: 下 (1, 0)。

d = 2: 左 (0, -1)。

d = 3: 上 (-1, 0)。

核心思想

vis[x][y] = true;
while (k--) {
    int nx = x + dir[d][0], ny = y + dir[d][1]; // 计算下一步的位置
    if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) { // 是否能走
        d = (d + 1) % 4; // 若不能走 右转
        continue;
    }
    x = nx, y = ny; // 若能走 更新
    vis[nx][ny] = true;
}
题目详情
770 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

T3 小木棍

答案与解析
参考答案
#include <iostream>
using namespace std;


string Solve(int n) {
    if (n == 1)
        return "-1";

    if (n % 7 == 0)
        return string(n / 7, '8');
    if (n % 7 == 1)
        return "10" + string((n - 8) / 7, '8');
    if (n % 7 == 2)
        return "1" + string((n - 2) / 7, '8');
    if (n % 7 == 3)
        return n == 3 ? "7" : n == 10 ? "22" : "200" + string((n - 17) / 7, '8');
    if (n % 7 == 4)
        return n == 4 ? "4" : "20" + string((n - 11) / 7, '8');
    if (n % 7 == 5)
        return "2" + string((n - 5) / 7, '8');
    if (n % 7 == 6)
        return "6" + string((n - 6) / 7, '8');
}


int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << Solve(n) << endl;
    }
    return 0;
}

拼出0~9分别需要的木棍数量:

求解思想:

因为拼出8所需的木棍最多(7根),所以用8,可以使位数更少

在保证位数最少的前提下,还要尽可能把高位的数字变小(必须保证位数最小)

按照思想,可以找到这样的规律:

题目详情
771 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

T4 接龙

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 5, R = 105;
vector<int> s[N];
int n, k, q;

vector<vector<int> > Solve(int mx) {
    vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
    dp[0][1] = -2;
    for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
                int tmp = s[i][j];
                if (lst != -1 && j - lst + 1 <= k) {
                    if (dp[r][tmp] == -1)
                        dp[r][tmp] = i;
                    else if (dp[r][tmp] != i)
                        dp[r][tmp] = -2;
                }

                if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
                    lst = j;
            }
        }
    }
    return dp;
}


int main() {
    int t;
    cin >> t;
    while (t--) {
        int mx = -1;
        cin >> n >> k >> q;
        for (int i = 1; i <= n; i++) {
            int l;
            cin >> l;
            s[i].clear();
            s[i].resize(l);
            for (int j = 0; j < l; j++) {
                cin >> s[i][j];
                mx = max(mx, s[i][j]);
            }
        }
        
        vector<vector<int> > dp = Solve(mx);
        while (q--) {
            int r, c;
            cin >> r >> c;
            cout << (dp[r][c] != -1 ? 1 : 0) << endl;
        }
    }
    return 0;
}

解题思路

本文的解题思想为dp。

dp[r][x]:接龙 r 轮、以 x 结尾的状态:

dp[r][x] = -1:不可实现。

dp[r][x] = i(一个自然数):可以通过词库 i 实现(最后一次接龙操作使用的是词库 i 中的某个连续子序列)。

dp[r][x] = -2:可以通过多个词库实现。

代码解析

完整的求解部分:

vector<vector<int> > Solve(int mx) {
    vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
    dp[0][1] = -2;
    for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
                int tmp = s[i][j];
                if (lst != -1 && j - lst + 1 <= k) {
                    if (dp[r][tmp] == -1)
                        dp[r][tmp] = i;
                    else if (dp[r][tmp] != i)
                        dp[r][tmp] = -2;
                }

                if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
                    lst = j;
            }
        }
    }
    return dp;
}

逐行分析

mx:所有词库中的最大值,用于构建dp的第二个维度。

dp的大小为R(最大轮数) * mx(所有词库中的最大值)。

vector<vector<int> > Solve(int mx) {
	vector<vector<int> > dp(R, vector<int>(mx + 5, -1));

dp[0][1] = -2:作为虚拟起点,使得第一次接龙可以从数字 1 开始。

dp[0][1] = -2;

r:轮数。

i:尝试让第 i 个人接龙。

j:第 i 个人词库中第 j 个词语。

lst:当前序列 i 中最近一个满足接龙条件的起始位置(可以以lst为起点开始接龙)。

for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
            }
        }
    }

获取当前人员 i 的词库中第 j 个词语。

如果当前词库中有一个合适的起点可以开始接龙,并且长度合适:

那么选择子序列[lst, j]开始接龙。

更新当前状态。

如果上一轮接龙不是 i 在接龙,并且可以以tmp结束,那么这一轮也可以从tmp开始接龙。

int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
    if (dp[r][tmp] == -1)
        dp[r][tmp] = i; // 首次发现路径则记录序列i
    else if (dp[r][tmp] != i)
        dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}

if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
    lst = j;
题目详情
772 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

阅读程序(1)

#include <iostream>
using namespace std;
bool isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
int countPrimes(int n) {
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
count++;
}
}
return count;
}
int sumPrimes(int n) {
int sum = 0;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
sum += i;
}
}
return sum;
}
int main() {
int x;
cin >> x;
cout << countPrimes(x) << " " << sumPrimes(x) << endl;
return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
773 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

阅读程序(2)

#include <iostream>
#include <vector>
using namespace std;
int compute(vector<int> &cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0);
    dp[1] = cost[0];
    for (int i = 2; i <= n; i++) {
      dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1];
   }
   return min(dp[n], dp[n - 1]);
}
int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    cout << compute(cost) << endl;
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
774 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

阅读程序(3)

#include <iostream>
#include <cmath>
using namespace std;
int customFunction(int a, int b) {
    if (b == 0) {
        return a;
    }
    return a + customFunction(a , b - 1);
}
int main() {
    int x, y;
    cin >> x >> y;
    int result = customFunction(x, y);
    cout << pow(result, 2) << endl;
    return 0;
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
775 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

完善程序(1)

(判断平方数) 问题:给定一个正整数 n,判断这个数 是不是完全平方数,即存在一个正整数 x 使得 x 的平方等于 n。试补全程序。

#include<iostream>
#include<vector>
using namespace std;
bool isSquare(int num){
int i = ___(1)___;
int bound =___(2)___;
for(;i<=bound;++i){
if(___(3)___){
return ___(4)___;
}
}
return ___(5)___;
}
int main(){
int n;
cin>>n;
if(isSquare(n)){
cout<<n<<" is a Square number"<<endl;
}else{
cout<<n<<" is not a Square number"<<endl;
}
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
776 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

完善程序(2)

(汉诺塔问题)给定三根柱子,分别标记为 A、B 和 C。初始状态下,柱子A上有若干个圆盘,这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子c上,且必须保持原有顺序不变。在移动过程中,需要遵守以不规则:

1.只能从一根柱子的顶部取出圆盘,并将其放入另一根柱子的顶部。

2.每次只能移动一个圆盘

3.小圆盘必须始终在大圆盘之上。

试补全程序

#include <bits/stdc++.h>
using namespace std;
void move(char src, char tgt) {
cout << "从柱子" << src << "挪到柱子上" << tgt << endl;
}
void dfs(int i, char src, char tmp, char tgt) {
if(i == ___(1)___) {
move(___(2)___);
return;
}
dfs(i-1, ___(3)___);
move(src, tgt);
dfs(___(4)___, ___(5)___);
}
int main() {
int n;
cin >> n;
dfs(n, 'A', 'B', 'C');
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
777 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

小苹果(apple)

【题目描述】

小Y的桌子上放着n个苹果从左到右排成一列,编号为从1到n。

小苞是小Y的好朋友,每天她都会从中拿走一些苹果。

每天在拿的时候,小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道,多少天能拿完所有的苹果,而编号为n的苹果是在第几天被拿走的?

【输入格式】

从文件apple.in中读入数据。

输入的第一行包含一个正整数n,表示苹果的总数。

【输出格式】

输出到文件apple.out中。

输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为n的苹果是在第几天。


【样例1输入】

8

【样例1输出】

5 5

【样例1解释】

小苞的桌上一共放了8个苹果。

小苞第一天拿走了编号为1、4、7的苹果。

小苞第二天拿走了编号为2、6的苹果。

小苞第三天拿走了编号为3的苹果。

小苞第四天拿走了编号为5的苹果。

小苞第五天拿走了编号为8的苹果。


【样例2】

见选手目录下的apple/apple2.in与apple/apple2.ans。

答案与解析
参考答案

题目详情
778 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

公路(road)

【题目描述】

小苞准备开着车沿着公路自驾。

公路上一共有n个站点,编号为从1到n。其中站点i与站点i+1的距离为vi公里。

公路上每个站点都可以加油,编号为i的站点一升油的价格为ai元,且每个站点只出售整数升的油。

小苞想从站点1开车到站点n,一开始小苞在站点1且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进d公里。问小苞从站点1开到站点n,至少要花多少钱加油?

【输入格式】

从文件road.in中读入数据。

输入的第一行包含两个正整数n和d,分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含n−1个正整数v1,v2...vn−1,分别表示站点间的距离。

输入的第二行包含n个正整数a1,a2...an,分别表示在不同站点加油的价格。

【输出格式】

输出到文件road.out中。

输出一行,仅包含一个正整数,表示从站点1开到站点n,小苞至少要花多少钱加油。


【样例1输入】

5 4
10 10 10 10
9 8 9 6 5

【样例1输出】

79


【样例1解释】

最优方案下:小苞在站点1买了3升油,在站点2购买了5升油,在站点4购买了2升油。

【样例2】

见选手目录下的road/road2.in与road/road2.ans。

。


答案与解析
参考答案

题目详情
779 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

一元二次方程(uqe)

【样例 1 输入】

1 9 1000
2 1 ‐1 0
3 ‐1 ‐1 ‐1
4 1 ‐2 1
5 1 5 4
6 4 4 1
7 1 0 ‐432
8 1 ‐3 1
9 2 ‐4 1
10 1 7 1


【样例 1 输出】

1 1
2 NO
3 1
4 ‐1
5 ‐1/2
6 12*sqrt(3)
7 3/2+sqrt(5)/2
8 1+sqrt(2)/2
9 ‐7/2+3*sqrt(5)/2

【样例 2】

见选手目录下的 uqe/uqe2.in 与 uqe/uqe2.ans。

答案与解析
参考答案

题目详情
780 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

旅游巴士(bus)

【题目描述】

小Z打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有n处地点,在这些地点之间连有m条道路。其中1号地点为景区入口,n号地点为景区出口。我们把一天当中景区开门营业的时间记为0时刻,则从0时刻起,每间隔k单位时间便有一辆旅游巴士到达景区入口,同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路,游客步行通过的用时均为恰好1单位时间。

小Z希望乘坐旅游巴士到达景区入口,并沿着自己选择的任意路径走到景区出口,再乘坐旅游巴士离开,这意味着他到达和离开景区的时间都必须是k的非负整数倍。由于节假日客流众多,小Z在坐旅游巴士离开景区前只想一直沿着景区道路移动,而不.想在任何地点(包括景区入口和出口)或者道路上逗留。

出发前,小Z忽然得知:景区采取了限制客流的方法,对于每条道路均设置了一个“开放时间”ai,游客只有不早于ai时刻才能通过这条道路。

请你帮助小Z设计一个旅游方案,使得他乘坐旅游巴士离开景区的时间尽量地早。

【输入格式】

从文件bus.in中读入数据。

输入的第一行包含3个正整数n,m,k,表示旅游景点的地点数、道路数,以及旅游巴士的发车间隔。

输入的接下来m行,每行包含3个非负整数ui,vi,ai,表示第i条道路从地点ui出发,到达地点vi,道路的“开放时间”为ai。

【输出格式】

输出到文件bus.out中。

输出一行,仅包含一个整数,表示小Z最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案,输出‐1。


【样例1输入】

1 5 5 3
2 1 2 0
3 2 5 1
4 1 3 0
5 3 4 3
6 4 5 1

【样例1输出】

1 6

【样例1解释】

图1:

样例1示例

小Z可以在3时刻到达景区入口,沿1→3→4→5的顺序走到景区出口,并在6时刻离开。

【样例2】

见选手目录下的bus/bus2.in与bus/bus2.ans。

【数据范围】

对于所有测试数据有:2≤n≤104,1≤m≤2×104,1≤k≤100,1≤ui,vi≤n,0≤ai≤106。

答案与解析
参考答案

参考程序1:

参考程序2:

题目详情