1锰镀、問題描述
1200000有多少個(gè)約數(shù)（只計(jì)算正約數(shù)）兄纺。
答案提交
這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可技矮。本題的結(jié)果為一個(gè)整數(shù)抖誉，在提交答案時(shí)只填寫這個(gè)整數(shù)，填寫多余的內(nèi)容將無法得分衰倦。
答案：96
算法分析
試除法求一個(gè)數(shù)的所有約數(shù)
時(shí)間復(fù)雜度 
Java代碼
import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<Integer> get_divide(int x)
{
List<Integer> list = new ArrayList<Integer>();
for(int i = 1;i <= x / i;i++)
{
if(x % i == 0)
{
list.add(i);
if(i != x / i) list.add(x / i);
}
}
return list;
}
public static void main(String[] args) {
int x = 1200000;
List<Integer> ans = get_divide(x);
System.out.println(ans.size());
}
}
2袒炉、問題描述
在計(jì)算機(jī)存儲(chǔ)中，15.125GB是多少M(fèi)B樊零？
答案提交
這是一道結(jié)果填空的題我磁，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個(gè)整數(shù)驻襟，在提交答案時(shí)只填寫這個(gè)整數(shù)夺艰，填寫多余的內(nèi)容將無法得分。
答案：15488
算法分析
1GB = 1024 MB
時(shí)間復(fù)雜度)
Java代碼
public class Main {
public static void main(String[] args) {
System.out.printf("%.0f",15.125 * 1024);
}
}
3沉衣、問題描述
在1至2019中郁副，有多少個(gè)數(shù)的數(shù)位中包含數(shù)字9？
注意豌习，有的數(shù)中的數(shù)位中包含多個(gè)9存谎，這個(gè)數(shù)只算一次拔疚。例如，1999這個(gè)數(shù)包含數(shù)字9既荚，在計(jì)算只是算一個(gè)數(shù)稚失。
答案提交
這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可固以。本題的結(jié)果為一個(gè)整數(shù)墩虹，在提交答案時(shí)只填寫這個(gè)整數(shù)，填寫多余的內(nèi)容將無法得分憨琳。
答案：544
算法分析
枚舉每個(gè)數(shù)的每位數(shù)是否有9
時(shí)間復(fù)雜度)
Java 代碼
public class Main {
static boolean check(int x)
{
while(x != 0)
{
int t = x % 10;
if(t == 9) return true;
x /= 10;
}
return false;
}
public static void main(String[] args) {
int ans = 0;
for(int i = 1;i <= 2019;i ++)
{
if(check(i))
{
ans ++;
}
}
System.out.println(ans);
}
}
4诫钓、問題描述
一棵包含有2019個(gè)結(jié)點(diǎn)的樹，最多包含多少個(gè)葉結(jié)點(diǎn)篙螟？
答案提交
這是一道結(jié)果填空的題菌湃，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個(gè)整數(shù)遍略，在提交答案時(shí)只填寫這個(gè)整數(shù)惧所，填寫多余的內(nèi)容將無法得分。
答案：2018
算法分析 最多的情況是绪杏，一個(gè)父節(jié)點(diǎn)下愈，其他都是子結(jié)點(diǎn)
5、問題描述
小明對(duì)類似于 hello 這種單詞非常感興趣蕾久，這種單詞可以正好分為四段势似，第一段由一個(gè)或多個(gè)輔音字母組成，第二段由一個(gè)或多個(gè)元音字母組成僧著，第三段由一個(gè)或多個(gè)輔音字母組成履因，第四段由一個(gè)或多個(gè)元音字母組成。
給定一個(gè)單詞盹愚，請(qǐng)判斷這個(gè)單詞是否也是這種單詞栅迄，如果是請(qǐng)輸出yes，否則請(qǐng)輸出no皆怕。
元音字母包括 a, e, i, o, u毅舆，共五個(gè)，其他均為輔音字母端逼。
輸入格式
輸入一行朗兵，包含一個(gè)單詞，單詞中只包含小寫英文字母顶滩。
輸出格式
輸出答案余掖，或者為yes，或者為no。
樣例輸入
lanqiao
樣例輸出
yes
樣例輸入
world
樣例輸出
no
評(píng)測(cè)用例規(guī)模與約定
對(duì)于所有評(píng)測(cè)用例盐欺，單詞中的字母?jìng)€(gè)數(shù)不超過100赁豆。
算法分析
雙指針
題目要求字符的區(qū)域順序是：輔，元冗美，輔魔种，元
[i,j]區(qū)域維護(hù)的是同一片區(qū)域，找出同一塊區(qū)域的個(gè)數(shù)粉洼，若區(qū)域個(gè)數(shù)是4個(gè)节预，則返回true，否則返回false
注意：需要對(duì)第一個(gè)字母進(jìn)行特判属韧，若第一個(gè)字母是元音安拟，則直接返回false
時(shí)間復(fù)雜度)
Java 代碼
//機(jī)器人判分系統(tǒng)要求必須如下規(guī)則：
// 1： 不能有package關(guān)鍵字
// 2： 必須類名必須是Main
import java.util.Scanner;
public class Main {
static char[] temp;
static int n ;
//判斷a和b是否是同一種類型的字母
static boolean check2(char a,char b)
{
boolean flag1 = false;
boolean flag2 = false;
if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u') flag1 = true;
if(b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u') flag2 = true;
if((flag1 && flag2) || (!flag1 && !flag2)) return true;
return false;
}
static boolean check()
{
if(temp[0] == 'a' || temp[0] == 'e' || temp[0] == 'i' || temp[0] == 'o' || temp[0] == 'u')
return false;
int cnt = 1;
for(int i = 1,j = 0;i < n;i ++)
{
if(!check2(temp[i],temp[j]))
{
cnt ++;
j = i;
}
}
if(cnt == 4) return true;
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
temp = scan.next().toCharArray();
n = temp.length;
if(check()) System.out.println("yes");
else System.out.println("no");
}
}
6、問題描述
在數(shù)列 a[1], a[2], ..., a[n] 中宵喂，如果對(duì)于下標(biāo) i, j, k 滿足 0<i<j<k<n+1 且 a[i]<a[j]<a[k]糠赦，則稱 a[i], a[j], a[k] 為一組遞增三元組，a[j]為遞增三元組的中心锅棕。
給定一個(gè)數(shù)列拙泽，請(qǐng)問數(shù)列中有多少個(gè)元素可能是遞增三元組的中心。
輸入格式
輸入的第一行包含一個(gè)整數(shù) n裸燎。
第二行包含 n 個(gè)整數(shù) a[1], a[2], ..., a[n]顾瞻，相鄰的整數(shù)間用空格分隔，表示給定的數(shù)列德绿。
輸出格式
輸出一行包含一個(gè)整數(shù)朋其，表示答案。
樣例輸入
5
1 2 5 3 5
樣例輸出
2
樣例說明
a[2] 和 a[4] 可能是三元組的中心脆炎。
評(píng)測(cè)用例規(guī)模與約定
對(duì)于 50% 的評(píng)測(cè)用例，2 <= n <= 100氓辣，0 <= 數(shù)列中的數(shù) <= 1000秒裕。
對(duì)于所有評(píng)測(cè)用例，2 <= n <= 1000钞啸，0 <= 數(shù)列中的數(shù) <= 10000几蜻。
算法分析
從左到右枚舉所有元素，若當(dāng)前元素的左邊存在比該元素小 且 右邊存在比該元素大体斩，則表示該元素可能是遞增三元組的中心
時(shí)間復(fù)雜度)
Java代碼
//機(jī)器人判分系統(tǒng)要求必須如下規(guī)則：
// 1： 不能有package關(guān)鍵字
// 2： 必須類名必須是Main
import java.util.Scanner;
public class Main {
static int N = 1010;
static int[] a = new int[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 0;i < n;i ++)
{
a[i] = scan.nextInt();
}
int res = 0;
for(int i = 1;i < n - 1;i ++)
{
boolean flag1 = false;
for(int j = 0;j < i;j ++)
{
if(a[j] < a[i])
{
flag1 = true;
break;
}
}
boolean flag2= false;
for(int j = i + 1;j < n;j ++)
{
if(a[j] > a[i])
{
flag2 = true;
break;
}
}
if(flag1 && flag2) res ++;
}
System.out.println(res);
}
}
7梭稚、問題描述
一個(gè)正整數(shù)如果任何一個(gè)數(shù)位不大于右邊相鄰的數(shù)位，則稱為一個(gè)數(shù)位遞增的數(shù)絮吵，例如1135是一個(gè)數(shù)位遞增的數(shù)弧烤，而1024不是一個(gè)數(shù)位遞增的數(shù)。
給定正整數(shù) n蹬敲，請(qǐng)問在整數(shù) 1 至 n 中有多少個(gè)數(shù)位遞增的數(shù)暇昂？
輸入格式
輸入的第一行包含一個(gè)整數(shù) n莺戒。
輸出格式
輸出一行包含一個(gè)整數(shù)，表示答案急波。
樣例輸入
30
樣例輸出
26
評(píng)測(cè)用例規(guī)模與約定
對(duì)于 40% 的評(píng)測(cè)用例从铲，1 <= n <= 1000。
對(duì)于 80% 的評(píng)測(cè)用例澄暮，1 <= n <= 100000名段。
對(duì)于所有評(píng)測(cè)用例，1 <= n <= 1000000泣懊。
算法1
從1到n伸辟，暴力枚舉每個(gè)數(shù)，判斷該數(shù)是否符合任何一個(gè)數(shù)位不大于右邊相鄰的數(shù)位嗅定，
時(shí)間復(fù)雜度)
k表示最大的數(shù)的長(zhǎng)度
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static boolean check(int x)
{
List<Integer> nums = new ArrayList<Integer>();
while(x != 0)
{
nums.add(x % 10);
x /= 10;
}
boolean flag = true;//默認(rèn)是符合的
for(int i = nums.size() - 1;i >= 1;i --)
{
if(nums.get(i) > nums.get(i - 1))
{
flag = false;
break;
}
}
if(flag) return true;
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int ans = 9;
for(int i = 10;i <= n;i ++)
{
if(check(i)) ans ++;
}
System.out.println(ans);
}
}
算法2
數(shù)位dp
f[i][j]表示一共有i位自娩，且最高位填j的數(shù)的個(gè)數(shù)，先預(yù)處理f[][]數(shù)組渠退，直接求出1到n有多少個(gè)遞增的數(shù)
時(shí)間復(fù)雜度)
k表示最大的數(shù)的長(zhǎng)度
Java代碼
//機(jī)器人判分系統(tǒng)要求必須如下規(guī)則：
// 1： 不能有package關(guān)鍵字
// 2： 必須類名必須是Main
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int N = 15;
static int[][] f = new int[N][N];
static void init()
{
//f[i][j]表示一共有i位忙迁，且最高位填j的數(shù)的個(gè)數(shù)
for(int i = 0;i <= 9;i ++) f[1][i] = 1;
for(int i = 2;i < N;i ++)
for(int j = 0;j <= 9;j ++)
for(int k = j;k <= 9;k ++)
{
f[i][j] += f[i - 1][k];
}
}
static int dp(int n)
{
if(n == 0) return 1;
List<Integer> nums = new ArrayList<Integer>();
while(n != 0)
{
nums.add(n % 10);
n /= 10;
}
int res = 0;
int last = 0;//記錄前一個(gè)位的數(shù)
for(int i = nums.size() - 1;i >= 0;i --)
{
int x = nums.get(i);
for(int j = last;j < x;j ++) res += f[i + 1][j];
if(x < last) break;
last = x;
if(i == 0) res ++;
}
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
init();
int n = scan.nextInt();
System.out.println(dp(n) - dp(0));
}
}
8、問題描述
小明想知道碎乃，滿足以下條件的正整數(shù)序列的數(shù)量：
1. 第一項(xiàng)為 n姊扔；
2. 第二項(xiàng)不超過 n；
3. 從第三項(xiàng)開始梅誓，每一項(xiàng)小于前兩項(xiàng)的差的絕對(duì)值恰梢。
請(qǐng)計(jì)算，對(duì)于給定的 n梗掰，有多少種滿足條件的序列嵌言。
輸入格式
輸入一行包含一個(gè)整數(shù) n。
輸出格式
輸出一個(gè)整數(shù)及穗，表示答案摧茴。答案可能很大，請(qǐng)輸出答案除以10000的余數(shù)埂陆。
樣例輸入
4
樣例輸出
7
樣例說明
以下是滿足條件的序列：
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4
評(píng)測(cè)用例規(guī)模與約定
對(duì)于 20% 的評(píng)測(cè)用例苛白，1 <= n <= 5；
對(duì)于 50% 的評(píng)測(cè)用例焚虱，1 <= n <= 10购裙；
對(duì)于 80% 的評(píng)測(cè)用例，1 <= n <= 100鹃栽；
對(duì)于所有評(píng)測(cè)用例躏率，1 <= n <= 1000。
算法1
暴力通過50%
1、第二項(xiàng)從1枚舉到n禾锤，從第三項(xiàng)開始的每一項(xiàng)均小于前兩項(xiàng)的差的絕對(duì)值
2私股、用全局變量記錄總方案數(shù)，每dfs一遍方案數(shù)加1恩掷，dfs(pre,cur)表示的是前一個(gè)數(shù)是pre倡鲸，當(dāng)前數(shù)是cur的所有情況
時(shí)間復(fù)雜度（指數(shù)級(jí)別）
Java代碼（暴力寫法）
import java.util.Scanner;
public class Main {
static int ans = 0;
static int mod = 10000;
//x表示前一項(xiàng)，y表示當(dāng)前項(xiàng)
static void dfs(int x,int y)
{
ans = (ans + 1) % mod;
if(Math.abs(x - y) <= 1) return;
for(int i = 1;i < Math.abs(x - y);i ++)
{
dfs(y,i);
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
dfs(n,i);
}
System.out.println(ans);
}
}
算法2
記憶化搜索通過80%
從算法1可以看到由于每次遞歸都會(huì)重復(fù)計(jì)算相同的值黄娘，導(dǎo)致時(shí)間復(fù)雜度爆炸峭状。因?yàn)楫?dāng)某個(gè)數(shù)字?jǐn)?shù)列的前面兩個(gè)數(shù)字確定的情況下數(shù)字序列的方案數(shù)是一樣且確定的，因此該問題是個(gè)無后效性問題逼争，所以可以對(duì)算法1進(jìn)行改進(jìn)优床，用一個(gè)數(shù)組記錄每次求得的結(jié)果,因?yàn)檫@題的狀態(tài)定義比較特殊，所以采用記憶化搜索的方式來實(shí)現(xiàn)
時(shí)間復(fù)雜度)
Java代碼
import java.util.Scanner;
public class Main {
static int N = 1010;
static int mod = 10000;
static int[][] f = new int[N][N];
static int dfs(int pre,int cur)
{
if(f[pre][cur] != 0) return f[pre][cur];
f[pre][cur] = 1;
for(int i = 1;i < Math.abs(pre - cur);i ++)
f[pre][cur] = (f[pre][cur] + dfs(cur,i)) % mod;
return f[pre][cur];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int res = 0;
for(int i = 1;i <= n;i ++) res = (res + dfs(n,i)) % mod;
System.out.println(res);
}
}
其實(shí)到這里誓焦，對(duì)于騙分選手來說已經(jīng)可以開始騙到滿分了胆敞，雖然說算法2記憶化搜索到1000的時(shí)候會(huì)超時(shí)，可通過打表的方式杂伟，把1到1000全部打出來移层，放在一個(gè)數(shù)組中，就可以實(shí)現(xiàn)騙分了
騙分的代碼
import java.util.Scanner;
public class Main {
static int N = 1010;
static int[] ans = new int[] {0,1,2,4,7,14,26,53,106,220,452,946,1967,4128,8638,8144,8068,26,8127,3542,3277,3278,7643,5433,5774,8217,4846,687,3097,6887,3556,4840,3454,5378,722,2230,767,1447,1839,4776,7618,7831,6222,5236,7802,5696,1835,1102,9537,1605,1227,3034,2159,1613,6811,3941,6794,5960,4903,75,2158,349,4258,5189,4717,2894,4193,2890,258,2928,6125,2913,1482,8419,7244,1652,3440,2138,9272,4714,3333,3543,8834,6763,9180,1803,4631,6307,9056,3170,8339,6213,1176,3258,272,4257,1893,8020,3682,9531,6961,4145,3086,3455,9057,1346,5768,6907,247,2450,4732,8653,8229,842,3346,9671,7106,3561,4952,9539,1791,6208,6083,8838,7474,6854,198,7300,8219,5912,8884,3976,9650,4821,7317,9720,5572,3834,6326,2281,34,8409,28,445,8155,9846,9944,2504,3954,1639,7243,8502,6926,1609,7449,3769,5695,6683,7531,6275,5827,6184,1982,736,9718,2777,7688,6626,7456,961,5556,7573,6886,4543,3957,2859,4666,9795,305,9052,5350,9827,5445,6970,2599,7566,2848,2987,5179,1537,2392,6375,9621,7376,3301,1357,6545,7838,9390,4284,2631,1814,2566,7666,1110,5694,7595,5000,1290,4735,5994,9401,6475,9012,5877,2867,7912,3509,5505,885,7490,5622,4374,8721,5134,8788,5430,3869,9852,5762,75,5964,262,5565,1599,7525,5388,8612,1143,7938,7580,2953,7901,5629,1456,9852,5216,965,3739,7879,1212,9029,9263,9609,1926,8151,1997,6298,5125,5715,4864,3852,604,7652,313,6248,4077,3875,3816,7046,9525,3798,6959,9366,2216,4463,6546,6367,614,9477,3176,4098,7162,7535,4696,749,2686,8212,9050,255,1389,287,1086,9414,9897,2293,31,9121,4682,7084,8951,834,1051,2236,3712,6426,8642,185,785,8162,6015,658,8923,5741,2551,7629,2095,8882,7695,5629,8684,5116,6362,7701,9441,9403,1108,4395,5688,9466,953,9191,4967,7236,6020,3465,8165,872,4530,3353,7859,1422,1504,6366,126,1246,1530,1777,8970,4590,2195,6920,9086,689,2163,6035,4961,2055,7699,4121,3971,1824,3707,4405,854,6088,6971,1679,1779,7097,5696,2449,2104,3264,796,8595,6183,26,5597,7295,5926,9039,4550,9601,5959,3244,7451,5641,2343,6587,3755,4361,3890,446,8187,1979,7000,7094,8658,1647,6090,8332,4407,4570,2340,3057,5029,5424,2736,4844,2771,5782,5912,3745,2504,2782,7247,1393,5403,7175,9903,1723,7600,7021,4566,9778,5188,46,8542,7915,5043,4983,519,480,8199,1141,73,9316,6248,966,3218,6614,6974,5078,9775,7263,6263,7267,1947,5357,286,674,3876,1985,4731,1850,512,1493,5310,5443,4183,5963,8642,1389,6320,4264,9565,7348,4378,6192,1300,3393,4794,8323,6063,9651,9368,7899,9053,4933,5140,5604,9114,9299,7603,2485,884,7313,4139,9883,1405,9843,7419,1483,2031,8610,4150,3313,6257,3790,1688,994,1357,9660,583,5735,1548,7156,9678,8047,3617,9611,7966,7764,5177,7716,4206,7985,6989,6318,5854,8292,9639,687,370,3252,7104,5813,758,8219,3809,2506,3605,9340,3559,4118,4757,8229,4258,944,1596,4940,622,5832,1270,6948,1744,1125,7895,9348,7601,7426,1975,9611,3722,4143,4979,7904,3221,3817,5755,1798,6549,3463,3190,201,6894,6209,3488,670,7643,7020,6164,5583,5036,6309,8644,7961,3465,7795,1486,4535,3111,5252,4049,4253,7515,1517,6148,2438,1296,8826,7924,7761,9126,6951,7110,7549,1170,8533,793,1633,6451,6261,5887,8694,6447,8993,6398,1289,2925,2362,3935,6744,1358,1743,3937,9942,3696,1601,8295,3086,2595,9554,8566,1465,2109,3474,3950,9216,8948,2020,3536,943,4934,8377,6171,1243,3525,259,3001,4205,4548,4754,2365,8630,4690,7872,5131,3995,2672,728,6532,9785,9379,5865,4774,6660,3721,4451,9085,4771,8008,857,9737,5630,4040,3106,5997,4152,8542,3992,3294,5064,2656,5247,635,1521,3026,1502,9396,2171,7188,2425,9758,2640,8648,9454,274,9471,8972,9301,911,6023,4155,126,7802,2948,5675,6313,69,1374,9925,3685,6901,432,1884,4803,8173,9638,3626,695,4286,3836,8670,8834,1444,5187,6281,2482,8801,7656,9066,5138,5160,9857,906,5235,7243,5281,5103,5826,5023,3637,5607,1204,5697,3422,1192,8753,6087,2083,3256,8201,9853,1886,3953,4732,7351,6387,9148,2299,4843,3891,3572,874,9873,1235,7323,8860,3439,113,5132,6521,1234,7427,4062,1342,2480,641,8802,9788,5336,3649,1301,3268,749,1628,9202,2689,3284,9170,5252,1577,1705,5640,2185,2252,4943,271,5117,8699,2743,8221,2119,3851,701,2740,4247,7037,9764,4445,5848,6135,6166,5328,2584,1131,3005,8817,2783,7749,6112,5567,9688,2549,7929,8650,60,1896,3998,7345,3352,8990,1143,873,1191,5821,9485,5249,3086,8016,9319,4139,3566,8871,7528,7873,4117,1085,7064,8222,5947,4447,1326,5206,12,9703,5711,3951,219,6966,3168,2372,9603,9092,1904,1010,2704,2106,7568,3410,296,6825,9781,637,4465,7953,6861,2142,2035,9743,1921,3051,7424,7112,7676,5245,9531,2284,4498,6423,6977,3106,1367,5696,2003,1291,3025,76,3147,9094,4580,5097,7390,8637,5853,359,3153,4957,6635,5721,3353,2266,3481,7432,3020,7330,1172,5285,1525,2928,5331,8856,2163,5169,1465,4439,1876,7446,2192,5577,726,6599,352,3645,7733,8331,5447,8017,5017,7287,6602,7248,6323,4195,9617,2263,4013,450,4073,6131,3569,9019,1858,9827,8118,4972,7422,9666,5760,9213,2817,7952,3948,8683,3645,6402,3264,1919,9276,2519,190,766,8940,3413,2644,8048,83,9724,7009,3777,9663,2483,5752,4578,8951,5902,2170,9967,894,8556,6049,7254,2746,8962,8317,6848,767,7907,1028,9458,6881,4978,6717,8210,3835,1064,7434,746,9449
};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
System.out.println(ans[n]);
}
}
算法3
算法分析
在記憶化搜索的前提下進(jìn)一步優(yōu)化赫粥，把下面這行優(yōu)化掉观话，每次都需要從小到到枚舉，因此用利用前綴和的思想進(jìn)一步優(yōu)化
for(int i = 1;i < Math.abs(pre - cur);i ++)
f[pre][cur] = (f[pre][cur] + dfs(cur,i)) % mod;
滿分代碼
import java.util.Scanner;
public class Main {
static int N = 1010;
static int mod = 10000;
static int[][] f = new int[N][N];
static int dfs(int pre,int cur)
{
if(cur <= 0) return 0;
if(f[pre][cur] != 0) return f[pre][cur];
return f[pre][cur] = (1 + dfs(pre,cur - 1) + dfs(cur,Math.abs(pre - cur) - 1)) % mod;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
dfs(n,n);
System.out.println(f[n][n]);
}
}
9越平、問題描述
小明有一塊空地频蛔，他將這塊空地劃分為 n 行 m 列的小塊，每行和每列的長(zhǎng)度都為 1秦叛。
小明選了其中的一些小塊空地晦溪，種上了草，其他小塊仍然保持是空地挣跋。
這些草長(zhǎng)得很快尼变，每個(gè)月，草都會(huì)向外長(zhǎng)出一些浆劲，如果一個(gè)小塊種了草，則它將向自己的上哀澈、下牌借、左、右四小塊空地?cái)U(kuò)展割按，這四小塊空地都將變?yōu)橛胁莸男K膨报。
請(qǐng)告訴小明，k 個(gè)月后空地上哪些地方有草。
輸入格式
輸入的第一行包含兩個(gè)整數(shù) n, m现柠。
接下來 n 行院领，每行包含 m 個(gè)字母，表示初始的空地狀態(tài)够吩，字母之間沒有空格比然。如果為小數(shù)點(diǎn)，表示為空地周循，如果字母為 g强法，表示種了草。
接下來包含一個(gè)整數(shù) k湾笛。
輸出格式
輸出 n 行饮怯，每行包含 m 個(gè)字母，表示 k 個(gè)月后空地的狀態(tài)嚎研。如果為小數(shù)點(diǎn)蓖墅，表示為空地，如果字母為 g临扮，表示長(zhǎng)了草论矾。
樣例輸入
4 5
.g...
.....
..g..
.....
2
樣例輸出
gggg.
gggg.
ggggg
.ggg.
評(píng)測(cè)用例規(guī)模與約定
對(duì)于 30% 的評(píng)測(cè)用例，2 <= n, m <= 20公条。
對(duì)于 70% 的評(píng)測(cè)用例拇囊，2 <= n, m <= 100。
對(duì)于所有評(píng)測(cè)用例靶橱，2 <= n, m <= 1000寥袭，1 <= k <= 1000。
算法分析
bfs
初始把所有草的位置加到隊(duì)列中关霸，枚舉k輪隊(duì)列的所有的元素传黄，通過bfs遍歷，把四周的空地更新成草队寇，更新了草的位置繼續(xù)加到隊(duì)列中膘掰，為下一輪更新準(zhǔn)備
時(shí)間復(fù)雜度)
Java代碼
//機(jī)器人判分系統(tǒng)要求必須如下規(guī)則：
// 1： 不能有package關(guān)鍵字
// 2： 必須類名必須是Main
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 1010;
static int n,m;
static int k;
static char[][] g = new char[N][N];
static int[] dx = new int[] {0,-1,0,1};
static int[] dy = new int[] {-1,0,1,0};
static void bfs()
{
Queue<Pair> q = new LinkedList<Pair>();
for(int i = 0;i < n;i ++)
for(int j = 0;j < n;j ++)
{
if(g[i][j] == 'g') q.add(new Pair(i,j));
}
int cnt = 0;
while(!q.isEmpty())
{
cnt ++;
if(cnt > k) break;
int num = q.size();
for(int u = 0;u < num;u ++)
{
Pair t = q.poll();
for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] == 'g') continue;
g[a][b] = 'g';
q.add(new Pair(a,b));
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0;i < n;i ++)
{
char[] temp = scan.next().toCharArray();
for(int j = 0;j < m;j ++)
{
g[i][j] = temp[j];
}
}
k = scan.nextInt();
bfs();
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < m;j ++)
{
System.out.print(g[i][j]);
}
System.out.println();
}
}
}
class Pair
{
int x,y;
Pair(int x,int y)
{
this.x = x;
this.y = y;
}
}
10、問題描述
小明要組織一臺(tái)晚會(huì)佳遣，總共準(zhǔn)備了 n 個(gè)節(jié)目识埋。然后晚會(huì)的時(shí)間有限，他只能最終選擇其中的 m 個(gè)節(jié)目零渐。
這 n 個(gè)節(jié)目是按照小明設(shè)想的順序給定的窒舟，順序不能改變。
小明發(fā)現(xiàn)诵盼，觀眾對(duì)于晚上的喜歡程度與前幾個(gè)節(jié)目的好看程度有非常大的關(guān)系惠豺，他希望選出的第一個(gè)節(jié)目盡可能好看银还，在此前提下希望第二個(gè)節(jié)目盡可能好看，依次類推洁墙。
小明給每個(gè)節(jié)目定義了一個(gè)好看值蛹疯，請(qǐng)你幫助小明選擇出 m 個(gè)節(jié)目，滿足他的要求热监。
輸入格式
輸入的第一行包含兩個(gè)整數(shù) n, m 捺弦，表示節(jié)目的數(shù)量和要選擇的數(shù)量。
第二行包含 n 個(gè)整數(shù)狼纬，依次為每個(gè)節(jié)目的好看值羹呵。
輸出格式
輸出一行包含 m 個(gè)整數(shù)，為選出的節(jié)目的好看值疗琉。
樣例輸入
5 3
3 1 2 5 4
樣例輸出
3 5 4
樣例說明
選擇了第1, 4, 5個(gè)節(jié)目冈欢。
評(píng)測(cè)用例規(guī)模與約定
對(duì)于 30% 的評(píng)測(cè)用例，1 <= n <= 20盈简；
對(duì)于 60% 的評(píng)測(cè)用例凑耻，1 <= n <= 100；
對(duì)于所有評(píng)測(cè)用例柠贤，1 <= n <= 100000香浩，0 <= 節(jié)目的好看值 <= 100000。
算法分析
- 1臼勉、有兩個(gè)數(shù)組邻吭，一個(gè)是
a[]數(shù)組，表示初始的數(shù)組宴霸，一個(gè)是b[]數(shù)組囱晴，表示a[]數(shù)組排序后的數(shù)組 - 2、從
b[]數(shù)組中找出前m大瓢谢，扔到set中畸写，再?gòu)那巴竺杜ea[]數(shù)組，若枚舉的當(dāng)前元素氓扛，set中有枯芬，則輸出
注意：
1、set.contain的函數(shù)的復(fù)雜度是
2千所、不知道有沒有可能存在多個(gè)相同的好看值，為了保險(xiǎn)起見蒜埋，設(shè)前m大最下的元素是x淫痰，需要記錄x在前m大中有多少個(gè)
時(shí)間復(fù)雜度)
Java 代碼
//機(jī)器人判分系統(tǒng)要求必須如下規(guī)則：
// 1： 不能有package關(guān)鍵字
// 2： 必須類名必須是Main
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Main {
static int N = 100010;
static int[] a = new int[N];
static int[] b = new int[N];
static Set<Integer> set = new HashSet<Integer>();
static int[] ans = new int[N];
static int k = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for(int i = 1;i <= n;i ++)
{
a[i] = Integer.parseInt(s2[i - 1]);
b[i] = a[i];
}
Arrays.sort(b,1,n + 1);
for(int i = n;i >= n - m + 1;i --)
{
set.add(b[i]);
}
int last = b[n - m + 1];
int cnt = 0;
//判斷最小的元素用到多少個(gè)
for(int i = n - m + 1;i <= n;i ++)
{
if(b[i] == last) cnt ++;
}
for(int i = 1;i <= n;i ++)
{
if(set.contains(a[i]))
{
if(a[i] == last)
{
if(cnt <= 0) continue;
cnt --;
}
ans[k ++] = a[i];
}
}
for(int i = 0;i < k;i ++)
{
if(i != k - 1) System.out.print(ans[i] + " ");
else System.out.println(ans[i]);
}
}
}
