2023/4/23小红书sde三道题

#小红书信息集散地#

总结：

很废物，总共只A了1道，第三题甚至都来不及看

1 AC 9%，报TLE超时

想了想这道题应该是找规律，然后dp

```java

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

List<Integer> list=new LinkedList<>();

for (int i=0;i<n;i++){

list.add(sc.nextInt());

}

System.out.println(getK(list));

}

public static int getK(List<Integer> list){

long res=0;

while(!list.isEmpty()){

int ele=(int)list.get(0);

list.set(0,ele-1);

for(int i=0;i<ele;i++){

list.add(ele-1);

}

res++;

if(res>20)break;

if(ele-1<0){

list.remove(0);

}

}

return (int)((long)res%((long)10e9+7));

}

```

2 并查集做，AC 91%

```java

public static void main2(String[] args) {

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int k=sc.nextInt();

String str=sc.next();

UnionFind uf=new UnionFind(n);

for (int i=0;i<n-1;i++){

int a=sc.nextInt()-1;

int b=sc.nextInt()-1;

if(str.charAt(a)=='R'&&'R'==str.charAt(b)){

uf.union(a,b);

}

}

int[]a=Arrays.copyOf(uf.size,n);

Arrays.sort(a);

System.out.println(a[n-k]);

}

static class UnionFind{

int[]p;

int[]rank;

int[]size;

boolean[]red;

public UnionFind(int n){

p=new int[n];

rank=new int[n];

size=new int[n];

red=new boolean[n];

for(int i=0;i<n;i++){

p[i]=i;

rank[i]=1;

size[i]=1;

}

}

void setColor(int x){

red[x]=true;

}

public int find(int x){

while(x!=p[x]){

x=p[x];

}

return x;

}

public void union(int x,int y){

int r1=find(x);

int r2=find(y);

if(r1==r2)return;

if(rank[r1]>rank[r2]){

p[r2]=r1;

size[r1]+=size[r2];

red[r2]|=red[r1];

}else if(rank[r1]<rank[r2]){

p[r1]=r2;

size[r2]+=size[r1];

red[r1]|=red[r2];

}else{

p[r1]=r2;

size[r1]+=size[r2];

rank[r2]++;

}

}

}

```