PREV55 小計(jì)算器
題目描述
問(wèn)題描述
模擬程序型計(jì)算器，依次輸入指令昵慌，可能包含的指令有
1. 數(shù)字：'NUM X'盐茎，X為一個(gè)只包含大寫字母和數(shù)字的字符串无宿，表示一個(gè)當(dāng)前進(jìn)制的數(shù)
2. 運(yùn)算指令：'ADD','SUB','MUL','DIV','MOD'，分別表示加減乘赂弓，除法取商绑榴，除法取余
3. 進(jìn)制轉(zhuǎn)換指令：'CHANGE K'，將當(dāng)前進(jìn)制轉(zhuǎn)換為K進(jìn)制(2≤K≤36)
4. 輸出指令：'EQUAL'拣展，以當(dāng)前進(jìn)制輸出結(jié)果
5. 重置指令：'CLEAR'彭沼，清除當(dāng)前數(shù)字
指令按照以下規(guī)則給出：
數(shù)字，運(yùn)算指令不會(huì)連續(xù)給出备埃，進(jìn)制轉(zhuǎn)換指令姓惑，輸出指令，重置指令有可能連續(xù)給出
運(yùn)算指令后出現(xiàn)的第一個(gè)數(shù)字按脚，表示參與運(yùn)算的數(shù)字于毙。且在該運(yùn)算指令和該數(shù)字中間不會(huì)出現(xiàn)運(yùn)算指令和輸出指令
重置指令后出現(xiàn)的第一個(gè)數(shù)字，表示基礎(chǔ)值辅搬。且在重置指令和第一個(gè)數(shù)字中間不會(huì)出現(xiàn)運(yùn)算指令和輸出指令
進(jìn)制轉(zhuǎn)換指令可能出現(xiàn)在任何地方
運(yùn)算過(guò)程中中間變量均為非負(fù)整數(shù)唯沮，且小于2^63。
以大寫的'A''Z'表示1035
輸入格式
第1行：1個(gè)n堪遂，表示指令數(shù)量
第2..n+1行：每行給出一條指令介蛉。指令序列一定以'CLEAR'作為開(kāi)始，并且滿足指令規(guī)則
輸出格式
依次給出每一次'EQUAL'得到的結(jié)果
樣例輸入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
樣例輸出
2040
算法分析
這里主要用到的核心語(yǔ)法是
- 1溶褪、
10進(jìn)制轉(zhuǎn)r進(jìn)制Integer.toString(int x,int r)將10進(jìn)制的x轉(zhuǎn)化為r進(jìn)制币旧，并返回字符串，若x過(guò)大猿妈，可以寫成Long.toString(int x,int r) - 2吹菱、
r進(jìn)制轉(zhuǎn)10進(jìn)制Integer.parseInt(String s,int r)將r進(jìn)制的s轉(zhuǎn)化為10進(jìn)制巍虫，并返回一個(gè)數(shù)字類型，若返回值過(guò)大鳍刷，可以寫成Long.parseLong(String s,int r)
注意： -
10進(jìn)制轉(zhuǎn)r進(jìn)制占遥，若有字母，轉(zhuǎn)出來(lái)的是小寫 -
r進(jìn)制轉(zhuǎn)10進(jìn)制输瓜，無(wú)論x里面包含小寫還是大寫瓦胎，出來(lái)的數(shù)字都是一樣的
public class Main {
//10進(jìn)制轉(zhuǎn)r進(jìn)制
static String ten_to_r(long x,int r)
{
return Long.toString(x,r);
}
//r進(jìn)制轉(zhuǎn)10進(jìn)制
static long r_to_ten(String s,int r)
{
return Long.parseLong(s,r);
}
public static void main(String[] args){
System.out.println(ten_to_r(1000,11)); // 答案：82a
System.out.println(r_to_ten("82A",11));// 答案：1000
System.out.println(r_to_ten("82a",11));// 答案：1000
}
}
模擬
ans記錄的是當(dāng)前10進(jìn)制的結(jié)果（統(tǒng)一記錄成10進(jìn)制），op代表當(dāng)前的操作數(shù)前痘，r表示當(dāng)前數(shù)的進(jìn)制凛捏，輸出的時(shí)候再?gòu)?code>10進(jìn)制轉(zhuǎn)化為當(dāng)前進(jìn)制數(shù)
時(shí)間復(fù)雜度
不清楚
Java 代碼
import java.util.Scanner;
public class Main {
static long ans = -1;//永遠(yuǎn)記錄10進(jìn)制的答案
static String op = "#";
static int r = 10;
//10進(jìn)制轉(zhuǎn)r進(jìn)制
static String ten_to_r(long x,int r)
{
return Long.toString(x,r);
}
//r進(jìn)制轉(zhuǎn)10進(jìn)制
static long r_to_ten(String s,int r)
{
return Long.parseLong(s,r);
}
//ans通過(guò)op操作更新答案
static void update_ans(String op,String x)
{
long t = r_to_ten(x,r);//將x變?yōu)?0進(jìn)制
if(op.equals("ADD"))
{
ans += t;
}
else if(op.equals("SUB"))
{
ans -= t;
}
else if(op.equals("MUL"))
{
ans *= t;
}
else if(op.equals("DIV"))
{
ans /= t;
}
else if(op.equals("MOD"))
{
ans %= t;
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
while(n -- > 0)
{
String t = scan.next();
if(t.equals("CLEAR"))
{
ans = -1;
}
else if(t.equals("NUM"))
{
String x = scan.next();
if(ans == -1) ans = r_to_ten(x,r);
else update_ans(op,x);
}
else if(t.equals("CHANGE"))
{
r = Integer.parseInt(scan.next());
}
else if(t.equals("ADD"))
{
op = "ADD";
}
else if(t.equals("SUB"))
{
op = "SUB";
}
else if(t.equals("MUL"))
{
op = "MUL";
}
else if(t.equals("DIV"))
{
op = "DIV";
}
else if(t.equals("MOD"))
{
op = "MOD";
}
else
{
String temp = ten_to_r(ans,r);
for(int i = 0;i < temp.length();i ++)
{
if(temp.charAt(i) >= 'a' && temp.charAt(i) <= 'z')
System.out.print((char)(temp.charAt(i) - ('a' - 'A')));
else System.out.print(temp.charAt(i));
}
System.out.println();
}
}
}
}
PREV54 合根植物
題目描述
資源限制
時(shí)間限制：2.0s 內(nèi)存限制：256.0MB
問(wèn)題描述
w星球的一個(gè)種植園，被分成 m * n 個(gè)小格子（東西方向m行芹缔，南北方向n列）坯癣。每個(gè)格子里種了一株合根植物。
這種植物有個(gè)特點(diǎn)最欠，它的根可能會(huì)沿著南北或東西方向伸展示罗，從而與另一個(gè)格子的植物合成為一體。
如果我們告訴你哪些小格子間出現(xiàn)了連根現(xiàn)象芝硬，你能說(shuō)出這個(gè)園中一共有多少株合根植物嗎蚜点？
輸入格式
第一行，兩個(gè)整數(shù)m拌阴，n绍绘，用空格分開(kāi)，表示格子的行數(shù)迟赃、列數(shù)（1<m,n<1000）陪拘。
接下來(lái)一行，一個(gè)整數(shù)k纤壁，表示下面還有k行數(shù)據(jù)(0<k<100000)
接下來(lái)k行左刽，第行兩個(gè)整數(shù)a，b酌媒，表示編號(hào)為a的小格子和編號(hào)為b的小格子合根了欠痴。
格子的編號(hào)一行一行，從上到下秒咨，從左到右編號(hào)喇辽。
比如：5 * 4 的小格子，編號(hào)：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
樣例輸入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
樣例輸出
5
算法分析
并查集
將所有能連通的點(diǎn)合并到一個(gè)集合雨席，求集合的個(gè)數(shù)茵臭，從1枚舉到n * m，將所有點(diǎn)對(duì)應(yīng)的集合根結(jié)點(diǎn)放進(jìn)set中進(jìn)行判重，輸出set的大小即可
時(shí)間復(fù)雜度 )
并查集操作接近O(1)
Java 代碼
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
public class Main {
static int N = 1000010;
static int n,m;
static int[] p = new int[N];
static Set<Integer> set = new HashSet<Integer>();
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
int k = Integer.parseInt(br.readLine());
for(int i = 1;i <= n * m;i ++) p[i] = i;
while(k -- > 0)
{
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
a = find(a);
b = find(b);
p[a] = b;
}
for(int i = 1;i <= n * m;i ++) set.add(find(i));
System.out.println(set.size());
}
}
PREV53 分考場(chǎng)
題目描述
資源限制
時(shí)間限制：1.0s 內(nèi)存限制：256.0MB
問(wèn)題描述
n個(gè)人參加某項(xiàng)特殊考試旦委。
為了公平，要求任何兩個(gè)認(rèn)識(shí)的人不能分在同一個(gè)考場(chǎng)雏亚。
求是少需要分幾個(gè)考場(chǎng)才能滿足條件缨硝。
輸入格式
第一行，一個(gè)整數(shù)n(1<n<100)罢低，表示參加考試的人數(shù)查辩。
第二行，一個(gè)整數(shù)m网持，表示接下來(lái)有m行數(shù)據(jù)
以下m行每行的格式為：兩個(gè)整數(shù)a宜岛，b，用空格分開(kāi) (1<=a,b<=n) 表示第a個(gè)人與第b個(gè)人認(rèn)識(shí)功舀。
輸出格式
一行一個(gè)整數(shù)萍倡，表示最少分幾個(gè)考場(chǎng)。
樣例輸入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
樣例輸出
4
樣例輸入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
樣例輸出
5
算法分析
經(jīng)驗(yàn)：在藍(lán)橋杯中辟汰，如果數(shù)據(jù)范圍是100列敲，用爆搜 + 各種剪枝還是可以通過(guò)的
此題沒(méi)有什么思路，可以只用dfs做
dfs(int x,int nums)表示當(dāng)前枚舉到底x個(gè)人帖汞，nums表示目前開(kāi)了多少個(gè)考場(chǎng)
g[i][j]數(shù)組記錄的是第i個(gè)人是否和第j個(gè)人認(rèn)識(shí)
dfs的過(guò)程戴而，依次枚舉所有的人往現(xiàn)有的nums考場(chǎng)上放，枚舉所有情況
第x個(gè)人往第1個(gè)考場(chǎng)放
第x個(gè)人往第2個(gè)考場(chǎng)放
...
第x個(gè)人往第nums個(gè)考場(chǎng)放
新開(kāi)一個(gè)考場(chǎng)翩蘸，第x個(gè)人往第nums + 1個(gè)考場(chǎng)放
優(yōu)化：
最優(yōu)性剪枝：若當(dāng)前考場(chǎng)數(shù)量比ans大所意，則退出
可行性剪枝，若當(dāng)前考場(chǎng)有當(dāng)前這個(gè)人x認(rèn)識(shí)的催首，則continue
時(shí)間復(fù)雜度
具有剪枝扶踊，不好分析
Java 代碼
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
static int N = 110;
static int n,m;
static boolean[][] g = new boolean[N][N];
static LinkedList[] list = new LinkedList[N];
static int ans = Integer.MAX_VALUE;
static boolean check(int x,int u)
{
for(int i = 0;i < list[u].size();i ++)
{
int t = (int)list[u].get(i);
if(g[x][t]) return false;
}
return true;
}
static void dfs(int x,int nums)
{
if(nums >= ans) return; //最優(yōu)性剪枝
if(x == n + 1)
{
ans = Math.min(ans, nums);
return;
}
//能否放在本來(lái)有的考場(chǎng)
for(int i = 1;i <= nums;i ++)
{
if(!check(x,i)) continue;
list[i].add(x);
dfs(x + 1,nums);
list[i].remove(list[i].size() - 1);
}
//新開(kāi)一個(gè)
list[nums + 1].add(x);
dfs(x + 1,nums + 1);
list[nums + 1].remove(list[nums + 1].size() - 1);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
while(m -- > 0)
{
int a = scan.nextInt();
int b = scan.nextInt();
g[a][b] = g[b][a] = true;
}
for(int i = 1;i <= n;i ++) list[i] = new LinkedList<Integer>();
dfs(1,0);
System.out.println(ans);
}
}
資源限制
時(shí)間限制：1.0s 內(nèi)存限制：256.0MB
問(wèn)題描述
我們知道，整數(shù)做除法時(shí)翅帜，有時(shí)得到有限小數(shù)姻檀，有時(shí)得到無(wú)限循環(huán)小數(shù)。
如果我們把有限小數(shù)的末尾加上無(wú)限多個(gè)0涝滴，它們就有了統(tǒng)一的形式绣版。
本題的任務(wù)是：在上面的約定下，求整數(shù)除法小數(shù)點(diǎn)后的第n位開(kāi)始的3位數(shù)歼疮。
輸入格式
一行三個(gè)整數(shù)：a b n杂抽，用空格分開(kāi)。a是被除數(shù)韩脏，b是除數(shù)缩麸，n是所求的小數(shù)后位置（0<a,b,n<1000000000）
輸出格式
一行3位數(shù)字，表示：a除以b赡矢，小數(shù)后第n位開(kāi)始的3位數(shù)字杭朱。
樣例輸入
1 8 1
樣例輸出
125
樣例輸入
1 8 3
樣例輸出
500
樣例輸入
282866 999000 6
樣例輸出
914
Java代碼
PREV52 小數(shù)第n位
資源限制
時(shí)間限制：1.0s 內(nèi)存限制：256.0MB
問(wèn)題描述
我們知道阅仔，整數(shù)做除法時(shí)，有時(shí)得到有限小數(shù)弧械，有時(shí)得到無(wú)限循環(huán)小數(shù)八酒。
如果我們把有限小數(shù)的末尾加上無(wú)限多個(gè)0，它們就有了統(tǒng)一的形式刃唐。
本題的任務(wù)是：在上面的約定下羞迷，求整數(shù)除法小數(shù)點(diǎn)后的第n位開(kāi)始的3位數(shù)。
輸入格式
一行三個(gè)整數(shù)：a b n画饥，用空格分開(kāi)衔瓮。a是被除數(shù)，b是除數(shù)抖甘，n是所求的小數(shù)后位置（0<a,b,n<1000000000）
輸出格式
一行3位數(shù)字热鞍，表示：a除以b，小數(shù)后第n位開(kāi)始的3位數(shù)字单山。
樣例輸入
1 8 1
樣例輸出
125
樣例輸入
1 8 3
樣例輸出
500
樣例輸入
282866 999000 6
樣例輸出
914
算法分析
這里主要的公式可以列出來(lái)
用快速冪求,時(shí)間復(fù)雜度
時(shí)間復(fù)雜度 )
Java 代碼
import java.util.Scanner;
public class Main {
static long qmi(int a,int k,int p)
{
long res = 1 % p;
long t = a;
while(k > 0)
{
if((k & 1) == 1) res = res * t % p;
k >>= 1;
t = t * t % p;
}
return res ;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
int n = scan.nextInt();
int p = b * 1000;
System.out.println(((a * qmi(10,n + 2,p)) % p) / b);
}
}
PREV51 觀光鐵路
資源限制
時(shí)間限制：2.0s 內(nèi)存限制：256.0MB
問(wèn)題描述
跳蚤國(guó)正在大力發(fā)展旅游業(yè)碍现，每個(gè)城市都被打造成了旅游景點(diǎn)。
許多跳蚤想去其他城市旅游米奸，但是由于跳得比較慢昼接，它們的愿望難以實(shí)現(xiàn)。這時(shí)悴晰，小C聽(tīng)說(shuō)有一種叫做火車的交通工具慢睡，在鐵路上跑得很快，便抓住了商機(jī)铡溪，創(chuàng)立了一家鐵路公司漂辐，向跳蚤國(guó)王請(qǐng)示在每?jī)蓚€(gè)城市之間都修建鐵路。
然而棕硫，由于小C不會(huì)扳道岔髓涯，火車到一個(gè)城市以后只能保證不原路返回，而會(huì)隨機(jī)等概率地駛向與這個(gè)城市有鐵路連接的另外一個(gè)城市哈扮。
跳蚤國(guó)王向廣大居民征求意見(jiàn)纬纪，結(jié)果跳蚤們不太滿意，因?yàn)檫@樣修建鐵路以后有可能只游覽了3個(gè)城市（含出發(fā)的城市）以后就回來(lái)了滑肉，它們希望能多游覽幾個(gè)城市包各。于是跳蚤國(guó)王要求小C提供一個(gè)方案，使得每只跳蚤坐上火車后能多游覽幾個(gè)城市才回來(lái)靶庙。
小C提供了一種方案給跳蚤國(guó)王问畅。跳蚤國(guó)王想知道這個(gè)方案中每個(gè)城市的居民旅游的期望時(shí)間（設(shè)火車經(jīng)過(guò)每段鐵路的時(shí)間都為1），請(qǐng)你來(lái)幫跳蚤國(guó)王。
輸入格式
輸入的第一行包含兩個(gè)正整數(shù)n护姆、m矾端，其中n表示城市的數(shù)量，m表示方案中的鐵路條數(shù)卵皂。
接下來(lái)m行须床，每行包含兩個(gè)正整數(shù)u、v渐裂，表示方案中城市u和城市v之間有一條鐵路。
保證方案中無(wú)重邊無(wú)自環(huán)钠惩，每?jī)蓚€(gè)城市之間都能經(jīng)過(guò)鐵路直接或間接到達(dá)柒凉，且火車由任意一條鐵路到任意一個(gè)城市以后一定有路可走。
輸出格式
輸出n行篓跛，第i行包含一個(gè)實(shí)數(shù)tBi膝捞，表示方案B中城市i的居民旅游的期望時(shí)間。你應(yīng)當(dāng)輸出足夠多的小數(shù)位數(shù)愧沟，以保證輸出的值和真實(shí)值之間的絕對(duì)或相對(duì)誤差不超過(guò)1e-9蔬咬。
樣例輸入
4 5
1 2
2 3
3 4
4 1
1 3
樣例輸出
3.333333333333
5.000000000000
3.333333333333
5.000000000000
樣例輸入
10 15
1 2
1 9
1 5
2 3
2 7
3 4
3 10
4 5
4 8
5 6
6 7
6 10
7 8
8 9
9 10
樣例輸出
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
數(shù)據(jù)規(guī)模和約定
對(duì)于10%的測(cè)試點(diǎn)，n <= 10沐寺；
對(duì)于20%的測(cè)試點(diǎn)林艘，n <= 12；
對(duì)于50%的測(cè)試點(diǎn)混坞，n <= 16狐援；
對(duì)于70%的測(cè)試點(diǎn)，n <= 19究孕；
對(duì)于100%的測(cè)試點(diǎn)啥酱，4 <= k <= n <= 21，1 <= u, v <= n厨诸。數(shù)據(jù)有梯度镶殷。
算法分析
不會(huì)
