B:
题目大意:你将得到一个整数数组a1,a2,,ana_1,a_2,…,a_n

如果可以从a中移除一些元素以获取b,则将数组b称为数组a的子序列。

如果数组b1,b2,bkb_1,b_2,\dots b_k不为空,并且对于每个i(1ik)i(1 \le i \le k)bib_i都可以被ii整除。

则认为此数组可行。

求有多少个可行的子序列,答案对于109+710^9+7整除.

如果子序列中包含的数字的下标不同,则认为这两个子序列不同。也就是说,在比较子序列时,元素的值并不重要。需要注意的是,数组a正好有2n12^n−1个不同的子序列(不包括空的子序列)。 $n \leq 10^5 $且 ai106a_i \leq 10^6

题解:考虑dp[i]dp[i] 表示 子序列长度为ii时的方案数。那么我们对于每个数xx,尝试分解他的因子。 当某个因子jxj \mid x说明对于长度jj把x放到最后是可行的。
那么dp[j]+=dp[j1]dp[j] += dp[j-1] 最后再统计一下答案

#include <bits/stdc++.h>
#define pa pair<ll, ll>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const ll INF = 0x3f3f3f3f;
const ll N = 1e6 + 5;
const ll p = 1e9 + 7;
ll dp[N];
vector<ll> v;
int main() {
#ifdef INCTRY
    freopen("input.txt", "rt", stdin);
#endif
    ll n;
    read(n);
    ll ti = 0;
    dp[0] = 1;
    for(ll i = 1; i <= n; i++) {
        int x;
        read(x); v.clear();
        for(int j = 1; j <= sqrt(x); j++) {
            if(x % j == 0) {
                v.push_back(j);
                if(j * j != x) v.push_back(x / j);
            }
        }
        sort(v.begin(), v.end());
        for(int j = v.size() - 1; j >= 0; j--) {
            dp[v[j]] = dp[v[j]] % p + dp[v[j] - 1] % p;
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = ans % p + dp[i] % p;
    }
    cout << ans;

#ifdef INCTRY
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

现在有nn个电视节目你想看。假设整个时间被分成相等的部分,称为"分钟"。第ii个节目的播放时间是从第li分钟到第ri分钟,包括播放结束部分。

你可以在一台电视来观看一个电视节目,但不能在同一台电视上看两个同时播放电视节目,因此你可能在几分钟内需要用多台电视。例如,如果片段[liri][l_i,r_i][ljrj][l_j,r_j]的播放时间有所交叉,那么一台电视就不能同时观看i和j这两个节目。

一旦你开始在某台电视上观看某个节目,就不可能"移动"注意力到另一台电视上(因为这样太分散注意力了),同时你也不可能在该节目结束之前,在同一台电视上观看另一个节目。

你附近有一家电视出租店。它出租一台电视机,租借费用为x元。并按照每额外多一分钟,收取x(y<x)x(y<x)元进行计费。因此,为了租用电视[a,b][a,b]分钟,你需要支付x+y×(ba)x+y \times (b−a)元。

假设租用和收看电视不会超出规定时间,也不会分散你看其他电视节目的注意力。计算出观看所有节目可能的最低费用。由于该值可能太大,请将答案模109+710^9+7输出。

n<=105n <= 10^5
1y<x1051 \leq y < x \leq 10^5

考虑贪心,需要新租一个电视机时,只有当等待花费的时间 >x+y[a[i].ra[i].l]> x + y * [a[i].r - a[i].l]
我们先讲节目排序,以ll为第一关键字从小到大排序
所以维护一个set,存档当前正在租的电视机的结束时间。当我们到了一个电视节目,当我们考虑第二分查找一个电视机的结束时间使得他小于当前电视节目的开始时间,且最大。 用set的lower_bound函数。 然后判断是否要新租一台电视,很显然贪心是对的。

#include <bits/stdc++.h>
#define pa pair<ll, ll>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const ll INF = 0x3f3f3f3f;
const ll N = 1e5 + 5;
const ll p = 1e9 + 7;
set<int> s;
bool cmp(node a, node b) {
    if(a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}
ll n,x,y;
ll dp[N];
int main() {
#ifdef INCTRY
    freopen("input.txt", "rt", stdin);
#endif
    read(n); read(x); read(y);
    ll d = 0;
    for(ll i = 1; i <= n; i++) {
        read(a[i].l); read(a[i].r);
    }
    sort(a + 1, a + n + 1, cmp);
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!s.empty()) {
            auto it = s.lower_bound(a[i].l);
            if(it == s.begin()) {
                ans = ans % p + x + (a[i].r - a[i].l) * y % p; 
                s.insert(a[i].r); continue;
            }
            it--;
            if(*(it) < a[i].l && (a[i].r - *(it)) * y  < (a[i].r - a[i].l) * y + x) {
                ans = ans % p + (a[i].r - *(it)) * y % p;
                s.erase(it);
            }
            else {
                ans = ans % p + x + (a[i].r - a[i].l) * y % p;
            }
            s.insert(a[i].r);
        } else {
            ans = ans % p + x + (a[i].r - a[i].l) * y % p;
            s.insert(a[i].r);
        }
    }
    cout << ans % p;
#ifdef INCTRY
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}