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.
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