AcWing《算法提高课》拼团优惠！https://www.acwing.com/activity/content/introduction/16/group_buy/134550/
活动打卡代码
AcWing 1562. 微博转发（每日一题）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N = 1010;
static int a [] = new int [N];
static Map <Integer,List<N>> adj = new HashMap<>();
static void add(int a,int b) {
if(!adj.containsKey(a))adj.put(a, new ArrayList<>());
adj.get(a).add(new N(b));
}
static int l;
public static void main(String agrs[]) throws IOException {
String s [] = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
l = Integer.parseInt(s[1]);
for(int i=1;i<=n;i++) {
adj.put(i, new ArrayList<>());
}
for(int i=1;i<=n;i++) {
s = br.readLine().split(" ");
int c = Integer.parseInt(s[0]);
for(int j=1;j<=c;j++) {
add(Integer.parseInt(s[j]),i);
}
}
s = br.readLine().split(" ");
int c = Integer.parseInt(s[0]);
for(int i=1;i<=c;i++) {
Arrays.fill(st, false);
ans = 0;
k=l;
int num = Integer.parseInt(s[i]);
st[num]=true;
dfs(num,k);
System.out.println(ans);
}
}
static int k,ans;
static boolean [] st = new boolean [1010];
static void dfs(int num,int k) {
if(k==0) {
return;
}
List<N> list=adj.get(num);
if(list==null)return;
for(N no:list) {
dfs(no.idx,k-1);
if(!st[no.idx]) {
ans++;
st[no.idx]=true;
}
}
}
}
class N {
int idx;
public N(int idx) {
this.idx = idx;
}
}
活动打卡代码
AcWing 3777. 砖块（每日一题）
import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
//acwing
public class Main {
static char [] s;
static char [] s1;
static char [] c;
static char [] d;
public static void main(String agrs[]) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
int t = sc.nextInt();
while(t-->0) {
int ans=0;int bns=0;
int n = sc.nextInt();
s = sc.next().toCharArray();
s1 = new char [s.length];
for(int i=0;i<s1.length;i++)s1[i]=s[i];
c = new char [s.length];
d = new char [s.length];
for(int i=0;i<c.length;i++)c[i]='W';
for(int i=0;i<d.length;i++)d[i]='B';
for(int i=0;i<s.length-1;i++) {
if(s[i]!=c[i]) {
turn(i,i+1);
list1.add(i);
ans++;
}
}
for(int i=0;i<s1.length-1;i++) {
if(s1[i]!=d[i]) {
turn1(i,i+1);
list2.add(i);
bns++;
}
}
boolean si =true;boolean ss = true;
for(int i=0;i<s.length;i++) {
if(s[i]!=c[i]) {
si=false;
}
}
for(int i=0;i<s1.length;i++) {
if(s1[i]!=d[i]) {
ss=false;
}
}
if(si&&ss) {
if(ans<bns) {
if(list1.isEmpty()) {
System.out.println(0);
continue;
}
System.out.println(list1.size());
for(int i:list1) {
System.out.print(i+1+" ");
}
System.out.println();
}else {
if(list1.isEmpty()) {
System.out.println(0);
continue;
}
System.out.println(list2.size());
for(int i:list2) {
System.out.print(i+1+" ");
}
System.out.println();
}
}else {
if(si) {
if(list1.isEmpty()) {
System.out.println(0);
list1.removeAll(list1);
list2.removeAll(list2);
continue;
}
System.out.println(list1.size());
for(int i:list1) {
System.out.print(i+1+" ");
}
System.out.println();
}
if(ss) {
if(list2.isEmpty()) {
System.out.println(0);
list1.removeAll(list1);
list2.removeAll(list2);
continue;
}
System.out.println(list2.size());
for(int i:list2) {
System.out.print(i+1+" ");
}
System.out.println();
}
if(!si&&!ss) {
System.out.println(-1);
}
}
list1.removeAll(list1);
list2.removeAll(list2);
}
}
public static void turn(int i,int j) {
if(s[i]=='W')s[i]='B';
else s[i]='W';
if(s[j]=='B')s[j]='W';
else s[j]='B';
}
public static void turn1(int i,int j) {
if(s1[i]=='W')s1[i]='B';
else s1[i]='W';
if(s1[j]=='B')s1[j]='W';
else s1[j]='B';
}
}
按照y总的优化后为：
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static int n;
static String str;
static char [] s;
public static void main(String agrs[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0) {
n = sc.nextInt();
str = sc.next();
if(!check('B')&&!check('W')) {
System.out.println(-1);
}
}
}
public static boolean check(char c) {
ArrayList<Integer> list = new ArrayList<>();
s = str.toCharArray();
for(int i=0;i+1<n;i++) {
if(s[i]!=c) {
update(s[i],i);
update(s[i+1],i+1);
list.add(i);
}
}
if(s[s.length-1]!=c)return false;
System.out.println(list.size());
for(int i:list) {
System.out.print(i+1+" ");
}
if(list.size()>0)System.out.println();
return true;
}
public static void update(char c,int i) {
if(c=='W')s[i]='B';
else s[i]='W';
}
}
活动打卡代码
AcWing 1240. 完全二叉树的权值
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int a [] = new int [100010];
public static void main(String agrs[]) throws IOException {
int n = Integer.parseInt(br.readLine());
String s [] = br.readLine().split(" ");
for(int i=1;i<=n;i++) {
a[i] = Integer.parseInt(s[i-1]);
}
long max = Long.MIN_VALUE;
int de = 0;
for(int d=1,i=1;i<=n;i*=2,d++) {
long sum = 0;
for(int j=i;j<i+(1<<(d-1))&&j<=n;j++) {
sum+=a[j];
}
if(sum>max) {
max=sum;
de = d;
}
}
System.out.println(de);
}
}
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int a [] = new int [100010];
public static void main(String agrs[]) throws IOException {
int n = Integer.parseInt(br.readLine());
String s [] = br.readLine().split(" ");
for(int i=1;i<=n;i++) {
a[i] = Integer.parseInt(s[i-1]);
}
long max = Long.MIN_VALUE;
int de = 0;
for(int d=1,i=1;i<=n;i*=2,d++) {
long sum = 0;
for(int j=i;j<i+(1<<(d-1))&&j<=n;j++) {
sum+=a[j];
}
if(sum>max) {
max=sum;
de = d;
}
}
System.out.println(de);
}
}
活动打卡代码
AcWing 4865. 有效类型
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static String ans="";
static StringBuilder s = new StringBuilder();
static String [] t;
static int flag=1,i=0;
public static void main(String agrs[]) throws NumberFormatException, IOException {
int n = Integer.parseInt(br.readLine());
t= br.readLine().split(" ");
dfs();
if(i<t.length)flag=0;
if(flag==1)out.print(s);
else out.print("Error occurred");
out.flush();
}
public static void dfs() {
if(flag==0) {
return;
}
if(i<t.length) {
String str = t[i++];
s.append(str);
if(str.equals("pair")) {
s.append("<");
dfs();
s.append(",");
dfs();
s.append(">");
}
}else {
flag = 0;
}
}
}
活动打卡代码
AcWing 3768. 字符串删减（每日一题）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String agrs[]) throws NumberFormatException, IOException {
int n = Integer.parseInt(br.readLine());
String s = br.readLine();
int ant=0;int ans=0;
for(int i=0;i<s.length();i++) {
String s1 = s.substring(i,i+1);
if(s1.equals("x"))ant++;
else ant=0;
if(ant>=3)ans++;
}
System.out.println(ans);
}
//直接暴力循环~O(n)
}
活动打卡代码
AcWing 113. 特殊排序（算法提高课）
class Solution extends Relation {
static void swap(int[] a, int x, int y){
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
public int[] specialSort(int N) {
int[] res = new int[N];
res[0] = 1;
int len = 1;
for (int i = 2; i <= N; i ++){
int l = 0, r = len - 1;
while (l < r){
int mid = l + r + 1 >> 1;
if (compare(res[mid], i)) l = mid;
else r = mid - 1;
}
res[len ++] = i;
for (int j = len - 2; j > r; j --) swap(res, j, j + 1);
if (compare(i, res[r])) swap(res, r, r + 1);
}
return res;
}
}
活动打卡代码
AcWing 1227. 分巧克力（蓝桥杯辅导课）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int)1e5+10;
static int a [][] = new int [N][2];
static int n,k;
public static void main(String args[]) throws NumberFormatException, 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(" ");
a[i][0]=Integer.parseInt(s[0]);
a[i][1]=Integer.parseInt(s[1]);
}
int l=1,r=(int)1e5;
while(l<r) {
int mid = l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
System.out.println(r);
}
public static boolean check(int mid) {
int res=0;
for(int i=0;i<n;i++) {
res+=(a[i][0]/mid)*(a[i][1]/mid);
if(res>=k)return true;
}
return false;
}
}
