01_被3整除
题目描述
小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。
并且小Q对于能否被3整除这个性质很感兴趣。
小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。
输入描述:
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。
输出描述:
输出一个整数, 表示区间内能被3整除的数字个数。
解题思路
计算数列前12项能否被3整除，结果如下表：
可以得出一个结论：
数组的f(3n+1) n>=0项不能被3整除，其余的可以被整除。
所以用数学归纳法可以得出一下公式：
设数组前n项中能被3整除的项的个数为count,则
count=2*n/3;
因此，要计算第l到r项中能被3整除的数字个数，只需要计算1到l和1到r能被3整除的数字的个数，再相减即可。
count(l,r)=count(1,r)-count(1,l)+1
但在计算中会忽略边界问题，比如
第2到第5项
count(2,5)=count(1,5)-count(1,2)=3-2+1=2
而实际有3个可以被3整除的数。
因此需要添加一个判段条件
“l%3!=0&&(l+1)%3==0||l%3==0”
如果l%3!=0&&(l+1)%3==0,比如f(2)、f(5)
l%3==0,比如f(3)、f(6)
此时就需要给差值上加1。因为在求通项时是从n=1开始的，而实际计算时n不一定为1。
java代码实现：
import java.util.Scanner;
public class 被3整除 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(Division(l, r));
}
public static int Division(int l, int r) {
int flag = 0;
if (l % 3 != 0 && (l + 1) % 3 == 0 || l % 3 == 0)
flag = 1;
int cl = 2 * l / 3;
int cr = 2 * r / 3;
return cr - cl + flag;
}
}
02_安置路灯
题目描述
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯
解题思路
贪心算法求解：
当遇到第一个'.'时，表示该位置sum需要被照亮，此时不安装路灯，在它的下一个位置安装路灯，即sum+1;因为该路灯位置的下一个位置sum+2已经被照亮了，因此下标+2；不需要处理'X'的情况，因为此处不需要安装路灯。
java代码实现：
import java.util.Scanner;
public class 安置路灯 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
String s = sc.next();
System.out.println(Count(n, s));
}
}
private static int Count(int n, String s) {
int flag = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '.') {
flag++;
i = i + 2;
}
}
return flag;
}
}
03_迷路的牛牛
题目描述
牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。
输出描述:
输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。
解题思路
如果一直向右转就是顺时针旋转，反之就是逆时针旋转。因为最初面朝正北，如果转4次或者4整数倍数次，还是面朝正北。所以，只需要统计向左旋转L和向右旋转R的次数，相减，就可以相互抵消一部分旋转次数。
记向左旋转次数为count_L，向右旋转次数为count_R。
用count_L和count_R相减之后的差的绝对值对4取余；
①count_L - count_R > 0
如果余数为1，则最后的方向为“W”
如果余数为3，则最后的方向为“E”
②count_L - count_R > 0
如果余数为1，则最后的方向为“W”
如果余数为3，则最后的方向为“E”
③count_L - count_R = 0
说明向左和向右转的次数一样，最终方向还是“N”
- 若余数为2，不管count_L 和 count_R 大小关系如何，都是旋转两次，最终方向为“S”
java代码实现：
import java.util.Scanner;
public class 迷路的牛牛 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String str = sc.next();
int count_L = 0;
int count_R = 0;
for (int i = 0; i < n; i++) {
if (str.charAt(i) == 'L')
count_L++;
if (str.charAt(i) == 'R')
count_R++;
}
int d = Math.abs(count_R - count_L);
if (d % 4 == 0) {
System.out.println("N");
}
if (d % 4 == 1) {
if (count_R > count_L)
System.out.println("E");
else
System.out.println("W");
}
if (d % 4 == 2) {
System.out.println("S");
}
if (d % 4 == 3) {
if (count_R > count_L)
System.out.println("W");
else
System.out.println("E");
}
}
}
京公网安备 11010502036488号