C# 代码

public class Solution {
    public int[][] DifferenceOfDistinctValues(int[][] grid) {
        int n = grid.Length, m = grid[0].Length;
        int[][] result = new int[n][];
        for (int i = 0; i < n; i++){
            result[i] = new int[m];
        }

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                result[i][j] = Get(i, j);
            }
        }

        return result;

        int Get(int x, int y){
            HashSet<int> left = new HashSet<int>();
            HashSet<int> right = new HashSet<int>();
            int r = x - 1, c = y - 1;
            while (r >= 0 && c >= 0){
                left.Add(grid[r][c]);
                r--;
                c--;
            }

            r = x + 1;
            c = y + 1;
            while (r < n && c < m){
                right.Add(grid[r][c]);
                r++;
                c++;
            }

            return Math.Abs(left.Count - right.Count);
        }
    }
}

C# 两次遍历代码

public class Solution {
    public long MaxStrength(int[] nums) {
        int n = nums.Length;
        Array.Sort(nums);
        long result = int.MinValue;
        long p = 1;
        for (int i = n - 1; i >= 0; i--){
            if (nums[i] > 0){
                p *= nums[i];
                result = Math.Max(result, p);
            }
        }

        for (int i = 0; i < n; i++){
             if (nums[i] < 0){
                p *= nums[i];
                result = Math.Max(result, p);
            }           
        }

        if (result < 0 && nums.Contains(0)) return 0; 
        return result;
    }
}

C# 优化代码

public class Solution {
    public long MaxStrength(int[] nums) {
        int n = nums.Length;
        long min = nums[0], max = nums[0];
        for (int i = 1; i < n; i++){
            long[] a = {max, nums[i], max * nums[i], min * nums[i]};
            long[] b = {min, nums[i], max * nums[i], min * nums[i]};
            max = a.Max();
            min = b.Min();
        }

        return max;
    }
}

哈希

考虑两个map=> hash1, hash2

hash1[x] => x/k的数量
hash2[x] => x的数量

枚举每一个数，这个值能给ans的贡献就是 hash1[nums[i]/k] 如果nums[i]%k == 0

为什么？

对于每一个nums[i]，如果nums[i]%k == 0，此时相当于构成了这样一个3元(_,nums[i]/k,nums[i]), 这个三元的数量就是 _ 的数量，而这个 _ 的数量就是hash1[nums[i]/k]

#include <iostream>
#include <unordered_map>

using namespace std;

const int maxn = 2e5 + 10;

int nums[maxn];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
    }
    using ll = long long;
    ll res = 0;
    unordered_map<int, ll> hash1, hash2;
    for (int i = 1; i <= n; ++i) {
        if (nums[i] % k == 0) {
            res += hash1[nums[i] / k];
            hash1[nums[i]] += hash2[nums[i] / k];
        }
        hash2[nums[i]]++;
    }
    cout << res;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int N, K;
long long A[200010];
map<long long, int> pre, suf;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 1; i <= N; i ++) {
        cin >> A[i];
        suf[A[i]] ++;
    }
    long long ans = 0;
    for (int i = 1; i <= N; i ++) {
        suf[A[i]] --;
        if (A[i] % K == 0)
            ans += 1ll * pre[A[i] / K] * suf[1ll * A[i] * K];
        pre[A[i]] ++;
    }
    cout << ans;
    return 0;
}

C# 代码

public class Solution {
    public int MinExtraChar(string s, string[] dictionary) {
        int n = s.Length;
        HashSet<string> set = dictionary.ToHashSet<string>();
        int[] cache = new int[n];
        Array.Fill(cache, -1);
        return DFS(n - 1);

        int DFS(int i){
            if (i < 0) return 0;
            if (cache[i] != -1) return cache[i];
            cache[i] = DFS(i - 1) + 1;
            for (int j = i; j >= 0; j--){
                string t = s.Substring(j, i - j + 1);
                if (set.Contains(t)){
                    cache[i] = Math.Min(cache[i], DFS(j - 1));
                }
            }

            return cache[i];
        }
    }
}

C# 代码

public class Solution {
    private static int[] result = new int[1010];

    static Solution(){
        for (int i = 1; i <= 1000; i++){
            char[] ch = (i * i).ToString().ToCharArray();
            result[i] = result[i - 1] + (DFS(ch, i, 0, 0) ? i * i : 0);
        }

        bool DFS(char[] ch, int x, int index, int sum){
            if (index == ch.Length){
                return sum == x;
            }

            int t = 0;
            for (int i = index; i < ch.Length; i++){
                t = t * 10 + ch[i] - '0';
                if (DFS(ch, x, i + 1, sum + t)) return true;
            }

            return false;
        }
    }

    public int PunishmentNumber(int n) {
        return result[n];
    }
}

dfs 二进制枚举

dfs

很多值得学习的地方，很多细节

#include <bits/stdc++.h>

using namespace std;

const int N = 11, INF = 0x3f3f3f3f;

char str[N];
int res = INF;

bool check(int x)
{
    int t = (int)sqrt(x);//强制转换，可能是浮点数
    return x && t * t == x;//x>0很关键
}

void dfs(int u, int t, int s)
{
    if (!str[u]) {//枚举到字符串最后一位
        if (check(s)) res = min(res, t);
        return;
    }

    //t和t+1的理解：
    //t表示在当前位置不再删除新的数字
    //t + 1表示在当前位置删除一个新的数字

    dfs(u + 1, t + 1, s);//分割出完全平方数，s不变
    if (s || str[u] != '0') //!= '0'避免前导零
        dfs(u + 1, t, s * 10 + str[u] - '0');

    //两个dfs递归函数参数t的理解、
    //思路是反向的，因为不是删数，而是添数（如果是正向，删除任意一位数字不好删）
    //如果s不变，那就是相当于删去一个数字，所以t+1
    //如果s变，那就是相当于数字不变，所以是t
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        scanf("%s", str);
        res = INF;//每组测试数据res要重置
        dfs(0, 0, 0);//搜索到第几位数字，已经删除了t个完全平方数，删除数字后的数字之和s
        if (res == INF) puts("-1");
        else cout << res << endl;
    }

    return 0;
}

二进制枚举

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        string str;
        cin >> str;
        int n = str.size();

        int res = INF;
        for (int i = 0; i < 1 << n; i ++ ) 
        {
            int x = 0;
            for (int j = 0; j < n; j ++ ) 
                if (i >> j & 1) 
                    x = x * 10 + str[j] - '0';

            int t = sqrt(x);                    //从 size_t 转换成整型
            if (x && t * t == x) res = min(res, n - (int)to_string(x).size());
        }   //减去的数字个数等于总的数字个数-添的数字个数
        if (res == INF) res = -1;
        cout << res << endl;
    }

    return 0;
}

长文警告,如引起不适自行略过

提醒:本文需要掌握树状数组作为前置知识,不懂的小伙伴可以先学再来看

tips:对于lis类问题(最长上升子序列模型),树状数组yyds好吧,必须吹爆,文末附ac代码

本文力求以最通俗易懂的方式,让大家理解用树状数组解决lis类问题的实现逻辑

想要理解这种方式,核心就在于编号(下标)数组,以下统称b数组

记a数组为给定序列,f[i]表示以位于下标i上的数为结尾的最长上升子序列的长度

我们不妨先简单化,用树状数组解决最基本的lis模型

给定序列a[],且a[]中无重复元素,求单调上升子序列的最大长度

对于一个序列{1, 4, 2, 8, 5},要求按序将此序列变为单调上升序列

操作步骤如下:

对于原序列的下标(b数组)的变化:

如果拥有排序后的b数组,就能遍历b数组按照对应的值将a数组排好序

遍历b数组过程中,假定当前为第i个数,数值为b[i],对应于a数组中的值a[b[i]]

则a[b[i]]大于前面已经遍历过的所有数a[b[j]],j从1~i-1

符合升序条件后,只需知道下标位置在当前数a[b[i]]前,即满足b[j]<b[i],j从1~i-1的数对应的f[b[j]]

取满足条件的f[b[j]]的最大值+1,即为以当前数结尾的最长上升子序列的长度f[b[i]]的值

树状数组的结点存的是以该结点为下标的f数组的值,维护的是前缀区间的最大值

待解决的问题:

1:如何求得排序后的b数组

2.如何维护树状数组并插入结点信息

问题1:

初始化b数组时令b[i]=i,自定义排序规则,针对lis模型为a[x]<a[y],不同问题排序规则有异

x和y为规则函数所需参数,二者皆为b数组的值,利用sort函数结合排序规则对b数组排序

问题2:

对于树状数组求区间和的模版,修改加号为max函数即可

为什么这么做能得到f数组的值?

当前已遍历的数a[b[j]] < a[b[i]],j从1到i-1,未遍历的数a[b[k]] > a[b[i]],k从i+1到n

注意f数组的定义,未遍历的数不管位于当前数前面还是后面,都无法同时满足两个条件

即小于a[b[i]]且位于a[b[i]]前,因此不会对f[b[i]]贡献答案

而对于已遍历的数,我们维护的树状数组可以查到f[b[i]]-1的最大值,算上自身(+1)即为f[b[i]]的值

其实树状数组的作用很好理解,我们想知道小于当前数且位于当前数前面的数对应的f的最大值

树状数组每个结点就对应每个数的f值,利用树状数组的性质和max函数就能得到我们想要的结果

细节说明:

对于当前数b[i],先查询再更新,因为当前数未插入到树状数组中,可直接用当前值查询

用查询到的值+1更新f[b[i]],再加f[b[i]]的值存到树状数组中的结点b[i]中

根据f数组的定义,最后的答案是取f[i]的最大值,i从1~n

可能存在的疑惑:

b数组的值是a数组排序前的下标,但是值的顺序是a数组排序后的下标顺序

可理解为b数组为a数组的一个映射关系,排序不会改变这种映射关系,但是会改变先后顺序

可自行举例或结合上文第二张图理解,一定要揣摩清楚不然容易懵

上文解决无重复元素求lis问题,加入重复元素会有何影响?

加入重复元素后,排序后相等元素的下标在b数组中位置会挨在一起

由于树状数组维护的是前缀区间的最大值,相等元素的前一个数修改后,会影响后一个数查询结果

即可能存在前一个数更新前缀的最大值,然后被后一个数查询到再次+1

那么相同数被加了两次,不再满足上升子序列的条件,而是不降序子序列

我们只需对排序规则稍作修改,若数值相等以下标较大为排序条件即可解决此隐患

举个例子,有两个相同元素4,在b数组中的值为5和7,即a[5] = a[7] = 4

按照排序规则排好序后,遍历b数组时,先遇到b[i]=7的情况,再遇到b[i]=5

由于7比5先遍历,查询7的前缀[1,7]的f最值时并无结点5的信息,因此不受影响

而5比7后,查询5的前缀[1,5]的f最值时不会包含结点7的信息,故而能做到互不影响

若要求最长的不降序子序列的长度呢?

结合上文所述,只要让重复元素间必然影响即可,即若两数相等时,以下标较小为规则排序

若还要求最长降序子序列的长度呢?

和上文所述lis模型定义的排序规则对称,以a[x]>a[y]为条件,x和y为b数组的值

其他要求方法类似,调整排序规则即可,读者可自行揣摩,这里不再过多赘述

对于利用树状数组求解lis模型的AC代码

https://www.acwing.com/activity/content/code/content/6108491/

弄明白b数组和排序规则,算是基本掌握树状数组求lis问题的方法

可试着用此类方法解决下面几道题目:

https://www.acwing.com/problem/content/790/
https://www.acwing.com/problem/content/898/
https://www.acwing.com/problem/content/3665/

对于本题的分析

求最长不降子序列就不说了,问题在于修改连续k个数后怎么在原来基础上求最大长度

先定义g[i]为以a[i]开头的最长不降子序列的长度,f[i]为以a[i]结尾的最长不降子序列的长度

若要修改连续k个数,可以想到存在三种情况贡献答案:

情况一:k + g[i], (i > k)

情况二:f[i] + k, (i + k <= n)

情况三:f[i] + k + g[j], (j - i > k且a[i] < a[j])

答案就是这三种情况的最大值

f数组结合上文所说求解不难,但是g数组的求解则会存在一些问题

结合g数组的定义,查询时要知道后缀区间的最大值才能更新g数组

但树状数组只能维护前缀的信息,且无法通过整个区间最值和前缀区间最值推出后缀区间最值

我们可以取b数组的对称值作为当前数的插入结点更新树状数组,很好的解决这个问题

如1的对称位置为n,2的对称位置是n - 1,i的对称位置就是n + 1 - i,开一个c数组,c[i] = n + 1 - i

那么原先求后缀区间的最值就转化成求前缀区间的最值,树状数组又可担此重任

求g数组时还需要倒序遍历c数组,所求的值才是正确的,并且注意当前位置是对称后的位置

更新的g数组的下标应该是n + 1 - c[i],而插入树状数组的结点则还是c[i],这里需要仔细揣摩

对于第三种情况:

若完全理解求解f和g数组的过程,那么第三种情况就是查询比当前下标小m+1的结点的前缀最值

枚举g[j]的位置应查询满足条件的f[i]的最值, (j - i > k且a[i] < a[j])

若枚举f[i]的位置,则应与求解g[j]同样的遍历方式和对称关系查询满足条件g[j]的最值

感悟:

花费很长时间终于把题解写完了,删删改改很多,虽然尽量精炼语言,但可能还是很多废话hh

从遇到此题到顺利ac中间也隔着很长时间,习惯y总讲都懒得看题解,y总不讲都没啥动力做

感觉其中的细节确实不容易想,本人也是调了很久代码才ac,归根结底对这种方法没有理解透彻

写这篇题解就是想分享一下这种方法,帮助大家学习,至少不会和我一样想很久浪费时间

当然求b数组的思想一些题中也可用到,至少我遇到过然后用的这种方法ac,还是有一定学习价值

若看到最后,首先非常感谢对本文及本人的支持,学习算法的过程固然痛苦,但好在有你我相伴,一起加油!

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>

#define ri register int
#define lowbit(x) (x&(-x))

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], b[N], c[N];
int t[N], f[N], g[N];
int ans, tmp;

bool cmp(ri x, ri y)
{
    if(a[x] != a[y]) return a[x] < a[y];
    return x < y;
}

void modify(ri k, ri x)
{
    while(k <= n)
    {
        t[k] = max(t[k], x);
        k += lowbit(k);
    }
}

int query(ri k)
{
    ri res = 0;
    while(k)
    {
        res = max(res, t[k]);
        k -= lowbit(k);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(ri i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        b[i] = i;
    }

    sort(b + 1, b + n + 1, cmp);
    for(ri i = 1; i <= n; ++ i) c[i] = n + 1 - b[i];

    for(ri i = 1; i <= n; ++ i)      //f[i]表示以a[i]结尾的最长不下降子序列长度
    {
        ri pos = b[i];
        f[pos] = query(pos) + 1;
        modify(pos, f[pos]);
        tmp = 0;
        if(pos + m <= n) tmp = m;    //结尾后k个数变为子序列一部分 f[i] + k
        ans = max(ans, f[pos] + tmp);
    }

    memset(t, 0, sizeof t);

    for(ri i = n; i; -- i)           //g[i]表示以a[i]开头的最长不下降子序列长度
    {
        ri pos = c[i], loc = n + 1 - pos;
        g[loc] = query(pos) + 1;
        modify(pos, g[loc]);
        tmp = 0;
        if(loc - m >= 1) tmp = m;    //开头前k个数变为子序列的一部分 k + g[i]
        ans = max(ans, g[loc] + tmp);
    }

    memset(t, 0, sizeof t);

    for(ri i = 1; i <= n; ++ i)      //开头和结尾中间k个数变为子序列一部分 f[i] + k + g[j] (a[i] <= a[j])
    {
        ri pos = b[i];
        if(pos > m + 1)
        {
            tmp = query(pos - m - 1);
            ans = max(ans, tmp + m + g[pos]);
        }
        modify(pos, f[pos]);
    }

    cout << ans << endl;

    return 0;
}

原题链接：https://codeforces.com/contest/1833/problem/F
滑动窗口+乘法逆元
答题要求:取m个数, 不能重复, 任意数差的绝对值小于m；
解题思路:m个不重复的数绝对值差值均小于m，即m个整数是连续的，找到有多少种情况

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#define int long long 
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
int w[N];
int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --)
    {
        int n, m;
        cin >> n >> m;
        map<int, int> s;
        for(int i = 1; i <= n; i ++)
        {
            cin >> w[i];
            s[w[i]] ++; 
        }
        sort(w + 1, w + n + 1);
        int cnt = unique(w + 1, w + n + 1) - w - 1;//unique去除一个元素相邻元素的重复元素，所以要在排序后使用 
        int res = 0, k = 1;//数的个数的积 
        int l = 0;//判断连续的数的个数 
        w[0] = w[1] - 1;
        for(int i = 1; i <= cnt; i ++)
        {
            if(w[i] == w[i - 1] + 1)
            {
                l ++;
                k =k * s[w[i]] % mod;
                if(l > m)  
                    k =k * qmi(s[w[i - m]], mod - 2, mod) % mod;//乘法逆元，因为只需要个m数 
            }
            else k = s[w[i]], l = 1; 
            if(l >= m) res = (res + k) % mod;
        }
        cout << res << '\n';
    }
    return 0;
}