NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	2ms	452 KiB
#2	Accepted 5	2ms	404 KiB
#3	Accepted 5	1ms	508 KiB
#4	Accepted 5	1ms	452 KiB
#5	Accepted 5	2ms	404 KiB
#6	Accepted 5	2ms	452 KiB
#7	Accepted 5	30ms	1.2 MiB
#8	Accepted 5	29ms	1.2 MiB
#9	Accepted 5	2ms	404 KiB
#10	Accepted 5	2ms	404 KiB
#11	Accepted 5	30ms	1.1 MiB
#12	Accepted 5	30ms	1.1 MiB
#13	Accepted 5	2ms	408 KiB
#14	Accepted 5	2ms	404 KiB
#15	Accepted 5	38ms	1.2 MiB
#16	Accepted 5	28ms	1.1 MiB
#17	Accepted 5	2ms	404 KiB
#18	Accepted 5	2ms	404 KiB
#19	Accepted 5	30ms	1.2 MiB
#20	Accepted 5	30ms	1.2 MiB

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 114;
int T, n, cnt, ans, tot;
char s1[N], s2[N], t1[N], t2[N];

int bel[N];
int n0[N], n1[N];
int ll[N], rr[N];

void solve(int l, int r, int m0, int m1)
{
    // cout << l << " " << r << " " << m0 << " " << m1 << "  :  ";
    int res = 0;
    for(int i = bel[l]; i <= bel[r]; i = i + 1)
    {
        int r0 = 0, r1 = 0;
        r0 = min(m0, n0[i]), r1 = min(m1, n1[i]);
        if(i == bel[l])
        {
            int ml = rr[i] - l + 1;
            if(r0 + r1 > ml)
            {
                int cha = r0 + r1 - ml;
                if(r0 >= cha)
                    r0 -= cha;
                else
                    r1 -= (cha - r0),
                    r0 = 0;
            }
        }
        if(i == bel[r])
        {
            int ml = r - ll[i] + 1;
            if(r0 + r1 > ml)
            {
                int cha = r0 + r1 - ml;
                if(r0 >= cha)
                    r0 -= cha;
                else
                    r1 -= (cha - r0),
                    r0 = 0;
            }
        }
        ans += r0;
        ans += r1;
        res += r0 + r1;
        m0 -= r0;
        m1 -= r1;
        n0[i] -= r0;
        n1[i] -= r1;
    }
    // if(m0 && m1)
    //     cout << " fuck \n";
    // cout << res << " !!!\n";
}

void solvedot(int w)
{
    ++ tot;
    solve(w, w, s1[w] == '0', s1[w] == '1');
    // if(s1[w] == '0' && n0[pos])
    //     n0[pos] --,
    //     ans ++;
    // if(s1[w] == '1' && n1[pos])
    //     n1[pos] --,
    //     ans ++;
}

signed main()
{
    freopen("edit.in", "r", stdin);
    freopen("edit.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T --)
    {
        cin >> n;
        for(int i = 1; i <= n; i = i + 1)
            cin >> s1[i];
        for(int i = 1; i <= n; i = i + 1)
            cin >> s2[i];
        for(int i = 1; i <= n; i = i + 1)
            cin >> t1[i];
        for(int i = 1; i <= n; i = i + 1)
            cin >> t2[i];
        ans = 0;
        tot = 0;
        cnt = 1;
        for(int i = 1; i <= n; i = i + 1)
        {
            if((t2[i] == '0' || t2[i - 1] == '0') && i != 1)
                cnt ++,
                ll[cnt] = i;
            if(s2[i] == '0')
                n0[cnt] ++;
            else
                n1[cnt] ++;
            bel[i] = cnt;
            rr[cnt] = i;
        }

        // for(int i = 1; i <= n; i = i + 1)
        //     cout << bel[i] << " ";
        // cout << "\n";
        // for(int i = 1; i <= cnt; i = i + 1)
        //     cout << n0[i] << " " << n1[i] << " $$\n";

        int l = 1, r = 0, w0 = 0, w1 = 0;
        for(int i = 1; i <= n; i = i + 1)
        {
            if(t1[i] == '0')
            {
                r = i - 1;
                if(l <= r)
                    solve(l, r, w0, w1);
                l = i + 1;
                w0 = 0;
                w1 = 0;
                solvedot(i);
            }
            else
            {
                w0 += (s1[i] == '0');
                w1 += (s1[i] == '1');
                if(i == n)
                    solve(l, n, w0, w1);
            }
        }
        cout << ans << "\n";
        for(int i = 1; i <= cnt; i = i + 1)
            bel[i] = n0[i] = n1[i] = 0;
    }
    return 0;
}

递交者: LN-0004
题目: NOIP2024A NOIP2024A
比赛: 【民间数据】NOIP2024 LN 批量测试
语言: C++14(O2)
代码长度: 3.2 KiB
递交时间: 2024-12-1 15:26:43
评测时间: 2024-12-1 15:33:10

分数: 100
总耗时: 265ms
峰值时间: 38ms
峰值内存: 1.2 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录