尺取

HDU 5806 NanoApe Loves Sequence Ⅱ

Posted on

垃圾题!!!!!!

首先我在此表示,我怀疑整个网上的题解和题目都是错的!!!!!!!

我的个人理解包括所有网上的题解都说的是这样的题意:

满足区间中第k大的数必须大于等于 m 的数量。

恩,感觉不是很好想,觉得终于碰到了难一点的题目了。脑子拙劣的我还想到快排求序列第k大去了……

后来看了题解,很多题解,题意跟我想的是一个意思。但他们的题解都是这么说的。只要一个序列,大于等于m的数量大于等于k,那么这个数列必定符合要求……………………

mather fucker ????

那我小于m的数字无穷多怎么办????

附上我个人认为正确理解的正确代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int n, m, k, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &k);
        each(i, n) scanf("%d", ary + i), ary[i] = ary[i] < m ? 1 : 0;
        int i = 0, j = 0, sum = 0;
        ll ans = 0;
        while (i < n) {
            while (sum < k && j < n)
                sum += ary[j++];
            if (sum == k)
                sum -= ary[--j];
            if (sum == k && j - i < k)
                break;
            ans += (j - i - 1);
            sum -= ary[i++];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

再附上网上的思路代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int n, m, k, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &k);
        each(i, n) scanf("%d", ary + i), ary[i] = ary[i] < m ? 0 : 1;
        int l = 0, r = 0, sum = 0;
        ll ans = 0;
        while (l < n) {
            while (sum < k && r < n)
                sum += ary[r++];
            if (sum < k)
                break;
            ans += (n - r + 1);
            sum -= ary[l++];
        }
        printf("%lld\n", ans);
    }
    return 0;
}
尺取

HDU 5672 String

Posted on

这道题是之前POJ这道题的弱化版本。

这应该是第五道尺取了吧,有点感觉了。

只要看出尺取可做,就是水题。

题意:
给你一个字符串,问你有多少个子串至少含有k个不同的字母。

思路:
恩。因为字符串的元素全都是字母,也就是上面poj里将数字限制在里0~25,是一样的做法。
但是这道题并没有要求最少,也就是一旦一个字符串符合要求,往后的所有子串都符合要求。累加即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

char str[maxn];
int num[30];

int main()
{
    int T, k;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %d", str, &k);
        int len = strlen(str), ch_num = 0;
        ll ans = 0;
        fill(num, 0);
        for (int i = 0, j = 0; i < len; i++) {
            while (ch_num < k && j < len) {
                if (num[str[j++] - 'a']++ == 0)
                    ch_num++;
            }
            if (ch_num < k)
                break;
            ans += (len - j + 1LL);
            if (--num[str[i] - 'a'] == 0)
                ch_num--;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
尺取

HDU 5328 Problem Killer

Posted on

哇,又是一道水题……
还是说数据太水???
老实说我自己写的时候都没什么自信……

特么居然直接A了

题意:
找出最长的等差序列或者等比序列。输出长度。

思路:
本来就是一道水题,但是尝试用着尺取去写。有点不是很自信。

但是尺取并不是最优的,当找到一个元素和已知序列不构成等差或者等比数列的时候,可以直接跳转到那个位置另外开始判断,这样,时间大概会降低一半左右。

注: 只有一个元素的时候最好特判一下

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        each(i, n) scanf("%d", ary + i);
        ary[n] = ary[n + 1] = inf;
        int d = ary[1] - ary[0], dj = 1, qj = 1, ans = 1;
        double q = 1.0 * ary[1] / ary[0];
        each(i, n)
        {
            while (ary[dj + 1] == ary[dj] + d && dj < n)
                dj++;
            while (ary[qj + 1] == ary[qj] * q && qj < n)
                qj++;
            ans = max(ans, dj - i + 1);
            ans = max(ans, qj - i + 1);
            if (i + 1 == dj) {
                d = ary[i + 2] - ary[i + 1];
                dj++;
            }
            if (i + 1 == qj) {
                q = 1.0 * ary[i + 2] / ary[i + 1];
                qj++;
            }
        }
        printf("%d\n", n == 1 ? 1 : ans);
    }
    return 0;
}
尺取

POJ 3220 Jessica’s Reading Problem

Posted on

尺取法第三题,读题好烦……直接找了一个题解把中文意思拿来了。

感觉还是挺简单的,但是用了map费了点时间。500+ ms ,如果用hash估计可以降低很多……

题意:
给你一串序列,可能有很多相同元素,要你求最短的连续序列,使得这个序列包含整个序列中的所有元素。

思路:
set+map+尺取。因为数据范围在int内,开数组记录不实际,必须得用hash做,用map偷了个懒。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

set<int> key;
map<int, int> num;

int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        key.clear(), num.clear();
        each(i, n) scanf("%d", ary + i), key.insert(ary[i]);
        unsigned sz = key.size(), ans = inf;
        key.clear();
        for (int i = 0, j = 0; i < n; i++) {
            while (key.size() < sz && j < n) {
                num[ary[j]]++;
                key.insert(ary[j++]);
            }
            if (key.size() < sz)
                break;
            ans = min((unsigned)j - i, ans);
            if (--num[ary[i]] == 0)
                key.erase(ary[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}
尺取

CodeForces 231C To Add or Not to Add

Posted on

昨天比赛的尺取题,稍微看了一下尺取算法的原理就很好理解了。

貌似可用尺取法解决的问题,二分都可以做,在复杂度上就不清楚了……

一开始也是想用二分的,感觉有点难想……

不过老实说,这道尺取对我现在来说还有有点难想到需要排序尺取……

题意:
给你很多桶水,再给你一缸水,要你从一缸水中将水补给到其他水桶中,要求相同水量的数目最多,在此条件下,水量最少。

思路:
若要水量相同,同时花费最少,那么显然在差距最小的水桶间加水。所以排序+尺取。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int n, k;
    ll sum = 0;
    pair<int, int> ans = make_pair(0, 0);
    scanf("%d %d", &n, &k);
    each(i, n) scanf("%d", ary + i);
    sort(ary, ary + n);
    for (int i = 0, j = 0; i < n; i++) {
        sum += ary[i];
        while ((i - j + 1LL) * ary[i] - sum > k)
            sum -= ary[j++];
        if (ans.second < i - j + 1LL)
            ans = make_pair(ary[i], i - j + 1LL);
    }
    printf("%d %d\n", ans.second, ans.first);
    return 0;
}
尺取

POJ 3061 Subsequence

Posted on

感觉新生什么都会系列?
火星系列?

反正很早之前是知道尺取法的,在华农那场有道题可以用尺取,但是我用非尺取写了,就没有去多管……

这次算是又踩到了以前留下来的坑。

尺取法的简单介绍

关于尺取,简单介绍一下,与其说是算法,不如说是一种思维,其适用范围为设定上下限连续最优序列问题.

看其他博主都说这是一种类似于毛毛虫爬行的算法。其实就是用两个指针维护一个连续序列,在每次爬行(就是增加元素)的过程中,不断让这个序列尽可能的满足要求。

对于可用尺取法解决的问题,一般都不会直接让我们求连续序列,需要排个序转化一下。

复杂度为 O(n)

题解

题意:
给你一个序列,要你求最短的连续序列,其和不小于给定数字 m 。

思路:
每次增加前一个元素的同时,不断减少后面的元素使的该序列最短。

AC Code

#include <algorithm>
#include <cstdio>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int ary[maxn];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        each(i, n) scanf("%d", ary + i);
        ll sum = 0, ans = inf;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && sum < m)
                sum += ary[j++];
            if (sum < m)
                break;
            ans = min(ans, (ll)j - i);
            sum -= ary[i];
        }
        printf("%lld\n", ans == inf ? 0 : ans);
    }
    return 0;
}