程序设计思维与实践
8 minutes read (About 1138 words)

Csp-M1

CSP-M1

最后一题写炸，220滚粗（

T1 咕咕东的奇遇

题目描述

咕咕东是个贪玩的孩子，有一天，他从上古遗迹中得到了一个神奇的圆环。这个圆环由字母表组成首尾相接的环，环上有一个指针，最初指向字母a。咕咕东每次可以顺时针或者逆时针旋转一格。例如，a顺时针旋转到z，逆时针旋转到b。咕咕东手里有一个字符串，但是他太笨了，所以他来请求你的帮助，问最少需要转多少次。

image-20200320001121670
输入格式

输入只有一行，是一个字符串。

输出格式

输出最少要转的次数。

问题分析

单纯模拟，假设c为当前所在字母，s[i]为目标字母，每次答案加上短弧即可

$min(abs(c-s[i]),26-abs(c-s[i]))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
    string s;
    cin>>s;
    char c = 'a';
    int ans =0;
    for(int i = 0;i<s.size();i++){
        ans += min(abs(c-s[i]),26-abs(c-s[i]));
        c = s[i];
    }
    cout<<ans;
    return 0;
}

T2 咕咕东想吃饭

题目描述

咕咕东考试周开始了，考试周一共有n天。他不想考试周这么累，于是打算每天都吃顿好的。他决定每天都吃生煎，咕咕东每天需要买$a_i$个生煎。但是生煎店为了刺激消费，只有两种购买方式：①在某一天一次性买两个生煎。②今天买一个生煎，同时为明天买一个生煎，店家会给一个券，第二天用券来拿。没有其余的购买方式，这两种购买方式可以用无数次,但是咕咕东是个节俭的好孩子，他训练结束就走了，不允许训练结束时手里有券。咕咕东非常有钱，你不需要担心咕咕东没钱，但是咕咕东太笨了，他想问你他能否在考试周每天都能恰好买$a_i$个生煎。

输入格式

输入两行，第一行输入一个正整数n(1<=n<=100000)(1<=n<=100000)，表示考试周的天数。

第二行有n个数，第i个数a_i（0<=a_i<=10000）ai（0<=ai<=10000）表示第i天咕咕东要买的生煎的数量。

输出格式

如果可以满足咕咕东奇怪的要求，输出”YES”，如果不能满足，输出“NO”。（输出不带引号）

问题分析

image-20200320002050344

样例可以抽象为上面这种方块，那么我们可以将问题转化为：有两种取法（红蓝），问能不能将方块取完。

可以采取贪心策略：从左到右按列取，对于每列：

  • 如果是奇数，则采取n蓝色取法+1\红色取法（后面一列方块数量-1）
  • 如果是偶数，则采取n*蓝色取法

除了最后一列，前面的列按上述方法必然可以取完。如果遇到不够减的情况则必然无法达到要求。

对每一列处理，最后检查最后一列是否为奇数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxx = 100010;
int t[maxx];
int main(){
    int n ;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>t[i];
    }
    for(int i = 1;i<=n;i++){
        if(t[i]%2 == 1){
            if(t[i+1] == 0){
                cout<<"NO";
                return 0;
            }else t[i+1]--;
        }else{
            t[i] = 0;
        }
    }
    cout<<"YES";
    return 0;
}

T3 可怕的宇宙射线

问题描述

有一个射线，每次可以向左右45°方向分裂，问射线最终能覆盖到多少个位置。

输入描述

第一行一个正整数n表示分裂次数$(n\leq 30)$

第二行n个正整数，表示每次分裂后直线传播的长度($a_i\leq 5$)

输出描述

一个数ans表示有多少个位置被覆盖

样例说明
image-20200320004717982

问题分析

  • 表面上题目的数据范围十分巨大2^30，实际上每次分裂仅走5，分裂三十次的话，射线最远仅能覆盖到300*300的范围。

  • 那么我们可以直接用搜索，bfs dfs均可，只要剪枝剪的好，没啥搜索过不了（雾。

  • 考虑同次分裂产生的射线有可能形成“T”字重合，这种情况可以剪掉。

  • 再进一步，对于我们记flag[300][300][30][8]​为图上某点的状态值，30为最大分裂次数，8为方向。也就是说，对于从同一次分裂产生的同方向的射线，我们是完全不用重复遍历的，可以通过记录这个状态给他剪掉。

  • 但是即使是不同方向的射线经过同一个点，这个点最多对答案产生一点贡献，因此需要另开一个无次数无方向，只记录走没走过的数组vis[300][300]

  • 其实还可以再进一步，把分裂次数一维改为：在某方向上剩下要走的单位数，因为如果方向相同+要走的步数相同，就是完全重合的射线了。就可以更大程度上剪枝。但是好像没必要就直接过了。

代码

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
bool vis[355][355];
long long ans;
int zx[8] = {0,1,1,1,0,-1,-1,-1};
int zy[8] = {1,1,0,-1,-1,-1,0,1};
int sum;
bool flag[355][355][160][8];
int turn[200];
int count;
struct rec{
    int x,y,d,t;
    rec(int x,int y,int d,int t):x(x),y(y),d(d),t(t){}
};
void bfs(){
    queue<rec> q;
    rec first(160,160,0,1);
    q.push(first);
    while(!q.empty()){
        rec h = q.front();
        q.pop();
        if(h.t > sum || flag[h.x][h.y][h.t][h.d]){
            continue;
        }
        flag[h.x][h.y][h.t][h.d] = 1;
        if(!vis[h.x][h.y]){
            ans++;
            vis[h.x][h.y] = 1;
        }
        if(!turn[h.t]){
            rec nex(h.x + zx[h.d] , h.y + zy[h.d], h.d, h.t+1);
            q.push(nex);
        }else{
            int d1 = (h.d+1)%8;
            int d2 = (h.d+7)%8;
            rec nex1(h.x + zx[d1] , h.y + zy[d1], d1, h.t+1);
            rec nex2(h.x + zx[d2] , h.y + zy[d2], d2, h.t+1);
            q.push(nex1);
            q.push(nex2);
        }
    }
}
int main(){
    int n ;
    cin>>n;
    int t;
    for(int i = n;i>=1;i--){
        cin>>t;
        sum += t;
        turn[sum] = 1;
    }
    bfs();
    cout<<ans;
    return 0;
}
# 搜索, 模拟, 贪心
程设Week4-作业
Tkinter+Graphviz+Swig|如何用Python调用c++接口实现跳表结构动态展示GUI
Follow
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×