AtCoder Beginner Contest 374 Java题解
代码中已去除冗余
直接判断末尾字符串是否为"san"即可，时间复杂度O(1)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
System.out.println(sc.next().endsWith("san")?"Yes":"No");
}
}
遍历字符串找到第一个不同的字符，时间复杂度O(len(t)+len(s))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
String s=sc.next(),t=sc.next();
if(s.equals(t)){
System.out.println("0");
}
else{
for(int i=0;;i++){
if(i>=Math.min(s.length(),t.length())||s.charAt(i)!=t.charAt(i)){
System.out.println(i+1);
break;
}
}
}
}
}
根据数据范围，可以利用状态压缩来代表其中一个组选了什么，算出总数，进而知道剩下的总数，取所有情况的最小值即可，时间复杂度O(n*2^n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k[]=new int[n],ans=(int)2e9,sum=0;
for(int i=0;i<n;i++){
k[i]=sc.nextInt();
sum+=k[i];
}
for(int i=0;i<(1<<n);i++){
int cur=0;
for(int j=0;j<n;j++){
cur+=k[j]*(i>>j&1);
}
ans=Math.min(ans,Math.max(cur,sum-cur));
}
System.out.println(ans);
}
}
本题的距离是欧几里得距离，根据数据范围，枚举已完成的状态以及完成时所在的线段的编号和那一端，再枚举上一次完成的线段，即可完成动态规划，时间复杂度O(n^2*2^n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),s=sc.nextInt(),t=sc.nextInt(),p[][][]=new int[n][2][2];
double dis1[]=new double[n],dis2[][][][]=new double[n][n][2][2],dis3[][][]=new double[1<<n][n][2],ans=1e20;
for(int i=0;i<n;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
p[i][j][k]=sc.nextInt();
}
}
dis1[i]=getDis(p[i][0],p[i][1])/t;
for(int j=0;j<n;j++){
for(int k=0;k<2;k++){
for(int w=0;w<2;w++){
dis2[i][j][k][w]=dis2[j][i][w][k]=getDis(p[i][k],p[j][w])/s;
}
}
}
}
for(int i=1,bit=0;i<(1<<n);i++){
if(Integer.bitCount(i)==1){
for(int j=0;j<2;j++){
dis3[i][bit][j]=getDis(new int[2],p[bit][j^1])/s+dis1[bit];
}
bit++;
}
else{
for(int j=0;j<n;j++){
if((i>>j&1)==1){
Arrays.fill(dis3[i][j],1e20);
int mask=i^(1<<j);
for(int k=0;k<n;k++){
if((mask>>k&1)==1){
for(int u=0;u<2;u++){
for(int v=0;v<2;v++){
dis3[i][j][u]=Math.min(dis3[i][j][u],dis3[mask][k][v]+dis2[j][k][u^1][v]+dis1[j]);
}
}
}
}
}
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<2;j++){
ans=Math.min(ans,dis3[(1<<n)-1][i][j]);
}
}
System.out.println(ans);
}
static double getDis(int a[],int b[]){
return Math.sqrt(Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2));
}
}
E Sensor Optimization Dilemma 2
二分答案：对于每一个任务，要想使得用钱最少，一定优选择单位价钱较便宜的那个，但是最小值需要从0到100测试插入另一个机器的任务（鉴于数据范围不大于100，因此最多使用100次较贵的机器来做任务能造成至少一次的较便宜机器任务空缺），时间复杂度O(100nlog(1e9)*)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),x=sc.nextInt(),a[]=new int[n],p[]=new int[n],b[]=new int[n],q[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
p[i]=sc.nextInt();
b[i]=sc.nextInt();
q[i]=sc.nextInt();
}
int l=0,r=(int)1e9;
while(l<r){
int mid=(l+r)>>1;
if(find(a,p,b,q,mid)<=x){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(find(a,p,b,q,r)<=x){
l=r;
}
break;
}
}
System.out.println(l);
}
static long find(int a[],int p[],int b[],int q[],int w){
if(w==0){
return 0;
}
long ans=0;
for(int i=0;i<a.length&&ans<=1e18;i++){
if(a[i]*q[i]<b[i]*p[i]){
a[i]^=b[i];
b[i]^=a[i];
a[i]^=b[i];
p[i]^=q[i];
q[i]^=p[i];
p[i]^=q[i];
}
long min=((w-1)/a[i]+1)*(long)p[i];
for(int j=1;j<=100;j++){
long cur=q[i]*j+(b[i]*j>=w?0:((w-b[i]*j-1)/a[i]+1)*(long)p[i]);
min=Math.min(min,cur);
}
ans+=min;
}
return ans;
}
}
对于每一个最早出发时间，这一批最优的选择出发时间点无非是t+[0,n]*x，且最优的方案一定是运送相邻的连续一批，因此考虑的时间最多n^2种，离散化所有时间点后进行动态规划，时间复杂度O(n^4)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt(),x=sc.nextInt(),p=0;
Map<Long,Integer> map1=new HashMap<>();
long t[]=new long[n],map2[]=new long[n*n+5],ans[][]=new long[n+1][n*n+5];
TreeSet<Long> set=new TreeSet<>();
set.add(-1L*x);
for(int i=0;i<n;i++){
t[i]=sc.nextLong();
for(int j=0;j<n;j++){
set.add(t[i]+j*(long)x);
}
}
for(long a:set){
map1.put(a,p);
map2[p]=a;
p++;
}
for(int i=1;i<=n;i++){
Arrays.fill(ans[i],(long)1e18);
}
for(int i=0;i<n;i++){
for(int j=1;j<p;j++){
ans[i+1][j]=ans[i+1][j-1];
if(map2[j]<t[i]){
//运送时间不能早于货物最早可运送时间
continue;
}
int count=0,last=map1.get(set.floor(map2[j]-x));
long sum=0;
for(int w=i;w>=0;w--){
count++;
sum+=map2[j]-t[w];
if(count<=k){
ans[i+1][j]=Math.min(ans[i+1][j],ans[w][last]+sum);
}
else{
break;
}
}
}
}
System.out.println(ans[n][p-1]);
}
}
首尾相同的字符串可以组成连边，本题的题意即为，把环状的强连通分量缩点后，最少可以用多少路径覆盖，缩点利用tarjan算法，最少路径覆盖问题，可以考虑可达点之间的二分匹配，每匹配一对点，即可较少考虑一个路径，时间复杂度O(能过)
import java.util.*;
public class Main{
static int timeStamp=0,sccNum=0;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),low[]=new int[n],time[]=new int[n],group[]=new int[n];
String s[]=new String[n];
List<Integer> path[]=new List[n];
for(int i=0;i<n;i++){
s[i]=sc.next();
path[i]=new ArrayList<>();
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(s[i].charAt(1)==s[j].charAt(0)){
path[i].add(j);
}
}
}
Stack<Integer> stack=new Stack<>();
boolean has[]=new boolean[n+5];
for(int i=0;i<n;i++){
if(time[i]==0){
tarjan(i,path,stack,time,low,group,has);
}
}
path=find(path,group);
int ans=sccNum,idx[]=new int[n+5];
for(int i=1;i<=sccNum;i++){
if(hungary(path,idx,new boolean[n+5],i)){
ans--;
}
}
System.out.println(ans);
}
static List<Integer>[] find(List<Integer> path[],int group[]){
//在已有的图上，把可达点之间全部连边，并输出新图
Set<Integer> child[]=new Set[sccNum+5];
List<Integer> ans[]=new List[sccNum+5];
for(int i=1;i<=sccNum;i++){
child[i]=new HashSet<>();
}
for(int i=0;i<group.length;i++){
for(int a:path[i]){
child[group[i]].add(group[a]);
}
}
boolean has[]=new boolean[sccNum+5];
for(int i=1;i<=sccNum;i++){
allEdge(i,child,has);
ans[i]=new ArrayList<>(child[i]);
}
return ans;
}
static void allEdge(int k,Set<Integer> child[],boolean has[]){
//递归实现find函数
if(!has[k]){
has[k]=true;
Set<Integer> set=new HashSet<>();
for(int a:child[k]){
if(!has[a]){
allEdge(a,child,has);
}
set.addAll(child[a]);
}
child[k].addAll(set);
child[k].remove(k);
}
}
static boolean hungary(List<Integer> path[],int idx[],boolean has[],int k){
//匈牙利算法计算最大匹配
for(int a:path[k]){
if(has[a]){
continue;
}
has[a]=true;
if(idx[a]==0||hungary(path,idx,has,idx[a])){
idx[a]=k;
return true;
}
}
return false;
}
static void tarjan(int k,List<Integer> path[],Stack<Integer> stack,int time[],int low[],int group[],boolean has[]){
//塔扬算法缩点
timeStamp++;
time[k]=low[k]=timeStamp;
stack.push(k);
has[k]=true;
for(int a:path[k]){
if(time[a]==0){
tarjan(a,path,stack,time,low,group,has);
low[k]=Math.min(low[k],low[a]);
}
else if(has[a]){
low[k]=Math.min(low[k],time[a]);
}
}
if(time[k]==low[k]){
sccNum++;
while(true){
int a=stack.pop();
group[a]=sccNum;
has[a]=false;
if(a==k){
break;
}
}
}
}
}
查看14道真题和解析
