C~F Java
方法一：猜结论
假如能够销完的话，总数一定是偶数，并且最大的数量的二倍不大于总数，那么就假设每种颜色是剩下的颜色，判断剩下的（剩下的假如是奇数的话需要从当前遍历的气球种类借一个进来），能留下的条件妖魔石剩下的可以自我消耗完，要么剩下的最大数量被抵消完后的数量小于当前遍历，实现上利用了有序映射计数，时间复杂度O(nlogn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),a[]=new int[n],ans=0;
TreeMap<Integer,Integer> map=new TreeMap<>();
inc(map,0,1);
long sum=0;
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
inc(map,a[i],1);
sum+=a[i];
}
for(int b:a){
sum-=b;
inc(map,b,-1);
int max=map.lastKey();
if(sum%2==0&&b>max*2-sum||sum%2==1&&b>1&&(max*2<=sum+1||b>max*2-sum)){
ans++;
}
inc(map,b,1);
sum+=b;
}
System.out.println(ans);
}
static void inc(TreeMap<Integer,Integer> map,int a,int b){
map.put(a,map.getOrDefault(a,0)+b);
if(map.get(a)==0){
map.remove(a);
}
}
}
方法二：简便做法
待定
方法一：数位动态规划
很给的一个题，不解释，时间复杂度O(C+Tnlogn),其中C==480，为预处理的固定时间
import java.util.*;
public class Main{
public static void main(String args[]){
long count[][][]=new long[17][10][3];
for(int i=0;i<10;i++){
if(i!=3){
count[1][i][i%3]=1;
}
}
for(int i=2;i<17;i++){
for(int j=0;j<10;j++){
for(int k=0;k<3;k++){
for(int p=0;p<10;p++){
count[i][j][k]+=count[i-1][p][(k+30-j)%3];
}
}
}
}
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
long n=sc.nextLong();
long l=0,r=n*10;
while(l<r){
long mid=(l+r)>>1;
if(find(mid,count)>=n){
r=mid;
}
else{
l=mid+1;
}
if(l==r-1){
if(find(l,count)>=n){
r=l;
}
break;
}
}
System.out.println(r);
}
}
static long find(long a,long count[][][]){
List<Long> list=new ArrayList<>();
while(a!=0){
list.add(a%10);
a/=10;
}
int size=list.size();
long ans=0,pre=0;
for(int i=size-1;i>=0;i--){
a=list.get(i);
for(int j=0;j<a;j++){
for(int k=1;k<3;k++){
ans+=count[i+1][j][(int)(k+30-pre)%3];
}
}
pre=(pre+a)%3;
if(i==0&&pre!=0&&a!=3){
ans++;
}
}
return ans;
}
}
方法二：打表
每30个数中有18个，打表即可，时间复杂度O(1)
import java.util.*;
public class Main{
static int move[]={1,2,4,5,7,8,10,11,14,16,17,19,20,22,25,26,28,29};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
long n=sc.nextLong();
System.out.println((n-1)/18*30+move[(int)((n-1)%18)]);
}
}
}
横对称+纵对称-横纵对称，时间复杂度O(log(mod))
import java.util.*;
public class Main{
static int mod=(int)1e9+7;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println(n%2==0?(pow(4,n/2)+pow(4,n)-pow(2,n/2)+mod)%mod:(pow(4,n/2)*2+pow(4,n)-pow(2,n/2)*2+mod*2L)%mod);
}
static long pow(long a,int b){
long ans=1;
while(b!=0){
if(b%2==1){
ans=ans*a%mod;
}
b>>=1;
a=a*a%mod;
}
return ans;
}
}
方法一：一格更新整列
最短路的思路，每次遇到障碍物的格子，假如得到的新距离可以更新该格子的最短距离，则直接更新整列的距离，优先队列实现，时间复杂度O(nm^2log(mn))
import java.util.*;
public class Main{
static int move[][]={{0,1},{0,-1},{1,0},{-1,0}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),c[]=new int[m],dis[][]=new int[n][m];
String s[]=new String[n];
for(int i=0;i<n;i++){
s[i]=sc.next();
Arrays.fill(dis[i],(int)1e9);
}
dis[0][0]=0;
for(int i=0;i<m;i++){
c[i]=sc.nextInt();
}
Queue<int[]> q=new PriorityQueue<>((a,b)->Integer.compare(a[2],b[2]));
q.add(new int[]{0,0,0});
while(!q.isEmpty()){
int a[]=q.poll();
if(dis[a[0]][a[1]]<a[2]){
continue;
}
for(int mo[]:move){
int x=a[0]+mo[0],y=a[1]+mo[1];
if(x>=0&&x<n&&y>=0&&y<m){
int d=a[2]+(s[x].charAt(y)=='#'?c[y]:0);
if(d<dis[x][y]){
dis[x][y]=d;
q.add(new int[]{x,y,d});
if(s[x].charAt(y)=='#'){
for(int k=0;k<n;k++){
if(dis[k][y]>d){
dis[k][y]=d;
q.add(new int[]{k,y,d});
}
}
}
}
}
}
}
System.out.println(dis[n-1][m-1]);
}
}
方法二：建图
根据视频讲解，每一列建立一个虚拟点，代表一次性摧毁一列的所有障碍，建图后进行最短路，实现上用了优先队列，时间复杂度O(mnlog(mn))
import java.util.*;
public class Main{
static int move[][]={{0,1},{0,-1},{1,0},{-1,0}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),c[]=new int[m],dis[][]=new int[n+1][m];
String s[]=new String[n];
List<int[]> path[][]=new List[n+1][m];
for(int i=0;i<=n;i++){
Arrays.fill(dis[i],(int)1e9);
for(int j=0;j<m;j++){
path[i][j]=new ArrayList<>();
}
if(i<n){
s[i]=sc.next();
}
}
for(int i=0;i<m;i++){
c[i]=sc.nextInt();
}
dis[0][0]=0;
Queue<int[]> q=new PriorityQueue<>((a,b)->Integer.compare(a[2],b[2]));
q.add(new int[]{0,0,0});
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i].charAt(j)=='#'){
path[n][j].add(new int[]{i,j,0});
}
for(int mo[]:move){
int x=i+mo[0],y=j+mo[1];
if(x>=0&&x<n&&y>=0&&y<m){
if(s[x].charAt(y)=='#'){
path[i][j].add(new int[]{n,y,c[y]});
}
else{
path[i][j].add(new int[]{x,y,0});
}
}
}
}
}
while(!q.isEmpty()){
int a[]=q.poll();
if(dis[a[0]][a[1]]<a[2]){
continue;
}
for(int b[]:path[a[0]][a[1]]){
int d=a[2]+b[2];
if(d<dis[b[0]][b[1]]){
dis[b[0]][b[1]]=d;
q.add(new int[]{b[0],b[1],d});
}
}
}
System.out.println(dis[n-1][m-1]);
}
}
方法三：动态规划
京公网安备 11010502036488号