import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static int N = 1010, n;
static char[][] g = new char[N][N];
//每个点只会遍历一次，时间复杂度为O(N * N)
static int bfs() {
int cnt = 0;
boolean[][] st = new boolean[N][N];
Queue<PII> queue = new LinkedList<>();
for (int i = 1; i <= n; i ++) //遍历每行
for (int j = 0; j < n; j ++) //遍历每列
if (g[i][j] == '#' && !st[i][j]) { //加入该岛屿
boolean success = false;
queue.add(new PII(i, j));
st[i][j] = true;
while (!queue.isEmpty()) {
PII p = queue.poll();
int x = p.x, y = p.y;
for (int k = 0; k < 4; k ++) {
int a = x + dx[k], b = y + dy[k];
if (!st[a][b] && g[a][b] == '#') { //题目要求边缘必须是’.‘，所以不会有越界问题
queue.add(new PII(a, b));
st[a][b] = true; //表示该点已经遍历过
if (g[a - 1][b] == '#' && g[a + 1][b] == '#' && g[a][b - 1] == '#' && g[a][b + 1] == '#') success = true;
}
}
}
if (!success) cnt ++; //如果该岛屿存在不会被淹没的点则结果加一
}
return cnt;
}
public static void main(String[] args) throws IOException {
n = Integer.parseInt(in.readLine());
for (int i = 1; i <= n; i ++) g[i] = in.readLine().toCharArray();
out.println(bfs());
out.flush();
}
}
class PII {
int x, y;
PII(int a, int b) {
x = a;
y = b;
}
}
活动打卡代码
AcWing 1233. 全球变暖（蓝桥杯辅导课）
活动打卡代码
AcWing 3768. 字符串删减（每日一题）
import java.util.*;
public class Main{
static char s[] = new char[105];
public static void main(String[] args)
{
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
String str=sc.next();
s=str.toCharArray();
int ans=0;
int res=0;
for(int i=0;i<n;i++)
{
if(s[i]=='x')
{
res++;
if(res==3)
{
ans++;
res--;
}
}
else
{
res=0;
}
}
System.out.println(ans);
}
}
活动打卡代码
AcWing 836. 合并集合（算法基础课）
import java.io.*;
public class Main{
static int N = 100010;
static int[] p = new int[N];
public static int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args)throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
String str[] = bf.readLine().split(" ");
int n=Integer.parseInt(str[0]);
int m=Integer.parseInt(str[1]);
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=1;i<=m;i++)
{
String cur[] =bf.readLine().split(" ");
if(cur[0].equals("M"))
{
int a=Integer.parseInt(cur[1]);
int b=Integer.parseInt(cur[2]);
if(find(a)!=find(b))
p[find(b)]=find(a);
}
else
{
int a=Integer.parseInt(cur[1]);
int b=Integer.parseInt(cur[2]);
if(find(a)==find(b))
{
wt.println("Yes");
}
else
{
wt.println("No");
}
}
}
wt.flush();
}
}
活动打卡代码
AcWing 1249. 亲戚（每日一题）
**import java.io.*;
public class Main{
static int N = 20010;
static int[] p = new int[N];
public static int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args)throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
String[] s1 = bf.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
for (int i = 1; i <= n; i ++) p[i] = i;
while (m -- > 0){
String[] s2 = bf.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
if (find(a) != find(b)) p[find(a)] = find(b);
}
int q = Integer.parseInt(bf.readLine());
while (q -- > 0){
String[] s3 = bf.readLine().split(" ");
int a = Integer.parseInt(s3[0]);
int b = Integer.parseInt(s3[1]);
if (find(a) == find(b)) wt.println("Yes");
else wt.println("No");
}
wt.flush();
}
}**
活动打卡代码
AcWing 2. 01背包问题（算法基础课）
import java.util.*;
public class Main {
static int [] f=new int[1010];
public static void main(String args[])
{
Scanner sc= new Scanner(System.in);
int n=sc.nextInt(),V=sc.nextInt();
for(int i=0;i<n;i++)
{
int v=sc.nextInt(),w=sc.nextInt();
for(int j=V;j>=v;j--)
{
f[j]=Math.max(f[j],f[j-v]+w);
}
}
System.out.println(f[V]);
}
}
import java.util.*;
public class Main{
static int N;
static int[] a=new int[100005];
static int[] b=new int[100005];
public static void main(String[] args)
{
Scanner sc= new Scanner(System.in);
int N=sc.nextInt();
for(int i=0;i<N;i++)
{
a[i]=sc.nextInt();
}
int res=0;
for(int i=0,j=0;i<N;i++)
{
b[a[i]]++;
while(j<i&&b[a[i]]>1)
{
b[a[j]]--;
j++;
}
res=Math.max(res,i-j+1);
}
System.out.printf("%d",res);
}
}
活动打卡代码
AcWing 1460. 我在哪？（每日一题）
#include <iostream>
#include <unordered_set>
using namespace std;
int n;
string s;
int main()
{
cin >> n >> s;
for (int i = 1; i <= n; i++)
{
unordered_set<string> st;
bool flag = true;
for (int j = 0; j + i <= n; j++)
{
string t = s.substr(j, i);
if (st.count(t) != 0)
{
flag = false;
break;
}
st.insert(t);
}
if (flag == true)
{
cout << i << endl;
break;
}
}
return 0;
}
