北京大学计算概论A 2018年期中考试

2018年11月4日9,0830

监考的时候顺便做了一遍题

1.短信计费

用手机发短信，一般一条短信资费为0.1元，但限定每条短信的内容在70个字以内（包括70个字）。如果你所发送的一条短信超过了70个字，则大多数手机会按照每70个字一条短信的限制把它分割成多条短信发送。假设已经知道你当月所发送的每条短信的字数，试统计一下你当月短信的总资费。

2.集体照

医学部口腔3班n位同学约定拍集体照，n大于1且不超过100。摄影师要求同学按照身高站成两排，保证第二排的人身高都要大于等于第一排的人，且第二排的人数和第一排的人数相等或者比第一排多一个人。
输入n位同学的身高，请问第二排中身高最矮的人的身高是多少？

3.1020 跳格问题

有一种游戏，在纸上画有很多小方格，第一个方格为起点(S)，最后一个方格为终点。有一个棋子，初始位置在起点上，棋子每次可移动一次，棋子在起点时，可向前移动一个格子到第二个方格内；棋子在其他方格内时，可根据方格内的数字Ni进行移动。如果Ni大于零，就向前移动Ni个格子；如果Ni小于零，就向后移动-Ni个格子；如果Ni等于零，则此次原地不动一次，在下一步移动时可向前移动一步到下一个格子。显然，如果仅按此方案，会出现棋子永远移动不到终点的情形。为防止这种情况发生，我们规定，当棋子再次来到它曾经到过的方格时，它需要原地不动一次，在下一步移动时可向前移动一步到下一个格子。按此方案，棋子总能够走到终点(F)。如果给定一个方格图，试求棋子要走多少步才能从起点走到终点。（注：当然还可能会出现向前移动Ni个格子就跑过终点了，则把棋子放到终点上。如果Ni太小，使得棋子向后移动跑过了起点，则把棋子放到起点上。）（如图所示，其中S代表起点，F代表终点）（只有离开后再次来到一个方格时，才算来到它曾经到过的方格，包括起点S）

#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 2147483647
using namespace std;
int n, ans;
int a[105];
bool vis[105];
void dfs(int x)
{
    if(x < 1)
        x = 1;
    if(x > n + 2)
        x = n + 2;    
    if(vis[x])
    {
        if(a[x])ans += 2;
        else ans += 1;
        dfs(x + 1);
    }
    else
    {
        vis[x] = 1;
        if(x == n + 2)return;
        ans++;
        dfs(x + a[x]);
    }
}
int main()
{
    scanf("%d", &n);
    a[1] = 1;
    for(int i = 2; i <= n + 1; i++)
        cin >> a[i];
    dfs(1);
    cout << ans << endl;
    return 0;
}

#include <set>

#include <map>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 2147483647

using namespace std;

int n, ans;

int a[105];

bool vis[105];

void dfs(int x)

{

if(x < 1)

x = 1;

if(x > n + 2)

x = n + 2;

if(vis[x])

{

if(a[x])ans += 2;

else ans += 1;

dfs(x + 1);

}

else

{

vis[x] = 1;

if(x == n + 2)return;

ans++;

dfs(x + a[x]);

}

int main()

{

scanf("%d", &n);

a[1] = 1;

for(int i = 2; i <= n + 1; i++)

cin >> a[i];

dfs(1);

cout << ans << endl;

return 0;

}

4.配对碱基链

脱氧核糖核酸（DNA）由两条互补的碱基链以双螺旋的方式结合而成。而构成DNA的碱基共有4种，分别为腺瞟呤（A）、鸟嘌呤（G）、胸腺嘧啶（T）和胞嘧啶（C）。我们知道，在两条互补碱基链的对应位置上，腺瞟呤总是和胸腺嘧啶配对，鸟嘌呤总是和胞嘧啶配对。你的任务就是根据一条单链上的碱基序列，给出对应的互补链上的碱基序列。

#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 2147483647
using namespace std;
int n;
string x;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        for(int j = 0; j < x.length(); j++)
        {
            if(x[j] == 'T')
                x[j] = 'A';
            else if(x[j] == 'A')
                x[j] = 'T';
            else if(x[j] == 'C')
                x[j] = 'G';
            else
                x[j] = 'C';
        }
        cout << x << endl;
    }
    return 0;
}

#include <set>

#include <map>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 2147483647

using namespace std;

int n;

string x;

int main()

{

scanf("%d", &n);

for(int i = 1; i <= n; i++)

{

cin >> x;

for(int j = 0; j < x.length(); j++)

{

if(x[j] == 'T')

x[j] = 'A';

else if(x[j] == 'A')

x[j] = 'T';

else if(x[j] == 'C')

x[j] = 'G';

else

x[j] = 'C';

}

cout << x << endl;

}

return 0;

}

5.打鱼还是晒网

中国有句俗语叫“三天打鱼两天晒网”。某人从1990年1月1日起开始“三天打鱼两
天晒网”，问这个人在以后的某一天中是“打鱼”还是“晒网”。
注意要区分闰年和不是闰年的两种情况

#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 2147483647
using namespace std;
int y, m, d;
int mm[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int tot;
int main()
{
    cin >> y >> m >> d;
    for(int i = 1990; i < y; i++)
        if((i % 4 == 0 && i % 100 != 0) || i % 400 == 0)
            tot += 366;
        else tot += 365;
    for(int i = 1; i < m; i++)
        if(((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && i == 2)
            tot += 29;
        else
            tot += mm[i - 1];
    tot += (d - 1);
    if(tot % 5 <= 2)
        puts("fishing");
    else
        puts("sleeping");
    return 0;
}

#include <set>

#include <map>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 2147483647

using namespace std;

int y, m, d;

int mm[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int tot;

int main()

{

cin >> y >> m >> d;

for(int i = 1990; i < y; i++)

if((i % 4 == 0 && i % 100 != 0) || i % 400 == 0)

tot += 366;

else tot += 365;

for(int i = 1; i < m; i++)

if(((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && i == 2)

tot += 29;

else

tot += mm[i - 1];

tot += (d - 1);

if(tot % 5 <= 2)

puts("fishing");

else

puts("sleeping");

return 0;

}

6.优先队列

给定一个初始数字集合，对其做如下两种操作：
1. 添加一个新的数字
2. 将集合中当前最小的数字取出（输出并删除），如果最小的数字有多个，只取出其中一个。

#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 2147483647
using namespace std;
int n, m;
struct data{
    int a[200005];
    int cnt;
    bool empty(){
        return cnt == 0;
    }
    void push(int x){
        a[++cnt] = x;
        int p = cnt;
        while(p > 1 && a[p] < a[p / 2])
        {
            swap(a[p], a[p / 2]);
            p = p / 2;
        }
    }
    int top(){
        return a[1];
    }
    void down(int x){
        int t = x << 1;
        if(t > cnt)return;
        if(t + 1 <= cnt && a[t + 1] < a[t])
            t++;
        if(a[t] < a[x])
        {
            swap(a[t], a[x]);
            down(t);
        }            
    }
    void pop(){
        a[1] = a[cnt];
        cnt--;
        down(1);
    }
}q;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;        
        q.push(x);
    }
    cin >> m;
    char opt[15];
    for(int i = 1; i <= m; i++)
    {
        scanf("%s", opt);
        if(opt[0] == 'E')
        {
            if(q.empty())
                puts("NULL");
            else
            {
                cout << q.top() << endl;
                q.pop();
            }
        }
        else
        {
            int x;
            cin >> x;
            q.push(x);
        }
    }
    return 0;
}

#include <set>

#include <map>

#include <queue>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 2147483647

using namespace std;

int n, m;

struct data{

int a[200005];

int cnt;

bool empty(){

return cnt == 0;

}

void push(int x){

a[++cnt] = x;

int p = cnt;

while(p > 1 && a[p] < a[p / 2])

{

swap(a[p], a[p / 2]);

p = p / 2;

}

int top(){

return a[1];

}

void down(int x){

int t = x << 1;

if(t > cnt)return;

if(t + 1 <= cnt && a[t + 1] < a[t])

t++;

if(a[t] < a[x])

{

swap(a[t], a[x]);

down(t);

}

void pop(){

a[1] = a[cnt];

cnt--;

down(1);

}

}q;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

{

int x;

cin >> x;

q.push(x);

}

cin >> m;

char opt[15];

for(int i = 1; i <= m; i++)

{

scanf("%s", opt);

if(opt[0] == 'E')

{

if(q.empty())

puts("NULL");

else

{

cout << q.top() << endl;

q.pop();

}

else

{

int x;

cin >> x;

q.push(x);

}

return 0;

}

7.护林员盖房子

在一片保护林中，护林员想要盖一座房子来居住，但他不能砍伐任何树木。
现在请你帮他计算：保护林中所能用来盖房子的矩形空地的最大面积。

#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 2147483647
using namespace std;
int n, m;
int ans;
int v[25][25];
bool check(int a, int b, int c, int d)
{
    for(int i = a; i <= c; i++)
        for(int j = b; j <= d; j++)
            if(v[i][j])return 0;
    return 1;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> v[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = i; k <= n; k++)
                for(int l = j; l <= m; l++)
                    if(check(i, j, k, l))
                        ans = max(ans, (k - i + 1) * (l - j + 1));
    cout << ans << endl;
    return 0;
}

#include <set>

#include <map>

#include <queue>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 2147483647

using namespace std;

int n, m;

int ans;

int v[25][25];

bool check(int a, int b, int c, int d)

{

for(int i = a; i <= c; i++)

for(int j = b; j <= d; j++)

if(v[i][j])return 0;

return 1;

}

int main()

{

cin >> n >> m;

for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++)

cin >> v[i][j];

for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++)

for(int k = i; k <= n; k++)

for(int l = j; l <= m; l++)

if(check(i, j, k, l))

ans = max(ans, (k - i + 1) * (l - j + 1));

cout << ans << endl;

return 0;

}

8.汽车限行

为了缓解交通压力、减少空气污染，B市市政府决定在工作日（周一至周五）对机动车进行限行，每辆机动车每周将有一个工作日不能出行，但周末不限行。假设该政策从2000年1月1日起开始执行。限行安排为：
尾号为1和6：周一限行
尾号为2和7：周二限行
尾号为3和8：周三限行
尾号为4和9：周四限行
尾号为5、0和字母：周五限行

已知2000年1月1日为周六，现在给出一些日期和车牌号，求问该机动车在该天是否限行。

#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 2147483647
using namespace std;
int T;
int y, m, d;
int mm[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{
    cin >> T;
    while(T--)
    {
        char ch;
        cin >> y >> ch >>  m >> ch >> d;
        string s;
        cin >> s;
        int day, tot = 0;
        if(s[5] > '9' || s[5] < '0')day = 5;        
        else day = (s[5] - '0') % 5;
        if(day == 0)day = 5;
        for(int i = 2000; i < y; i++)
            if((i % 4 == 0 && i % 100 != 0) || i % 400 == 0)
                tot += 366;
            else tot += 365;
        for(int i = 1; i < m; i++)
            if(((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && i == 2)
                tot += 29;
            else
                tot += mm[i - 1];
        tot += (d - 1);
        if((tot + 6 - 1) % 7 + 1 == day)
            puts("yes");
        else
            puts("no");
    }
    return 0;
}

#include <set>

#include <map>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 2147483647

using namespace std;

int T;

int y, m, d;

int mm[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main()

{

cin >> T;

while(T--)

{

char ch;

cin >> y >> ch >> m >> ch >> d;

string s;

cin >> s;

int day, tot = 0;

if(s[5] > '9' || s[5] < '0')day = 5;

else day = (s[5] - '0') % 5;

if(day == 0)day = 5;

for(int i = 2000; i < y; i++)

if((i % 4 == 0 && i % 100 != 0) || i % 400 == 0)

tot += 366;

else tot += 365;

for(int i = 1; i < m; i++)

if(((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && i == 2)

tot += 29;

else

tot += mm[i - 1];

tot += (d - 1);

if((tot + 6 - 1) % 7 + 1 == day)

puts("yes");

else

puts("no");

}

return 0;

}

9.人工智能

人工智能一直是计算机学所追求的一个很高的境界，全世界的计算机学家们至今仍在不断努力力求达到这个境界。
这道题也跟“人工智能”有关。
学过初中物理的同学都应该知道物理学中的这个公式P（功率）= U（电压）* I（电流）。如果给定其中的任意两个值，第三个值都是很容易求的，这个就是本题的任务。

#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 2147483647
using namespace std;
int T;
string s;
map<char, double> mp;
double get(int x)
{
    double v = 0, t = 1;
    for(int i = x; i < s.length(); i++)
        if(s[i] >= '0' && s[i] <= '9')
        {
            if(t == 1)
                v = v * 10 + s[i] - '0';
            else
            {
                v = v + (s[i] - '0') * t;
                t *= 0.1;
            }
        }
        else if(s[i] == '.')
            t = 0.1;
        else if(s[i] == 'm')
            v *= 0.001;
        else if(s[i] == 'k')
            v *= 1000;
        else if(s[i] == 'M')
            v *= 1000000;
        else break;
    return v;
}
int main()
{
    cin >> T;
    char ch;
    ch = getchar();
    for(int t = 1; t <= T; t++)
    {
        printf("Problem #%d\n", t);
        getline(cin, s);
        mp['I'] = mp['U'] = mp['P'] = -1;
        for(int i = 0; i < s.length(); i++)
            if(s[i] == '=')
                mp[s[i - 1]] = get(i + 1);
        if(mp['I'] == -1)
            printf("I=%.2lfA\n", mp['P'] / mp['U']);
        if(mp['U'] == -1)
            printf("U=%.2lfV\n", mp['P'] / mp['I']);        
        if(mp['P'] == -1)
            printf("P=%.2lfW\n", mp['U'] * mp['I']);        
        }
    return 0;
}

#include <set>

#include <map>

#include <vector>

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 2147483647

using namespace std;

int T;

string s;

map<char, double> mp;

double get(int x)

{

double v = 0, t = 1;

for(int i = x; i < s.length(); i++)

if(s[i] >= '0' && s[i] <= '9')

{

if(t == 1)

v = v * 10 + s[i] - '0';

else

{

v = v + (s[i] - '0') * t;

t *= 0.1;

}

else if(s[i] == '.')

t = 0.1;

else if(s[i] == 'm')

v *= 0.001;

else if(s[i] == 'k')

v *= 1000;

else if(s[i] == 'M')

v *= 1000000;

else break;

return v;

}

int main()

{

cin >> T;

char ch;

ch = getchar();

for(int t = 1; t <= T; t++)

{

printf("Problem #%d\n", t);

getline(cin, s);

mp['I'] = mp['U'] = mp['P'] = -1;

for(int i = 0; i < s.length(); i++)

if(s[i] == '=')

mp[s[i - 1]] = get(i + 1);

if(mp['I'] == -1)

printf("I=%.2lfA\n", mp['P'] / mp['U']);

if(mp['U'] == -1)

printf("U=%.2lfV\n", mp['P'] / mp['I']);

if(mp['P'] == -1)

printf("P=%.2lfW\n", mp['U'] * mp['I']);

}

return 0;

}

« 《数据结构与算法》编程练习算法竞赛编程变量命名指南 »

hzwer.com _ Home | http://hzwer.com

北京大学计算概论A 2018年期中考试

分类目录

热门文章

Myfriends

近期评论