【游记】Code M 2018 滚粗记

Day 资格赛

其实我是在航电的OJ上面看到这个比赛的,说实话我觉得HDOJ特别难用
然后随便报了个名,发现可以中学生参赛,却没有中学给我填,那我就只好233,填了THU,事后觉得给THU丢脸了
顺手A了一题,然后发现后面几题有点不好做,就不管了。

Day 初赛A轮

当天才收到晋级通知的,还蛮开心。
不过这题面着实比较xx,很多我都没有涉及过的样子,顺便发个题面:

A轮T1

题面

小美想要在电视上看电影,我们知道在电视上搜索电影可以通过搜索电影名字首字母缩写得到,通过首字母搜索电影的界面由一个九宫格组成,如下图:
| @!: | ABC | DEF |
| ———— | ———— | ———— |
| GHI | JKL | MNO |
| PQRS | TUV | WXYZ |
光标初始在这个九宫格的左上方,也就是在 “@!:”的位置,每次小美想要输入一个字母,需要通过不断地按上下左右四个方向键(并且只能按方向键),把光标从当前所在的格子移动到目标的格子(也就是待输入的字母所在的格子),然后在目标的格子上通过其他的按键来输入字母。小美觉得频繁地按方向键是十分烦人的事情,所以她想设计一种移动光标方案使得方向键按的次数最少。问最少要几次?
小美想看$ T $部电影,所以她会问你$ T $个电影名字的缩写分别需要多少次输入。
注意在一个电影名字输入完以后,光标会回到左上角,期间按的方向键不会计入答案。
输入描述:
第一行一个$T(T ≤ 10)$,表示小美想看的电影数。
接下来$ T $行,每行一个长度不超过$100,000$的字符串,表示一部电影名字的缩写,保证缩写的每个字符都是大写英文字母。
输出描述:
对于每个电影名字缩写,输出输入这个名字的最小按方向键的次数。
示例1
输入

2
AA
AT

输出

1
3

这题非常水,好像也是我唯一$100$%$AC$的题哇,我好菜,直接打暴力就好了。

#include<cstdio>
#include<string>
#include<iostream> 

using namespace std;

int main(){
    int T;scanf("%d",&T);

    string name;
    while(T--){
        cin >> name;
        int ans = 0,pos = 1;
        int len = name.size();
        if(name[0] == 'A' || name[0] == 'B' || name[0] == 'C'){
            ans = 1;pos = 2;
        }else if(name[0] == 'D' || name[0] == 'E' || name[0] == 'F'){
            ans = 2;pos = 3;
        }else if(name[0] == 'G' || name[0] == 'H' || name[0] == 'I'){
            ans = 1;pos = 4;
        }else if(name[0] == 'J' || name[0] == 'K' || name[0] == 'L'){
            ans = 2;pos = 5;
        }else if(name[0] == 'M' || name[0] == 'N' || name[0] == 'O'){
            ans = 3;pos = 6;
        }else if(name[0] == 'P' || name[0] == 'Q' || name[0] == 'R' || name[0] == 'S'){
            ans = 2;pos = 7;
        }else if(name[0] == 'T' || name[0] == 'U' || name[0] == 'V'){
            ans = 3;pos = 8;
        }else if(name[0] == 'W' || name[0] == 'X' || name[0] == 'Y' || name[0] == 'Z'){
            ans = 4;pos = 9;
        }
        for(int i = 0;i < len - 1;i++){
            if(pos == 2){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 0;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 1;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 2;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 1;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 2;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 3;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 2;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 3;pos = 9;
                }
            }else if(pos == 3){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 1;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 0;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 3;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 2;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 1;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 4;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 3;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 2;pos = 9;
                }
            }else if(pos == 4){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 2;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 3;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 0;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 1;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 2;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 1;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 2;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 3;pos = 9;
                }
            }else if(pos == 5){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 1;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 2;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 1;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 0;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 1;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 2;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 1;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 2;pos = 9;
                }
            }else if(pos == 6){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 2;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 1;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 2;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 1;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 0;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 3;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 2;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 1;pos = 9;
                }
            }else if(pos == 7){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 3;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 4;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 1;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 2;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 3;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 0;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 1;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 2;pos = 9;
                }
            }else if(pos == 8){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 2;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 3;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 2;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 1;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 2;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 1;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 0;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 1;pos = 9;
                }
            }else if(pos == 9){
                if(name[i + 1] == 'A' || name[i + 1] == 'B' || name[i + 1] == 'C'){
                    ans += 3;pos = 2;
                }else if(name[i + 1] == 'D' || name[i + 1] == 'E' || name[i + 1] == 'F'){
                    ans += 2;pos = 3;
                }else if(name[i + 1] == 'G' || name[i + 1] == 'H' || name[i + 1] == 'I'){
                    ans += 3;pos = 4;
                }else if(name[i + 1] == 'J' || name[i + 1] == 'K' || name[i + 1] == 'L'){
                    ans += 2;pos = 5;
                }else if(name[i + 1] == 'M' || name[i + 1] == 'N' || name[i + 1] == 'O'){
                    ans += 1;pos = 6;
                }else if(name[i + 1] == 'P' || name[i + 1] == 'Q' || name[i + 1] == 'R' || name[i + 1] == 'S'){
                    ans += 2;pos = 7;
                }else if(name[i + 1] == 'T' || name[i + 1] == 'U' || name[i + 1] == 'V'){
                    ans += 1;pos = 8;
                }else if(name[i + 1] == 'W' || name[i + 1] == 'X' || name[i + 1] == 'Y' || name[i + 1] == 'Z'){
                    ans += 0;pos = 9;
                }
            }
        }
        printf("%d\n",ans);
    }

    return 0;
} 

A轮T2

题目描述
有一个$1\times n$的棋盘,上面有若干个棋子,一个格子上可能有多个棋子。
你每次操作是先选择一个棋子,然后选择以下两个操作中的一个:
(1) 若该棋子不在 $(1,1)$,让这个棋子往左走一格,即从 $(1,x)$ 走到 $(1,x-1)$;
(2) 若该棋子不在 $(1,n)$,且这个棋子曾经到达过$(1,1)$,让这个格子往右走一格,即从 $(1,x)$ 走到 $(1,x+1)$。
给定一开始每个格子上有几个棋子,再给定目标局面每个格子上需要几个棋子,求最少需要多少次操作。

输入描述:
第一行一个正整数$n$表示棋盘大小。
第二行$n$个非负整数$a_1, a_2, …, a_n$表示一开始 $(1,i)$ 上有几个棋子。
第三行n个非负整数$b_1, b_2, …, b_n$表示目标局面里 $(1,i)$ 上有几个棋子。
保证 $1 \leq n \leq 100,000$,

输出描述:
输出一个非负整数,表示最少需要几次操作。
示例1
输入

5
0 0 1 1 0
1 0 0 0 1

输出

9

说明
先把$(1,3)$上的棋子走到$(1,1)$,花费了$2$次操作。
然后把$(1,4)$上的棋子走到$(1,1)$,再往右走到$(1,5)$,花费了$3+4=7$次操作。
所以一共花了$9$次操作。

A轮T3

题目描述
在点点和评评的世界里有一个城市,城市是一个树形结构,由$n$个节点组成,有$n-1$条双向边把这些节点连在了一起(即在任意两个节点$AB$之间都存在从$A$到$B$的路径)。每条边都有一个边权,表示通过这条边需要的时间。
现在点点和评评想要从他们所在的$S$点到$T$点参加会议,他们想要在过程中体会旅途的乐趣,即好好欣赏每条边上的风景。详细地说,对于每条边,都有一个值$l$,$l$表示在从$S$点到$T$点的过程中,最少需要经过这条边的次数。因为会期将至,所以点点和评评想要在看够风景的情况下,花费尽可能少的时间。
点点和评评一共想询问$m$组这样的$S$和$T$,每组询问单独考虑,对于某一组特定的询问,他们想知道最少需要花费的时间。
输入描述:
第一行一个整数$n(1 ≤ n ≤ 100,000)$表示点数。
接下来$n-1$行,每行四个整数$x, y, z, l(1 ≤ x, y ≤ n, 1 ≤ z, l ≤ 1,000,000,000)$,表示从$x$到$y$之间有一条边权为$z$的边,并且这条边至少要经过$l$次。
数据保证没有重边和自环。
接下来一个整数$m(1 ≤ m ≤ 100,000)$表示询问组数。
接下来$m$行,每行两个整数$S, T(1 ≤ S, T ≤ n)$表示一组询问。
输出描述:
输出m行,每行一个整数表示答案,因为答案可能很大,请输出答案 $mod 1,000,000,007$的值。
示例1
输入

3
1 2 10 1  
2 3 20 2
2
1 3
3 2

输出

70
80

说明
路径为:
$1->2->3->2->3$
$3->2->1->2->3->2$

A轮T4

题目描述
给定一个$n\times m$的迷宫,其中任意两个相邻单元之间可能存在墙,定义从单元$S$到单元$T$的路径为从$S$出发,通过向上、下、左、右四个方向上的移动组合,在不通过墙的前提下,最终到达$T$的轨迹。数据保证迷宫中的任意两点之间存在合法的路径。现在考虑一张有$k$个顶点的完全图$G$, 其中每个顶点对应迷宫中的某个单元,并且任意两个顶点之间连边的长度为其所对应迷宫单元之间的最短路径的长度。求$G$的最小生成树的边权和。
输入描述:
第一行三个正整数$n, m, k (2 ≤ n, m ≤ 2,000, k ≤ 100,000)$。
接下来$n$行,每行$m-1$个 $0/1$。其中$i$行第$j$个数描述单元$(i, j)$和$(i, j+1)$之间是否存在墙。($1$表示有墙,$0$表示没墙)
接下来$n-1$行,每行$m$个 $0/1$。其中$i$行第$j$个数描述单元$(i, j)$和$(i+1, j)$之间是否存在墙。($1$表示有墙,$0$表示没墙)
接下来$k$行,每行两个正整数$x, y$,描述$G$中一个顶点所对应的单元,其中$x$代表行号,$y$代表列号。保证这$k$个顶点所对应的单元两两不同。
输出描述:
输出一行一个整数,描述最小生成树的边权和。
示例1
输入

5 5 3
0111
0010
0101
0110
0111
10000
10000
10001
10000
1 4
4 3
4 2

输出

9

A轮T5

题目描述
袋鼠先生最近迷上了玩塔防游戏。塔防游戏中有若干座防御塔。一些防御塔能覆盖的范围为这里面任意三个防御塔形成的三角形区域的并集。注意这里的三角形包括边界,且如果三角形退化那么就相当于一条线段。换句话说,三个或以上的防御塔所能覆盖的范围为这些点形成的凸包,小于三个的防御塔没有任何功能。
袋鼠先生发现有些防御塔和其他防御塔不同,如果拆除这个防御塔会导致防御的区域缩小那么我们称这个防御塔为关键的防御塔。这里区域缩小包括区域的面积减小,线段变短,或者从有到无。
袋鼠先生在建造某些防御塔上面氪了很多金币,所以袋鼠先生希望能通过拆除其他的防御塔使得他氪过金币的防御塔全部成为关键的防御塔。还有一点,袋鼠先生希望剩下的防御塔能覆盖的面积是正的。
袋鼠先生想知道有多少种这样的方案,答案可能很大,所以要对$1,000,000,007$取模。
输入描述:
第一行一个整数$n (1 ≤ n ≤ 200)$。

接下来n行每行三个整数$X_i, Y_i, W_i(0 ≤ |X_i|, |Y_i| ≤ 1,000,000,000, W_i \in (0,1))$。$(X_i, Y_i)$表示每个塔的坐标。$W_i$表示每个塔的属性,如果$W_i = 0$表示这个塔可以拆除,否则表示这个塔不可拆除。

数据保证没有重点。
输出描述:
输出一行表示答案,即有多少种方案。
示例1
输入

5
0 0 0
0 2 0
2 0 0
2 2 0
1 1 1

输出

4

示例2
输入

8
0 0 0
0 1 1
0 2 0
1 2 1
2 2 0
2 1 1
2 0 0
1 0 1

输出

7

示例3
输入

6
0 0 0
0 4 0
4 0 0
4 4 0
2 2 1
2 1 0

输出

11

A轮T6

题目描述
小团在美团旅行的安全部门实习研究加密算法,他提出了一个加密算法。现在小团把解密算法告诉你,希望你对数据进行解密。
加密数据包有两部分构成,一对数字$a, b$和一个字符串$S$。解密的方式$S$串最早在$a/b$的小数部分出现的位置$k$,$k$即为解密信息。小数点后从$1$开始计数。如果$a/b$不是一个无限循环小数,则在认为后面有无穷多个$0$,如$5/4=1.2500000000…$。
如果$S$不在$a/b$的小数部分出现,则无法解密输出$-1$。
输入描述:
第一行两个正整数$a, b (1 ≤ a, b ≤ 1,000,000,000)$。第二行一个数字串$S(1 ≤ |S| ≤100,000)$。
输出描述:
输出一行$k$表示答案。
示例1
输入

1 2
500000000000

输出

1

示例2
输入

1234 5678
4579

输出

8

示例3
输入

233 999
333

输出

-1

这一题对于Java来说非常好做,但是因为Java比较慢,所以大概只能得到一半的分。

import java.io.BufferedInputStream;
import java.math.BigDecimal;
import java.util.Scanner;;

public class Main {
    static Scanner in = new Scanner(new BufferedInputStream(System.in));
    public static void main(String[] args) {
        long a = in.nextLong(),b = in.nextLong();
        String s = in.next();

        boolean isDiv = false;
        if(a % b == 0) {
            isDiv = true;
        }

        int eps = (int) 2e5 + (int)1e5;
        BigDecimal A = new BigDecimal(a);
        BigDecimal B = new BigDecimal(b);
        if(isDiv == true) {
            String GG = "00000000000000000000000000000000000000";
            System.out.println(GG.indexOf(s,0));
            System.exit(0);
        }

        BigDecimal ans = A.divide(B,eps,BigDecimal.ROUND_DOWN);

        String GG = "00000000000000000000000000000000000";

        String ANS = ans.toString();
        ANS = ANS.substring(ANS.indexOf('.'));
        ANS += GG;
        System.out.println(ANS.indexOf(s,0));
    }
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注