import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
/*
* h(i)/x*w(i)/x等于个数
*/
public class Main {
static int N = 100010;
static int[] h = new int[N];
static int[] w = new int[N];
static int n, k;
private static boolean check(int x) {
int res=0;
for (int i = 0; i < n; i++) {
res += (h[i] / x) * (w[i] / x);
}
if (res >= k)
return true;
return false;
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
k = Integer.parseInt(s[1]);
for (int i = 0; i < n; i++) {
s = br.readLine().split(" ");
h[i] = Integer.parseInt(s[0]);
w[i] = Integer.parseInt(s[1]);
}
// 操作
int l = 0, r = 100000;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
System.out.println(l);
}
}
活动打卡代码
AcWing 1227. 分巧克力
活动打卡代码
AcWing 1221. 四平方和
import java.util.Scanner;
public class Main {
static int N=5000010;
static int h[]=new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
//打表c和d
for(int c=0;c*c<=n;c++) {
for(int d=c;c*c+d*d<=n;d++) {
if(h[c*c+d*d]==0)
h[c*c+d*d]=c+1;//防止有0
}
}
//操作
for(int a=0;a*a<=n;a++) {
for(int b=a;a*a+b*b<=n;b++) {
int t=h[n-a*a-b*b];
if(t!=0) {
int c=t-1;
int d=(int)Math.sqrt(n-a*a-b*b-c*c);
System.out.println(a+" "+b+" "+c+" "+d);
return;
}
}
}
}
}
活动打卡代码
AcWing 730. 机器人跳跃问题
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n;
static int N=100010;
static int a[]=new int[N];
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
private static boolean check(int e) {
for(int i=0;i<n;i++) {
e=e*2-a[i];
//如果不写会爆掉 极端情况数特别大long也不行
if(e>100000) return true;
if(e<0) return false;
}
return true;
}
public static void main(String[] args) throws IOException {
n=Integer.parseInt(br.readLine());
String[] s=br.readLine().split(" ");
for(int i=0;i<n;i++) a[i]=Integer.parseInt(s[i]);
int l=0,r=100000;
while(l<r) {
int mid=l+r>>1;
//mid如果满足所有大于mid的一定满足，而题目找最小
if(check(mid)) r=mid;
else l=mid+1;
}
System.out.println(r);
}
}
活动打卡代码
AcWing 796. 子矩阵的和
import java.util.Scanner;
public class Main {
static int N=1010;
static long a[][]=new long[N][N];
static long s[][]=new long[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int q=sc.nextInt();
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
a[i][j]=sc.nextLong();
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
}
}
int x1,y1,x2,y2;
for(int i=0;i<q;i++) {
x1=sc.nextInt();
y1=sc.nextInt();
x2=sc.nextInt();
y2=sc.nextInt();
System.out.println(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
}
}
}
活动打卡代码
AcWing 795. 前缀和
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N=100010;
static long a[]=new long[N];
static long s[]=new long[N];
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String []st=br.readLine().split(" ");
int n=Integer.parseInt(st[0]);
int m=Integer.parseInt(st[1]);
st=br.readLine().split(" ");
for(int i=1;i<=n;i++) {
a[i]=Integer.parseInt(st[i-1]);
s[i]=s[i-1]+a[i];
}
for(int i=0;i<m;i++) {
st=br.readLine().split(" ");
int l=Integer.parseInt(st[0]);
int r=Integer.parseInt(st[1]);
System.out.println(s[r]-s[l-1]);
}
}
}
活动打卡代码
AcWing 790. 数的三次方根
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double n=sc.nextDouble();
double l=-10000,r=100000;
//保留6位多两位比较好
while(r-l>=1e-8) {
double mid=(l+r)/2;
if(mid*mid*mid>=n) r=mid;
else l=mid;
}
System.out.printf("%.6f",r);
}
}
活动打卡代码
AcWing 789. 数的范围
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int a[]=new int[100010];
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s=br.readLine().split(" ");
int n=Integer.parseInt(s[0]);
int q=Integer.parseInt(s[1]);
s=br.readLine().split(" ");
for(int i=0;i<n;i++) a[i]=Integer.parseInt(s[i]);
for(int i=0;i<q;i++) {
int x=Integer.parseInt(br.readLine());
int l=0,r=n-1;
while(l<r) {
int mid=l+r>>1;
if(a[mid]>=x) r=mid;//说明mid在x右边
else l=mid+1;
}
//找到左端点
if(a[r]==x) {
System.out.print(r+" ");
r=n-1;
while(l<r) {
int mid=l+r+1>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
System.out.print(l+" ");
System.out.println();
}
else System.out.println("-1 -1");
}
}
}
活动打卡代码
AcWing 116. 飞行员兄弟
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
static int N=5;
static char g[][]=new char[N][N];
static char backup[][]=new char[N][N];
static ArrayList<PII> res=new ArrayList<PII>();//存答案
private static int get(int x, int y) {
return 4*x+y;
}
private static void turn_all(int x, int y) {
for(int i=0;i<4;i++) {
turn_one(x,i);
turn_one(i,y);
}
turn_one(x,y);
}
private static void turn_one(int x, int y) {
if(g[x][y]=='+') g[x][y]='-';
else g[x][y]='+';
}
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
//读入
for(int i=0;i<4;i++) g[i]=br.readLine().toCharArray();
for(int op=0;op<1<<16;op++) {
ArrayList<PII> temp=new ArrayList<PII>();
//备份g
for(int i=0;i<4;i++) backup[i]=Arrays.copyOf(g[i], 4);
//操作
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
if((op>>get(i,j)&1)!=0) {
PII pii = new PII();
pii.setX(i);
pii.setY(j);
temp.add(pii);
turn_all(i,j);
}
}
}
//判断是否全关
boolean has_close=false;
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
if(g[i][j]=='+') {
has_close=true;
}
}
}
if(!has_close) {
if(res.isEmpty()||res.size()>temp.size()) {
//res.clear();
res=temp;
}
}
//还原
for(int i=0;i<4;i++) g[i]=Arrays.copyOf(backup[i], 4);
}
//输出
System.out.println(res.size());
for (PII p : res)
System.out.println(p.x + 1 + " " + (p.y + 1));
}
}
class PII {
int x;
int y;
public PII() {}
public PII(int x, int y) {
super();
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
活动打卡代码
AcWing 95. 费解的开关
**
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 6;
static int[] dx ={-1,0,1,0,0};
static int[] dy ={0,1,0,-1,0};//上下左右中 偏移量
static char[][] g = new char[N][N];
static char[][] backup = new char[N][N];
// 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色
static void turn (int x, int y)
{
for (int i = 0; i < 5; i ++ )
{
int a = x + dx[i], b = y + dy[i];
//如果在边界外边，直接忽略即可
if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
//等价于 g[a][b] = '0' + ('1' - g[a][b])
g[a][b] ^= 1; //异或，不同的时候就变成相反的数
//【‘0’ ASCII值48 ‘1’ 49】
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
while(n-- >0) {
// 按行输入，把每一行当成一个字符串 然后转换成字符数组
for(int i=0;i<5;i++) g[i] = in.next().toCharArray();
int res = 7;
//第一行覆盖所有状态
for(int op=0;op<32;op++){
// 我在对这种情况操作的时候，得先备用一下
// 把原始数组备份一下，然后操作g，操作完了还原，然后再操作
for(int j=0;j<5;++j)
{
backup[j]=Arrays.copyOf(g[j], 5);
}
int step = 0;
//计算翻转操作的step
for (int i = 0; i < 5; ++i)
{
if ((op>>i & 1) == 1)
{
step++;
turn(0,i);
}
}
//然后通过第一行按完之后的状态，按234行 递推
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 5; ++j)
{
if (g[i][j] == '0')
{
step++;
// 如果这个位置是灭的，就按下一行对应的位置
turn(i+1,j);
}
}
boolean dark = false;
for (int j = 0; j < 5; j ++ )
if (g[4][j] == '0')
{
dark = true;
break;
}
// 判断可行性 可行的话 是否更优
if (!dark) res = Math.min(res, step);
for(int j=0;j<5;++j)
{
g[j]=Arrays.copyOf(backup[j], 5);
}
}
if(res > 6) res = -1;
System.out.println(res);
}
}
}
活动打卡代码
AcWing 1208. 翻硬币
import java.util.Scanner;
public class Main {
static char start[]=new char[100];
static char end[]=new char[100];
static int ans=0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
start=sc.next().toCharArray();
end=sc.next().toCharArray();
for(int i=0;i<start.length;i++) {
if(start[i]!=end[i]) {
ans++;
turn(i);
turn(i+1);
}
}
System.out.println(ans);
}
private static void turn(int i) {
if(start[i]=='*') start[i]='o';
else start[i]='*';
}
}
