题解 | 牛客小白月赛89 BCDEF
伊甸之花
https://ac.nowcoder.com/acm/contest/76795/A
思路：首先为了使得最后一个数字最小，需要尽量先取出小的数字加到其他数字（一个或者多个）数字上，很明显，如果累加的值为非正数，那么为了使得剩下的数字在一次累加操作后尽可能小，最贪心的方式为给目前所有没有加到的数字都累加这个值，反之如果累加的数为正数，那么应该贪心地尽可能让少的数字变大，选取剩下的最小值去变大即可，其他数字不要动
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int j=0;j<t;j++){
int n=sc.nextInt();
Queue<Long> q=new PriorityQueue<>();
for(int i=0;i<n;i++){
q.add(sc.nextLong());
}
long add=0;
for(int i=0;i<n-1;i++){
long a=q.poll();
if(add+a<=0){
add+=add+a;
}
else{
q.add(q.poll()+a+add);
}
}
System.out.println(add+q.poll());
}
}
}
思路：因为红为先手，那么需要特判没有红的情况返回blue，，其次先手如果可以使得蓝色全部消失，则返回red，否则先手红扩之后，一个蓝色（这个蓝色一定之前与一圈蓝色为邻，即使先手后，周围的蓝色蓝被换成红色，后手可以选择这个蓝色扩展出至少两个不相邻的蓝色块）总可以至少扩展出两个其他的蓝块
import java.util.*;
public class Main{
static int move[][]={{1,0},{-1,0},{0,1},{0,-1}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt(),m=sc.nextInt();
char c[][]=new char[n][];
for(int j=0;j<n;j++){
c[j]=sc.next().toCharArray();
}
System.out.println(find(c,n,m));
}
}
static String find(char c[][],int n,int m){
int hasBlue=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(c[i][j]=='.'){
hasBlue++;
}
}
}
if(hasBlue==m*n){
return "Blue";
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(c[i][j]=='#'){
List<int[]> list=new ArrayList<>();
list.add(new int[]{i,j});
c[i][j]='p';
for(int k=0;k<list.size();k++){
int a[]=list.get(k);
for(int mo[]:move){
int x=a[0]+mo[0],y=a[1]+mo[1];
if(x>=0&&x<n&&y>=0&&y<m&&c[x][y]=='#'){
list.add(new int[]{x,y});
c[x][y]='p';
}
}
}
Set<Integer> set=new HashSet<>();
for(int a[]:list){
for(int mo[]:move){
int x=a[0]+mo[0],y=a[1]+mo[1];
if(x>=0&&x<n&&y>=0&&y<m&&c[x][y]=='.'){
set.add(x*3000+y);
}
}
}
if(set.size()==hasBlue){
return "Red";
}
}
}
}
return "Draw";
}
}
经典的问题：前i种距离可以得到多少种j种距离排列的方案，第i种选或者不选的问题，动态规划
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(),m=sc.nextInt(),q=sc.nextInt(),x=sc.nextInt();
List<Integer> path[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
}
for(int i=0;i<m;i++){
int u=sc.nextInt(),v=sc.nextInt();
path[u].add(v);
path[v].add(u);
}
int dis[]=new int[n+5],count[]=new int[5005];
Arrays.fill(dis,-1);
dis[x]=0;
Queue<Integer> queue=new LinkedList<>();
queue.add(x);
while(!queue.isEmpty()){
int a=queue.poll();
for(int b:path[a]){
if(dis[b]==-1){
dis[b]=1+dis[a];
count[dis[b]]++;
queue.add(b);
}
}
}
long ans[]=new long[5005];
ans[0]=1;
for(int i=0;i<5005;i++){
long temp[]=new long[5005];
temp[0]=1;
for(int j=1;j<=i;j++){
temp[j]=(ans[j]+ans[j-1]*count[i])%mod;
}
ans=temp;
}
for(int i=0;i<q;i++){
int k=sc.nextInt();
System.out.println(ans[k]);
}
}
}
思路：对每一列，记录放置的最后一个位置的所有可能的高度，由前一列转移的时候，需要考虑上一列或者只一列只允许放置一个方块的情况，否则只考虑上一列的底部接这一列的顶部，以及考虑这一列的底部接上一列的顶部两种状况，同时需要保证不出界
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt(),m=sc.nextInt(),a[]=new int[m+5];
for(int j=1;j<=m;j++){
a[j]=sc.nextInt();
}
//count表示的是，作为一列中最下边的方块可能出现的
int count[]=new int[n+5];
Arrays.fill(count,1);
for(int j=2;j<=m;j++){
int pre[]=new int[n+5];
if(a[j-1]==1){
for(int k=1;k<=n;k++){
if(count[k]>0){
int min=Math.max(a[j],k),max=Math.min(n,k+a[j]-1);
pre[min]++;
pre[max+1]--;
}
}
}
else if(a[j]==1){
for(int k=1;k<=n;k++){
if(count[k]>0){
int min=Math.max(1,k-a[j-1]+1),max=k;
pre[min]++;
pre[max+1]--;
}
}
}
else{
for(int k=1;k<=n;k++){
if(count[k]>0){
//下对上：
if(k+a[j]-1<=n){
pre[k+a[j]-1]++;
pre[k+a[j]]--;
}
//上对下：
if(k-a[j-1]-a[j]+2>=1){
pre[k-a[j-1]+1]++;
pre[k-a[j-1]+2]--;
}
}
}
}
for(int k=1;k<=n;k++){
pre[k]+=pre[k-1];
}
count=pre;
}
int ans=0;
for(int j=1;j<=n;j++){
if(count[j]>0){
ans++;
}
}
System.out.println(ans);
}
}
}
思路：这个我不会，这个链接里的题解看明白了，按照写了代码
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt();
List<Integer> path[]=new List[n+5],born[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
born[i]=new ArrayList<>();
}
for(int i=1;i<n;i++){
int u=sc.nextInt(),v=sc.nextInt();
path[u].add(v);
path[v].add(u);
}
for(int i=0;i<m;i++){
int a=sc.nextInt(),t=sc.nextInt();
born[a].add(t);
}
int l=0,r=(int)5e6;
while(l<r){
int mid=(l+r)>>1;
if(check(mid,n,path,born)){
r=mid;
}
else{
l=mid+1;
}
if(l==r-1){
if(check(l,n,path,born)){
r=l;
}
break;
}
}
System.out.println(r);
}
static boolean check(int t,int n,List<Integer> path[],List<Integer> born[]){
int ans[][]=new int[n*2][];
find(1,t,path,born,ans);
for(int i=1;i<=n;i++){
if(ans[i][0]+ans[i][1]<=t){
return true;
}
}
return false;
}
static void find(int k,int t,List<Integer> path[],List<Integer> born[],int ans[][]){
ans[k]=new int[]{(int)1e7,(int)1e7};
for(int a:path[k]){
if(ans[a]==null){
find(a,t,path,born,ans);
ans[k]=merge(ans[k],new int[]{ans[a][0]+1,ans[a][1]+1});
}
}
for(int b:born[k]){
if(b*2<=t){
ans[k]=merge(ans[k],new int[]{b});
}
}
}
static int[] merge(int a[],int b[]){
for(int c:b){
if(c<a[0]){
a[1]=a[0];
a[0]=c;
}
else if(c<a[1]){
a[1]=c;
}
}
return a;
}
}
