本文写于 2019年03月10日,距今已超过 1 年,距 2020年07月25日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分
1552195706947

文字显示

1552194065656
1552194079411
1552194084709

一直在犹豫这道题是贪心还是动态规划,想了很久,觉得贪心是成立的,后来事实证明确实是成立的。

处理方法是,如果当前是字母,那么很简单,这一行放得下就放在这一行,放不下就新开一行,只需要用一个变量记录一下当前这一行占用了多少宽度就行。

如果当前处理的是标点,那么找到标点结束的地方,把这一整段标点作为一个整体考虑,要么全放在当前行的末尾,如果当前行放不下,那么这一整段就要放到下面一行。

由于这一段都是标点,所以不能从中间截断,否则就势必会有出现在行首的标点,因此,没有其他情况需要考虑。

对于能直接放在当前行末尾的,那么直接放上去,如果放不下,就要放下一行,但是下一行的行首不能是标点,这意味着要从当前行取出一个字母放到下一行的行首,由于标点只作为一个整体考虑,因此,当前行最后一个一定是字母,不会是标点,所以直接判断所有标点长度加 1 以后的大小是不是够放下一行。

任何情况下出现放不下,直接给出 impossible

对于换行符,由于是无条件换行,所以可以在开始的时候就直接以换行符作为 split,每一段分别计算最短行数,累加得到答案。

特别需要注意的是,\n 的转义是 \\\\n,而不是 \\n。(我以为 \ 的转义是 \\,结果交了一次通过 0% 的样例,修改后再交就是 AC)

import java.util.HashSet;
import java.util.Scanner;

/* 共提交 2 次,第 1 次通过 0% 的样例,第 2 次通过 100% 的样例 */

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int ans = 0;
            int x = in.nextInt();
            int y = in.nextInt();
            String[] ss = in.next().split("\\\\n");
            /* 这里是 \\\\n 表示 \n 的转义,不是 \n 或者 \\n */
            try {
                for (String s : ss) {
                    if (s.length()==0)
                        continue;
                    ans += solve(x,y,s);
                }
            } catch (Exception e) {
                System.out.println("impossible");
                continue;
            }
            System.out.println(ans);
        }
        in.close();
    }

    private static int solve(int x, int y, String s) throws Exception {
        final HashSet<Character> SYMBOL = new HashSet<Character>();
        SYMBOL.add(',');
        SYMBOL.add('.');
        SYMBOL.add('!');
        SYMBOL.add('?');
        int len = s.length();
        int index = 0;
        int yy = 0;
        int ret = 0;
        while (index < len) {
            char c = s.charAt(index);
            if (!SYMBOL.contains(c)) {
                if (yy + x <= y) {
                    yy += x;
                } else {
                    ret++;
                    yy = x;
                }
                index++;
            } else {
                int begin = index;
                while (index < len && SYMBOL.contains(s.charAt(index)))
                    index++;
                int end = index;
                if (yy + x * (end - begin) <= y) {
                    yy += x * (end - begin);
                } else if (x * (end - begin + 1) <= y){
                    yy = x * (end - begin + 1);
                    ret++;
                } else {
                    throw new Exception();
                }
            }   
        }   
        return ret + 1;
    }
}

特殊键盘

1552195485080
1552195488104

最短路径。

这道题看出是最短路径以后就非常简单了,由于只有 26 个字母,所以直接无脑 Floyd 跑三重循环。

注意自己到自己的距离是 1,遇到一个 shift 就加 1。或者也可以自己到自己的距离为 0,最后得到的最短路长度加上原始文章的长度(因为每个按键至少按一次)。

计算出最短路径以后,把损坏的按键那一行的点全部置为无穷大。

计算最短路,如果最短路结果为无穷大,则这篇文章不可能被输出。

import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int n = in.nextInt();
            int[][] keyboard = new int[26][26];
            final int INFINITY = 1000;
            for (int i = 0; i < keyboard.length; i++)
                for (int j = 0; j < keyboard[i].length; j++) {
                    if (i == j)
                        keyboard[i][j] = 0;
                    else 
                        keyboard[i][j] = INFINITY;
                }
            for (int i = 0; i < n; i++) {
                int x = in.next().charAt(0) - 'a';
                int y = in.next().charAt(0) - 'a';
                keyboard[x][y] = 1; 
            }
            int m = in.nextInt();
            HashSet<Character> broken = new HashSet<Character>();
            for (int i = 0; i < m; i++) {
                char c = in.next().charAt(0);
                broken.add(c);
            }

            for (int k = 0; k < keyboard.length; k++)
                for (int i = 0; i < keyboard.length; i++)
                    for (int j = 0; j < keyboard.length; j++)
                        if (keyboard[i][j] > keyboard[i][k] + keyboard[k][j])
                            keyboard[i][j] = keyboard[i][k] + keyboard[k][j];

            for (char c : broken) 
                for (int j = 0; j < keyboard.length; j++) 
                    keyboard[c - 'a'][j] = INFINITY;
            String s = in.next();
            int len = s.length();
            int ans = len;
            for (int index = 0; index < len; index++) {
                int c = s.charAt(index) - 'a';
                int who = c;
                for (int i = 0; i < keyboard.length; i++)
                    if (keyboard[i][c] < keyboard[who][c])
                        who = i;
                if (keyboard[who][c] == INFINITY)
                    ans = -1;
                else 
                    ans += keyboard[who][c];
                if (ans == -1)
                    break;
            }
            System.out.println(ans);
        }
        in.close();
    }
}

AOE

1552195692144
1552195694653
1552195697244

这道题目我没做出来,没能转化成可以做的题。

我在考虑的是,所有点两两组队,计算两点之间的距离,如果小于等于直径,求两点中点,以中点画圆,看半径覆盖范围内最大有多少点。

后来证明这个思路是错的。考试结束后问 zerol,他说要转化一下,把一个圆覆盖多少个点,转化为:以每个点为圆心,画半径为 r 的圆,问所有圆之间会有相互重叠的地方,问哪个地方被最多的圆重叠,那么站在这个区域内施法,就可以攻击到最多的目标。

圆与圆相互重叠最厚的那儿就是施法点,由于圆的边界也是可以攻击到目标的,所以只需要遍历所有圆的交点,看哪个点最多个圆相交。

0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论