股票问题集合

股票问题汇总

股票问题，指给定一系列数列，可以在某些天以当天价格买入，也可以在某些天以当天价格卖出。

按照买卖规则，可以分为：
1. 不能进行多笔交易；买股票之前只能先把手上的股票卖出。一般此类题是dp。
2. 可以进行多笔交易；手里可以同时持有多只股票。一般要贪心。

股票问题的核心是发现如何使得手里的资产最多。

无论是哪种模型，都可以看成如果第二天价格更高就卖，大不了可以反悔（可以以这天的价格再把卖掉的股票再买回来）。

问题1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
int w[maxn], f[maxn][110][2];
int main()
{
    int n, k; scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    memset(f, 0xcf, sizeof f);
    for(int i = 0; i <= n; i++) f[i][0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            f[i][j][0] = max(f[i - 

【2017四川省赛/牛客】2017 Revenge【数论/指标】

传送门

题意是说给2e6个数，每个数都小于2017，从中选取一些数字使得乘积模2017等于给定的r，问方案数%2输出

DP，f[i][ja[i]%2017]=f[i-1][j]+f[i-1][ja[i]]，因为答案只需要奇偶，所以考虑异或操作。

不过这样的复杂度是2017n的。

考虑把乘法变成加法，5是2017的原根，并且2017是质数，剩余系是完全剩余系。所以把1-2016的指标存下来到I[]里面。

f[i][j+I[a[i]]]=f[i-1][j]+f[i-1][j+I[a[i]]]

可以把f开成一个bitset，f[i]表示第i个指标的方案数。所有的状态j每次加一个数I，就相当于循环左移了I位。再用异或滚动状态就可以了。

f^=(f<<I[a[i]])^(f(2016-a[i]))

#include<bits/stdc++.h>
using namespace std;
bitset<2016> f;
int a[2000002], I[2020];
int main()
{
    int n, r;
    int g = 1;
    for(int i = 1; i <= 2016; i++) 
    {
        g = g * 5 % 2017;
        I[g] = i;
    }
    // I[1] = 0;
    while(~scanf("%d%d", &n, &r))
    {
        f.reset();
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        f.set(0);
        for(int i = 1; i <= n; i++)
        {
            f 

【最短路/拆点】ACwing176

传送门

把每个点拆成100个点，分别表示到这个点的时候油量剩余的状态。跑最短路即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int p[maxn], val[maxn], e[maxn], pre[maxn], h[maxn], cnt;
void add(int u, int v, int w)
{
    e[cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt++;
}
struct Ver{
    int a, b, c;
    bool operator<(const Ver &W)const 
    {
        return c > W.c;
    }
};
int dis[1010][110];
bool vis[1010][110];
int dijkstra(int cost, int start, int end)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis,0, sizeof vis);
    priority_queue<Ver> pq;
    pq.push({start, 

【min_25筛】筛欧拉函数、莫比乌斯函数、积性函数

传送门：欧拉函数、莫比乌斯函数

花了一下午学了一下min25筛。

一知半解。不过还是学会了套板子。

mu函数要看成质数个数取反，在预处理g的时候不能带负数（我也不知道为什么）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
ll primes[maxn], cnt;
bool st[maxn];
ll sp1[maxn], sp2[maxn], g1[maxn], g2[maxn], sm[maxn], g[maxn], w[maxn], wcnt;
ll id1[maxn], id2[maxn];
ll inv2, inv6, qn;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * n;
        n = n * n ;
        k >>= 1;
    }
    return res;
}
void get_primes(int n)
{
    for(int i = 

【树状数组】query

传送门

题意是给一个长度为n的排列。给出m个询问，每次询问一个区间。

问区间内所有数一个数是另一个数的倍数的对数。

l \le i < j \le r 而且 \min(p_i,p_j) = \gcd(p_i,p_j )

由于是排列，n<=1e5，所以用pos[i]存下i这个数的为位置。

在nlogn的时间里可以找出所有pair的对数，并以(l,r)的二元组表示。

再把询问L,R以二元组的形式离线。

问题转化成了二维偏序问题：L \le l \ \text{and}\ r \le R

用树状数组即可解决

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef pair<int,int> pii;
int pos[maxn], a[maxn];
vector<pii> v;
vector<pair<pii,int> > q;
int c[maxn];
int n, m;
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] ++ ;
}
int ask(int x)
{
    int res = 0;
    

【博弈】HDU 1079 Calendar Game

传送门

题意是说，给定一个日期，每个人可以轮流操作，要么将日期+1变为下一天，要么将日期变为下个月的同一天。

当下个月没有同一天的时候，只能讲日期变为下一天。

谁把日期变为2001.11.4即胜利。

是用sg函数做的。

当局面的sg=1的时候必胜。

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int gap[2020];
int ms[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int sg[2010][13][33];
bool check(int y, int m, int d)
{
    if(y > 2001) return 0;
    else if(y == 2001 && m > 11)  return 0;
    else if(y == 2001 && m==11 && d > 4) return 0;
    return 1;
}
int getsg(int y, int m, int d)
{
    //cerr << y << ":" << m << ":" << d << 

【杜教筛】HUD-6706 huntian oy

传送门

题意：f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7)
给定n,a,b求f

打表可知f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i (i-j)[gcd(i,j)=1]\%(10^9+7)

即：\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ i\ [gcd(i,j)=1]-\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ j\ [gcd(i,j)=1]

在i j互质的时候才有值。前面一部分就是每个数与其互质的个数的和，\sum\limits_{i=1}^{n}i\varphi(i)

后面一部分是每个数，与其互质的数值的和。\sum\limits_{i=1}^{n}\frac{i\varphi(i)}{2}(n1)

原因是gcd(n,x)=gcd(n,n-x)，当出现一个与n互质的数x的时候必然有一个n-x成对出现与其互质。他们的和为\frac{n}{2}，但这只是在n1的时候成立。

由于n==1的时候只有一个数字1，所以式子完整来写应该是\sum\limits_{i=1}^{n}\frac{i\varphi(i)+1}{2}因为在i=1的时候答案是1，如果除2就成了1/2，所以在分子上加个1使其成立

完整式子是\sum\limits_{i=1}^{n}\frac{i\varphi(i)-1}{2}

由于n有1e9，线筛是存不下的。
考虑
f=i\varphi(i)=id\varphi(i)
g=id
f*g(n)=\sum\limits_{i|n}\varphi(i)i\frac{n}{i}=n\sum\limits_{i|n}\varphi(i)

然后套杜教筛的板子。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 233;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv2, inv6;
bool st[maxn];
int primes[maxn], cnt;
ll phi[maxn];
unordered_map<int, ll> up;
ll ksm(ll n, ll k)
{
    

【权值线段树】HDU6703-array

传送门

题意是说给定一个排列，长度1e5，要求支持两种操作：
1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的，并且大于等于k的，最小的数字。

经过分析，答案最大不可能超过n+1。这样的话，操作1其实相当于把这个数字从排列中删去。

用两棵权值线段树，每个点上存的是位置。

对每次2操作，在[k,n]区间里找最靠左的并且val[x]大于r的数。

对每次1操作，最开始是初始化一颗每个点值都是n+1的权值线段树，删掉一个数代表这个数字在区间内可以被使用了。所以在线段树上把点改为该位置。

同时2操作也要找[k,n]区间里最靠左而且val2[x]小于等于r的数。

两个数取最小就是答案。

同时还需记录区间最大最小值，以用来在查询的时候剪枝。

没有这个剪枝，查询会退化为n^2log(n)的，因为区间里可能每个数都会递归到底。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define min(a,b) (a)<(b)?(a):(b)
const int maxn = 1e5 + 233;

struct Node{
    int l, r, v;
}t1[maxn * 4], t2[maxn * 4];
int a[maxn], pos[maxn];
int n;
void build(int p, int l, int r)
{
    if(l == r)
    {
        t1[p].l = l, t1[p].r = 

【19HDU多校】Rikka with Coin，贪心

传送门

题意是说有面值10 20 50 100的钱，有n个价格给定的菜，要求用最少的硬币数量，使得所有n个菜品的价格都能被凑出来。

贪心：直观想法是先用大的面值，依次用小的面值。

这样的话可以发现10， 20， 20， 50四个面值能凑出所有100以内的价格。

但是有个例外：90 110 这样的数据，如果按照上面的贪法是100 50 20 20 10五个硬币，实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替，四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100和dish[i] % 100在某个组合的子集生成里有没有。（有先后顺序，第一个如果有了第二个就不用判断。因为既然零钱数量是固定的，那么100圆的越少约好）如果有，100圆的数量就分别是(dish[i] - （dish[i] % 100 + 100）/ 100) ，和dish[i] / 100。

对于100圆判断是个重要细节。
比如1000 90 110这样的数据，1000其中的100圆可以用零钱拼出来，所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 

【19牛客多校9_J】Symmetrical Painting【另类扫描线】

传送门

题意是说给n<=3e5条宽度为1的线段，长度不定。

要求一个对称轴，使得将图按照对称轴处理以后剩下的线段最多。

首先猜到的就是对称轴必定出现在某个线段的正中央。但是枚举对称轴以后需要用数据结构维护两边的长度。

有一种离线的做法，更为简单。

1. 预处理出每条线的 下边线(l)、中线(l+r1)、上边线(r)。

2. 对于这些预处理出的线，仅仅记录一个y坐标，按照坐标从小到大排序。

3. 枚举这些线当作对称轴，从下往上做扫描线。线性讨论当前这条线和上一条线之间的线段产生的贡献。也就是当前线为对称轴，上一条线为下半段。按照扫描线一层一层的计算面积贡献。

4. 在某个线段遇到中线之前，他的面积贡献都是存在的。因为他按照当前扫描线往上翻折，扫描线下方的面积肯定小 于上方，所以贡献是下方面积的两倍 ，于是下边界的贡献flag = 1。

5. 当扫描线遇到中线的时候，肯定是之前某个线段的中线，此时这条线段在扫描线下方的面积大于等于上方面积，同时这条线段已经达到最大的面积贡献，当扫描线再往上走的时候会减少贡献，每当中线网上移动距离 k 的时候，这条线段就应该减去 2k 的面积贡献。当遇到上边界的时候负贡献消失，变成 0 贡献。于是中线的贡献flag = -2，上边界的flag = 1。

6. 所以用变量cnt对当前层做出贡献的线段条数，面积和sum每次都+=cnt*(i-last)。然后cnt+=当前层数的贡献。因为兑成轴的只可能产生0.5这种小数，于是为了代码方便，把坐标都扩大两倍，同时计算面积的时候不用乘2。

其实最核心的点就是每当对称轴向上移动k距离的时候，整条线就应该缩短2k的距离，这样才能保证图形是对称的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 233;
int n;
vector<pii> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        a.push_back({l *