山东省第七届ACM大学生程序设计竞赛解题报告【8/12】

发表于 | 更新于 | 分类于
－－－－－－－－－－－山东省第七届ACM大学生程序设计竞赛解题报告－－－－－－－－－－ －

A.Julyed【签到】

题意：寻找最小的 $k$使得$ k × M ≥ N$。

思路：输出$\lceil \frac{N}{M} \rceil$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t, a, b;
    cin >> t;
    while(t--)
    {
        cin >> a >> b;
        cout << (a/b)+((a%b) != 0) << endl;
    }
    return 0;
}

B.Fibonacci【模拟】

题意：将一个正整数表示为若干个不连续的 Fibonacci 数之和。

思路：对于正整数 $N$, 每次选择不超过它的最大的 Fibonacci数$x$，之后转
为$ N − x$的子问题。可以证明如果不选择最大的 Fibonacci 数$x$，以后所选择的 Fibonacci
数的和是小于$x$的，所以必须选择$x$。

Zeckendorf 定理: 任何正整数可以表示为若干个不连续的 Fibonacci 数之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 55;

int t, n, a[N];
void init()
{
    a[0] = 1; a[1] = 2;
    for(int i = 2; i < 44; ++i)
        a[i] = a[i - 1] + a[i - 2];
}
int main()
{
    init();
    scanf("%d", &t);
    while(t--)
    {
        vector<int> G;
        scanf("%d", &n);
        printf("%d=", n);
        while(n)
        {
            int pos = upper_bound(a, a + 44, n) - a;
            G.push_back(a[pos-1]);
            n -= a[pos-1];
        }
        for(int i = G.size() - 1; i >= 0; --i)
            printf("%d%c", G[i], i == 0 ? '\n' : '+');
    }
    return 0;
}

C.Proxy【最短路】

题意：给定一个有向图$G$和起点$S$、终点$T$。输出最短路上除起点外的第一个点，同时使得这个点的标号最小。

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn =10010;
const int maxm =100010;
const int inf = 0x3f3f3f3f;
int n,m;
struct node{
    int v,ne,len;
}ed[maxm];
int head[maxn],cnt;
int vis[maxn];
struct fucker{
    int dis,num;
}d[maxn];
void init(){
    memset(vis,0,sizeof vis);
    memset(head,-1,sizeof head);
    cnt=0;
}
void add(int u,int v,int len){
    ed[cnt].len=len;
    ed[cnt].v=v;ed[cnt].ne=head[u];head[u]=cnt++;
}
void spfa(){
    for(int i=0;i<=n+1;i++){
        d[i].dis=inf;
    }
    d[0].dis=0;d[0].num=0;
    queue<int>q;
    vis[0]=1;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];~i;i=ed[i].ne){
            int v=ed[i].v;
            if(d[v].dis>d[u].dis+ed[i].len){
                d[v].dis=d[u].dis+ed[i].len;
                if(d[u].num==0)d[v].num=v;
                else d[v].num=d[u].num;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
            else if(d[v].dis==d[u].dis+ed[i].len){
                int pos=d[u].num;
                if(pos==0)pos=v;
                if(pos<d[v].num){
                    d[v].num=pos;
                    if(!vis[v]){
                        q.push(v);
                        vis[v]=1;
                    }
                }
            }
        }
    }
}
int main()
{
    int te;
    ios::sync_with_stdio(0);
    cin>>te;
    while(te--){
        cin>>n>>m;
        init();
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        spfa();
        if(d[n+1].dis==inf){
            cout<<-1<<"\n";
        }
        else if(d[n+1].num==n+1){
            cout<<0<<"\n";
        }
        else{
            cout<<d[n+1].num<<"\n";
        }
    }
    return 0;
}

D.Swiss-system tournament

题意：

思路：归并排序的模拟？

E.The Binding of Isaac【模拟】

题意：给定一个$N × M$的01矩阵。统计只和1个1元素共享边的0的个数。

思路：直接做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
const int MAX = 105;
char mapa[MAX][MAX];

int main()
{
    int t;
    int n, m;
    cin >> t;

    while(t--)
    {
        cin >> n >> m;
        for(int i = 0; i < n; ++i)
            scanf("%s",mapa[i]);

        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                if(mapa[i][j] == '#') continue;
                int num = 0;
                if(i > 0 && mapa[i-1][j] == '#') num++;
                if(j > 0 && mapa[i][j-1] == '#') num++;
                if(i < n-1 && mapa[i+1][j] =='#') num++;
                if(j < m-1 && mapa[i][j+1] == '#') num++;
                if(num == 1) ans++;
            }
        }

        for(int i = 0; i<m; i++)
        {
            if(mapa[0][i] == '#') ans++;
            if(mapa[n-1][i] == '#') ans++;
        }

        for(int i = 0; i<n; i++)
        {
            if(mapa[i][0] == '#') ans++;
            if(mapa[i][m-1] == '#') ans++;
        }

        cout << ans << endl;
    }
    return 0;
}

F.Feed the monkey

题意：统计长度为$N$的含有$3$个元素的排列个数。其中1最多连续出现$D1$次，2最多连续出现$D2$次，3最多连续出现$D3$次。

思路：DP？

G.Triple Nim【规律】【二进制】

题意：将$n$块石子分为三堆，问能有多少种情况满足分完后先手必败。

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, n;
long long res[44];
void init()
{
    res[0] = 1;
    for(int i = 1; i < 28; ++i)
        res[i] = res[i - 1] * 3 + 1;
}

int main()
{
    init();
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        if(n & 1)
        {
            puts("0");
            continue;
        }

        int tem = n, cnt = 0;
        while(tem)
        {
            if(tem & 1) ++cnt;
            tem >>= 1;
        }
        if(cnt == 1)
            puts("0");
        else
            printf("%lld\n", res[cnt-2]);
    }
    return 0;
}

H.Memory Leak【模拟】

题意：内存泄漏是指当输入的字符串的长度≥数组的大小时出现的一种bug，这时超出长度的部分不会被存储而且在输出时会一直输出下去知道碰到’\0’。给出一些列的定义语句，问输出时的结果是什么。

思路：存储每个内存块的内容 && 标记每个内存块是否泄漏就完成任务了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int N = 10010;

int T, tem;
string s, t, c;
map<string, int> id;
map<int, string> co;
bool leak[N];
int len[N], idx;
int main()
{
    scanf("%d", &T);
    getchar();
    while(T--)
    {
        idx = 0;
        id.clear();
        co.clear();
        memset(leak, 0, sizeof(leak));
        memset(len, 0, sizeof(len));
        while(getline(cin, s) && s[0] != 'r')
        {
            if(s[1] == 'h')
            {
                for(int i = 0; i < s.size(); ++i)
                {
                    if(s[i] == ' ')
                    {
                        t = "";
                        ++i;
                        while(s[i] != '[')
                        {
                            t += s[i]; ++i;
                        }
                        id[t] = idx;
                        tem = 0;
                        ++i;
                        while(s[i] != ']')
                        {
                            tem = tem * 10 + (s[i] - '0');
                            ++i;
                        }
                        len[idx] = tem;
                        ++idx;
                    }
                }
            }
            /*
            for(int i = 0; i < idx; ++i)
                cout << len[i] << '\n';
            for(auto it = id.begin(); it != id.end(); ++it)
                cout << it -> first << '\n';
            */
            else if(s[1] == 'e')
            {
                t = c = "";
                int i;
                for(i = 5; s[i] != ' '; ++i)
                {
                    t += s[i];
                }
                ++i;
                c = s.substr(i);
//                cout << t << ' ' << c << endl;
//                for(; i < s.size(); ++i)
//                {
//                    c += s[i];
//                }
                tem = id[t];
                if(c.size() >= len[tem])
                    leak[tem] = 1;
                else
                    leak[tem] = 0;
//                cout << c.size() << ' ' << len[tem] << endl;
                co[tem] = c;
            }
            else
            {
                t = s.substr(5);
                tem = id[t];
                for(int j = 0; j < min(len[tem], (int)co[tem].size()); ++j)
                        cout << co[tem][j];
                if(leak[tem])
                {
                    for(int i = tem + 1; i < idx; ++i)
                    {
                        if(leak[i - 1])
                        {
                            for(int j = 0; j < min(len[i], (int)co[i].size()); ++j)
                                cout << co[i][j];
                        }
                        else
                            break;
                    }
                }
                cout << '\n';
//                cout << t << '\n';
            }
//            for(auto it = co.begin(); it != co.end(); ++it)
//                cout << it -> first << '\n';
        }
    }
    return 0;
}

I.Rock Paper Scissors

题意：

思路：

J.Execution of Paladin【贪心】

题意：炉石传说的背景，队友做的，据说是个简单的贪心。

思路：贪心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int te,n,m;
    ios::sync_with_stdio(0);
    cin>>te;
    while(te--){
        cin>>n>>m;
        int zf=0,cfsum=0,cfsh=0;
        for(int i=0;i<n;i++){
            string m;
            cin>>m>>m;
            if(m=="Warleader"){
                zf++;
            }
            if(m=="Warrior"){
                cfsum++;
            }
            if(m=="Murk-Eye"){
                cfsh+=n-1;
                cfsum++;
            }
        }
        cfsh+=2*cfsum*zf;
        cfsh+=2*cfsum;
        if(cfsh>=m){
            cout<<"Mrghllghghllghg!"<<endl;
        }
        else{
            cout<<"Tell you a joke, the execution of Paladin."<<endl;
        }
    }
    return 0;
}

K.Reversed Words【签到】

题意：反转字符串。

思路：做就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;

int main()
{
    int t;
    string s, tem;
    cin >> t;
    getchar();
    while(t--)
    {
        getline(cin, s);
        stringstream ss(s);
        int cou = 0;
        while(ss >> tem)
        {
            if(cou) cout << " ";
            reverse(tem.begin(),tem.end());
            cout << tem;
            cou++;
        }
        puts("");
    }
    return 0;
}

L.Password

题意：

思路：

Donate comment here
0%