TOC
前言: 这就是上次心态做崩的那次比赛，由于太弱现在也仅仅做出来三道，第一道是纯模拟题，但要注意几个点，否则是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 ，并将形如 {x^k,k∈Z+}{x^k,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;
}
}
「真诚赞赏，手留余香」
水的一匹Lu的Blog
真诚赞赏，手留余香
使用微信扫描二维码完成支付
