头像

T-SHLoRk

BUAA


访客:44882

离线:1天前



题目描述

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

题意:给定一个从1 到 n 排序的整数列表。
首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。
第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。
我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。
返回长度为 n 的列表中,最后剩下的数字。


算法1

(找规律)

题解:这道题其实是变种的约瑟夫循环问题。我们用$f(n)$代表将1 - n先从左到右再从右到左遍历最后剩下来的数字,用$b(n)$代表将1-n先从右到左,再从左到右遍历最后剩下来的数字。我们可以发现其中一些规律:
$$
f(1) = 1,b(1)=1
$$
$$
f(n) = 2 * b(n/2)
$$
$$
f(n) + b(n) = n + 1
$$

  • 规则1很好理解,是初始状态
  • 规则2是因为,假设初始数组是[1,2,3,4,5,6],最终剩下来的数字是$f(6)$,经过第一轮从左到右遍历后剩下来的是[2,4,6],恰好是2 * [1,2,3],但是这时候我们开始要从右侧开始遍历了,最终剩下来的数字是$b(3)$,我们可以发现$f(6) = 2 * b(3)$。如果初始数组长度为奇数也可以得到一样的结果。
  • 规则3是因为,假设$f(n)$最终留下来的是从左到右的第$k$个数字,那么$b(n)$和$f(n)$是对称的操作,那么最后剩下来的肯定是从右到左的第$k$个数字,在这一题中二者相加之和是$n + 1$。

有了上面三个定理,答案就很好求解了,把公式3代入公式2可以得到:
$$
f(n) = 2 * b(n/2)\
=2*(n/2 + 1 - f(n / 2))\
$$
所以最终的代码可以写成:

    int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * (n / 2 + 1 - f(n / 2));
    }



T-SHLoRk
2个月前

题目描述

Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

  • 1 <= maxSize <= 1000
  • 1 <= x <= 1000
  • 1 <= k <= 1000
  • 0 <= val <= 100
  • At most 1000 calls will be made to each method of increment, push and pop each separately.

题意:请你设计一个支持下述操作的栈。

实现自定义栈类 CustomStack

CustomStack(int maxSize):用 maxSize初始化对象,maxSize 是栈中最多能容纳的元素数量,栈在增长到 maxSize之后则不支持push操作。
void push(int x):如果栈还未增长到 maxSize,就将x 添加到栈顶。
int pop():返回栈顶的值,或栈为空时返回 -1 。
void inc(int k, int val):栈底的k 个元素的值都增加 val。如果栈中元素总数小于 k ,则栈中的所有元素都增加 val


算法1

题解:我们需要一个数组来辅助记录每一个位置的数字被加上了多少,这样出栈的时候直接是栈中元素和当前辅助数组元素的和。如果直接记录的话,时间复杂度是$O(k)$的。我们可以简化成$O(1)$的操作:每次只在辅助数组第$k$个位置上加上val,等到这个元素出栈的时候,我们将该辅助数组上的arr[k]加到arr[k - 1]上,同时将arr[k]清零。为了描述清晰,我这里没有使用数组模拟栈。

class CustomStack {
public:
    vector<int> inc_arr;
    stack<int> st;
    int m_size,cnt = 0;
    CustomStack(int maxSize) {
        m_size = maxSize;
        inc_arr.resize(maxSize + 1,0);
    }

    void push(int x) {
        if(cnt < m_size){
            cnt ++;
            st.push(x);
        }
    }

    int pop() {
        if(cnt == 0)
            return -1;
        int p = st.top();
        st.pop();
        if(inc_arr[cnt] != 0){
            inc_arr[cnt - 1] += inc_arr[cnt];
            p += inc_arr[cnt];
            inc_arr[cnt] = 0;
        }
        cnt --;
        return p;
    }

    void increment(int k, int val) {
        inc_arr[min(k,cnt)] += val;
    }
};



T-SHLoRk
2个月前

Summary

今年KS的改革包括题目数量从三题变成四题,大数据集的结果可以直接即时返回。由于题目数量的增加,第一二题的难度有所降低,第三第四题还是具有一定难度的。不过也有可能由于是A轮,题目会出的简单一些,也是我第七次参加KS中唯一一次AC,不过排名也是七次中最低的一次。

Allocation

Problem

There are N houses for sale. The i-th house costs Ai dollars to buy. You have a budget of B dollars to spend.

What is the maximum number of houses you can buy?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing the two integers N and B. The second line contains N integers. The i-th integer is Ai, the cost of the i-th house.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of houses you can buy.

Limits

Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ B ≤ 105.
1 ≤ Ai ≤ 1000, for all i.

Test set 1

1 ≤ N ≤ 100.

Test set 2

1 ≤ N ≤ 105.

Sample

Input
3
4 100
20 90 40 90
4 50
30 30 10 10
3 300
999 999 999
Output
Case #1: 2
Case #2: 3
Case #3: 0

In Sample Case #1, you have a budget of 100 dollars. You can buy the 1st and 3rd houses for 20 + 40 = 60 dollars.
In Sample Case #2, you have a budget of 50 dollars. You can buy the 1st, 3rd and 4th houses for 30 + 10 + 10 = 50 dollars.
In Sample Case #3, you have a budget of 300 dollars. You cannot buy any houses (so the answer is 0).

Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

题意:一共有N套房子正在出售,第i个房子的售价是A_i,我们的总预算是B,请问我们最多能买多少个房子。

题解:这题按照以往的难度思维惯性,我一度以为是个背包问题,但是计算了时间复杂度后发现不可行。仔细一看其实就是一个简单的贪心问题,每次尽可能的选取售价最低的房子即可。时间复杂度$O(NlogN)$

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        int A[N],n,m;
        scanf("%d %d",&n,&m);
        for(int i = 0 ; i < n ; i ++)
            scanf("%d",&A[i]);
        sort(A,A + n);
        int i = 0,cur = 0;
        for(i = 0 ; i < n ; i ++){
            cur += A[i];
            if(cur > m)
                break;
        }

        printf("Case #%d: %d\n",t,i);
    }
    return 0;
}

如果我们可以观察到房屋的售价不超过1000,那么计数排序可以略微加快运行速度。时间复杂度$O(N) $

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int A[N];
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        int n,m,x;
        memset(A,0,sizeof(A));
        scanf("%d %d",&n,&m);
        for(int i = 0 ; i < n ; i ++){
            scanf("%d",&x);
            A[x] ++;
        }
        int res = 0;
        for(int i = 1 ; m > 0 && i <= 1000 ; i ++){
            int cur = min(m / i, A[i]);
            res += cur;
            m -= cur * i;
        }

        printf("Case #%d: %d\n",t,res);
    }
    return 0;
}

Plates

Dr. Patel has N stacks of plates. Each stack contains K plates. Each plate has a positive beauty value, describing how beautiful it looks.

Dr. Patel would like to take exactly P plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.

Help Dr. Patel pick the P plates that would maximize the total sum of beauty values.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, K and P. Then, N lines follow. The i-th line contains K integers, describing the beauty values of each stack of plates from top to bottom.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sum of beauty values that Dr. Patel could pick.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ PN * K.
The beauty values are between 1 and 100, inclusive.

Test set 1

1 ≤ N ≤ 3.

Test set 2

1 ≤ N ≤ 50.

Sample

Input
2
2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

Output
Case #1: 250
Case #2: 180

In Sample Case #1, Dr. Patel needs to pick P = 5 plates:

  • He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
  • He can pick the top 2 plates from the second stack (80 + 50 = 130) .

In total, the sum of beauty values is 250.

In Sample Case #2, Dr. Patel needs to pick P = 3 plates:

  • He can pick the top 2 plates from the first stack (80 + 80 = 160).
  • He can pick no plates from the second stack.
  • He can pick the top plate from the third stack (20).

In total, the sum of beauty values is 180.

题意:帕特尔有N堆盘子,每一堆盘子包括K个盘子,每个盘子有一个正的美丽值来形容这个杯子有多么的好看。现在帕特尔想取出其中恰好P个盘子在今天的晚餐中使用。如果他决定拿出堆中某一个盘子,他必须同时把在这一堆中在该盘子上面的所有盘子也取走。请帮助帕特尔先生求出P个盘子的美丽值的最大和。

题解:这一题看起来就是一个比较经典的背包问题了。

状态表示:dp[i][j]代表从前i堆盘子中总共取出j个盘子能够获得的最大美丽值。

状态初始化:全部初始化为0即可。

状态转移:dp[i][j] = max(temp[k] + dp[i - 1][j - k])。其中k代表第i堆盘子取出k个盘子,那么前i - 1堆只需要取出j - k个盘子即可。注意到这里k的取值范围是[0,min(j,K)],因为每一堆最多只有K个盘子,前面堆至少需要0个盘子,遍历所有可能的k,求最大值即可。

答案表示:dp[N][P]

时间复杂度:$O(NPK)$。

#include<stdio.h>
#include<cstring>
#include<iostream>

using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        int N,K,P;
        scanf("%d %d %d",&N,&K,&P);
        int dp[N + 1][P + 1];
        memset(dp,0,sizeof(dp));
        for(int i = 1 ; i <= N ; i ++){
            int temp[K + 1];
            memset(temp,0,sizeof(temp));
            for(int j = 1 ; j <= K ; j ++)
                scanf("%d ",&temp[j]);
            for(int j = 1 ; j <= K ; j ++)
                temp[j] = temp[j] + temp[j - 1];
            for(int j = 1 ; j <= P ; j ++){
                for(int k = 0 ; k <= min(j,K) ; k ++){
                    dp[i][j] = max(dp[i][j],temp[k] + dp[i - 1][j - k]);
                }
            }
        }
        printf("Case #%d: %d\n",t,dp[N][P]);
    }
    return 0;
}

Workout

Tambourine has prepared a fitness program so that she can become more fit! The program is made of N sessions. During the i-th session, Tambourine will exercise for Mi minutes. The number of minutes she exercises in each session are strictly increasing.

The difficulty of her fitness program is equal to the maximum difference in the number of minutes between any two consecutive training sessions.

To make her program less difficult, Tambourine has decided to add up to K additional training sessions to her fitness program. She can add these sessions anywhere in her fitness program, and exercise any positive integer number of minutes in each of them. After the additional training session are added, the number of minutes she exercises in each session must still be strictly increasing. What is the minimum difficulty possible?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and K. The second line contains N integers, the i-th of these is Mi, the number of minutes she will exercise in the i-th session.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum difficulty possible after up to K additional training sessions are added.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
For at most 10 test cases, 2 ≤ N ≤ 105.
For all other test cases, 2 ≤ N ≤ 300.
1 ≤ Mi ≤ 109.
Mi < Mi+1 for all i.

Test set 1

K = 1.

Test set 2

1 ≤ K ≤ 105.

Samples

Input 1
1
3 1
100 200 230

Output 1
Case #1: 50

Input2
3
5 2
10 13 15 16 17
5 6
9 10 20 26 30
8 3
1 2 3 4 5 6 7 10

Output2
Case #1: 2
Case #2: 3
Case #3: 1

Sample #1

In Case #1: Tambourine can add up to one session. The added sessions are marked in bold: 100 150 200 230. The difficulty is now 50.

Sample #2

In Case #1: Tambourine can add up to six sessions. The added sessions are marked in bold: 9 10 12 14 16 18 20 23 26 29 30. The difficulty is now 3.

In Case #2: Tambourine can add up to three sessions. The added sessions are marked in bold: 1 2 3 4 5 6 7 8 9 10. The difficulty is now 1. Note that Tambourine only added two sessions.

Note #1: Only Sample #1 is a valid input for Test set 1. Consequently, Sample #1 will be used as a sample test set for your submissions.

Note #2: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

题意:我们准备了一个健身计划来让自己变得更加健康,这个计划由N个课程组成,在第i个课程当中,我们将会锻炼M_i分钟,在这个健身计划中,每个课程的持续时长是严格递增的。我们健身计划的难度等于任意相邻两个训练课程时间长度的最大差值。为了让我们的计划变得容易一些,我们决定额外增加K个课程。我们可以在任意两个课程之间加入一个或者多个任意时间长度的课程。唯一的要求是,增加完之后,我们每个课程的持续时长仍然是严格递增的。那么在添加了K个课程之后,最小难度是多少呢。

题解1(优先队列,堆,贪心):其实我们并不关心每一个课程的持续长度是多少,我们关心的是连续两个课程时间的差值。假设我们由M时长数组计算出差值数组gap

我们考虑K = 1的情况(小数据集),我们如何使得难度最小呢?我们贪心的选择差值最大的两个相邻课程之间插入一个新的课程,可以使得我们的答案最小。

假设差值是x,那么在中间插入一个课程后,该部分的最大差值就变成了x / 2 + (x % 2 != 0)。我们只需要将该值和次大的差值取一个最大值即可。更一般的,对于差值是x的两个相邻课程,其中插入了k个新的课程之后,该部分的最大差值就是x / k + (x % k != 0)

那么K > 1的情况呢?我们只需要将上述思路重复K次即可。我们使用一个结构体记录(用pair数据结构也可以,重写比较函数即可)每一个区间长度sum和该区间已经插入了cnt个新课程。我们按照该区间插入cnt个课程后的该区间的最大差值从大到小排序即可。每次取出堆顶元素,将其cnt加上1之后重新插入优先队列。重复K次后,堆顶元素对应的区间最大值就是答案。

时间复杂度:$O(KlogN)$

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 100010;
int A[N],gap[N];
struct node{
    int sum,cnt;
    node(){}
    node(int sum,int cnt):sum(sum),cnt(cnt){}
    bool operator< (const node& b) const{
        int x = (sum / cnt) + (sum % cnt > 0);
        int y = (b.sum / b.cnt) + (b.sum % b.cnt > 0);
        return x < y;
    }
};
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        memset(A,0,sizeof(A));
        memset(gap,0,sizeof(gap));
        int n,K;
        scanf("%d %d",&n,&K);
        for(int i = 0 ; i < n ; i ++)
            scanf("%d",&A[i]);
        for(int i = 0 ; i < n - 1 ; i ++)
            gap[i] = A[i + 1] - A[i];
        if(K == 1){
            sort(gap,gap + n - 1);
            if(n == 2) 
                printf("Case #%d: %d\n",t,(gap[0] + 1) / 2);
            else
                printf("Case #%d: %d\n",t,max((gap[n - 2] + 1) / 2,gap[n - 3]));
        }else{
            priority_queue<node> q;
            for(int i = 0 ; i < n - 1 ; i ++){
                q.push(node(gap[i],1));
            }
            for(int i = 0 ; i < K ; i ++){
                auto p = q.top();
                q.pop();
                q.push(node(p.sum,p.cnt + 1));
            }
            auto p = q.top();
            int res = (p.sum / p.cnt) + (p.sum % p.cnt > 0);
            printf("Case #%d: %d\n",t,res);
        }
    }
    return 0;
}

题解2(二分):假设我们的最优答案是res,那么每一个区间x最少需要插入多少个新课程才能满足上述要求呢?我们最少需要插入(x - 1)/ res个新的课程。我们发现随着res的增加,所需要的新课程总量是减少的,随着res的减少,所需要的新课程总量是增加的。所以我们需要找到一个最小的res,使的所需要的课程总量个数小于等于K。那么我们可以使用二分查找解决这一题。

该题目属于二分查找满足某条件的最小值

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 100010;
int A[N],gap[N];
bool check(int op,int n,int K){
    int cnt = 0;
    for(int i = 0 ; i < n - 1 ; i ++)
        cnt += (gap[i] - 1) / op;
    return cnt <= K;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        memset(A,0,sizeof(A));
        memset(gap,0,sizeof(gap));
        int n,K;
        scanf("%d %d",&n,&K);
        for(int i = 0 ; i < n ; i ++)
            scanf("%d",&A[i]);
        for(int i = 0 ; i < n - 1 ; i ++)
            gap[i] = A[i + 1] - A[i];
        int l = 1,r = 1e9;
        while(l < r){
            int mid = (l + r) >> 1;
            if(check(mid,n,K)) r = mid;
            else l = mid + 1;
        }
        printf("Case #%d: %d\n",t,l);
    }
    return 0;
}

Bunding

Problem

Pip has N strings. Each string consists only of letters from A to Z. Pip would like to bundle their strings into groups of size K. Each string must belong to exactly one group.

The score of a group is equal to the length of the longest prefix shared by all the strings in that group. For example:

  • The group {RAINBOW, RANK, RANDOM, RANK} has a score of 2 (the longest prefix is 'RA').
  • The group {FIRE, FIREBALL, FIREFIGHTER} has a score of 4 (the longest prefix is 'FIRE').
  • The group {ALLOCATION, PLATE, WORKOUT, BUNDLING} has a score of 0 (the longest prefix is '').

Please help Pip bundle their strings into groups of size K, such that the sum of scores of the groups is maximized.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and K. Then, N lines follow, each containing one of Pip’s strings.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum sum of scores possible.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 105.
2 ≤ KN.
K divides N.
Each of Pip’s strings contain at least one character.
Each string consists only of letters from A to Z.

Test set 1

Each of Pip’s strings contain at most 5 characters.

Test set 2

The total number of characters in Pip’s strings across all test cases is at most 2 × 106.

Samples

Input1
2
2 2
KICK
START
8 2
G
G
GO
GO
GOO
GOO
GOOO
GOOO

Output1
Case #1: 0
Case #2: 10

Input2
1
6 3
RAINBOW
FIREBALL
RANK
RANDOM
FIREWALL
FIREFIGHTER

Output2
Case #1: 6

Sample #1

In Case #1, Pip can achieve a total score of 0 by make the groups:

  • {KICK, START}, with a score of 0.

In Case #2, Pip can achieve a total score of 10 by make the groups:

  • {G, G}, with a score of 1.
  • {GO, GO}, with a score of 2.
  • {GOO, GOO}, with a score of 3.
  • {GOOO, GOOO}, with a score of 4.

Sample #2

In Case #1, Pip can achieve a total score of 6 by make the groups:

  • {RAINBOW, RANK, RANDOM}, with a score of 2.
  • {FIREBALL, FIREWALL, FIREFIGHTER}, with a score of 4.

Note #1: Only Sample #1 is a valid input for Test set 1. Consequently, Sample #1 will be used as a sample test set for your submissions.

Note #2: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

题意:我们现在有N个字符串,每个字符串只包括字符A-Z,我们现在将这N个字符串划分为K个字符串一组,每个字符串只能属于一组,我们保证N % K = 0。每一组字符串的得分等于该组所有字符串的最长公共前缀长度。请帮助我进行划分,使得划分后所有组的得分总和最大。

题解:因为是公共前缀的题目,而且大数据特意强调了总字符个数不超过$2 \times 10^6$,大概率这一题是Trie树数据结构的做法。

我们考虑被划分为同一个组的字符串,假设其最长公共前缀为ABCD,长度为4,得分也为4,我们也可以看作是前缀A,AB,ABC,ABCD分别贡献了一分。如果某个前缀在x个组中都是公共前缀(不一定是最长的),那么这个前缀贡献的分数就是x

那么现在我们不再去求每一个组的分数(我比赛时的思路,罚时爆炸),而是去考虑每一个前缀为最终答案贡献了多少分。

如果某一个前缀出现了S次,那么他的最多贡献的分就是S / K。那么是否存在一种划分能让每一个前缀都实现其最大分数呢?假设存在一个长度为L的最长前缀$P_L$,其出现次数为cnt,我们先贪心的将其尽可能的划分为同一组,那么这个前缀P的贡献分数恰好是cnt / K,那么还剩下cnt % K个字符串,我们再考虑长度为L - 1的次最长前缀$P_{L-1}$,每次都处理一个最长前缀即可,可以使得所有前缀都满足最大值。

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int N = 2000010;
int son[N][26],cnt[N * 26],idx = 0,res;
void insert(string &s,int k){
    int p = 0;
    for(auto ch : s){
        cnt[p] ++;
        int j = ch - 'A';
        if(son[p][j] == 0) son[p][j] = ++idx;
        p = son[p][j];
    }
    cnt[p] ++;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        idx = 0,res = 0;
        memset(son,0,sizeof(son));
        memset(cnt,0,sizeof(cnt));
        int n,k;
        scanf("%d %d",&n,&k);
        string s;
        for(int i = 0 ; i < n ; i ++){
            cin >> s;
            insert(s,k);
        }
        for(int i = 1 ; i <= idx ; i ++)
            res += cnt[i] / k ;
        printf("Case #%d: %d\n",t,res);
    }
    return 0;
}

我当时比赛虽然AC了,但是思路略微麻烦,代码也不够整洁,我将我的AC代码贴在最后。我当时的思路是:使用Trie树记录所有字符串,同时记录每一个节点的出现次数及其深度。每次找到一个最深的出现次数大于K的节点,答案累计上这个深度,同时将从根节点到该节点路径上所有节点出现次数都减去K,代表这个字符串已经被使用过了,其子节点我们可以不用管,因为其子节点出现次数小于K,我们永远不会使用。

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int N = 2000010;
int son[N][26],cnt[N * 26],pa[N * 26],dep[N * 26],idx = 0,max_depth = 0;
vector<set<int>> ha;
void insert(string &s,int k){
    int p = 0,depth = 0;
    for(auto ch : s){
        cnt[p] ++;
        if(cnt[p] >= k) {
            ha[depth].insert(p);
            max_depth = max(max_depth,depth);
        }

        int j = ch - 'A';
        if(son[p][j] == 0) son[p][j] = ++idx;
        pa[son[p][j]] = p;
        dep[son[p][j]] = ++ depth;
        p = son[p][j];
    }
    cnt[p] ++;
    if(cnt[p] >= k) {
        ha[depth].insert(p);
        max_depth = max(max_depth,depth);
    }
}
int dfs(int K){
    while(max_depth >= 0 && ha[max_depth].size() == 0)
        max_depth --;
    int i = *ha[max_depth].begin();
    while(i != 0){
        cnt[i] -= K;
        if(cnt[i] < K)
            ha[dep[i]].erase(i);
        i = pa[i];
    }
    cnt[0] -= K;
    if(cnt[0] < K)
        ha[dep[i]].erase(i);
    return max_depth;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        idx = 0;
        max_depth = 0;
        ha.clear();
        ha.resize(N);
        memset(son,0,sizeof(son));
        memset(cnt,0,sizeof(cnt));
        memset(dep,0,sizeof(dep));
        memset(pa,0,sizeof(pa));
        int n,k;
        scanf("%d %d",&n,&k);
        string s;
        for(int i = 0 ; i < n ; i ++){
            cin >> s;
            insert(s,k);
        }
        int res = 0;
        while(cnt[0] > 0){
            res += dfs(k);
        }
        printf("Case #%d: %d\n",t,res);
    }
    return 0;
}



T-SHLoRk
2个月前

题目描述

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

img

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

  • 1 <= n <= 10^5
  • n-1 <= connections.length <= 10^5
  • connections[i][0] != connections[i][1]
  • There are no repeated connections.

题意:力扣数据中心有n 台服务器,分别按从 0 到n-1的方式进行了编号。

它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群,其中连接 connections是无向的。

从形式上讲,connections[i] = [a, b]表示服务器 ab之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。

「关键连接」是在该集群中的重要连接,也就是说,假如我们将它移除,便会导致某些服务器无法访问其他服务器。请你以任意顺序返回该集群内的所有 「关键连接」。


算法1

(tarjan) $O(V + E)$

题解:其实这道题让我们求的就是联通图中的桥,我们可以通过一遍DFS求出割点和桥也就是tarjan算法。

我们首先介绍一下dfs搜索树:

dfs搜索树.png

右图就是一个dfs搜索树,树中的边可以分为两种:

  • 树边:DFS过程中访问未访问节点而引出的边 实线
  • 回边:DFS过程中遇到已访问过节点的边。虚线

我们定义如下几个数组:

  • dfn数组:dfn[i]代表的是第i号节点在dfs过程中的遍历顺序,可以看作是时间戳。在第一次设定后保持不变。
  • low数组:low[i]代表的是第i号节点在不经过其父节点能够到达的所有节点中最小时间戳。在递归搜索的过程中不断更新

我们用cnt代表时间戳,初始时,dfn数组和low数组都相等等于cnt,假设我们从u节点开始,递归搜索其所有的子节点v,那么low数组的更新方式为:
$$low[u] = min(low[u],low[v]),如果v没有被访问过即(u,v)是树边$$
$$low[u] = min(low[u],dfn[v]),如果v已经访问过了,并且v不是u的父节点$$
桥的判定方法:如果v是未访问的节点,并且dfn[u] < low[v],那么(u,v)是树边。

割点判断方法:如果u不是根,vu某一个未访问子节点,只要存在dfn[u] <= low[v],那么u就是割点;如果u是根的话,当u有两个以上子树的时候就是割点(这个可以通过判断其有几个未访问过的子节点来判断)。

class Solution {
public:
    vector<vector<int>> graph,bridges;
    vector<int> dfn,low;
    vector<int> cut;
    int root,cnt = 1;
    void tarjan(int u,int fa)
    {
        dfn[u] = cnt;
        low[u] = cnt ++;
        int child = 0;
        for(auto v : graph[u])
        {
            if(dfn[v] == 0){ //v未被访问过
                child ++;    //记录节点u的子树个数
                tarjan(v,u);
                low[u] = min(low[u],low[v]);
                if(dfn[u] < low[v]) //判断桥
                    bridges.push_back({u,v});
                if(dfn[u] <= low[v]) //判断割点,注意此处是小于等于
                {
                    if(u == root && child > 1) cut[u] = 1;
                    else if(u != root)
                        cut[u] = 1;
                }
            }else if(v != fa){ // v被访问过了并且不是u的父节点
                low[u] = min(low[u],dfn[v]);
            }
        }
    }
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        graph.resize(n);
        dfn.resize(n);
        low.resize(n);
        cut.resize(n);
        for(auto &p : connections)
        {
            graph[p[0]].push_back(p[1]);
            graph[p[1]].push_back(p[0]);
        }
        // 如果整个图是联通的话
        root = 0;
        tarjan(0,-1);
        // for(int i = 0 ; i < n ; i ++)
        //     printf("%d ",cut[i]);
        // 如果原来的图不是联通的话
        // for(int i = 0 ; i < n ; i ++)
        // {
        //     if(dfn[i] == 0)
        //     {
        //         root = i;
        //         tarjan(i,-1);
        //     }
        // }
        return bridges;
    }
};



T-SHLoRk
2个月前

题目描述

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

img

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

img

Input: tree = [7], target =  7
Output: 7

Example 3:

img

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

img

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

img

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
  • The values of the nodes of the tree are unique.
  • target node is a node from the original tree and is not null.

题意:给出两棵二叉树originalcloned,并且给出original树中某一个节点targetcloned树是original树的一个深复制,请返回在cloned树中与target节点相对应的节点。

我们不允许改变任何一个节点,而且返回值必须是cloned树中的节点。

请考虑树中有重复值节点的情况。


算法1

(非递归后序遍历)

题解:如果树中没有重复节点的话,那么很简单,我们只需要记录target的值,然后使用任何一种遍历找到值相等的节点即可。有重复节点的话,问题会稍微困难一些,但是我们知道二叉树有一个很重要的特性:当使用后序遍历到某一个节点时,栈中的所有节点就是从根节点到当前节点的路径。因此,我们可以先在original树中使用后序遍历找到target节点,然后根据路径判断从originaltarget的每一步是向左还是向右。我们在cloned树中使用同样的方向即可。

    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        //  二叉树非递归后序遍历
        stack<TreeNode*> st_node;
        stack<int> st_vis;
        TreeNode* cur = original;
        while(!st_node.empty() || cur != NULL)
        {
            while(cur != NULL)
            {
                st_node.push(cur);
                st_vis.push(0);
                cur = cur->left;
            }
            TreeNode* p = st_node.top();
            if(st_vis.top() == 0)
            {
                st_vis.top() = 1;
                cur = p->right;
            }else{
                if(p == target)
                    break;
                st_vis.pop();
                st_node.pop();
            }
        }
        //  根据遍历结果还原每一步的方向,0代表左儿子,1代表右儿子
        vector<int> dir;
        while(!st_node.empty())
        {
            TreeNode* p = st_node.top();
            st_node.pop();
            if(!st_node.empty())
            {
                if(p == st_node.top()->left)
                    dir.push_back(0);
                else
                    dir.push_back(1);
            }
        }
        //  根据方向数组找到对应的节点
        TreeNode* res = cloned;
        for(int i = dir.size() - 1 ; i >= 0 ; i --)
        {
            if(dir[i] == 0) res = res->left;
            else res = res->right;
        }
        return res;
    }



T-SHLoRk
2个月前

题目描述

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

img

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

img

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:

  1. 1 <= R <= 100
  2. 1 <= C <= 100
  3. 0 <= r0 < R
  4. 0 <= c0 < C

题意:在 R 行 C 列的矩阵上,我们从 (r0, c0) 面朝东面开始

这里,网格的西北角位于第一行第一列,网格的东南角位于最后一行最后一列。

现在,我们以顺时针按螺旋状行走,访问此网格中的每个位置。

每当我们移动到网格的边界之外时,我们会继续在网格之外行走(但稍后可能会返回到网格边界)。

最终,我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。


算法1

题解:我们观察到在每个方向上走过的步长为1,1,2,2,3,3,。。。并且每次走完一定的步长都需要右转90度。我们对走过的每一个坐标进行模拟即可,只有当坐标在网格内部才记录答案。

    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        // cnt:已经访问的网格数,tar:总共需要访问的网格数,cur:当前循环内的步长
        //  st:当前方向,dx,dy为方向数组
        int st = 0,dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0},cnt = 0,tar = R * C;
        vector<vector<int>> res;
        int cur = 1;
        while(cnt < tar)
        {
            res.push_back(r0,c0);
            for(int i = 0 ; i < cur ; i ++)
            {
                r0 += dx[st],c0 += dy[st];
                if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                {
                    res.push_back({r0,c0});
                    cnt ++;
                }
            }
            st = (st + 1) % 4;
            for(int i = 0 ; i < cur ; i ++)
            {
                r0 += dx[st],c0 += dy[st];
                if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                {
                    res.push_back({r0,c0});
                    cnt ++;
                }
            }
            cur ++ ;
        }
        return res;
    }



T-SHLoRk
2个月前

题目描述

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1)such that :

  • p[0] = start
  • p[i] and p[i+1] differ by only one bit in their binary representation.
  • p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

Example 1:

Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Constraints:

  • 1 <= n <= 16
  • 0 <= start < 2 ^ n

题意:给你两个整数nstart。你的任务是返回任意(0,1,2,,...,2^n-1) 的排列 p,并且满足:

p[0] = start
p[i]p[i+1] 的二进制表示形式只有一位不同
p[0]p[2^n -1] 的二进制表示形式也只有一位不同


算法1

题解:该问题可以分解为以下三个部分:

  1. 我们首先考虑从0开始生成n位格雷码(Leetcode89)
  2. 找到start在格雷码数组中的位置k(遍历即可)
  3. 将数组向左循环移动k位(Leetcode189)。
    vector<int> circularPermutation(int n, int start) {
        vector<int> res = {0,1};
        int size = 2,t = 2;
        // 生成n位格雷码
        for(int i = 2 ; i <= n ; i ++)
        {
            vector<int> cur;
            cur.assign(res.begin(),res.end());
            for(int j = size - 1 ; j >= 0 ; j --)
                cur.push_back(res[j] + t);
            t = t << 1;
            size = size << 1;
            res = cur;
        }
        //  找到start是第多少位格雷码
        int u = 0;
        while(res[u] != start) u ++;

        // 开始循环移位数组,相当于将数组向右循环移动(size - u)位
        reverse(res.begin(),res.end());
        reverse(res.begin(),res.begin() + size - u);
        reverse(res.begin() + size - u,res.end());
        return res;
    }



T-SHLoRk
2个月前

题目描述

Given a number N, return a string consisting of "0"s and "1"s that represents its value in base **-2** (negative two).

The returned string must have no leading zeroes, unless the string is "0".

Example 1:

Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2

Example 2:

Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

Example 3:

Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4

Note:

  1. 0 <= N <= 10^9

题意:给出数字 N,返回由若干 “0” 和 “1”组成的字符串,该字符串为 N 的负二进制(base -2)表示。

除非字符串就是 “0”,否则返回的字符串中不能含有前导零


算法1

题解:我们依然采用与正数进制一样的方法,只不过这里的余数必须为正数。但是当基数为负数的时候,我们的余数会出现负数的情况,因此我们可以将余数加上一个基数的绝对值保证其为正数,同时更新商为:(被除数-余数)/除数。

//适用于正负十以内的基数    
string baseK(int N,int k)
    {
        if(N == 0) return "0";
        vector<int> res;
        while(N != 0)
        {
            int r = ((N % k) + abs(k)) % abs(k);
            N = (N - r) / k;
            res.push_back(r);
        }
        string ans = "";
        for(int i = res.size() - 1 ; i >= 0 ; i --)
            ans += to_string(res[i]);
        return ans;        
    }
    string baseNeg2(int N) {
        return baseK(N,-2);
    }



T-SHLoRk
2个月前

题目描述

Given the coordinates of four points in 2D space, return whether the four points could construct a square.

The coordinate (x,y) of a point is represented by an integer array with two integers.

Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

Note:

  1. All the input integers are in the range [-10000, 10000].
  2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  3. Input points have no order.

题意:给定二维空间中四点的坐标,返回四点是否可以构造一个正方形。

一个点的坐标(x,y)由一个有两个整数的整数数组表示。


算法1

题解:判断空间中的四个点是否是正方形:

  • 四个顶点总共有六条边,那么有四条边相等且不为0(菱形)
  • 对角线相等的菱形是正方形。
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        int p12 = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
        int p23 = (p3[0] - p2[0]) * (p3[0] - p2[0]) + (p3[1] - p2[1]) * (p3[1] - p2[1]);
        int p34 = (p3[0] - p4[0]) * (p3[0] - p4[0]) + (p3[1] - p4[1]) * (p3[1] - p4[1]);
        int p41 = (p1[0] - p4[0]) * (p1[0] - p4[0]) + (p1[1] - p4[1]) * (p1[1] - p4[1]);
        int p13 = (p1[0] - p3[0]) * (p1[0] - p3[0]) + (p1[1] - p3[1]) * (p1[1] - p3[1]);
        int p24 = (p2[0] - p4[0]) * (p2[0] - p4[0]) + (p2[1] - p4[1]) * (p2[1] - p4[1]);
        if(p12 == 0 || p23 == 0 || p34 == 0 || p41 == 0 || p13 == 0 || p24 == 0)
            return false;
        if((p12 == p13 && p24 == p34 && p12 == p24 && p41 == p23) || (p12 == p41 && p41 == p34 && p23 == p34 && p13 == p24) || (p13 == p41 && p23 == p24 && p13 == p23 && p12 == p34))
            return true;
        return false;
    }



T-SHLoRk
2个月前

题目描述

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0“ 

Constraints:

  • 1 <= digits.length <= 10^4
  • 0 <= digits[i] <= 9
  • The returning answer must not contain unnecessary leading zeros.

题意:给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。由于答案可能不在整数数据类型范围内,请以字符串形式返回答案。如果无法得到答案,请返回一个空字符串。


算法1

(计数,枚举) $O(n)$

我们都知道如果一个数字能够整除3,那么各位数字之和也可以整除3。我们先计算出所有数字的和,然后分三种情况讨论:

  • 数组和恰好是3的倍数,那么我们只需要将所有的数字从大到小拼接起来即可。
  • 数组和除以3余1,为了使得数字最大,我们需要删除一个[1,4,7]当中的数字,如果找不到,我们就删除两个[2,5,8]当中的数字。
  • 数组和除以3余2,为了使得数字最大,我们需要删除一个[2,5,8]当中的数字,如果找不到,我们就删除两个[1,4,7]当中的数字。

我们只需要将剩余的数字从大到小排序即可,此外还需要注意答案可能是空串,去除前导0。还有数据范围是在0-9之间,根本没有必要排序,只需要进行计数即可。所以总的时间复杂度就是统计每个数字出现次数,$O(n )$

    string largestMultipleOfThree(vector<int>& digits) {
        int n = digits.size(),sum = 0;
        vector<int> cnts(10,0);
        for(int i = 0 ; i < n ; i ++)
        {
            cnts[digits[i]] ++;
            sum += digits[i];
        }
        if(sum % 3 == 1)
        {
            bool flag = false;
            for(int i = 1 ; i < 10 ; i += 3)
            {
                if(cnts[i] > 0)
                {
                    cnts[i] --;
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                int cnt = 2;
                for(int i = 2 ; i < 10 ; i += 3)
                {
                    while(cnts[i] > 0)
                    {
                        cnts[i] --;
                        cnt --;
                    }
                    if(cnt == 0)
                        break;
                }
            }
        }else if(sum % 3 == 2)
        {
            bool flag = false;
            for(int i = 2 ; i < 10 ; i += 3)
            {
                if(cnts[i] > 0)
                {
                    cnts[i] --;
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                int cnt = 2;
                for(int i = 1 ; i < 10 ; i += 3)
                {
                    while(cnts[i] > 0)
                    {
                        cnts[i] --;
                        cnt --;
                    }
                    if(cnt == 0)
                        break;
                }
            }
        }
        string res = "";
        for(int i = 9 ; i > 0 ; i --)
            for(int j = 0 ; j < cnts[i] ; j ++)
                res.push_back('0' + i);
        if(res.length() == 0)
        {
            if(cnts[0] == 0) return "";
            else return "0";
        }
        for(int j = 0 ; j < cnts[0] ; j ++)
            res.push_back('0');
        return res;
    }