11012: 【原1012】增长率问题

题目描述

author: 刘勤原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1012

Description

有一个数列，它是由自然数组成的，并且严格单调上升。最小的数不小于S，最大的不超过T。现在知道这个数列有一个性质：后一个数相对于前一个数的增长率总是百分比下的整数（如5相对于4的增长率是25%，25为整数；而9对7就不行了）。现在问：这个数列最长可以有多长？满足最长要求的数列有多少个？

Input Format

输入仅有一行，包含S和T两个数（ \( 0 < S < T \leq 200000 \) ）。

30%的数据，\( 0 < S < T \leq 100 \) ；

100%的数据，\( 0 < S < T \leq 200000 \)。

Output Format

输出有2行。第一行包含一个数表示长度，第二行包含一个数表示个数。

Sample Input

2 10

Sample Output

5
2

样例解释

2 4 5 6 9以及2 4 5 8 10

FineArtz's solution

/* 增长率问题 */
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector<int> CanInc[200005];
int len[200005] = {0};
long long tms[200005] = {0}, cnt[200005] = {0};
//f[i]表示以i结尾的最长序列长度，tms[i]表示以i结尾的最长序列的个数，cnt[i]表示长度为i的序列数

/*void PreTreatment(int s, int t){
    for (int i = s; i != t; ++i)
        for (int p = 1; p <= 99; ++p){
            if (trunc(s * p * 0.01) == (s * p / 100))
                CanInc[i].push_back(p);
        }
}
*/
int main(){
    int s, t;
    cin >> s >> t;
    for (int i = s; i <= t; ++i){
        len[i] = 1;
        tms[i] = 1;
    }
    cnt[1] = t - s + 1;
    long long ans = 1;
    for (int i = s; i < t; ++i){
        for (int j = 1; j <= 100; ++j){
            if (i * j % 100 == 0){
                int next = i + i * j / 100;
                if (next > t) continue;
                if (len[next] == len[i] + 1){
                    tms[next] += tms[i];
                }
                else if (len[next] < len[i] + 1){
                    len[next] = len[i] + 1;
                    tms[next] = tms[i];
                }
                ans = (ans > len[next] ? ans : len[next]);
                cnt[len[i] + 1] += tms[i];
            }
        }
    }
    cout << ans << endl;
    cout << cnt[ans] << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstring"
#include "cstdio"
using namespace std;

long long dp_data[500009] = { 0 };
long long cal_num[500009] = { 0 };

long long dp(long long num, long long T) {
    if (dp_data[num] > 0)
        return dp_data[num];
    if (num > T) {
        return 0;
    }

    long long ans = 0;
    for (long long i = 1; i <= 100; ++i) {
        if (num * i % 100 == 0) {
            long long cur_ans = dp(num * i / 100 + num, T) + 1;
            ans = cur_ans > ans ? cur_ans : ans;
        }
    }
    for (long long i = 1; i <= 100; ++i) {
        if (num * i % 100 == 0) {
            if (dp_data[num + num * i / 100] + 1 == ans) {
                cal_num[num] += cal_num[num + num * i / 100];
            }
        }
    }
    if (ans == 1)
        cal_num[num] = 1;
    dp_data[num] = ans;
    return ans;
}

int main() {
    long long S, T;
    cin >> S >> T;

    long long ans = 0;
    for (long long i = S; i <= T; ++i) {
        long long cur_ans = dp(i, T);
        ans = cur_ans > ans ? cur_ans : ans;
    }

    long long cnt = 0;
    for (long long i = S; i <= T; ++i) {
        if (dp(i, T) == ans) {
            cnt += cal_num[i];
        }
    }

    cout << ans << endl << cnt;

    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 200007;
int d[maxn];
long long cnt[maxn], times[maxn];

int main() {

    int s, t;
    cin >> s >> t;
    memset(cnt, 0, sizeof(cnt));
    int tmp, ans = 1;
    cnt[1] = t - s + 1;

    for (int i = s; i <= t; ++i) d[i] = times[i] = 1;

    for (int i = s; i <= t; ++i) 
        for (int j = 1; j <= 100; ++j)
            if ((i*j)%100 == 0) {
                tmp = i + i * j / 100;
                if (tmp <= t) {
                    if(d[i] + 1 > d[tmp]) {
                        d[tmp] = d[i] + 1;
                        times[tmp] = times[i];
                    }
                    else if(d[i] + 1 == d[tmp]) times[tmp] += times[i];
                    ans = max(ans, d[tmp]);
                    cnt[d[i] + 1] += times[i]; 
                }
            } 
    cout << ans << endl << cnt[ans];    
    return 0;
}