# AP325 補救計畫(I)
作者:欉恩祁
因為我跟竑誠在APCS被其他人給電爛了，所以決定來寫TCIRC的神奇題目來補救。
[>>Part II](https://hackmd.io/@r1cky/rJjSMrQ5Y)
---
## d001~d020
### d001 合成函數(1)
解法:遞迴
```Java=
import java.io.*;
public class d001 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static long ret,r;
public static boolean neg;
public static void main(String[] args) throws Exception{
System.out.println(orz());
}
public static long f() throws Exception{
return 2*orz()-1;
}
public static long g() throws Exception{
return orz()+2*orz()-3;
}
public static long orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='f') {
r=br.read();
return f();
}
else if(r=='g') {
r=br.read();
return g();
}
else if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d002 合成函數(2)
解法:遞迴
```Java=
import java.io.*;
public class d002 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static long ret,r;
public static boolean neg;
public static void main(String[] args) throws Exception{
System.out.println(orz());
}
public static long f() throws Exception{
return 2*orz()-3;
}
public static long g() throws Exception{
return 2*orz()+orz()-7;
}
public static long h() throws Exception{
return 3*orz()-2*orz()+orz();
}
public static long orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='f') {
r=br.read();
return f();
}
else if(r=='g') {
r=br.read();
return g();
}
else if(r=='h') {
r=br.read();
return h();
}
else if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d003 棍子中點切割
解法:遞迴(魔王題，切中點要開double不然會卡測資:/)
```Java=
import java.io.*;
import java.util.*;
public class d003 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static int[] cut=new int[200005];
public static void main(String[] args) throws Exception{
final int n=orz();
final int l=orz();
cut[0]=0;
for(int i=1;i<=n;i++) cut[i]=orz();
cut[n+1]=l;
System.out.println(rec(0,n+1));
}
public static long rec(int l,int r) {
if(l+1==r)return 0;
double mid=((double)cut[l]+cut[r])/2;
double d=1<<30;
int c=-1;
for(int i=l+1;i<r;i++) {
if(Math.abs(cut[i]-mid)<d) {
d=Math.abs(cut[i]-mid);
c=i;
}
}
return rec(l,c)+rec(c,r)+cut[r]-cut[l];
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d004 支點切割
解法:前綴和、數學
```Java
import java.io.*;
public class d004 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,k;
public static long rt=0;
public static int[] mp=new int[50005];
public static long[] ls=new long[50005];
public static long[] rs=new long[50005];
public static long[] lss=new long[50005];
public static long[] rss=new long[50005];
public static void main(String[] args) throws Exception{
final int n=orz();
k=orz();
for(int i=1;i<=n;i++)mp[i]=orz();
ls[0]=lss[0]=0;
rs[n+1]=rss[n+1]=0;
for(int i=1;i<=n;i++)ls[i]=ls[i-1]+mp[i];
for(int i=1;i<=n;i++)lss[i]=lss[i-1]+ls[i];
for(int i=n;i>0;i--)rs[i]=rs[i+1]+mp[i];
for(int i=n;i>0;i--)rss[i]=rss[i+1]+rs[i];
cut(1,n,0);
System.out.println(rt);
}
public static void cut(int l,int r,int c) {
if(c==k||l+1>=r)return;
long min=1L<<60,t;
int p=-1;
for(int i=l+1;i<r;i++) {
t=Math.abs(lss[i-1]-lss[l-1]-ls[l-1]*(i-l)-rss[i+1]+rss[r+1]+rs[r+1]*(r-i));
if(t<min) {
min=t;
p=i;
}
}
rt+=mp[p];
cut(l,p-1,c+1);
cut(p+1,r,c+1);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d005 二維黑白影像編碼
解法:遞迴
```Java=
import java.io.*;
public class d005 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,p=0;
public static long rt=0;
public static String in;
public static void main(String[] args) throws Exception{
in=br.readLine();
int l=orz();
switch(in.charAt(p)) {
case '0':
break;
case '1':
rt+=l*l;
break;
case '2':
rec(l/2);
break;
}
System.out.println(rt);
}
public static void rec(int l) {
for(int i=0;i<4;i++) {
p++;
switch(in.charAt(p)) {
case '0':
break;
case '1':
rt+=l*l;
break;
case '2':
rec(l/2);
break;
}
}
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d006 子集合乘積
解法:暴力窮舉
```Java=
mport java.io.*;
public class d006 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,t,p=10009;
public static int[] in=new int[25];
public static long rt=0;
public static void main(String[] args) throws Exception{
t=orz();
for(int i=0;i<t;i++)in[i]=orz();
force(0,1);
System.out.println(rt-1);
}
public static void force(int id,long x) {
if(id==t) {
if(x==1)rt++;
return;
}
force(id+1,(x*in[id])%p);
force(id+1,x);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d007 子集合的和
解法:暴力窮舉
```Java=
import java.io.*;
public class d007 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,t,p;
public static int[] in=new int[25];
public static long max=0;
public static void main(String[] args) throws Exception{
t=orz();
p=orz();
for(int i=0;i<t;i++)in[i]=orz();
force(0,0);
System.out.println(max);
}
public static void force(int id,long x) {
if(id==t) {
if(x<p&&x>max) {
max=x;
}
return;
}
force(id+1,x+in[id]);
force(id+1,x);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d008 最多得分的皇后
解法:遞迴、undo
```Java=
import java.util.*;
import java.io.*;
public class d008 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int n;
public static int[][] mp=new int[15][15];
public static int[][] cs=new int[15][15];//current state
public static int mux=-(1<<30);//-inf
public static void main(String[] args) throws Exception{
String[] in=br.readLine().split(" ");
n=Integer.parseInt(in[0]);
for(int i=0;i<n;i++) {
in=br.readLine().split(" ");
for(int j=0;j<n;j++) {
mp[i][j]=Integer.parseInt(in[j]);
}
}
fill(0,0);
System.out.println(mux);
}
public static void fill(int x,int c) {
if(x==n) {
mux=Math.max(mux,c);
return;
}
fill(x+1,c);
for(int y=0;y<n;y++) {
if(cs[x][y]==0) {
for(int i=y-1;i>=0;i--) {
cs[x][i]++;
}
for(int i=y+1;i<n;i++) {
cs[x][i]++;
}
for(int i=x-1;i>=0;i--) {
cs[i][y]++;
}
for(int i=x+1;i<n;i++) {
cs[i][y]++;
}
for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--) {
cs[i][j]++;
}
for(int i=x+1,j=y+1;i<n&&j<n;i++,j++) {
cs[i][j]++;
}
for(int i=x-1,j=y+1;i>=0&&j<n;i--,j++) {
cs[i][j]++;
}
for(int i=x+1,j=y-1;i<n&&j>=0;i++,j--) {
cs[i][j]++;
}
cs[x][y]++;
fill(x+1,c+mp[x][y]);
for(int i=y-1;i>=0;i--) {
cs[x][i]--;
}
for(int i=y+1;i<n;i++) {
cs[x][i]--;
}
for(int i=x-1;i>=0;i--) {
cs[i][y]--;
}
for(int i=x+1;i<n;i++) {
cs[i][y]--;
}
for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--) {
cs[i][j]--;
}
for(int i=x+1,j=y+1;i<n&&j<n;i++,j++) {
cs[i][j]--;
}
for(int i=x-1,j=y+1;i>=0&&j<n;i--,j++) {
cs[i][j]--;
}
for(int i=x+1,j=y-1;i<n&&j>=0;i++,j--) {
cs[i][j]--;
}
cs[x][y]--;
}
}
}
}
```
---
### d009 刪除邊界
解法:遞迴、dp
```Java=
import java.util.*;
import java.io.*;
public class d009 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int r,ret;
public static int[][] mp=new int[15][15];
public static void main(String[] args) throws Exception{
final int n=orz();
final int m=orz();
for(int i=0;i<n;i++)for(int j=0;j<m;j++)mp[i][j]=orz();
System.out.println(dp(0,n-1,0,m-1));
}
public static int dp(int lx,int rx,int ly,int ry) {
if(lx==rx||ly==ry)return 0;
int m=Math.min(dp(lx+1,rx,ly,ry)+cut(lx,lx,ly,ry),dp(lx,rx-1,ly,ry)+cut(rx,rx,ly,ry));
m=Math.min(dp(lx,rx,ly+1,ry)+cut(lx,rx,ly,ly),m);
m=Math.min(dp(lx,rx,ly,ry-1)+cut(lx,rx,ry,ry),m);
return m;
}
public static int cut(int lx,int rx,int ly,int ry) {
int cnt=0,c=0;
for(int i=lx;i<=rx;i++) {
for(int j=ly;j<=ry;j++) {
if(mp[i][j]==0) {
cnt++;
}
else {
c++;
}
}
}
return Math.min(cnt,c);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d010 不同的數—排序
解法:排序、set
```Java=
import java.io.*;
import java.util.*;
public class d010 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r;
public static boolean neg;
public static void main(String[] args) throws Exception{
final int t=orz();
HashSet<Integer> s=new HashSet<>();
PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer f,Integer s) {
if(f>s)return 1;
if(f==s)return 0;
return -1;
}
});
for(int i=0;i<t;i++)s.add(orz());
bw.write(s.size()+"\n");
for(int i:s)pq.offer(i);
while(!pq.isEmpty())bw.write(pq.poll()+" ");
bw.flush();
}
public static int orz() throws Exception{
ret=0;
neg=false;
r=br.read();
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d011 離散化 – sort
解法:排序、map
```Java=
import java.io.*;
import java.util.*;
public class d011 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r,in;
public static boolean neg;
public static void main(String[] args) throws Exception{
final int t=orz();
HashSet<Integer> s=new HashSet<>();
Queue<Integer> q=new LinkedList<>();
for(int i=0;i<t;i++) {
in=orz();
s.add(in);
q.offer(in);
}
ArrayList<Integer> al=new ArrayList<>(s);
Collections.sort(al);
HashMap<Integer,Integer> mp=new HashMap<>();
for(int i=0;i<al.size();i++) {
mp.put(al.get(i),i);
}
while(!q.isEmpty())bw.write(mp.get(q.poll())+" ");
bw.flush();
}
public static int orz() throws Exception{
ret=0;
neg=false;
r=br.read();
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d012 快速冪
解法:快速冪
```Java=
import java.io.*;
public class d012 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,x,y,p;
public static boolean neg;
public static void main(String[] args) throws Exception{
x=orz();
y=orz();
p=orz();
System.out.println(f(y));
}
public static long f(int y) throws Exception{
if(y==0)return 1;
if(y==1)return x;
long a;
a=f(y/2);
if(y%2==0) {
return (a*a)%p;
}
return (((a*a)%p)*x)%p;
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d013 快速冪--200 位整數
解法:快速冪、數學
```Java=
import java.io.*;
public class d013 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static long ret;
public static int r,x,y,p;
public static String[] in;
public static void main(String[] args) throws Exception{
in=br.readLine().split(" ");
y=Integer.parseInt(in[1]);
p=Integer.parseInt(in[2]);
x=premod();
System.out.println(f((int)y));
}
public static long f(int y) throws Exception{
if(y==0)return 1;
if(y==1)return x;
long a;
a=f(y/2);
if(y%2==0) {
return a*a%p;
}
return ((a*a)%p*x)%p;
}
public static int premod() throws Exception{
int pt=-1;
ret=0;
while(pt<in[0].length()-1) {
pt++;
ret*=10;
r=in[0].charAt(pt);
ret+=(r&15);
ret%=p;
}
return (int)ret;
}
}
```
---
### d014 快速計算費式數列第 n 項
解法:快速冪、矩陣
```Java=
import java.io.*;
public class d014 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r,n;
public static final int p=(int)Math.pow(10,9)+7;
public static void main(String[] args) throws Exception{
n=orz();
while(n!=-1) {
bw.write((fib(n-1).t[0][0])+"\n");
n=orz();
}
bw.flush();
}
public static matrix fib(int y) throws Exception{
if(y==-1)return new matrix(0,0,0,0);
if(y==0||y==1)return new matrix(1,1,1,0);
matrix a=fib(y/2);
if(y%2==0) {
return x(a,a);
}
return x(x(a,a),new matrix(1,1,1,0));
}
public static matrix x(matrix u,matrix v) throws Exception{
long a=u.t[0][0]*v.t[0][0]+u.t[0][1]*v.t[1][0];
long b=u.t[0][0]*v.t[0][1]+u.t[0][1]*v.t[1][1];
long c=u.t[1][0]*v.t[0][0]+u.t[1][1]*v.t[1][0];
long d=u.t[1][0]*v.t[0][1]+u.t[1][1]*v.t[1][1];
return new matrix(a%p,b%p,c%p,d%p);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
if(r=='-')return -1;
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class matrix{
long[][] t=new long[2][2];
matrix(long a,long b,long c,long d) {
t[0][0]=a;
t[0][1]=b;
t[1][0]=c;
t[1][1]=d;
}
}
```
---
### d015 Two-Number problem
解法:排序
```Java=
import java.io.*;
import java.util.*;
public class d015 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
String[] in=br.readLine().split(" ");
final int m=Integer.parseInt(in[0]);
final int n=Integer.parseInt(in[1]);
final int k=Integer.parseInt(in[2]);
int[] a=new int[m];
int[] b=new int[n];
int begin=n-1,ans=0;
in=br.readLine().split(" ");
for(int i=0;i<m;i++)a[i]=Integer.parseInt(in[i]);
in=br.readLine().split(" ");
for(int i=0;i<n;i++)b[i]=Integer.parseInt(in[i]);
Arrays.sort(a);
Arrays.sort(b);
for(int i=0;i<m;i++) {
for(int j=begin;j>=0;j--,begin--) {
if(a[i]+b[j]<k)break;
if(a[i]+b[j]==k)ans++;
}
}
System.out.println(ans);
}
}
```
---
### d016 互補團隊
解法:位元運算
```Java=
import java.io.*;
import java.util.*;
public class d016 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static long[] cp;
public static void main(String[] args) throws Exception{
long ans=0;
String[] in=br.readLine().split(" ");
int m=Integer.parseInt(in[0]);
int n=Integer.parseInt(in[1]);
cp=new long[n];
getline(n,m);
Arrays.parallelSort(cp);
final long tg=(1L<<(m))-1;
long ck;
int ch=n-1;
for(int i=0;i<n;i++) {
for(int j=ch;j>i;j--) {
ck=cp[i]+cp[j];
if(ck>tg)ch--;
else if(ck<tg)break;
else {
ans++;
}
}
}
System.out.println(ans);
}
public static void getline(int n,int m) throws Exception {
long ret=0;
long a;
for(int i=0;i<n;i++) {
a=br.read();
while(a>64&&a<91) {
ret|=(1L<<(a-65));
a=br.read();
}
cp[i]=ret;
ret=0;
}
}
}
```
### d017 模逆元
解法:費馬小定理、快速冪
```Java=
import java.io.*;
public class d017 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r,p,x;
public static void main(String[] args) throws Exception{
final int n=orz();
p=orz();
for(int i=0;i<n;i++) {
x=orz();
bw.write(f(p-2)+" ");
}
bw.flush();
}
public static long f(int y) throws Exception{
if(y==0)return 1;
if(y==1)return x;
long a;
a=f(y/2);
if(y%2==0) {
return a*a%p;
}
return ((a*a)%p*x)%p;
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d018 子集合乘積(折半枚舉)
解法:折半枚舉、模逆元
```Java=
import java.io.*;
import java.util.*;
public class d018 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,p;
public static long ans=0;
public static void main(String[] args) throws Exception{
final int n=orz();
int begin=-1,q=0;
long in;
Integer query;
long[] a=new long[(1<<(n/2))];
long[] b=new long[1<<(n-n/2)];
p=orz();
a[0]=b[0]=1;
for(int i=0;i<n/2;i++) {
in=orz();
for(int j=0;j<(1<<i);j++) {
a[j+(1<<i)]=(a[j]*in)%p;
}
}
a[0]=1<<30;
Arrays.sort(a);
HashMap<Integer,Integer> mp=new HashMap<>();
for(int i=0;i<a.length;i++) {
if(a[i]==1)ans++;
if(begin!=a[i]) {
mp.put(begin,q);
q=0;
begin=(int)a[i];
}
q++;
q%=p;
}
for(int i=0;i<(n-n/2);i++) {
in=orz();
for(int j=0;j<(1<<i);j++)b[j+(1<<i)]=(b[j]*in)%p;
}
for(int i=1;i<b.length;i++) {
if(b[i]==1) {
ans++;
}
query=mp.get(f((int)b[i],p-2));
if(query!=null) {
ans+=query;
ans%=p;
}
}
System.out.println(ans);
}
public static int f(int x,int y) throws Exception{
if(y==0)return 1;
if(y==1)return x;
long a;
a=f(x,y/2);
if(y%2==0) {
return (int)(a*a%p);
}
return (int)(((a*a)%p*x)%p);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d019 子集合的和(折半枚舉)
解法:折半枚舉、排序+二分搜
```Java=
import java.io.*;
import java.util.*;
public class d019 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static long ret,r;
public static long ans=0;
public static void main(String[] args) throws Exception{
final int n=(int)orz();
long p=orz();
long in;
int l,r,mid=0;
long[] a=new long[(1<<(n/2))];
long[] b=new long[(1<<(n-n/2))];
a[0]=b[0]=0;
for(int i=0;i<n/2;i++) {
in=orz();
for(int j=0;j<(1<<i);j++) {
a[j+(1<<i)]=a[j]+in;
}
}
a[0]=0;
Arrays.sort(a);
for(int i=0;i<(n-n/2);i++) {
in=orz();
for(int j=0;j<(1<<i);j++) {
b[j+(1<<i)]=b[j]+in;
}
}
for(int i=0;i<b.length;i++) {
l=0;
r=a.length-1;
while(l!=r) {
mid=(l+r+1)/2;
if(a[mid]+b[i]>p) {
r=mid-1;
}
else {
l=mid;
}
}
if(a[l]+b[i]>p)continue;
if(a[l]+b[i]>ans)ans=a[l]+b[i];
}
System.out.println(ans);
}
public static long orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d020 最接近的區間和
解法:前綴和、二分搜
```Java=
import java.io.*;
import java.util.*;
public class d020 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static boolean neg;
public static long sum=0,ans=0;
public static void main(String[] args) throws Exception{
final int n=orz();
final int k=orz();
int bis;
ArrayList<Long> al=new ArrayList<>();
al.add(0L);
for(int i=0;i<n;i++) {
sum+=orz();
bis=Collections.binarySearch(al,sum-k);
if(bis<0)bis=bis*-1-1;
if(bis<al.size()) {
if(sum-al.get(bis)>ans)ans=sum-al.get(bis);
}
bis=Collections.binarySearch(al,sum);
if(bis<0)bis=bis*-1-1;
al.add(bis,sum);
}
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
## d021~d040
### d021 unsolved
解法:這題會卡時間限制，所以下面的扣過不了，有主意可題
```Java=
import java.io.*;
import java.util.*;
public class d021 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static boolean neg;
public static int sum=0,ans=0;
public static int[][] presum;
public static void main(String[] args) throws Exception{
orz();
final int k=ret;
orz();
final int m=ret;
orz();
final int n=ret;
int bis;
presum=new int[m+5][n+5];
for(int a=1;a<=m;a++) {
for(int b=0;b<n;b++) {
orz();
presum[a][b]=presum[a-1][b]+ret;
}
}
ArrayList<Integer> al=new ArrayList<>();
for(int x=1;x<=m;x++) {
for(int y=x;y<=m;y++) {
sum=0;
al.clear();
al.add(0);
for(int i=0;i<n;i++) {
sum+=(presum[y][i]-presum[x-1][i]);
bis=Collections.binarySearch(al,sum-k);
if(bis<0)bis=bis*-1-1;
if(bis<al.size()) {
if(sum-al.get(bis)>ans)ans=sum-al.get(bis);
}
bis=Collections.binarySearch(al,sum);
if(bis<0)bis=bis*-1-1;
al.add(bis,sum);
}
}
}
System.out.println(ans);
}
public static void orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
}
}
```
---
### d022 無理數的快速冪
解法:快速冪、數學
```Java=
import java.io.*;
public class d022 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,x,y,n;
public static final int p=(int)Math.pow(10,9)+9;
public static boolean neg;
public static void main(String[] args) throws Exception{
x=orz();
y=orz();
n=orz();
pair ans=f(n);
System.out.println(ans.s+" "+ans.t);
}
public static pair f(int n) throws Exception{
if(n==0)return new pair(0,0);
if(n==1)return new pair(x,y);
pair a;
a=f(n/2);
if(n%2==0) {
return multiply(a,a);
}
return multiply(multiply(a,a),new pair(x,y));
}
public static pair multiply(pair a,pair b) {
long ssum=(((a.t*b.t)*2)+a.s*b.s)%p;
long tsum=(a.t*b.s+a.s*b.t)%p;
return new pair(ssum,tsum);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pair{
long s,t;
pair(long A,long B){
s=A;
t=B;
}
}
```
---
### d023 水槽
解法:遞迴
```Java=
import java.util.*;
import java.io.*;
public class d023 implements Runnable{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r,idx,in;
public static long retl,w;
public static int[] wa=new int[100005];
public static partri[] H;
public static void main(String[] args) throws Exception{
new Thread(null,new d023(),"",1<<26).start();
}
public void run(){
String[] in2 = null;
try {
in2 = br.readLine().split(" ");
} catch (IOException e1) {
}
final int n=Integer.parseInt(in2[0]);
final int s=Integer.parseInt(in2[1]);
w=Long.parseLong(in2[2]);
in=s;
try {
in2=br.readLine().split(" ");
} catch (IOException e1) {
}
H=new partri[n];
for(int i=0;i<n;i++)H[i]=new partri(i,Integer.parseInt(in2[i]));
Arrays.sort(H,new Comparator<partri>() {
public int compare(partri f,partri s) {
return (int) (f.h-s.h);
}
});
idx=n;
fill(0,n-1);
for(int i=0;i<n-1;i++) {
try {
bw.write(wa[i]+" ");
} catch (IOException e) {
}
}
try {
bw.flush();
} catch (IOException e) {
}
}
static void fill(long l,long r) {
if(l==r-1) {
wa[(int) l]=(int) w;
w=0;
return;
}
else {
idx--;
while(idx>0&&H[idx].x<l||H[idx].x>r) {
idx--;
}
if(w>=(r-l)*H[idx].h) {
for(int i=(int) l;i<r;i++) {
wa[i]=(int) (w/(r-l));
}
w=0;
return;
}
else if(H[idx].x>in) {
if(w>=(H[idx].x-l)*H[idx].h) {
for(int i=(int) l;i<H[idx].x;i++) {
wa[i]=(int) H[idx].h;
}
w-=(H[idx].x-l)*H[idx].h;
fill(H[idx].x,r);
}
else {
fill(l,H[idx].x);
}
}
else {
if(w>=(r-H[idx].x)*H[idx].h) {
for(int i=(int) H[idx].x;i<r;i++) {
wa[i]=(int) H[idx].h;
}
w-=(r-H[idx].x)*H[idx].h;
fill(l,H[idx].x);
}
else {
fill(H[idx].x,r);
}
}
}
}
}
class partri{
long x,h;
partri(int a,int b){
x=a;
h=b;
}
}
```
---
### d024 圓環出口
解法:前綴和、二分搜
```Java=
import java.util.*;
import java.io.*;
public class d024 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
int r = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
//build sum
int[] sum = new int[2*r];
int[] s = new int[2*r];
int[] mis = new int[m];
input=br.readLine().split(" ");
for(int i=0;i<r;i++) {
s[i]=Integer.parseInt(input[i]);
s[i+r]=Integer.parseInt(input[i]);
}
input=br.readLine().split(" ");
for(int i=0;i<m;i++) {
mis[i]=Integer.parseInt(input[i]);
}
sum[0]=s[0];
for(int i=1;i<2*r;i++) {
sum[i]=sum[i-1]+s[i];
}
int cal,bis;
int pos=0;
for(int i=0;i<m;i++) {
if(pos==0)cal=0;
else cal=sum[pos-1];
cal+=mis[i];
bis=Arrays.binarySearch(sum,cal);
if(bis<0)bis=-bis-1;
pos=bis+1;
pos%=r;
}
System.out.println(pos);
}
}
```
---
### d025 樹的高度與根
解法:Bottom up
```Java=
import java.io.*;
public class d025 implements Runnable{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int r,ret;
static int[] h=new int[100005];
static int[] fa=new int[100005];
static boolean[] lf=new boolean[100005];
public static void main(String[] args) throws Exception {
new Thread(null, new d025(), "", 1<<26).start();
}
public void run() {
final int n=orz();
int num;
for(int i=1;i<=n;i++) {
num=orz();
if(num==0)lf[i]=true;
for(int j=0;j<num;j++) {
fa[orz()]=i;
}
}
for(int i=1;i<=n;i++) {
if(lf[i]) {
bottom_up(fa[i],1);
}
}
long ans=0,root=0;
for(int i=1;i<=n;i++) {
if(fa[i]==0)root=i;
ans+=h[i];
}
System.out.println(root);
System.out.println(ans);
}
static void bottom_up(int x,int ht) {
if(x==0)return;
if(h[x]!=0) {
if(ht>h[x]) {
h[x]=ht;
}
else {
return;
}
}
else {
h[x]=ht;
}
bottom_up(fa[x],ht+1);
}
static int orz() {
try {
ret=0;
r=br.read();
while (r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
catch(Exception e) {
return 0;
}
}
}
```
---
### d026 括弧配對
解法:牛排
```Java=
import java.io.*;
import java.util.*;
public class d026 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static boolean neg;
public static void main(String[] args) throws Exception{
String in;
Stack<Integer> st=new Stack<>();
all:
while(true) {
int r;
in=br.readLine();
if(in==null||in.length()==0)break;
st.clear();
for(int i=0;i<in.length();i++) {
r=in.charAt(i);
if(r=='(') {
st.push(0);
}
if(r=='{') {
st.push(1);
}
if(r=='[') {
st.push(2);
}
if(r==')') {
if(st.isEmpty()||st.pop()!=0) {
System.out.println("no");
continue all;
}
}
if(r=='}') {
if(st.isEmpty()||st.pop()!=1) {
System.out.println("no");
continue all;
}
}
if(r==']') {
if(st.isEmpty()||st.pop()!=2) {
System.out.println("no");
continue all;
}
}
}
if(st.isEmpty()) {
System.out.println("yes");
}
else {
System.out.println("no");
}
}
}
}
```
---
### d027 加減乘除
解法:Python_eval(這是別人的扣)
```Python=
import sys
for s in sys.stdin:
s=s.replace('/',"//")
print(int(eval(s)))
```
---
### d028 最接近的高人
解法:二分搜、遞增序列維護
```Java=
import java.io.*;
import java.util.*;
public class d028 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int r,ret;
public static void main(String[] args) throws Exception{
final int n=orz();
int l,r,mid,t;
long ans=0;
ArrayList<pii> al=new ArrayList<>();
al.add(new pii(-(1<<30),-1));
al.add(new pii((1<<30),-1));
for(int i=0;i<n;i++) {
t=orz();
l=0;
r=al.size()-1;
while(l!=r) {
mid=(l+r)/2;
if(al.get(mid).h>t) {
r=mid;
}
else {
l=mid+1;
}
}
ans+=(i-al.get(l).id);
al.add(l,new pii(t,i));
l--;
while(l>=0&&al.get(l).h<=t) {
al.remove(l);
l--;
}
}
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
if(r=='-') {
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pii{
int h,id;
pii(int a,int b){
h=a;
id=b;
}
}
```
---
### d029 帶著板凳排雞排的高人
解法:二分搜、遞增序列維護
```Java=
import java.io.*;
import java.util.*;
public class d029 {
public static int ret,r;
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception {
final int n=readint();
ArrayList<pair> v=new ArrayList<>();
int[] h=new int[n];
int l,r,m=0,t;
long rt=0;
for(int i=0;i<n;i++) {
h[i]=readint();
}
v.add(new pair(0,1<<30));
v.add(new pair(0,-(1<<30)));
for(int i=1;i<=n;i++) {
t=readint()+h[i-1];
l=0;
r=v.size()-1;
while(l!=r) {
m=(l+r)/2;
if(v.get(m).h>t) {
l=m+1;
}
else {
r=m;
}
}
rt+=i-(v.get(l-1).id+1);
for(int j=v.size()-2;j>-1;j--) {
if(v.get(j).h<=h[i-1]) {
v.remove(j);
}
else{
v.add(v.size()-1,new pair(i,h[i-1]));
break;
}
}
}
System.out.println(rt);
}
public static int readint() throws Exception {
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pair{
int id,h;
pair(int a,int b){
id=a;
h=b;
}
}
```
---
### d030 砍樹
解法:ArrayList
```Java=
import java.io.*;
import java.util.*;
public class d030 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,mx,ans=0;
public static int[] idx=new int[100005];
public static int[] h=new int[100005];
public static void main(String[] args) throws Exception{
final int n=orz();
final int l=orz();
ArrayList<tree> al=new ArrayList<>();
al.add(new tree(0,1<<30));
for(int i=0;i<n;i++)idx[i]=orz();
for(int i=0;i<n;i++)h[i]=orz();
for(int i=0;i<n;i++)al.add(new tree(idx[i],h[i]));
al.add(new tree(l,1<<30));
for(int i=0;i<al.size()-1;i++) {
if(i==0)continue;
if(al.get(i).x-al.get(i).h>=al.get(i-1).x) {
mx=Math.max(mx,al.get(i).h);
al.remove(i);
i-=2;
ans++;
}
else if(al.get(i).x+al.get(i).h<=al.get(i+1).x){
mx=Math.max(mx,al.get(i).h);
al.remove(i);
i-=2;
ans++;
}
}
System.out.println(ans);
System.out.println(mx);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class tree{
int x,h;
tree(int a,int b){
x=a;
h=b;
}
}
```
---
### d031 正整數序列之最接近的區間和
解法:Sliding Window
```Java=
import java.io.*;
import java.util.*;
public class d031 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,ans=0;
public static long max=0;
public static void main(String[] args) throws Exception{
long sum=0;
int l=0;
final int n=orz();
final int k=orz();
int[] a=new int[n];
for(int i=0;i<n;i++)a[i]=orz();
for(int i=0;i<n;i++) {
sum+=a[i];
while(sum>k) {
sum-=a[l++];
}
if(sum>max) {
max=sum;
ans=1;
}
else if(sum==max)ans++;
}
System.out.println(max);
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d032 固定長度區間的最大區段差
解法:ArrayList(串列)
```Java=
import java.io.*;
import java.util.*;
public class d032 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,rd,mx=0,l,r,m;
public static ArrayList<P> a=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=orz();
final int L=orz();
int[] in=new int[n];
for(int i=0;i<n;i++)in[i]=orz();
for(int i=0;i<L-1;i++) {
a.add(bis(in[i]),new P(i,in[i]));
}
for(int i=0,j=L-1;j<n;i++,j++) {
a.add(bis(in[j]),new P(j,in[j]));
while(a.get(0).idx<i)a.remove(0);
while(a.get(a.size()-1).idx<i)a.remove(a.size()-1);
mx=Math.max(a.get(a.size()-1).val-a.get(0).val,mx);
}
System.out.println(mx);
}
public static int bis(int x) {
l=0;
r=a.size();
while(l!=r) {
m=(l+r)/2;
if(a.get(m).val<=x) {
l=m+1;
}
else {
r=m;
}
}
return l;
}
public static int orz() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
class P{
int idx,val;
P(int a,int b){
idx=a;
val=b;
}
}
```
---
### d033 最多色彩帶
解法:雙指標
```Java=
import java.io.*;
import java.util.*;
public class d033 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,rd,mx=0,cc=0;
public static int[] col=new int[200005];
public static void main(String[] args) throws Exception{
final int n=orz();
final int L=orz();
int[] in=new int[n];
for(int i=0;i<n;i++)in[i]=orz();
for(int j=0;j<L-1;j++) {
if(col[in[j]]==0)cc++;
col[in[j]]++;
}
for(int i=0,j=L-1;j<n;i++,j++) {
if(col[in[j]]==0)cc++;
col[in[j]]++;
if(mx<cc)mx=cc;
col[in[i]]--;
if(col[in[i]]==0)cc--;
}
System.out.println(mx);
}
public static int orz() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
```
---
### d034 全彩彩帶
解法:雙指標
```Java=
import java.io.*;
import java.util.*;
public class d034 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,rd,idx=0,min;
public static int[] col=new int[200005];
public static void main(String[] args) throws Exception{
final int n=orz();
HashMap<Integer,Integer> mp=new HashMap<>();
int[] in=new int[n];
for(int i=0;i<n;i++) {
in[i]=orz();
if(mp.get(in[i])==null)mp.put(in[i],idx++);
}
int cc=0,l=0,r=-1,g;
while(cc<idx) {
g=mp.get(in[++r]);
if(col[g]==0)cc++;
col[g]++;
}
min=r-l+1;
for(;r<n;r++) {
col[mp.get(in[r])]++;
while(col[mp.get(in[l])]>1) {
col[mp.get(in[l])]--;
l++;
}
if(r-l+1<min)min=r-l+1;
}
System.out.println(min);
}
public static int orz() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
```
---
### d035 最長的相異色彩帶
解法:雙指標
```Java=
import java.io.*;
import java.util.*;
public class d035 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,rd,idx=0,mx=0;
public static int[] col=new int[200005];
public static int[] last=new int[200005];
public static void main(String[] args) throws Exception{
final int n=orz();
Arrays.fill(last,-1);
int l=0,read;
for(int i=0;i<n;i++) {
read=orz();
if(last[read]!=-1)l=Math.max(l,last[read]+1);
last[read]=i;
mx=Math.max(mx,i-l+1);
}
System.out.println(mx);
}
public static int orz() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
```
---
### d036 完美彩帶
解法:雙指標
```Java=
import java.io.*;
import java.util.*;
public class d036 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,rd,ans=0,idx=0;
public static int[] last=new int[200005];
public static void main(String[] args) throws Exception{
final int m=orz();
final int n=orz();
Arrays.fill(last,-1);
HashMap<Integer,Integer> mp=new HashMap<>();
int l=0,read;
for(int i=0;i<n;i++) {
read=orz();
if(mp.get(read)==null)mp.put(read,idx++);
read=mp.get(read);
if(last[read]!=-1)l=Math.max(l,last[read]+1);
last[read]=i;
if(i-l+1==m)ans++;
}
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
```
---
### d037 X差值範圍內的最大Y差值
解法:ArrayList、二分搜
```Java=
import java.io.*;
import java.util.*;
public class d037 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,rd,mx=0,l,r,m;
public static boolean neg;
public static ArrayList<P> a=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=orz();
final int L=orz();
int[] x=new int[n];
int[] y=new int[n];
P[] in=new P[n];
for(int i=0;i<n;i++)x[i]=orz();
for(int i=0;i<n;i++)y[i]=orz();
for(int i=0;i<n;i++) {
in[i]=new P(x[i],y[i]);
}
Arrays.sort(in,new Comparator<P>() {
public int compare(P f,P s) {
return f.idx-s.idx;
}
});
for(int i=0;i<n;i++) {
a.add(bis(in[i].val),in[i]);
while(a.get(0).idx<in[i].idx-L)a.remove(0);
while(a.get(a.size()-1).idx<in[i].idx-L)a.remove(a.size()-1);
mx=Math.max(a.get(a.size()-1).val-a.get(0).val,mx);
}
System.out.println(mx);
}
public static int bis(int x) {
l=0;
r=a.size();
while(l!=r) {
m=(l+r)/2;
if(a.get(m).val<=x) {
l=m+1;
}
else {
r=m;
}
}
return l;
}
public static int orz() throws Exception{
neg=false;
ret=0;
rd=br.read();
if(rd=='-') {
neg=true;
rd=br.read();
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
class P{
int idx,val;
P(int a,int b){
idx=a;
val=b;
}
}
```
---
### d038 unsolved
解法:
```Java=
```
---
## d041~d060
### d042 少林寺的代幣
解法:Greedy
```Java=
import java.io.*;
import java.util.*;
public class d042 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r,rr;
public static void main(String[] args) throws Exception{
final int t=orz();
for(int i=0;i<t;i++) {
rr=orz();
bw.write((rr/50+rr%50/10+rr%10/5+rr%5)+"\n");
}
bw.flush();
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d043 笑傲江湖之三戰
解法:Greedy
```Java=
import java.io.*;
import java.util.*;
public class d043 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,cnt=0;
public static void main(String[] args) throws Exception{
final int n=orz();
int[] m=new int[n];
int[] o=new int[n];
for(int i=0;i<n;i++)o[i]=orz();
for(int i=0;i<n;i++)m[i]=orz();
Arrays.sort(m);
Arrays.sort(o);
for(int i=0;i<n;i++) {
if(m[i]>o[cnt])cnt++;
}
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d044 十年磨一劍
解法:Greedy
```Java=
import java.io.*;
import java.util.*;
public class d044 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long cnt=0,presum=0;
public static void main(String[] args) throws Exception{
final int n=orz();
int[] a=new int[n];
for(int i=0;i<n;i++)a[i]=orz();
Arrays.sort(a);
for(int i=0;i<n;i++) {
presum+=a[i];
cnt+=presum;
}
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d045 幾場華山論劍
解法:Greedy
```Java=
import java.io.*;
import java.util.*;
public class d045 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,cnt,cr=-1;
public static void main(String[] args) throws Exception{
final int n=orz();
pair[] a=new pair[n];
for(int i=0;i<n;i++) {
a[i]=new pair(orz(),orz());
}
Arrays.sort(a,new Comparator<pair>() {
public int compare(pair f,pair s) {
return (f.r-s.r==0)?(f.l-s.l):(f.r-s.r);
}
});
for(int i=0;i<n;i++) {
if(cr<a[i].l) {
cnt++;
cr=a[i].r;
}
}
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pair{
int l,r;
pair(int x,int y){
l=x;
r=y;
}
}
```
---
### d046 嵩山磨劍坊的問題
解法:sort
```Java=
import java.io.*;
import java.util.*;
public class d046 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long t=0,sum=0;
public static void main(String[] args) throws Exception{
final int n=orz();
pair[] p=new pair[n];
for(int i=0;i<n;i++) p[i]=new pair(orz());
for(int i=0;i<n;i++) p[i].wei(orz());
Arrays.sort(p,new Comparator<pair>(){
public int compare(pair f,pair s) {
return f.t*s.w-f.w*s.t;
}
});
for(int i=0;i<n;i++) {
t+=p[i].t;
sum+=p[i].w*t;
}
System.out.println(sum);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pair{
int t,w;
pair(int x){
t=x;
}
void wei(int y){
w=y;
}
}
```
---
### d047 少林寺的自動寄物櫃
解法:sort(d046改)
```Java=
import java.io.*;
import java.util.*;
public class d047 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long t=0,sum=0;
public static void main(String[] args) throws Exception{
final int n=orz();
pair[] p=new pair[n];
for(int i=0;i<n;i++) p[i]=new pair(orz());
for(int i=0;i<n;i++) p[i].wei(orz());
Arrays.sort(p,new Comparator<pair>(){
public int compare(pair f,pair s) {
return f.t*s.w-f.w*s.t;
}
});
for(int i=0;i<n;i++) {
sum+=p[i].w*t;
t+=p[i].t;
}
System.out.println(sum);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pair{
int t,w;
pair(int x){
t=x;
}
void wei(int y){
w=y;
}
}
```
---
### d048 岳不群的併派問題
解法:博愛排隊(Priority-Queue)
```Java=
import java.io.*;
import java.util.*;
public class d048 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long sum=0,cost=0;
public static void main(String[] args) throws Exception{
final int n=orz();
long a,b;
PriorityQueue<Long> pq=new PriorityQueue<>(new Comparator<Long>(){
public int compare(Long a,Long b) {
if(a>b)return 1;
else if(a==b)return 0;
return -1;
}
});
for(int i=0;i<n;i++) {
a=orz();
sum+=a;
pq.offer(a);
}
while(pq.size()!=1) {
a=pq.poll();
b=pq.poll();
cost+=(a+b);
pq.offer(a+b);
}
System.out.println(sum);
System.out.println(cost);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d049 基地台
解法:二分搜
```Java=
import java.util.*;
import java.io.*;
public class d049 {
public static int[] data;
public static int k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
int n=Integer.parseInt(input[0]);
k=Integer.parseInt(input[1]);
input=br.readLine().split(" ");
data=new int[n];
for(int i=0;i<n;i++) data[i]=Integer.parseInt(input[i]);
Arrays.sort(data);
int min=1;
int max=1000000000;
int mid;
while(min<max) {
mid=(min+max)/2;
if(bis(mid)) max=mid;
else min=mid+1;
}
System.out.println(max);
}
public static boolean bis(int x) {
int range=0;
int kkkk=0;
for(int i=0;i<data.length;i++) {
if(data[i]>range) {
range=data[i]+x;
kkkk++;
}
if(kkkk>k)return false;
}
return true;
}
}
```
---
### d050 線段覆蓋長度
解法:sort
```Java=
import java.io.*;
import java.util.*;
public class d050 {
public static int r;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception{
final int t=readint();
int[][] l=new int[t][2];
for(int i=0;i<t;i++) {
l[i][0]=readint();
l[i][1]=readint();
}
Arrays.sort(l,new Comparator<int[]>() {
public int compare(int[] f,int[] s){
if(f[0]>s[0])return 1;
else {
return -1;
}
}
});
int cs=-1;
int ce=-2;
int e;
int out=0;
for(int i=0;i<t;i++) {
if(l[i][0]>ce+1) {
out+=ce-cs+1;
cs=l[i][0];
}
e=l[i][1]-1;
ce=(e>ce)?e:ce;
}
System.out.println(out+ce-cs+1);
}
public static int readint() throws Exception {
int add=0;
while(true) {
r=br.read();
if(r<47||r>58) {
return add;
}
else {
r=r&15;
add*=10;
add+=r;
}
}
}
}
```
---
### d051 一次買賣
解法:greedy
```Java=
import java.io.*;
import java.util.*;
public class d051 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long ans=0,min=(1<<30);
public static void main(String[] args) throws Exception{
final int n=orz();
int a;
for(int i=0;i<n;i++) {
a=orz();
if(a-min>ans)ans=a-min;
if(min>a)min=a;
}
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d052 最大連續子陣列
解法:DP(低批)
```Java=
import java.io.*;
import java.util.*;
public class d052 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long ans=0;
public static boolean neg;
public static long[] sum=new long[100005];
public static void main(String[] args) throws Exception{
final int n=orz();
int a;
sum[0]=orz();
for(int i=1;i<n;i++) {
a=orz();
if(sum[i-1]>0) {
sum[i]=sum[i-1]+a;
}
else {
sum[i]=a;
}
if(sum[i]>ans)ans=sum[i];
}
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
```
---
### d053 先到先服務
解法:greedy、Priority-Queue
```java=
import java.io.*;
import java.util.*;
public class d053 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
final int m=orz();
int ans=0;
PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b) {
return a-b;
}
});
for(int i=0;i<m;i++) pq.offer(0);
for(int i=0;i<n;i++) {
pq.offer(pq.poll()+orz());
}
while(!pq.isEmpty())ans=pq.poll();
System.out.println(ans);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d054 恢復能量的白雲熊膽丸
解法:二分搜
```java=
import java.io.*;
import java.util.*;
public class d054 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
final int m=orz();
int[] mp=new int[n+1];
int mx=0;
for(int i=0;i<n;i++) {
mp[i]=orz();
mx=Math.max(mx,mp[i]);
}
mp[n]=0;
int l=mx,r=(int) Math.pow(10,9),mid,cp,c;
boolean pass=true;
while(l!=r) {
pass=true;
mid=(l+r)/2;
cp=mid;
c=m;
for(int i=0;i<n;i++) {
cp-=mp[i];
if(cp-mp[i+1]<0) {
cp=mid;
c--;
if(c<0) {
pass=false;
break;
}
}
}
if(pass) {
r=mid;
}
else{
l=mid+1;
}
}
System.out.println(l);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d055 控制點
解法:sort、greedy
```Java=
import java.io.*;
import java.util.*;
public class d055 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
int[][] xy=new int[n][2];
for(int i=0;i<2;i++) {
for(int j=0;j<n;j++) {
xy[j][i]=orz();
}
}
Arrays.sort(xy,new Comparator<int[]>() {
public int compare(int[] f,int[] s) {
return (f[0]==s[0])?f[1]-s[1]:f[0]-s[0];
}
});
int maxy=0,cnt=0;
for(int i=n-1;i>=0;i--) {
if(xy[i][1]>maxy) {
maxy=xy[i][1];
cnt++;
}
}
System.out.println(cnt);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d056 最靠近的一對
解法:排序、二分搜
```Java=
import java.io.*;
import java.util.*;
public class d056 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static boolean neg;
public static void main(String[] args) throws Exception{
final int n=orz();
int best=1<<30,l,r,m,lo,hi,dx=0,dy=0;
dot[] in=new dot[n];
for(int i=0;i<n;i++) {
in[i]=new dot(orz(),orz());
}
Arrays.sort(in,new Comparator<dot>(){
public int compare(dot f,dot s) {
if(f.x==s.x)return f.y-s.y;
return f.x-s.x;
}
});
ArrayList<dot> a=new ArrayList<>();
for(int i=0;i<n;i++) {
lo=in[i].y-best;
hi=in[i].y+best;
l=0;
r=a.size()-1;
while(l<r) {
m=(l+r)/2;
if(a.get(m).y<lo) {
l=m+1;
}
else {
r=m;
}
}
//if(l!=0)l--;
for(int j=l;j<a.size();j++) {
if(a.get(j).x<in[i].x-best) {
a.remove(j--);
}
else {
dx=Math.abs(a.get(j).x-in[i].x);
dy=Math.abs(a.get(j).y-in[i].y);
if(dx+dy<best)best=dx+dy;
if(a.get(j).y>hi)break;
}
}
l=0;
r=a.size()-1;
while(l<r) {
m=(l+r)/2;
if(a.get(m).y<=in[i].y) {
l=m+1;
}
else {
r=m;
}
}
a.add(l,new dot(in[i].x,in[i].y));
}
System.out.println(best);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
neg=false;
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
class dot{
int x,y;
dot(int a,int b){
x=a;
y=b;
}
}
```
---
### d057 賺錢與罰款
解法:greedy
```Java=
import java.io.*;
import java.util.*;
public class d057 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long time=0,sum=0;
public static void main(String[] args) throws Exception{
final int n=orz();
int[] t=new int[n];
for(int i=0;i<n;i++)t[i]=orz();
for(int i=0;i<n;i++)sum+=orz();
Arrays.sort(t);
for(int i=0;i<n;i++) {
time+=t[i];
sum-=time;
}
System.out.println(sum);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d058 死線高手
解法:greedy
```Java=
import java.io.*;
import java.util.*;
public class d058 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static long time=0;
public static boolean penalty=false;
public static void main(String[] args) throws Exception{
final int t=orz();
for(int a=0;a<t;a++) {
penalty=false;
int n=orz();
int[][] w=new int[n][2];
for(int i=0;i<n;i++) {
w[i][0]=orz();
}
for(int i=0;i<n;i++) {
w[i][1]=orz();
}
Arrays.sort(w,new Comparator<int[]>() {
public int compare(int[] f,int[] s) {
return f[1]-s[1];
}
});
time=0;
for(int i=0;i<n;i++) {
time+=w[i][0];
if(w[i][1]<time) {
penalty=true;
break;
}
}
System.out.println((penalty)?"no":"yes");
}
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d059 少林寺的櫃姐
解法:greedy、博愛排隊、二分搜
```Java=
import java.io.*;
import java.util.*;
public class d059 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r;
public static void main(String[] args) throws Exception{
final int n=orz();
final int m=orz();
int l=1;
int r=100000;//max ans
int mid,ans=0;
int[] t=new int[n];
PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b) {
return a-b;
}
});
for(int i=0;i<n;i++) {
t[i]=orz();
}
while(l!=r) {
mid=(l+r)/2;
for(int i=0;i<mid;i++)pq.offer(0);
for(int i=0;i<n;i++) {
pq.offer(pq.poll()+t[i]);
}
while(!pq.isEmpty())ans=pq.poll();
if(ans>m)l=mid+1;
else {
r=mid;
}
}
System.out.println(l);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
```
---
### d060 五嶽盟主的會議場所
解法:sliding window、博愛排隊
```Java=
import java.io.*;
import java.util.*;
public class d060 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int ret,r,idx=0,cnt=0,max=0;
public static void main(String[] args) throws Exception{
final int n=orz();
seg[] s=new seg[n];
seg p;
for(int i=0;i<n;i++) s[i]=new seg(orz(),orz(),orz());
Arrays.sort(s,new Comparator<seg>() {
public int compare(seg f,seg s) {
return f.l-s.l;
}
});
PriorityQueue<seg> pq=new PriorityQueue<>(new Comparator<seg>() {
public int compare(seg f,seg s) {
return f.r-s.r;
}
});
for(int i=0;i<n;i++) {
while(!pq.isEmpty()) {
p=pq.poll();
if(p.r>=s[i].l) {
pq.offer(p);
break;
}
else {
cnt-=p.v;
}
}
pq.offer(s[i]);
cnt+=s[i].v;
max=Math.max(max,cnt);
}
System.out.println(max);
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class seg{
int v,l,r;
seg(int a,int b,int c){
v=a;
l=b;
r=c;
}
}
```
---
Sign in with Wallet
Connect another wallet