刷题总结
刷题总结
P2433 【深基1-2】，问题十
注意
- 单位时间内均匀增加，意思是每天天增加的数量是一样的，也就是，
n天后草的总数=原有草的总数量+n*每天增加草的数量
关键
1. 假设一头牛每天吃一份草，（这个数量的是多少都可以）
2. 求出每天增长的草的数量，让后求出原有的草的数量，
3. 求解答案的时候，
* 让对应数量的牛吃每天增长的草就好，即增长草的数量=这部分的牛的数量
* 原有的草就用 原有的草数/天数=吃这部分草的牛的数量
* 两部分的牛加起来就是要使用的牛的数量
P1914 小书童——凯撒密码
向后移几位，注意移的位数超过Z的要循环从a开始+
关键代码
c=(char)(((c-'a')+n)%26+'a');
P1125 [NOIP2008 提高组] 笨小猴
这道题用一个map来统计每一个字母的个数，然后再遍历这个hashmap来获取minn，maxn，
然后再判断是不是质数即可
P1957 口算练习题
这题不难，先判断每一行有多少个字符，如果有三个就取第一个字符来判断操作的类型，并且把这个操作字符存起来，然后根据操作类型输出结果，如果只有两个字符，就把存起来的操作字符拿出来判断，进行操作即可
P1038统计单词数目
这道题目请注意 :
- 单词之间的空格不一定只有一个
- 是查找整个单词匹配，而不能部分对应
- 是查找在字符串中的第一个出现位置，而不是split之后分离的数组位置（详见下面代码）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String word = sc.nextLine().toLowerCase();
String string = sc.nextLine().toLowerCase();
String[] s = string.split(" ");
int locate=-1;
int count=0;
int postion=0;
for (int i=0;i<s.length;i++) {
if (s[i].equals(word)){
if (locate==-1){
locate=postion;
}
count++;
}
postion+=s[i].length()+1;
}
if (locate!=-1){
System.out.printf("%d ",count);
}
System.out.println(locate);
}
}
P1765 手机
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
int count=0;
String a = "abcdefghijklmnotuv"; //打表，这里都是只用按三次的
String b = "pqrswxyz";//这里都是只用按4次的
for (char c : line.toCharArray()) {
int x = a.indexOf(c);
if (c==' ')count++;
else if (x !=-1){
count+=(x%3+1); //关键
} else {
int y = b.indexOf(c);
if (y !=-1) {
count+=(y%4+1); //关键
}
}
}
System.out.println(count);
}
}
P3741 小果的键盘
解题思路
- 我先从头到尾统计’VK’的数量,再替换成"!!"或者其他的两个字符也行
- 因为最多改变一次,所以去找到一个kk或者VV就行了,可以简化为
noneVK.charAt(i)==noneVK.charAt(i+1)&&noneVK.charAt(i)!='!'
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int strLenght = sc.nextInt();
sc.nextLine();
String s = sc.nextLine();
int count=0;
if (strLenght==1){
System.out.println(0);
return;
}
for (int i = 0; i < strLenght-1; i++) {
if (s.charAt(i)=='V'&&s.charAt(i+1)=='K'){
count++;
}
}
String noneVK = s.replace("VK", "!!");
for (int i = 0; i < noneVK.length()-1; i++) {
if (noneVK.charAt(i)==noneVK.charAt(i+1)&&noneVK.charAt(i)!='!'){
count++;
flag=false;
break;
}
}
System.out.println(count);
}
}
P1321 单词覆盖还原
感觉这个题目单纯就是我想的太多了，只要字符按照顺序满足boygirl部分相同就行了，看代码
package P1321;
import javax.swing.*;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] str = sc.next().toCharArray();
char[] boy = "boy".toCharArray();
char[] girl = "girl".toCharArray();
int cboy=0,cgirl=0;
for (int i = 0; i < str.length-2; i++) {
if (str[i]=='b'||str[i+1]=='o'||str[i+2]=='y')cboy++;
if (i+3>=str.length)continue;
if (str[i]=='g'||str[i+1]=='i'||str[i+2]=='r'||str[i+3]=='l')cgirl++;
}
System.out.println(cboy);
System.out.println(cgirl);
}
}
P1553 数字反转（升级版）
注意点
- 首先是要注意这个题目的输入范围，可能会超过int的范围，那么我们就需要用BigInteger来存这个数字
- 使用split的时候，里面的分离字符需要的是regex正则表达式，，那么替换".“这个符号的时候就需要这样
s.split("\\."),”."符号代表的是任意字符
请看代码
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
if (s.contains(".")){
//这里要注意split里面的是正则表达式，符号”."则代表任意字符，要注意一下
String[] split = s.split("\\.");
for (int i = 0; i < split.length; i++) {
split[i]=reverse(split[i]);
}
System.out.println(split[0]+"."+split[1]);
} else if (s.contains("/")) {
String[] split = s.split("\\/");
for (int i = 0; i < split.length; i++) {
split[i]=reverse(split[i]);
}
System.out.println(split[0]+"/"+split[1]);
}else if(s.contains("%")){
String temp = s.replace("%", "");
temp=reverse(temp);
System.out.println(temp+"%");
}else {
System.out.println(reverse(s));
}
}
public static String reverse(String s){
BigInteger i1 = new BigInteger(s);
String s1 = new StringBuilder(String.valueOf(i1)).reverse().toString();
BigInteger i = new BigInteger(s1);
String s2 = String.valueOf(i);
return s2;
}
}
这道题还可以学习一下题解的优秀代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
char p=0;//放符号
int cnt=0;
cin>>s;
for(int i=0;i<s.size();i++)
{
if(s[i]>='0'&&s[i]<='9') cnt++;//记录第一个数长度
else //遇到符号，记录，跳出
{
p=s[i];
break;
}
}
int x=cnt;//记下第一个数末后一个的位置，也就是符号的位置，如果是分数或小数就要用
cnt--;
while(s[cnt]=='0'&&cnt>0) cnt--;//去除多余前导0；
for(int i=cnt;i>=0;i--)//输出第一个数
cout<<s[i];
if(p==0) return 0;//无符号return 0
else
if(p=='%') {cout<<p;return 0;}
else cout<<p;//其他继续
int m=s.size()-1;
while(s[x+1]=='0'&&x<m-1) x++;//去除末尾0
while(s[m]=='0'&&m>x+1) m--; //去除多余前导0
for(int i=m;i>x;i--)//输出第二个数
cout<<s[i];
return 0;
}
P1603 斯诺登的密码
- 水题，暴力打表即可
- 需要注意的是，里面的非正规英文字符也是要识别的一种
上代码
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
HashMap<String, String> number = new HashMap<>();
number.put("zero","00");
number.put("one","01");
number.put("a","01");
number.put("another","01");
number.put("first","01");
number.put("two","04");
number.put("both","04");
number.put("second","04");
number.put("three","09");
number.put("third","09");
number.put("four","16");
number.put("five","25");
number.put("six","36");
number.put("seven","49");
number.put("eight","64");
number.put("nine","81");
number.put("ten","00");
number.put("eleven","21");
number.put("twelve","44");
number.put("thirteen","16");
number.put("fourteen","96");
number.put("fifteen","25");
number.put("sixteen","56");
number.put("seventeen","89");
number.put("eighteen","24");
number.put("nineteen","61");
number.put("twenty","00");
String s = sc.nextLine();
String[] s1 = s.split(" ");
StringBuilder sb = new StringBuilder();
for (String s2 : s1) {
if (number.get(s2)!=null){
sb.append(number.get(s2));
}
}
if (sb.length()==0){
System.out.println(0);
return;
}
char[] chars = sb.toString().toCharArray();
int begin=0,end=sb.length()-1;
while (chars[begin]=='0')begin++;
while (chars[end]=='0')end--;
for (int i = begin ; i <= end; i++) {
System.out.print(chars[i]);
}
}
}
P1200 [USACO1.1] 你的飞碟在这儿 Your Ride Is Here
- 仍旧是水题
- 0是48，A是65，a是97，ASCII码值
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String start = sc.nextLine();
String team = sc.nextLine();
int teamNum=1,startNum=1;
for (char c : start.toCharArray()) {
startNum*=((c-'A')+1);
}
for (char c : team.toCharArray()) {
teamNum*=((c-'A')+1);
}
if (teamNum%47==startNum%47){
System.out.println("GO");
}else {
System.out.println("STAY");
}
}
}
P1088 [NOIP2004 普及组] 火星人
这道题目是好题，可以学到dfs，从某种状态开始的dfs，生成下一个字典序算法
- 暴力dfs
通过dfs暴力生成到给出的排列，然后再生成m个即可,但是这样包会超时的
上代码
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); // 最优输入流
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流
static int nextInt() throws IOException { // 输入流的封装函数
in.nextToken();
return (int) in.nval;
}
static Double nextDouble() throws IOException { // 输入流的封装函数
in.nextToken();
return in.nval;
}
static Long nextLong() throws IOException { // 输入流的封装函数
in.nextToken();
return (long) in.nval;
}
static int cnt;
static int m=0;
static int resultNum=-1;
static boolean isFinded=false;
public static void main(String[] args) throws IOException {
int n=nextInt();
m=nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i]=nextInt();
}
int[] result = new int[n];
boolean []used=new boolean[n+1];
dfs(result,0,n,used,num);
out.flush(); // 刷新输出流
out.close();//关闭流
}
public static void dfs(int[]result,int size ,int n,boolean []used,int []num){
if (isFinded)return;
if (size==n){
cnt++;
if (cnt==resultNum){
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(result[i]).append(" ");
}
out.println(sb);
}
boolean flag=true;
for (int i = 0; i < n; i++) {
if (num[i]!=result[i]) {
flag=false;
break;
}
}
if (flag){
resultNum=cnt+m;
}
}
for (int i = 1; i <= n; i++) {
if (isFinded)break;
if (used[i])continue;
result[size]=i;
used[i]=true;
dfs(result,size+1,n,used,num);
used[i]=false;
}
}
}
- 通过改变i的状态，使得 dfs 直接到题目给出状态，
- 注意51行，是代码的关键，即使第size层的位置直接是题目给的i，生成特定状态的dfs
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); // 最优输入流
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流
static int nextInt() throws IOException { // 输入流的封装函数
in.nextToken();
return (int) in.nval;
}
static Double nextDouble() throws IOException { // 输入流的封装函数
in.nextToken();
return in.nval;
}
static Long nextLong() throws IOException { // 输入流的封装函数
in.nextToken();
return (long) in.nval;
}
static int cnt;
static int m=0;
static boolean isFinded=false;
public static void main(String[] args) throws IOException {
int n=nextInt();
m=nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i]=nextInt();
}
int[] result = new int[n];
boolean []used=new boolean[n+1];
dfs(result,0,n,used,num);
out.flush(); // 刷新输出流
out.close();//关闭流
}
public static void dfs(int[]result,int size ,int n,boolean []used,int []num){
if (isFinded)return;
if (size==n){
cnt++;
if (cnt==m+1){
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(result[i]).append(" ");
}
out.println(sb);
isFinded=true;
}
}
for (int i = 1; i <= n; i++) {
if (isFinded)return;
if (cnt==0)i=num[size];
if (used[i])continue;
result[size]=i;
used[i]=true;
dfs(result,size+1,n,used,num);
used[i]=false;
}
}
}
- 下一个字典序算法
字典序的基本概念：
给定一个排列，我们可以通过交换元素的顺序来生成下一个排列。字典序的生成遵循以下原则：字母/数字越小的排列越靠前。
例如，给定排列 [1, 2, 3]，下一个排列是 [1, 3, 2]，而 [2, 1, 3] 是大于 [1, 3, 2] 的排列。
字典序生成的核心步骤
1. <font style="color:#000000;background-color:#D9DFFC;">从后向前查找第一个升序对：</font>
我们从排列的末尾开始，查找第一个满足 a[i] < a[i+1] 的位置，记作 i。这个位置的含义是：如果当前位置不满足升序对，则说明当前排列已经是最大的排列，没有下一个排列可生成。
为什么这样做？
如果我们从后向前检查排列，当我们发现某个元素 a[i] < a[i+1] 时，意味着我们可以对其进行交换来得到更大的排列。
2. <font style="background-color:#D9DFFC;">从后向前查找第一个比 a[i] 大的元素：</font>
接下来，我们需要找到一个比 a[i] 大的元素，并且这个元素应该尽量大。为了确保字典序最小，我们从后向前遍历并找到第一个比 a[i] 大的元素 a[j]，使得 a[j] > a[i]。
为什么选择 a[j] > a[i]？
这是为了确保交换后的排列不会跳过较大的排列（也就是说，尽量“最小化”交换后的排列），从而生成下一个字典序排列。
3. <font style="background-color:#D9DFFC;">交换 a[i] 和 a[j]：</font>
一旦我们找到 a[i] 和 a[j]，我们交换这两个元素。交换后，数组的前半部分已经生成了字典序较大的排列。
4. 反转 i 之后的部分：
交换之后，数组 a[i+1] 到 a[n-1] 这部分是一个递减序列。为了保证这部分元素排列在最小字典序，我们需要将它们进行反转。这是因为，如果这部分已经是最大排列（递减排列），反转后就变成了最小排列（递增排列）。
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); // 最优输入流
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流
static int nextInt() throws IOException { // 输入流的封装函数
in.nextToken();
return (int) in.nval;
}
static Double nextDouble() throws IOException { // 输入流的封装函数
in.nextToken();
return in.nval;
}
static Long nextLong() throws IOException { // 输入流的封装函数
in.nextToken();
return (long) in.nval;
}
public static void main(String[] args) throws IOException {
int n=nextInt(),m=nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i]=nextInt();
}
for (int i = 0; i < m; i++) {
nextPermutation(nums);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(nums[i]).append(" ");
}
out.println(sb);
out.flush(); // 刷新输出流
out.close();//关闭流
}
public static void nextPermutation(int []num){
int n = num.length;
int i = n - 2;
for (; i >= 0&&num[i]>num[i+1]; i--);
if (i<0)return;
int j= n -1;
for (; j >i&&num[j]<num[i]; j--);
//交换
num[i]=num[i]^num[j];
num[j]=num[i]^num[j];
num[i]=num[i]^num[j];
for (int k = 1; k <= (n - i) / 2; k++) {
if (i+k==n-k)break;
num[i+k]=num[i+k]^num[n-k];
num[n-k]=num[i+k]^num[n-k];
num[i+k]=num[i+k]^num[n-k];
}
}
}
P3799 小 Y 拼木棒
- 解题思路
- 首先，如果要拼成这样一个正三角形，必须有两边是相等的，即设四条木棍为a,b,c,d，则有a=b,
- 再有，题目问有几种选法，那么我只要 a的可能c的可能d的可能 （分步乘法计数原理） 即可
- a的可能：如果一个长度的木棍数目>2 ，从中选 2个出来，即a的可能，即 $ C_{\text该长度的木棍数目}^2
$ - 对于c 和 d ，则有两种可能，c==d，或者c !=d ,
- 对于c==d： 则只需要 $ C_{c长度的木棍数目}^2 $ 即可
- 对于c!=d： 则 $ c长度的木棍数目*d长度的木棍数目 $即可
- 对于d的求法，建议是d=a-c,若d不存在，则在上一步不会做出贡献，所以不会计入最终结果
- 最后 所有的可能=$ C_{a长度的木棍数目}^2C_{c长度的木棍数目}^2
$(c==d) 或者$ C_{a长度的木棍数目}^2（c长度的木棍数目*d长度的木棍数目）
$(c==d)
- 注意点（错点）
- 10行的i的范围写错
- 9行的1e9写成1e7
- 代码
public class Main {
public static void main(String[] args) throws IOException {
int n=nextInt();
int[] cnt = new int[5001];
for (int i = 0; i < n; i++) {
cnt[nextInt()]++;
}
long sum=0;
long mod=(long)1e9+7;
for (int i = 0; i < 5001; i++) {
if (cnt[i]>=2){
long chooseA=cnt[i]*(cnt[i]-1)/2;
long chooseCD=0;
for (int c = 1; c <= i / 2; c++) {
int d=i-c;
if (c==d){
chooseCD+=cnt[c]*(cnt[c]-1)/2;
}
else {
chooseCD+=cnt[c]*cnt[d];
}
}
sum=(sum+ (long) chooseA *chooseCD)%mod;
}
}
out.println(sum);
out.flush(); // 刷新输出流
out.close();//关闭流
}
}
P2392 kkksc03考前临时抱佛脚
- 因为可以同时做两件事情，时间久的时间就会把时间短的事情覆盖掉，这道题一开始想到的就是贪心，分为左脑和右脑，将科目的任务排序，总是选择最大的科目任务到当前总时间较小的脑中，这样离答案是比较接近的，但是错了，因为如{7，6，5，4，3}这样的集合，找不到{7，6}和{5，4，3}这样的组合
- 那么开始考虑dp
P1002 [NOIP 2002 普及组] 过河卒
- 这道题我的理解是用dp算法做，
- 如果首先不考虑马的控制点，那么到达B点 的路径数等于左边那个点的路径数+上面个点的路径数（其他点也是这样），
- 可以的得到状态转移方程 dp[i][j]=dp[i][j-1]+dp[i-1][j]
- 然后加入马的控制点的话就跳过这个点，这个点（马的控制点）的路径数为0，
- 然后就这样一直dp，最后输出dp[B点X][B点Y]即可
代码
public static void main(String[] args) throws IOException {
int[] B=new int[2];
int[] horse=new int[2];
//整体平移2个格子，防止马的控制点越界
B[0]=nextInt()+2;
B[1]=nextInt()+2;
horse[0]=nextInt()+2;
horse[1]=nextInt()+2;
int[] controlPx={-1,-2,-2,-1,1,2,2,1};
int[] controlPy={-2,-1,1,2,2,1,-1,-2};
long[][] dp=new long[B[0]+1][B[1]+1];
boolean[][] cantPoint=new boolean[B[0]+1][B[1]+1];
cantPoint[horse[0]][horse[1]]=true;
for (int i = 0; i < 8; i++) {
cantPoint[horse[0]+controlPx[i]][horse[1]+controlPy[i]]=true;
}
//初始化原点左边的那个点，让原点在循环的时候是1
dp[2][1]=1;
for (int i = 2; i < (B[0] + 1); i++) {
for (int j = 2; j < B[1] + 1; j++) {
if (cantPoint[i][j])continue;
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
out.println(dp[B[0]][B[1]]);
out.flush(); // 刷新输出流
out.close();//关闭流
}
BUT 这道题还可以优化一下空间复杂度
- 使用滚动数组，及使用未更新的数据来更新数据
- 观察这道题目的状态转移方程 dp[i][j]=dp[i][j-1]+dp[i-1][j]，发现我们只需要第i行和第i-1行的数据就行了，然后我们就只要想办法只保存第i行和第i-1行的数据，
- 我发现，如果只用一维数组，我们从前到后更新数据，那么更新第j个数据的时候，这时候的j还是i-1的数据，即j的数据未更新，即符合上一个dp[i-1][j]的公式，所以我们可以得到一个新的状态转移方程，
- dp[j]=dp[j-1]+dp[j]
- 解释
- dp[j-1]即左边的数据
- dp[j] 因为dp[j]还没有更新，所以是上面的数据
- 解释
public static void main(String[] args) throws IOException {
int bx=nextInt()+2,by=nextInt()+2,mx=nextInt()+2,my=nextInt()+2;
boolean[][] canGo=new boolean[bx+1][by+1];
long []dp =new long[by+1];
int [] mConX={-2, -1, 1, 2, 2, 1, -1, -2};
int [] mConY={1, 2, 2, 1, -1, -2, -2, -1};
for (int i = 0; i < 8; i++) {
canGo[mx+mConX[i]][my+mConY[i]]=true;
}
canGo[mx][my]=true;
// dp[1]=1;
dp[2]=1;
for (int i = 2; i <= bx; i++) {
for (int j = 2; j <= by; j++) {
if (canGo[i][j]){
dp[j]=0;
continue;
}
dp[j]=dp[j]+dp[j-1];
}
}
out.println(dp[by]);
out.flush(); // 刷新输出流
out.close();//关闭流
}
P1028[NOIP 2001 普及组] 数的计算
- 分析题目，大致理解题意为生成一个数列，生成的下一位不能大于上一位的一半，问你有可以生成多少个数列
- 普通dfs
- 我首先想到的是dfs，从第一个数开始深度优先搜索，下一位的循环终点是上一位的一半，dfs的终点是 x/2==0的时候，即下一位的一半就是0了，就不用再搜索了
- 但是这样题目会超时
public static void main(String[] args) throws IOException {
int n=nextInt();
out.println(dfs(n));
out.flush(); // 刷新输出流
out.close();//关闭流
}
public static int dfs(int n){
if (n/2==0)return 1;
int temp=0;
for (int i = 0; i <= (n / 2); i++) {
temp+=dfs(i);
}
return temp;
}
- 记忆化dfs
- 既然普通dfs会超时，那么我们对dfs进行优化，即记忆化dfs
- 当搜索结果有重复的时候，我们可以搜索结果存起来，
- 我们搜索数据或者节点的时候，我们判断这个节点之前有没有搜索过，即有没有值，
- 如果有就返回之前的值
- 如果没有，就可以对这个节点进行深搜索了
- 既然普通dfs会超时，那么我们对dfs进行优化，即记忆化dfs
public static void main(String[] args) throws IOException {
int n=nextInt();
int []mem=new int[n+1];
mem[0]=1;
out.println(dfs(n,mem));
out.flush(); // 刷新输出流
out.close();//关闭流
}
public static int dfs(int n,int []mem){
int temp=0;
for (int i = 0; i <= (n / 2); i++) {
if (mem[i]>0)temp+=mem[i];
else temp+=(mem[i]=dfs(i,mem));
}
return temp;
}
- dp算法
- 顺着dfs的思路，我可以进行dp
- 进行推导公式
- 当 x/2==0时，f(x)=1;
- 当x/2>0时，f(x)=f(i) ,i为 0到x/2
- 可以看出 x/2>0时，f(x)=f(0)+f(1)+f(2)+·········+f(x/2)
- f(x)为前面的和加起来
- 那么我就将前面的和存起来，然后加到 x/2即可
public static void main(String[] args) throws IOException {
int n=nextInt();
int[]dp=new int[n+1];
int[]dpSum=new int[n+1];
dp[0]=1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i / 2; j++) {
dp[i]+=dp[j];
}
}
out.println(dp[n]);
out.flush(); // 刷新输出流
out.close();//关闭流
}
- dp优化
- 我们再开一个存储 前n个的和的数组 dpSum
- 可以看出dp[x]=dpSum[x/2] , dpSum[x]=dpSum[x-1]+dp[x]
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int [] dp=new int[n+1]; //代表的含义是 dp[x]是前x/2项的和
int [] dpSum=new int[n+1]; //代表的是前 n项的和；
dp[0]=1;
dpSum[0]=1;
for (int i = 1; i <= n; i++) {
dp[i]=dpSum[i/2];
dpSum[i]=dpSum[i-1]+dp[i];
}
System.out.println(dp[n]);
}
P1928 外星密码
- 这道题要求我们进行字符串的解密
- 那么我们来模拟字符串的解密过程
- 新建一个临时字符串
- 对每个字符进行读取
- 如果找到一个 【 符号，
- 然后读取要重复的数字（注意不要只读一个字符，因为数字可能是两位数，我就是这里踩了坑）
- 然后后面就是要重复的字符串
- 重复读取字符，添加进临时数组，直到遇到 【符号或者 】符号
- 遇到 【符号 跳到步骤3开始
- 遇到】符号 跳到我们将临时字符串返回
- 从上面的步骤中，我们可以看出有递归，即第九步
import java.io.*;
import java.util.Scanner;
public class Main {
static int l=0;
static int lenght;
static char[] str=null;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
str = sc.nextLine().toCharArray();
lenght=str.length;
System.out.println(decode());
}
public static String decode(){
StringBuilder temp = new StringBuilder();
while (l<lenght){
if (str[l]=='['){
l++; //跳过 '['符号
int num=0; //注意要定义在这里面，不然其他同级的数据会继续使用上一个同级的数据，
//这样结果就不对了
while (l<lenght&&Character.isDigit(str[l])) num = num * 10 + (str[l++] - '0');
String sub = decode();
for (int i = 0; i < num; i++) {
temp.append(sub);
}
}else if(str[l]==']'){
l++;
return temp.toString();
}
else {
temp.append(str[l++]);
}
}
return temp.toString();
}
}
P1228 地毯填补问题（第一道不看题解做出来的提高/普及-题目，庆祝！！！）
- 理解题意
- 题目要求我们使用四种地毯将除公主所在的格子以外的正方形内的格子铺满
- 开始解题
- 观察测试用例发现
- 铺地毯的时候总是从一个正方形的中间开始铺，
- 如第一步先铺最大的正方形的中间，第二步铺左边1/2小的正方形的中间，第三步铺右边，
第四步铺左下，第五步铺右下（看不出来可以前后对比着看，就很明显了）
4. 那么我就就知道了可以使用分治法进行解决这道题
5. 那么如何判断使用哪个地毯呢，
6. 从小往大看，地毯总是要将缺口对准公主的格子，
7. 那么我们可以将一个大正方形看作已经全部被公主占领了，
8. 那么就可以决定中间使用哪个方向的地毯了
9. 中间的解决了，如何解决四个小一点的正方形呢
10. 由于有一个方向有公主的格子，我们不用管
11. 其他三个正方形，我们可以将在中间的地毯的三个格子看成是公主已经占领的格子，
12. 那么我们就可以使用步骤f，来确定小一点的正方形的中间地毯的方向了
13. 那么自然的，递归出口就是，格子数为1的时候，或者step数为0的时候
3. 注意事项
1. 注意第57，58行，利用地毯的号数，来避免要写很多次重复的递归
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流
static int nextInt() throws IOException { // 输入流的封装函数
in.nextToken();
return (int) in.nval;
}
static Double nextDouble() throws IOException { // 输入流的封装函数
in.nextToken();
return in.nval;
}
static Long nextLong() throws IOException { // 输入流的封装函数
in.nextToken();
return (long) in.nval;
}
public static void main(String[] args) throws IOException {
int k=nextInt(),x=nextInt(),y=nextInt();
getPrincess(k,x,y,1,1);
out.flush(); // 刷新输出流
out.close();//关闭流
}
public static void getPrincess(int step,int x,int y,int beginX,int beginY){
if (step==0)return;
int nextStep=step-1;
int choice =0;
int center = (1 << (step-1))-1;
int cross=center+1;
int choiceX=center;
int choiceY=center;
if (x<= beginX+center){
if (y<=beginY+center){
choice=1;
choiceX=choiceY+=1;
}else {
choice = 2;
choiceX+=1;
}
}else {
if (y<=beginY+center){
choice=3;
choiceY+=1;
}else {
choice = 4;
}
}
out.println((beginX+choiceX)+" "+(beginY+choiceY)+" "+choice);
if (nextStep==0)return;
int[][] add={{beginX+center,beginY+center},{beginX+center,beginY+center+1},{beginX+center+1,beginY+center},{beginX+center+1,beginY+center+1}};
add[choice-1][0]=x;
add[choice-1][1]=y;
getPrincess(nextStep,add[0][0],add[0][1],beginX,beginY);
getPrincess(nextStep,add[1][0],add[1][1],beginX,beginY+cross);
getPrincess(nextStep,add[2][0],add[2][1],beginX+cross,beginY);
getPrincess(nextStep,add[3][0],add[3][1],beginX+cross,beginY+cross);
}
}
更新: 2025-04-06 11:12:53
原文: https://www.yuque.com/duifangzhengzaishuru-rqbua/axyc58/uzmm4zgcog3rlbt8