http://hihocoder.com/contest/offers55/problems
题目1 : 算式最大值
有负号，再判断有没有括号
package l551;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt(),p=sc.nextInt(),q=sc.nextInt(),k=sc.nextInt();
int[]a=new int[n];
for(int i=0;i<n;i++)a[i]=sc.nextInt();
int sum=0,min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
for(int i:a) {
sum+=i;
min=Math.min(min, i);
max=Math.max(max, i);
}
if(q==0) {
System.out.println(sum);
} else if(q==1) {
System.out.println(sum-2*min);
} else {
if(k==0) {
int t=0;
Arrays.sort(a);
for(int i=0;i<q;i++)t+=a[i];
System.out.println(sum-2*t);
} else {
System.out.println(sum-2*min);
}
}
}
}
题目2 : 朋友字符串
直接暴力AC
package l552;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
String[]ss=new String[n];
Set<String>s=new HashSet<String>();
for(int i=0;i<n;i++) {
ss[i]=sc.next();
s.add(ss[i]);
}
int res=0;
for(int i=0;i<n;i++) {
char[]cs=ss[i].toCharArray();
for(int j=0;j<cs.length;j++) {
// if(j!=0 && cs[j]==cs[j-1]) continue;
for(int k=j+1;k<cs.length;k++) {
if(cs[j]==cs[k]) continue;
String t=ss[i].substring(0,j)+cs[k]+ss[i].substring(j+1,k)+cs[j]+ss[i].substring(k+1);
if(s.contains(t)) res++;
}
}
}
System.out.println(res/2);
}
}
题目3 : 区间覆盖问题
区间合并再二分，第一次run time error，那多半是数组越界，找到强行用a[0]这样的地方，然后就想到ArrayList L可能是空的
package l553;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt(),q=sc.nextInt();
int[][]a=new int[n][2];
for(int i=0;i<n;i++) {
a[i][0]=sc.nextInt();
a[i][1]=sc.nextInt();
}
Arrays.sort(a,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
Stack<int[]>st=new Stack<int[]>();
st.push(a[0]);
for(int i=1;i<n;i++) {
int[]t=st.peek();
if(a[i][0]>t[1]) {
st.push(a[i]);
} else {
st.pop();
st.push(new int[]{t[0],Math.max(t[1], a[i][1])});
}
}
Stack<int[]>st2=new Stack<int[]>();
while(!st.isEmpty()) st2.push(st.pop());
List<int[]>l=new ArrayList<int[]>();
while(!st2.isEmpty()) l.add(st2.pop());
List<int[]>t=new ArrayList<int[]>();
if(l.get(0)[0]>1) t.add(new int[]{1,l.get(0)[0]-1});
for(int i=1;i<l.size();i++)
if(l.get(i)[0]-l.get(i-1)[1]>1)
t.add(new int[]{l.get(i-1)[1]+1, l.get(i)[0]-1});
int[]b=new int[t.size()];
b[0]=t.get(0)[1]-t.get(0)[0]+1;
for(int i=1;i<t.size();i++) {
b[i]=b[i-1]+t.get(i)[1]-t.get(i)[0]+1;
}
while(q-->0) {
int k=sc.nextInt();
int idx=Arrays.binarySearch(b, k);
if(idx>=0) System.out.println(t.get(idx)[1]);
else {
idx = -(idx+1);
if(idx==0) System.out.println(t.get(0)[0]+k-1);
else if(idx==b.length) System.out.println(l.get(l.size()-1)[1]+k-b[idx-1]);
else System.out.println(t.get(idx)[0]+k-b[idx-1]-1);
}
}
}
}
package l553;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt(),q=sc.nextInt();
int[][]a=new int[n][2];
for(int i=0;i<n;i++) {
a[i][0]=sc.nextInt();
a[i][1]=sc.nextInt();
}
int[]qs=new int[q];
for(int i=0;i<q;i++)qs[i]=sc.nextInt();
Arrays.sort(a,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
Stack<int[]>st=new Stack<int[]>();
st.push(a[0]);
for(int i=1;i<n;i++) {
int[]t=st.peek();
if(a[i][0]>t[1]) {
st.push(a[i]);
} else {
st.pop();
st.push(new int[]{t[0],Math.max(t[1], a[i][1])});
}
}
Stack<int[]>st2=new Stack<int[]>();
while(!st.isEmpty()) st2.push(st.pop());
List<int[]>l=new ArrayList<int[]>();
while(!st2.isEmpty()) l.add(st2.pop());
List<int[]>t=new ArrayList<int[]>();
if(l.get(0)[0]>1) t.add(new int[]{1,l.get(0)[0]-1});
for(int i=1;i<l.size();i++)
if(l.get(i)[0]-l.get(i-1)[1]>1)
t.add(new int[]{l.get(i-1)[1]+1, l.get(i)[0]-1});
if(t.size()==0) {
for(int k : qs) System.out.println(l.get(l.size()-1)[1]+k);
return;
}
int[]b=new int[t.size()];
b[0]=t.get(0)[1]-t.get(0)[0]+1;
for(int i=1;i<t.size();i++) {
b[i]=b[i-1]+t.get(i)[1]-t.get(i)[0]+1;
}
for(int k:qs) {
int idx=Arrays.binarySearch(b, k);
if(idx>=0) System.out.println(t.get(idx)[1]);
else {
idx = -(idx+1);
if(idx==0) System.out.println(t.get(0)[0]+k-1);
else if(idx==b.length) System.out.println(l.get(l.size()-1)[1]+k-b[idx-1]);
else System.out.println(t.get(idx)[0]+k-b[idx-1]-1);
}
}
}
}
