# 111北二區桃竹苗資訊學科能力複賽 Java Solution Code
[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)
## J242 111北二1a.自然數的平方根
解法:窮舉所有開方是否整除，複雜度為$O(\sqrt N)$。
code:
```java=
/*
* Author: rickytsung
* Date: 2023/2/2
* Problem: ZJ
*/
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long ret,cnt;
public static int reti,rd,n,m,ans;
public static boolean neg,b1,b2,b3;
public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=200005;
public static Useful us=new Useful(mod);
public static int[] A=new int[ma];
public static int[] B=new int[ma];
public static long[] Al=new long[ma];
public static long[] Bl=new long[ma];
public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
public static void main(String[] args) throws Exception{
long n=readint();
final long max=(long)Math.pow(10,5);
long a=1,b=n;
for(long i=1;i<=max;i++) {
if(n%(i*i)==0) {
a=i;
b=n/(i*i);
}
}
if(a!=1) {
out(a+" ");
}
if(b!=1) {
out("sqrt("+b+")");
}
if(a==1&&b==1)out(1);
outn();
}
/*
*/
public static int readint() throws Exception{
reti=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
reti*=10;
reti+=(rd&15);
rd=br.read();
}
if(neg)reti*=-1;
return reti;
}
public static long readlong() throws Exception{
ret=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
}
/*
*/
/*
*/
```
## J243 111北二2a.資料分組問題
解法:窮舉所有距離，找到最小重複距離，接著對此距離以下的做$dsu$，時間複雜度為$O(N^2\cdot(D+logN))$。
```java=
/*
* Author: rickytsung
* Date: 2023/2/2
* Problem: ZJ
*/
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long ret,cnt;
public static int reti,rd,n,m,ans;
public static boolean neg,b1,b2,b3;
public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=200005;
public static Useful us=new Useful(mod);
public static int[] A=new int[ma];
public static int[] B=new int[ma];
public static long[] Al=new long[ma];
public static long[] Bl=new long[ma];
public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int d=readint();
final int n=readint();
long[][] xy=new long[n][d];
for(int i=0;i<n;i++) {
for(int j=0;j<d;j++) {
xy[i][j]=readint();
}
}
HashSet<Long> hs=new HashSet<>();
HashSet<Integer> s=new HashSet<>();
long cnt=0,min=(long)Math.pow(10, 18),ans=0;
for(int i=0;i<n;i++) {
A[i]=i;
for(int j=i+1;j<n;j++) {
cnt=0;
for(int k=0;k<d;k++) {
cnt+=Math.abs(xy[i][k]-xy[j][k]);
}
if(cnt<min) {
if(hs.contains(cnt)) {
min=cnt;
}
else {
hs.add(cnt);
}
}
}
}
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
cnt=0;
for(int k=0;k<d;k++) {
cnt+=Math.abs(xy[i][k]-xy[j][k]);
}
if(cnt<min) {
join(i,j);
}
}
}
for(int i=0;i<n;i++) {
s.add(find(i));
}
outn(s.size());
}
public static void join(int x,int y) {
if(find(x)!=find(y));
A[find(x)]=A[(find(y))];
return;
}
public static int find(int x) {
if(A[x]==x)return x;
return A[x]=find(A[x]);
}
/*
*/
public static int readint() throws Exception{
reti=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
reti*=10;
reti+=(rd&15);
rd=br.read();
}
if(neg)reti*=-1;
return reti;
}
public static long readlong() throws Exception{
ret=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
}
/*
*/
/*
*/
```
## J244. 111北二3a.兌獎問題
解法:照題目實作就好。
```java=
/*
* Author: rickytsung
* Date: 2023/2/2
* Problem: ZJ
*/
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long ret,cnt;
public static int reti,rd,n,m,ans;
public static boolean neg,b1,b2,b3;
public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=200005;
public static Useful us=new Useful(mod);
public static int[] A=new int[ma];
public static int[] B=new int[ma];
public static long[] Al=new long[ma];
public static long[] Bl=new long[ma];
public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
public static void main(String[] args) throws Exception{
String[] inp=br.readLine().split(" ");
String[] lu=new String[3];
String in;
final int k=pint(inp[0]);
final int n=pint(inp[1]);
for(int i=0;i<3;i++) {
lu[i]=br.readLine().split(" ")[0];
}
long cnt=0,ans=0,max=0;
for(int i=0;i<n;i++) {
in=br.readLine().split(" ")[0];
max=0;
for(int j=0;j<3;j++) {
if(in.substring(0).equals(lu[j].substring(0))) {
ans=500000;
}
else if(in.substring(2).equals(lu[j].substring(2))) {
ans=10000;
}
else if(in.substring(4).equals(lu[j].substring(4))) {
ans=1000;
}
else if(in.substring(k-3).equals(lu[j].substring(k-3))) {
ans=300;
}
else {
ans=0;
}
max=Math.max(ans,max);
}
cnt+=max;
}
outn(cnt);
}
/*
*/
public static int readint() throws Exception{
reti=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
reti*=10;
reti+=(rd&15);
rd=br.read();
}
if(neg)reti*=-1;
return reti;
}
public static long readlong() throws Exception{
ret=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
}
/*
*/
/*
*/
```
## J245. 111北二4a.加密密文
解法:待補
```java=
```
## J246. 111北二5a.程式排程模擬
解法:用queue模擬，複雜度為$O(\sum T)$
```java=
/*
* Author: rickytsung
* Date: 2023/2/2
* Problem: ZJ
*/
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long ret,cnt;
public static int reti,rd,n,m,ans;
public static boolean neg,b1,b2,b3;
public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=200005;
public static Useful us=new Useful(mod);
public static int[] A=new int[ma];
public static int[] B=new int[ma];
public static long[] Al=new long[ma];
public static long[] Bl=new long[ma];
public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=readint();
final int k=readint();
final int x=readint();
int o=-1,ans=0,nxt=0;
for(int i=1;i<=n;i++) {
B[i]=readint();
A[i]=readint();
}
Queue<Integer> q=new LinkedList<>();
Pii[] s=new Pii[n];
for(int i=0;i<n;i++) {
s[i]=new Pii(i+1,B[i+1]);
}
Arrays.sort(s,new Comparator<Pii>() {
public int compare(Pii f,Pii s) {
if(f.y==s.y)return f.x-s.x;
return f.y-s.y;
}
});
while(A[x]!=0) {
if(q.isEmpty()) {
ans++;
}
else {
o=q.poll();
ans+=Math.min(A[o],k);
A[o]=Math.max(0,A[o]-k);
}
while(nxt<n&&s[nxt].y<ans) {
q.offer(s[nxt].x);
nxt++;
}
if(o!=-1&&A[o]>0) {
q.offer(o);
}
while(nxt<n&&s[nxt].y<=ans) {
q.offer(s[nxt].x);
nxt++;
}
}
outn(ans-B[x]);
}
/*
*/
public static int readint() throws Exception{
reti=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
reti*=10;
reti+=(rd&15);
rd=br.read();
}
if(neg)reti*=-1;
return reti;
}
public static long readlong() throws Exception{
ret=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
}
/*
*/
/*
*/
class Pii{
int x,y;
Pii(int a,int b){
x=a;
y=b;
}
@Override
public boolean equals(Object o) {
if (this==o) return true;
if (!(o instanceof Pii)) return false;
Pii key = (Pii) o;
return x==key.x&&y==key.y;
}
@Override
public int hashCode() {
long result=x;
result=31*result+y;
return (int)(result%998244353);
}
}
```
## J247. 111北二6a.不平衡配對數
解法:利用$BIT$維護前綴和，時間複雜度為$O(NlogC)$
```java=
/*
* Author: rickytsung
* Date: 2023/2/3
* Problem: ZJ
*/
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long ret,cnt;
public static int reti,rd,n,m,ans;
public static boolean neg,b1,b2,b3;
public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=200005;
public static Useful us=new Useful(mod);
public static int[] A=new int[ma];
public static int[] B=new int[ma];
public static long[] Al=new long[ma];
public static long[] Bl=new long[ma];
public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=readint();
final int k=readint();
int in;
long ans=0;
for(int i=1;i<=n;i++) {
in=readint();
ans+=query(ma-1)-query(in*k);
update(in);
}
outn(ans);
}
public static void update(int x) {
for(int i=x;i<ma;i+=(i&(-i))) {
A[i]++;
}
}
public static int query(int r) {
int ret=0;
for(int i=r;i>0;i-=(i&(-i))) {
ret+=A[i];
}
return ret;
}
/*
*/
public static int readint() throws Exception{
reti=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
reti*=10;
reti+=(rd&15);
rd=br.read();
}
if(neg)reti*=-1;
return reti;
}
public static long readlong() throws Exception{
ret=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
}
/*
*/
/*
*/
```
## J248. 111北二7a.驛站換馬、郵政系統
解法:待補
```java=
```
## J249.
解法:待補
```java=
```
## J250.
解法:待補
```java=
```
Sign in with Wallet
Connect another wallet