头像




离线:3小时前


最近来访(28)
用户头像
ssuunn
用户头像
itdef
用户头像
合计飞
用户头像
zombotany
用户头像
WanderOvO
用户头像
YottaByte_7
用户头像
VagrantAC
用户头像
剑过无声
用户头像
篮网
用户头像
用户头像
yxc
用户头像
asdfx
用户头像
__超
用户头像
嘶锅咦



1天前

区间最大子段和 可以用二分吗?
比如 -3 -2 3 -1 2 -4 1
区间最大子段和是 4 就是 3 -1 2
我知道On 就能做, 但是二分可以吗?
二分长度, 然后当前长度有正的子区间 就满足, 否则不满足
这样可以解决吗?





4天前

对于这个题 和HH的项链非常相似,但是稍微难点, 如果没有做HH的项链,先去做。再做这个题。
对于每个颜色记录前一个相同数字出现的位置。
对于每种颜色, 如果对答案有加成, 那么必须出现过两次, 所以我们就维护出现过两次。

1.png

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+5;

#define lowbit(x) ((x)&(-x))

int n, m, c;
int a[N], tr[N], ans[N], pre[N], ppre[N], b[N];

struct Node
{
    int l, r, id;
    bool operator < (const Node &t) const
    {
        return r < t.r;
    }
}p[N];

void add(int x, int val)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += val;
}

int query(int x)
{
    int ans = 0;
    for(int i = x; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main()
{
    cin >> n >> m >> c;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if(b[a[i]])
        {
            ppre[i] = b[a[i]];
        }
        b[a[i]] = i;
//      ppre[i] = pre[a[i]];
//      pre[a[i]] = i;
//      cout << ppre[i] << endl;
    }

    for(int i = 1; i <= c; i ++)
    {
        int l, r;
        cin >> l >> r;
        p[i] = {l, r, i};
    }
    sort(p + 1, p + 1 + c);

    int ll = 1;
    for(int i = 1; i <= c; i ++)
    {
        int l = p[i].l, r = p[i].r;
        for(ll; ll <= r; ll ++)
        {
            if(ppre[ll] == 0) continue; // ppre 表示当前位置之前出现的下标
            add(ppre[ppre[ll]]+1, 1);
            add(ppre[ll]+1, -1);
        }
        ans[p[i].id] = query(l);
    }
    for(int i = 1; i <= c; i ++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3828. 行走路径


5天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+5;

int T, n, m;
char g[1010][1010];
char lun[4] = {'Q', 'W', 'E', 'R'};
bool st[1010][1010];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int f[1010][1010];
bool is_inf = false;

int dfs(int x, int y)
{
    if(st[x][y])
    {
        is_inf = true;
        return -1;
    }
    if(f[x][y]) return f[x][y];
    st[x][y] = true;
    int now_id = -1;
    for(int i = 0; i < 4; i ++)
    {
        if(lun[i] == g[x][y])
        {
            now_id = i;
            break;
        }
    }

    int v = 1;
    for(int i = 0; i < 4; i ++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >=1 && nx <= n && ny>=1 && ny <= m && g[nx][ny] == lun[(now_id+1)%4])
        {
            v = max(v, dfs(nx, ny) + 1);
        }
    }
    st[x][y] = false;
    f[x][y] = v;
    return v;
}

int main()
{
//  cin >> n >> m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        scanf(" %s", g[i]+1);
    }

    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            int num = dfs(i, j);
            if(is_inf) break;
            if(g[i][j] == 'Q')
            ans = max(ans, num/4);
        }
        if(is_inf) break;
    }

    if(is_inf) puts("infinity");
    else if(ans == 0) puts("none");
    else printf("%d\n", ans);

    return 0;
}

/*
5 5
QWRQQ
QERQQ
QQQWQ
REEEQ
EWQRQ

*/
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3827. 最小正整数


6天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+5;

LL T, n, k;

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n >> k;
        LL num = pow(10 , k);
        LL now = __gcd(n, num);
        cout << n*num/now << endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3826. 青蛙跳


7天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+5;

int T;
LL a, b, k;

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> a >> b >> k;
        LL q = k/2;
        LL now = 0;
        if(k%2 == 0)
        {
            now = a*q - b*q;
        }
        else
        {

            now = a*(q+1) - b*q;
        }
        cout << now << endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3824. 在校时间


11天前
#include<bits/stdc++.h>
using namespace std;
int t,n,a[105];
int main(){
    cin>>t;
    while(t--){
        memset(a,0,sizeof(a));
        int ans=0;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)
            if(a[i-1]&&a[i+1]||a[i])ans++;
        cout<<ans<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 3824. 在校时间


11天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
int t,n,a[105];
int main(){
    cin>>t;
    while(t--){
        memset(a,0,sizeof(a));
        int ans=0;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)
            if(a[i-1]&&a[i+1]||a[i])ans++;
        cout<<ans<<endl;
    }
    return 0;
}

作者:yxc++
链接:https://www.acwing.com/solution/content/61998/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3823. 寻找字符串


30天前
//这里填你的代码^^
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1e6+6;

int ne[N], T, n;
bool st[N];

int main()
{
    cin >> T;
    while(T --)
    {
        memset(ne, 0, sizeof ne);
        string s;
        cin >> s;
        n = s.size();
        s = " " + s;

        for(int i = 2, j = 0; i <= n; i ++)
        {
            while(j && s[i] != s[j+1]) j = ne[j];
            if(s[i] == s[j+1]) j ++;
            ne[i] = j;
        }

        for(int i = 1; i <= n; i ++) st[i] = false;
        for(int i = 1; i < n; i ++) st[ne[i]] = true;

        int res = 0; 
        for(int i = ne[n]; i; i = ne[i])
        {
            if(st[i])
            {
                res = i;
                break;
            }
        }
        if(!res) puts("not exist");
        else
        {
            for(int i = 1; i <= res; i ++)
            {
                cout << s[i];
            }
            cout << endl;
        }
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3822. 食堂排队


30天前
//这里填你的代码^^
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1e5+5;

struct Node
{
    int l, r;
}tr[N];

int T, n;

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n;
        for(int i = 1; i <= n; i ++)
        {
            cin >> tr[i].l >> tr[i].r;
        }

        bool st[1001] = {false};
        int left = 1, time = 1;
        while(left <= n)
        {
            if(tr[left].l <= time && tr[left].r >= time )
            {
                cout << time << " ";
                time ++;
                left ++;
            }
            else if(tr[left].l > time)
            {
                time ++;
            }
            else if(tr[left].r < time)
            {
                cout << 0 << " ";
                left ++;
            }

        }
        cout << endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3821. 区间选数


30天前
//这里填你的代码^^
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1e5+5;

int T;

int main()
{
    cin >> T;
    while(T --)
    {
         int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    if(l1 != l2)
    cout << l1 << " " << l2 << endl;
    else
        cout << l1 << " " << l2 + 1 << endl;
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~