头像

小熊饼干吃QQ




离线:11小时前


最近来访(294)
用户头像
TDS_
用户头像
不高兴的兽奶
用户头像
dxh
用户头像
Homie
用户头像
happyfeng
用户头像
真银铃
用户头像
王兆松
用户头像
dushucheng0901
用户头像
WA声闹彻明
用户头像
知足常乐_44
用户头像
su尔
用户头像
爱因斯坦的猫
用户头像
yohu
用户头像
Ddoo
用户头像
白纸elf
用户头像
Lansong
用户头像
NG1
用户头像
ynerz
用户头像
zhaoxiaoyun
用户头像
YzWait2-4YsZth


由于数组b是一个单调非减的数组,且a中相同元素对应b中位置也相同,所以可以将a中某元素的第一次出现的位置和最后一次出现的位置之间当作一个段,在b的该段中,元素值相同,那么该问题化为一个简单的段合并问题,而两个相邻段之间可以+1或者保持不变,所以最终结果就是对2取 段个数-1的幂次。

该题为一个简单的段合并问题,而本题中段合并要求除该段外,没有任何元素与该段中的元素相同,所以得到最终段的过程就是在生成段过程中找到现有段中,具有最远终点(即最后一次出现)的元素的终点位置。

算法思路:
1. 首先保存各个元素的最后一次出现的位置d
2. 在段开始位置,定义终点e为第一个元素的终点e = d[a[idx]]
3. 从段开始到终点e进行遍历,将e更新为最远的终点,即e = max(e,d[a[idx]])
4. 直到遍历到e,说明当前段中所有的元素终点都已经被包括在当前段中,即一个最终段。
5. 如果到末尾则结束,否则转向2生成新的段。

时间复杂度O(n),空间复杂度O(n)

python 代码

n = int(input())
a = list(map(int,input().split()))
cnt = 1
idx = 0
d = dict(zip(a,range(n)))

while idx<n:
    e = d[a[idx]]
    while idx<=e:
        e = max(e,d[a[idx]])
        idx += 1
    if idx<n:
        cnt = (cnt<<1)%998244353
print(cnt)


活动打卡代码 AcWing 1912. 里程表

反过来构造这样有趣的数字,要注意 $x, y$ 都是 $1e16$ 的数据范围,要开 long long

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

using namespace std;
typedef long long LL;

LL cnt, x, y;
int main()
{
    cin >> x >> y;
    for (int len = 3; len <= 17; len ++ )
    {
        for (int i = 0; i <= 9; i ++ )
        {
            string str(len, '0' + i);
            for (int j = 0; j <= 9; j ++ )
            {
                if (i == j) continue;

                for (int pos = 0; pos < len; pos ++ )
                {
                    str[pos] = '0' + j;
                    LL tmp = 0;
                    for (int k = 0; k < len; k ++ ) tmp = tmp * 10 + str[k] - '0';
                    if (str[0] != '0' && tmp >= x && tmp <= y) cnt ++;
                    str[pos] = '0' + i;
                }
            }   
        }
    }
    cout << cnt << endl;
    return 0;
}


活动打卡代码 AcWing 1353. 滑雪场设计

由于山的高度0~100, 所以直接遍历山的最小高度:$i ∈ [0, 83]$

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

using namespace std;
const int N = 1010;
int n, a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int res = 1e8;
    for (int i = 0; i <= 83; i ++ )
    {
        int tmp = 0, l = i, r = i + 17;
        for (int j = 0; j < n; j ++ )
        {
            if (a[j] < l) tmp += pow(l - a[j], 2);
            else if (a[j] > r) tmp += pow(r - a[j], 2);
        }
        res = min(res, tmp);
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1944. 记录保存

将出现的三个字母,按从小到大排序后,重新拼接成字符串,然后计次。
需要注意如下这组数据,拼接的结果都是一样的,所以在拼接的时候,加入一些其他符号。

2
A AB C
AA B C

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

using namespace std;

int main()
{
    int n;
    cin >> n;
    unordered_map<string, int> mp;
    while (n -- )
    {
        string a, b, c;
        cin >> a >> b >> c;
        if (a > b) swap(a, b);
        if (a > c) swap(a, c);
        if (b > c) swap(b, c);
        mp[a + "-" + b + "-" + c] ++;
    }
    int res = 0;
    for (auto m : mp)
        res = max(res, m.second);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1351. 密码锁

#include <algorithm>
#include <iostream>

using namespace std;

int n, ans;
int w[7];

bool isClose(int a, int b)
{
    return abs(a - b) <= 2 || abs(a - b) >= n - 2;
}

bool check(int a, int b, int c)
{
    return (isClose(a, w[1]) && isClose(b, w[2]) && isClose(c, w[3])) ||
           (isClose(a, w[4]) && isClose(b, w[5]) && isClose(c, w[6]));
}

int main()
{
    cin >> n;
    for (int i = 1; i <= 6; i++)
        cin >> w[i];

    for (int a = 1; a <= n; a ++)
        for (int b = 1; b <= n; b ++)
            for (int c = 1; c <= n; c ++)
                if (check(a, b, c))
                    ans++;
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1883. 删减

题解代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

string s,t,res;

int main(){
    cin >> s >> t;
    int slen = s.size(),tlen = t.size();
    //一边添加一边判断
    for(int i = 0; i < slen; i++){
        res += s[i];
        //当添加到长度大于等于t字符串时,开始比较
        //每次从末尾向前匹配
        if(res.size() >= tlen && res.substr(res.size() - tlen, tlen) == t){
            //存在t字符串,则删除
            res.erase(res.begin() + res.size() - tlen, res.end());
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1902. 马拉松

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

using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;

int n;
PII q[N];
int res;

int dist(PII a, PII b)
{
    return abs(a.first-b.first) + abs(a.second-b.second);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >> q[i].first >> q[i].second;

    for (int i = 1; i < n; i ++ )
        res += dist(q[i - 1], q[i]);

    int ans = res;

    for (int i = 1; i < n - 1; i ++ )
        ans = min(ans, res - dist(q[i - 1], q[i]) - dist(q[i], q[i +1]) + dist(q[i - 1], q[i +1]));
    cout << ans <<endl;
    return 0;
}


活动打卡代码 AcWing 1824. 钻石收藏家

双指针, 先排序, 以当前$i$ 为柜子中最小的钻石, 求最多能放多少钻石

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

using namespace std;
const int N = 1e3 + 10;
int n, k, res;
int q[N];
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> q[i];
    sort(q + 1, q + n + 1);
    for (int i = 1; i <= n; i ++ )
    {
        int j = i + 1;
        int tmp = 1;
        while (j <= n && q[j] <= q[i] + k) tmp ++, j ++;
        res = max(res, tmp);
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1842. 牛奶桶

直接暴力枚举X,Y所有可能的桶数即可

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

using namespace std;

int main()
{
    int x, y, m;
    int res = 0;
    cin >> x >> y >> m;
    for (int i = 0; i <= m / x; i ++ )
    {
        for (int j = 0; j <= m / y; j ++ )
        {
            if (i * x + y * j <= m) res = max(res, i * x + y * j);
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 4403. 修剪灌木

找规律即可。

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

using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cout << max((n - i) * 2, (i - 1) * 2) << endl;
    }
    return 0;
}