Atcoder Regular 098 区间Pre=Xor Q询问区间连续K去最小值最小极差

用scanf("%s")就会WA..不知道为什么

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N = 3e5 + ;

int preE[N];

int preW[N];

string f;

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n;

        cin >> n;

        cin >> f;

        preE[] = preW[] = ;

        for (int i = ; i <= n; i++)

        {

                if (f[i - ] == 'W')

                {

                        preW[i] = preW[i - ] + ;

                        preE[i] = preE[i - ];

                }

                else

                {

                        preE[i] = preE[i - ] + ;

                        preW[i] = preW[i - ];

                }

        }

        ll anser = INT_MAX;

        ll now;

        for (int i = ; i <= n; i++)

        {

                now = preW[i - ] - preW[];

                now += preE[n] - preE[i];

                anser = min(anser, now);

        }

        cout << anser << endl;

        return ;

}

题意:

给你N个非负数(1e5) 要求你求出有多少个区间内区间和等于区间亦或和给的数小于2²⁰

解:

因为XOR操作中 0^0=0 1^1=0 0^1=1 如果两个数相加有进位操作的话肯定会损失值

所以我们把0特殊化直接暴力如果有位数重复的就不成立所以每次查询的区间长度不会超过20

复杂度为1e6左右

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N = 2e5 + ;

ll num[N];

int last = ;

int Left[N];

ll yihuo;

ll pre;

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n;

        cin >> n;

        ll anser = ;

        for (int i = ; i <= n; i++)

        {

                cin >> num[i];

                Left[i] = last;

                if (num[i])

                {

                        last = i;

                }

        }

        ll now;

        ll i, j;

        for (i = ; i <= n; i++)

        {

                yihuo = pre = num[i];

                for (j = Left[i]; j >= ;j = Left[j])

                {

                        yihuo = yihuo ^ num[j];

                        pre += num[j];

                        if (yihuo != pre)

                        {

                                break;

                        }

                }

                anser+=i-j;

        }

        cout << anser << endl;

        return ;

}

改进版:我们发现如果L-R区间是满足的那么 L - R 内任意一个子区间也是满足的即 L+1 - R 也行

所以每次取完极大满足条件的区间后当R右移一格时满足条件的L一定不会在前一个的左边

#include<bits/stdc++.h>

using namespace std;

int n;

long long s[];

long long a[];

long long ans;

int main(){;

    scanf("%d",&n);

    for (int i=;i<=n;i++){

        int x;

        scanf("%d",&x);

        s[i]=s[i-]+x;

        a[i]=a[i-]^x;

    }

    int l=;

    for (int r=;r<=n;r++){

        for (;(s[r]-s[l-])!=(a[r]^a[l-]);l++);

        ans+=r-l+;

    }

    printf("%lld\n",ans);

}

题意:

给你一个N个数(2000)的数列每次操作可以让长度为K的连续序列内的最小值去除你必须要去除Q次

假设这Q次中去除的最大的为X最小的为Y 问你X-Y最小可以是多少

解:

从1到N 枚举Y=A[i]

然后再找出全部原数列中可以删的不小于A[i]的数

如果找出的数的数目小于Q则不满足条件跳过反之则排序去第Q个减去A[i]即为一种的答案

总复杂度为N²LOGN

#include<bits/stdc++.h>

using namespace std;

int a[], b[], c[];

int n, k, q, ans;

int main()

{

        scanf("%d%d%d", &n, &k, &q);

        for (int i = ; i <= n; i++)

        {

                scanf("%d", &a[i]);

        }

        ans = 1e9 + ;

        for (int i = ; i <= n; i++) //枚举每个作为Y的a[i]

        {

                int l = ;

                int cnt = ;

                for (int j = ; j <= n + ; j++)

                        if (a[i] > a[j])

                        {

                                if (!l) //如果前面没有比a[i]大的 先跳过

                                {

                                        continue;

                                }

                                int r = j - ; //这样L到R区间内所有数都是不小于a[i]的

                                for (int p = l; p <= r; p++)

                                {

                                        b[p] = a[p];

                                }

                                sort(b + l, b + r + );

                                for (int p = l; p + k -  <= r; p++)  //L到R区间内得有不小于K数目的数

                                {

                                        c[++cnt] = b[p]; //把能删的最小的都删掉

                                }

                                l = ;

                        }

                        else if (!l) //枚举到不小于a[i]的

                        {

                                l = j;

                        }

                if (cnt < q)

                {

                        continue;

                }

                sort(c + , c + cnt + );

                //printf("%d\n",c[q]);

                ans = min(ans, c[q] - a[i]);

        }

        printf("%d\n", ans);

}

巴特西

Atcoder Regular 098 区间Pre=Xor Q询问区间连续K去最小值最小极差

最新文章

热门文章