您现在的位置是:首页 > 正文

Luogu十月月赛整理

2024-04-01 04:04:09阅读 1

前言: 这就是上次心态做崩的那次比赛,由于太弱现在也仅仅做出来三道,第一道是纯模拟题,但要注意几个点,否则是AC不了的;第二道是一个思维题,第三道是一个图论题,用到了DFS和SPFA算法还有差分约束;话不多说,先上代码。

ps:题目来自luogu

打字游戏

题目描述

R 君在练习打字。

有这样一个打字练习网站,给定一个范文和输入框,会根据你的输入计算准确率和打字速度。可以输入的字符有小写字母、空格和 .(英文句号),输入字符后,光标也会跟着移动。

输入的文本有多行,R 君可以通过换行键来换行,换行后光标移动到下一行的开头。

R 君也可以按退格键(为了方便,退格键用 < 表示),以删除上一个打的字符,并将光标回移一格。特殊的,如果此时光标已经在一行的开头,则不能继续退格(即忽略此时输入的退格键)。

网站的比较方式遵循以下两个原则:

  • 逐行比较,即对于范文和输入的每一行依次比较,不同行之间不会产生影响,多余的行会被忽略。
  • 逐位比较,即对于两行的每一个字符依次比较,当且仅当字符相同时才会被算作一次正确,否则会被算作错误。计算答案时,只统计相同的字符个数。

需要注意的是,回车键不会被计入正确的字符个数。

R 君看到网站上显示他花了 T 秒完成了这次的打字游戏,请你计算出他的 KPM(Keys per minutes,每分钟输入的字符个数),答案四舍五入保留整数部分。

输入格式

R 君会依次告诉你网站的范文,他的输入和花费的时间。

其中范文和输入将会这样读入:给定若干行字符串,以单独的一行 EOF 结束,其中 EOF 不算入输入的文本。

最后一行一个整数 T,表示他打字花费了 T 秒。

可以参考样例输入输出文件和样例解释辅助理解。

输出格式

一行一个整数,表示 KPM。

输入输出样例

输入 #1

hello world.
aaabbbb
x
EOF
heelo world.
aaacbbbb
y<x
EOF
60

输出 #1

18

AC代码

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        String[] strin = new String[10010];
        int index1 = 1;
        String[] strout = new String[10010];
        int index2 = 1;

        String putin = "nu";
        strin[0] = "nu";
        while (!putin.equals("EOF")) {
            putin = sc.nextLine();
            if (!putin.equals("EOF")) {
                strin[index1] = putin;
                index1++;
            }
        }

        putin = "nu";
        strout[0] = "nu";
        while (!putin.equals("EOF")) {
            putin = sc.nextLine();
            if (!putin.equals("EOF")) {
                strout[index2] = putin;
                index2++;
            }
        }

        int time = sc.nextInt();
        int sum = 0;
        double kpm = 0.0;

        if (index1 > index2) {
            index1 = index2;
        }
        //循环判断
        for (int i = 1; i < index1; i++) {
            String standard = strin[i];
            String myputin = strout[i];
            //对范文退格键进行处理
            if (standard.contains("<")) {
                StringBuffer tmp = new StringBuffer(standard);
                while (standard.contains("<")) {
                    if (tmp.charAt(0) == '<') {
                        tmp = tmp.delete(0,1);
                        standard = String.valueOf(tmp);
                        continue;
                    }
                    if (tmp.length() == 2) {
                        tmp = tmp.delete(0,1);
                        standard = String.valueOf(tmp);
                        break;
                    } else if (tmp.length() == 1) {
                        standard = String.valueOf(tmp);
                        break;
                    }
                    int x  = tmp.indexOf("<");
                    tmp = tmp.delete(x-1,x+1);
                    standard = String.valueOf(tmp);
                }
            }
            //对范文退格键进行处理
            if (myputin.contains("<")) {
                StringBuffer tmp = new StringBuffer(myputin);
                while (myputin.contains("<")) {
                    if (tmp.charAt(0) == '<') {
                        tmp = tmp.delete(0,1);
                        myputin = String.valueOf(tmp);
                        continue;
                    }
                    if (myputin.length() == 2) {
                        tmp = tmp.delete(0,1);
                        myputin = String.valueOf(tmp);
                        break;
                    } else if (myputin.length() == 1) {
                        myputin = String.valueOf(tmp);
                        break;
                    }
                    int x  = tmp.indexOf("<");
                    tmp = tmp.delete(x-1,x+1);
                    myputin = String.valueOf(tmp);
                }
            }
            int k =  0;
            if (standard.length() > myputin.length()) {
                k = myputin.length();
            }else {
                k = standard.length();
            }
            for (int j = 0; j < k; j++) {
                if (standard.charAt(j) == myputin.charAt(j)) {
                    sum++;
                }
            }
        }

        kpm = ((double)(sum*60.0)/(time*1.0));

        System.out.println(Math.round(kpm));

    }
}

小猪佩奇玩游戏

题目描述

佩奇和乔治玩游♂戏。

佩奇在黑板上写下数字 {1,2,⋯,n}{1,2,\cdots,n}{1,2,⋯,n} ,每次他们会等概率地报出黑板上的一个数字 x ,并删除所有 x 的正整数次幂。

形式化地,给定数列 {1,2,⋯,n}{1,2,\cdots,n}{1,2,⋯,n} ,每次等概率选出数列中存在的 1 个数字 x ,并将形如 {xk,k∈Z+}{xk,k \in Z^{+}}{xk,k∈Z+} 的数字删除。

他们玩了整整一个下午,游戏还是没有结束,所以他们想知道,该游戏期望在多少轮后会结束。

如果你的答案与正确答案的绝对误差在 10−410^{-4} 10−4以内,则被判定为正确。

输入格式

第一行 1 个正整数 t,表示佩奇和乔治打算玩 t 轮游戏。

之后t 行,每行 1 个正整数 n,表示佩奇在黑板上写下了数字 {1,2,⋯,n}{1,2,\cdots,n}{1,2,⋯,n} 并将进行游戏。

输出格式

一共 t 行,每行 1 个小数,表示答案,答案保留小数。

如果你的答案与正确答案的绝对误差在 10−410^{-4}10−4以内,则被判定为正确。

输入输出样例

输入 #1

5
4
8
16
32
100

输出 #1

3.50000000
7.00000000
13.83333333
28.33333333
93.41666667

AC代码

import java.io.BufferedInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        double[] p = new double[100010];

        //次数
        long T = sc.nextInt();

        while (T-- > 0) {
            double ans = 0;
            long n = sc.nextLong();
            Map<Long,Long> map = new HashMap<>();
            //i*i都大于n了,就没必要算i*i*i....的值了,一定也大于n
            for (long i = 2; i*i <= n; i++) {
                for (long j = i*i; j <= n; j=j*i) {
                    if (map.containsKey(j)) {
                        Long tmp = map.get(j);
                        map.replace(j,tmp,tmp+1);
                    }else {
                        map.put(j, Long.valueOf(1));
                    }
                }
            }
            ans+=(n-map.size());
            for (Map.Entry<Long,Long> entry : map.entrySet()) {
                Long key = entry.getKey();
                Long val = entry.getValue();
                ans = ans+ 1.0/(val+1);
            }
            System.out.printf("%.7f",ans);
            System.out.println();
        }

    }
}

赛车游戏

题目描述

R 君和小伙伴打算一起玩赛车。但他们被老司机 mocania 骗去了秋名山。

秋名山上有 n 个点和 m 条边,R 君和他的小伙伴要从点 111 出发开往点 n,每条边都有一个初始的方向。老司机 mocania 拿到了秋名山的地图但却不知道每条路有多长。显然,为了赛车游戏的公平,每条 1到 n 的路径应当是等长的。mocania 想,我就随便给边表上一个 1…91…91…9 的长度,反正傻傻的 R 君也看不出来。

可 mocania 的数学不大好,不知道怎么给边标长度,只能跑来请教你这个 OI 高手了。

输入格式

第一行两个整数 n,m。

接下来 m 行,每行两个整数 u,v,表示一条从 u 到 v 的有向边。

输出格式

如果无解或者不存在 1 到 n 的路径直接输出一个 -1。

如果有解第一行输出两个数 n,m,和输入文件中给出的相同。

借下来 m 行,每行三个整数 u,v,w,表示把从 u 到 v 的路径的长度设置为 w,其中 w 是一个 1…9 的整数。要求所有边的出现顺序和题目中给出的相同。

输入输出样例

输入 #1

10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10

输出 #1

10 10
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
1 10 9

前置知识&解题思路

本题主要分三步,存图,遍历1-n必经的节点,跑SPFA。

需要知道的几个名词:

差分约束:不等式之间的转换,实际上是一种转化,把某些问题转化成最短路问题来进行求解

SPFA:计算某个点到所有节点最短路的算法

松弛操作: 一个值先在上界,当存在比这个值小的值时,更新这个值,这次操作就算一次松弛操作

AC代码

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    public static int n,m;
    public static Roads[] roads1;
    public static Roads[] roads2;
    public static Roads[] roads;
    //判断是否两次都遍历到
    public static int[] signed;
    public static int[] f,t;
    public static int[] nums;
    //寻找1-n的必经之路
    public static void dfs1(int x){
        for (int i = 0; i < roads1[x].others.size(); i++) {
            int to = roads1[x].others.get(i)[0];
            if (roads1[to].ifUse) {
                continue;
            }
            roads1[to].ifUse = true;
            dfs1(to);
        }
    }
    //寻找从n-1的必经之路
    public static void dfs2(int x){
        for (int i = 0; i < roads2[x].others.size(); i++) {
            int to = roads2[x].others.get(i)[0];
            if (roads2[to].ifUse) {
                continue;
            }
            roads2[to].ifUse = true;
            dfs2(to);
        }
    }

    public static boolean spfa(){
        Queue<Integer> queue = new ArrayDeque<>();
        roads[1].dis = 0;
        roads[1].ifUse = true;
        queue.offer(1);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            roads[now].ifUse = false;
            nums[now]++;
            for (int i = 0; i < roads[now].others.size(); i++) {
                int v = roads[now].others.get(i)[0];
                int d = roads[now].others.get(i)[1];
                if (roads[v].dis > roads[now].dis + d) {
                    roads[v].dis = roads[now].dis+d;
                    if (nums[v] > n) {
                        return false;
                    }
                    if (roads[v].ifUse) {
                        continue;
                    }
                    roads[v].ifUse = true;
                    queue.offer(v);
                }
            }
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        ok:
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int)in.nval;
            in.nextToken();
            m = (int)in.nval;
            roads1 = new Roads[10010];
            roads2 = new Roads[10010];
            roads = new Roads[10010];
            f = new int[10010];
            t = new int[10010];
            nums = new int[10010];
            signed = new int[10010];
            for (int i = 0; i < roads2.length; i++) {
                roads1[i] = new Roads(i);
                roads2[i] = new Roads(i);
                roads[i] = new Roads(i);
            }
            for (int i = 1; i <= m; i++) {
                in.nextToken();
                int from = (int)in.nval;
                in.nextToken();
                int to = (int)in.nval;
                f[i] = from;
                t[i] = to;
                int[] tmp1 = new int[2];
                int[] tmp2 = new int[2];
                tmp1[0] = to;
                tmp1[1] = 1;
                tmp2[0] = from;
                tmp2[1] = 1;
                roads1[from].others.add(tmp1);
                roads2[to].others.add(tmp2);
            }
            dfs1(1);
            dfs2(n);
            //找到必经之路
            for (int i = 1; i <= n; i++) {
                if (roads1[i].ifUse && roads2[i].ifUse) {
                    signed[i] = 1;
                }
            }
            //n点到不了,更不用说从1-n了
            if (!roads1[n].ifUse) {
                out.println(-1);
                out.flush();
                continue ok;
            }
            //因为遍历不到1和n,强行加上1和n
            signed[1] = 1;
            signed[n] = 1;

            //建图
            for (int i = 1; i <= m; i++) {
                int from = f[i];
                int to = t[i];
                //都是必经之路
                if (signed[from] == 1 && signed[to] == 1) {
                    int[] tmp1 = new int[2];
                    int[] tmp2 = new int[2];
                    tmp1[0] = to;
                    tmp1[1] = -1;
                    tmp2[0] = from;
                    tmp2[1] = 9;
                    roads[from].others.add(tmp1);
                    roads[to].others.add(tmp2);
                }
            }
            if (!spfa()) {
                out.println(-1);
                out.flush();
                continue ok;
            }
            out.println(n+" "+m);
            for (int i = 1; i <= m; i++) {
                out.print(f[i]+" "+t[i]+" ");
                if (signed[f[i]] == 1 && signed[t[i]] == 1) {
                    out.print(roads[t[i]].dis*(-1)-roads[f[i]].dis*(-1));
                }else {
                    out.println(1);
                }
                out.println();
            }
            out.flush();
        }
    }
}
class Roads{
    //点序号
    int index;
    //是否在队列中
    boolean ifUse;
    //存储别的点
    List<int[]> others;
    //存储到这个点的距离
    int dis;

    public Roads(int index) {
        this.index = index;
        ifUse = false;
        others = new ArrayList<>();
        dis = 9999999;
    }
}


网站文章

  • 黑马程序员——c语言学习---数据结构

    -----------android培训、java培训、java学习型技术博客、期待与您交流!------------ 本节来讨论c语言主要的数据结构,包括数组、结构体、共用体、枚举。首先从数组开始。 1、数组 数组为同一类型的基本数据的集合。我们知道,基本数据类型都占据一定的内存空间,基本数据类型的定义,实际上就是内存地址的分配过程,同样的,数组作为基本数据类型的集合,在创建时也必须进行

    2024-04-01 04:04:02
  • CSDN竞赛第49期题解

    三、以字符串的形式给你一个长度为 M 的整数 N,请你计算出对这个数进行一次操作后模 9 的值为 1 的所有可能的不同操作 方式。在一次操作中, 我们可以选择 N 的一个数位 N[i],并把它替换成另...

    2024-04-01 04:03:24
  • 基于 HTML5 WebGL 的高炉炼铁厂可视化系统

    基于 HTML5 WebGL 的高炉炼铁厂可视化系统

    前言在当今 工业4.0 新时代的推动下,不仅迎来了 工业互联网 的发展,还开启了5G时代的新次元。而伴随着带宽的提升,网络信息飞速发展,能源管控上与实时预警在工业互联网中也占着举足轻重的地位,而对于高...

    2024-04-01 04:03:15
  • Python Tornado

    它是一个异步 Web 框架,利用非阻塞 I/O 和协程来实现并发性和高吞吐量。在本文中,我们将探讨 Tornado 的一些高级功能以及如何使用它们来构建强大的 Web 应用程序。通过使用协程和异步加载...

    2024-04-01 04:03:06
  • 卡尔曼滤波

      这篇文章完全是我自己为了记录一下自己对于KF的印象,表层的不能再表层了。如果是需要详细了解KF的请去阅读高手的文章,不要在此篇上浪费时间~   前言:在读一些文章的时候,总会看到研究方法基于卡尔曼...

    2024-04-01 04:02:24
  • android通知公告,通知公告 | 有了这个宝贝,我再也不用……

    android通知公告,通知公告 | 有了这个宝贝,我再也不用……

    原标题:通知公告 | 有了这个宝贝,我再也不用……有了DHU-1X这个宝贝我再也不用每周认证校园网了!东华大学校园无线网已推出802.1x的认证方式,选择DHU-1X,在校师生手机不再需要每周认证;这...

    2024-04-01 04:02:18
  • Java基础——Random

    java基础,Random类

    2024-04-01 04:02:14
  • MyBatis学习总结(七)——Mybatis缓存

    MyBatis学习总结(七)——Mybatis缓存

    2019独角兽企业重金招聘Python工程师标准>>> ...

    2024-04-01 04:02:07
  • 成都文理计算机科学与技术毕业工资如何,四川文理学院什么专业工资最高?

    成都文理计算机科学与技术毕业工资如何,四川文理学院什么专业工资最高?

    导读:在选择专业时,很多填报者会考虑四川文理学院什么专业好?什么专业薪资高?以下为招聘网统计出的在四川文理学院毕业后就业月薪最高的专业,其中数学与应用数学专业工资最高。四川文理学院什么专业工资最高?由...

    2024-04-01 04:01:30
  • 在Windows上搭建Python的开发环境

    在Windows上搭建Python的开发环境

    第一种:必要文件,先在Python官网(https://www.python.org/downloads/windows/)下载所需要版本的安装包,如下图:第一步:如果你是用免安装版python包那么你按照(1)操作,如果你是用的.exe安装版则按照(2)操作。(1)将zip包解压到指定目录,并在系统中配置python环境变量,也就是你的解压路径;(2)执行python安装文件,记...

    2024-04-01 04:01:17