Editorial for Bài toán số 7


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 1000006;
using namespace std;
char s[N];
int cnt[N];

int main() {
    scanf("%s", s);
    int n = strlen(s);
    int j, max7 = 0;
    for(int i = 0; i < n; i = j + 1) {
        j = i;
        if (s[i] == '7') {
            for(j = i; j < n - 1 && s[j + 1] == '7'; j++) ;
            for(int k = 1; k <= j - i + 1; k++)
                cnt[k] += j - i + 2 - k;
            max7 = max(max7, j - i + 1);
        }
    }
    for(int i = 1; i <= max7; i++)
        printf("%d %d\n", i, cnt[i]);
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<vector>
#define MAX   1000100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
class BIT {
    private:
    int n;
    vector<int> v;
    public:
    BIT() {
        n=0;
    }
    BIT(int n) {
        this->n=n;
        v.assign(n+7,0);
    }
    void update(int x,int d) {
        if (x<1 || x>n) return;
        for (;x<=n;x+=x&-x) v[x]+=d;
    }
    int get(int x) const {
        if (x<1 || x>n) return (0);
        int res=0;
        for (;x>=1;x&=x-1) res+=v[x];
        return (res);
    }
};
BIT bit;
char s[MAX];
int n;
void process(void) {
    scanf("%s",s+1);
    n=strlen(s+1);
    bit=BIT(n);
    int len=0;
    FOR(i,1,n) {
        len=s[i]=='7'?len+1:0;
        if (len<1) continue;
        bit.update(len+1,-1);
        bit.update(1,1);
    }
    FOR(i,1,n) {
        int t=bit.get(i);
        if (t<1) return;
        printf("%d %d\n",i,t);
    }
}
int main(void) {
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.