头像

殇ベ_11




离线:6小时前


最近来访(43)
用户头像
冰菓
用户头像
GTAlgorithm
用户头像
头戴凤翅紫金冠身披锁子黄金甲足蹬藕丝步云履手持如意金箍棒之煞
用户头像
shenjingwa
用户头像
未名湖畔的梦
用户头像
凌乱之风
用户头像
珂朵莉
用户头像
月见七日
用户头像
mouzaisi
用户头像
黄明杰
用户头像
yinyyy
用户头像
Amazing_
用户头像
qyzawa_phi
用户头像
Xinqwq
用户头像
潘潘_the_panda
用户头像
孤独を見守る
用户头像
小淇
用户头像
zxt
用户头像
lukelmouse
用户头像
梦醒


$中国剩余定理$

$1.前置算法:扩展欧几里得算法$

$2.相关定理$

$ 中国剩余定理:若m_1, m_2, …m_n满足两两互质,M = \prod_{i = 1}^{n}{m_i}, M_i = \frac{M}{m_i}, t_i满足 \\
t_i, M_i \equiv 1(\mod {m_i}). 对于任意的n个整数a_1, a_2,…a_n,方程组:$

\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\cdots \\
x \equiv a_2 \pmod{m_n} \\
\end{cases}

$\quad \quad \quad \quad 必有整数解,其中一个解为x = \Sigma_{i = 1}^{n}a_iM_it_i, 且在模M的意义下有唯一解。$

$证明:$

$\quad \quad \quad \quad 我们讨论其中一个方程x \equiv a_i(\mod {m_i}).对于\Sigma_{i = 1}^{n}a_iM_it_i $

$根据M_i = \frac{M}{m_i} = \frac{\prod_{j = 1}^{n}{m_j}}{m_i},可以得到\forall j \not= i \quad m_i | M_j,$

$因此\Sigma_{i = 1}^{n}a_iM_it_i \equiv 1(\mod m_i),得到a_iM_it_i \equiv a_i(\mod m_i).因此$

$\Sigma_{i = 1}^{n}a_i M_i t_i是方程组的一个解。接下来我们设x_1,与x_2是方程组的两个解,那么必有$

$x_1 - x_2 \equiv 0(\mod m_i).而由于m_i两两互质,且M = \prod_{i = 1}^{n}m_i,因此有x_1 - x_2$

$\equiv 0 (\mod M),所以在模M的意义下必定只有一个解.$


$例题$

问题描述:

$\quad \quad \quad \quad 给定一个方程组:$
\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\cdots \\
x \equiv a_2 \pmod{m_n} \\
\end{cases}

$其中m数组两两互质,求该方程组的正整数解.$

输入样例:
3
3 1
5 1
7 2
输出样例:
16

$代码:$

#include<cstdio>
using namespace std;
const int N = 1e6 + 1;
#define ll long long
ll n, a[N], b[N];
ll M = 1;
ll ans = 0;
ll exgcd(ll a, ll b, ll &x, ll&y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
ll d, x, y;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%lld%lld",&a[i], &b[i]);
    for(int i = 1;i <= n;i ++)
        M *= a[i];
    for(int i = 1;i <= n;i ++){
        exgcd(M / a[i], a[i], x, y);
        ans = (ans + b[i] * x * M / a[i] % M + M) % M;
    }
    printf("%lld",ans);
}





$单位矩阵:$

$主对角线上的元素都为1,其余元素全为0的n阶矩阵称为n阶单位矩阵,记为In或En,通常用I或E来表示$

$在矩阵乘法中,单位矩阵起着特殊的作用:单位矩阵的任意次方都等于它本身.$

$单位矩阵 I(E) = $ \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \cdots \\ 0 & 1 & 0 & 0 & 0 \cdots \\ 0 & 0 & 1 & 0 & 0 \cdots \\0 & 0 & 0 & 1 & 0\cdots\\0 & 0 & 0 & 0 & 1\cdots\end{bmatrix} $ $


$矩阵加/减法:$

$矩阵的加法和减法就是把两个矩阵的对应上位置上的数相加减,设A,B时规格相同$

$的矩阵.C是矩阵A, B相加的结果, 那么:$

$C = A + B <=> C_{i, j} = A_{i, j} + B_{i, j}, (i \in [1, n], j\in[1, m])$

$$例如: \begin{bmatrix} 5 & 4 & 3 \\ 2 & 1 & 3 \\ \end{bmatrix} + \begin{bmatrix} 2 & 4 & 3 \\ 2 & 5 & 6 \\ \end{bmatrix} = \begin{bmatrix} 7 & 8 & 6 \\ 4 & 6 & 9 \\ \end{bmatrix} $$


$矩阵乘法$

$设A,B是两个矩阵,令C = A * B; 那么:$

$(1)A的列数必须和B的行数相等$

$(2)设A是n * r的矩阵, B是r * m的矩阵;那么A, B的乘积C是一个n * m的矩阵;$

$(3)C_{i, j} = \Sigma_{k = 1}^{r} A_{i, k} + B_{k, j};$

例如:$ A = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \\ \end{bmatrix} $, $B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \ \end{bmatrix} .$

$$ A * B = \begin{bmatrix} 1 * 1 + 4 * 4 & 1 * 2 + 4 * 5 & 1 * 3 + 4 * 6 \\ 2 * 1 + 5 * 4 & 2 * 2 + 5 * 5 & 2 * 3 + 5 * 6 \\ 3 * 1 + 6 * 4 & 3 * 2 + 6 * 5 & 3 * 3 + 6 * 6 \end{bmatrix} = \begin{bmatrix} 17 & 22 & 27 \\ 22 & 29 & 36 \\ 27 & 36 & 45 \end{bmatrix} $$

$由矩阵乘法的运算法则,我们得出下列结论:矩阵乘法满足结合律,不满足交换律.$


$方阵乘幂$

$方阵是指行列数相等的矩阵.A是一个方阵,将A连乘n次称为方阵乘幂,$

$写作A^n.若不是方阵无法进行乘幂运算.因为矩阵乘法满足结合律,所以方阵乘幂可以利用快速幂的思想来优化.$

关于矩阵快速幂,本人认为比较好的博客




题目描述

$对于题目要求的三种操作,都可以转化为结点之间的移动.把爆竹视为走到0号结点,停在原地视为走$

$了一个自环,这样我们就能可以通过DP来解决问题了.$

$设f[i][j][k]为从i到j走k步的方案数,所以有:$

$ \quad \quad \quad \quad f[i][j][k] = \Sigma{f[i][p][k - 1] * f[p][j][1]} $

$对于每条图上的边(i, j), f[i][j][1] = f[j][i][1] = 1.其实可以从方程中看出f[i][j][k]只和$

$f[i][p][k - 1]有关,所以可以优化掉第三维.最后,方程式为:$

$ \quad \quad \quad \quad f[i][j] = \Sigma{f[i][p] * f[p][j]} $

$这个形式和矩阵快速幂很相似,而原来的方程需要转移t次,所以最后结果就相当于由初始的状态数组构成的$

$方阵A的t次幂.最后答案为1到各个结点的方案数之和.$

C++ 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MOD 2017
const int N = 101;
struct matrix{
    int a[N][N];
    void clear(){
        for(int i = 1;i < N;i ++)
            for(int j = 1;j < N;j ++)
                a[i][j] = (i == j);
    }
    matrix operator * (const matrix & x) const{
        matrix c;
        for(int i = 1;i < N;i ++)
            for(int j = 1;j < N;j ++){
                c.a[i][j] = 0;
                for(int k = 1;k < N;k ++)
                    c.a[i][j] = (c.a[i][j] + (a[i][k] * x.a[k][j]) % MOD) % MOD;                    
            }
        return c;
    }
};
int n, m, t;
matrix map;
matrix qmi(matrix a, int b){
    matrix ret;
    ret.clear();
    while(b){
        if(b & 1) ret = ret * a;
        a = a * a;
        b >>= 1;
    }
    return ret;
}
int main(){
    int u, v;
    scanf("%d%d",&n,&m);
    map.clear();
    for(int i = 0;i < m;i ++){
        scanf("%d%d",&u,&v);
        map.a[u][v] = map.a[v][u] = 1;
    }
    for(int i = 1;i <= n + 1;i ++)
        map.a[i][n + 1] = 1;
    scanf("%d",&t);
    matrix a;
    memset(a.a, 0, sizeof(a.a));
    a.a[1][1] = 1;
    a = a * qmi(map, t);
    int ans = 0;
    for(int i = 1;i <= n + 1;i ++)
        ans = (ans + a.a[1][i]) % MOD;
    printf("%d\n", ans);
    return 0;
}




题目描述

$\quad \quad 首先1~N中最大的反质数,就是1~N中约数个数最多的数中最小的一个.其次,如果不同的质因子超过10的$

$话,就会超过2 * 10^9,并且所有质因子的质数总和不会超过30,因为2^{31} > 2 * 10^9.$

$并且我们要保证x的质因子是素数表中从2开始的连续若干个,且质数的指数单调递减.$

$证明:$

$ \quad \quad 1.如果质数不是连续的话,也就是p_1 * p_3,那么我们还不如选择p_1 * p_2.$

$ \quad \quad 2.如果质数的指数不是单调递减的话吗,就会出现约数个数相等,但不是最小的情况.$

$ \quad \quad 根据上面的一系列性质,我们得出了最简洁的思路:使用DFS确定最小的十个质数的指数$

$且满足质数单调递减,总乘积不超过N,同时记录约数的个数.$


C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
const int N = 1e6 + 1;
int prime[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int maxd;
int number;
int n;
void dfs(int u, int last, int p, int s){
    if(s > maxd || s == maxd && p < number){
        maxd = s;
        number = p;
    }
    if(u == 9) return ;
    for(int i = 1;i <= last;i ++){
        if((ll)p * prime[u] > n) break;
        p *= prime[u];
        dfs(u + 1, i, p, s * (i + 1));
    }
}
int main(){
    scanf("%d",&n);
    dfs(0, 30, 1, 1);
    printf("%d\n", number);
    return 0;
}




$题目描述$

$ \quad \quad 这道题很显然跟质数有关,但是L和R的值非常大,我们无法求出[L, R]的所有质数,$

$但是我们发现R - L的值又非常小,所以我们可以从这里找突破点.$

$ \quad \quad 以为任何一个合数n,它一定有一个不超过\sqrt{n}的质数,所以对于一个质数p,$

$i * p就是一个合数,利用上面的性质,我们可以先预处理出[2, \sqrt{R}]的所有质数,然后通过这些$

$质数去筛出[L, R]中的合数,而在[L, R]中没有被筛到的数,就是质数.$


C++ 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e6 + 40;

typedef long long LL;

int primes[N],cnt;
bool st[N];

void get_primes(int n)
{
    memset(st, false, sizeof(st));
    cnt = 0;
    for(int i = 2;i <= n;i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i;j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
 long long l, r;
    while (cin >> l >> r)
    {
        get_primes(50000);

        memset(st, false, sizeof st);
        for (int i = 0; i < cnt; i ++ )
        {
            int p = primes[i];

            for (long long j = max((l + p - 1) / p * p, 2ll * p); j <= r; j += p)
                st[j - l] = true;
        }

        cnt = 0;
        for (int i = 0; i <= r - l; i ++ )
            if (!st[i] && i + l > 1)
                primes[cnt ++ ] = i + l;

        if (cnt < 2) puts("There are no adjacent primes.");
        else
        {
            int minp = 0, maxp = 0;
            for (int i = 0; i + 1 < cnt; i ++ )
            {
                int d = primes[i + 1] - primes[i];
                if (d < primes[minp + 1] - primes[minp]) minp = i;
                if (d > primes[maxp + 1] - primes[maxp]) maxp = i;
            }

            printf("%d,%d are closest, %d,%d are most distant.\n", primes[minp], primes[minp + 1], primes[maxp], primes[maxp + 1]);
        }
    }
    return 0;
}




题目描述

$设f(i)表示机器跳到第i个格子获得的最大总分,则:$

$\quad \quad f(i) = {max_{x_j + d - g <= x_i <= x_j + d + g} \quad }{{f(j) + s_i}}$

$\quad \quad 同样,我们也可以用滑动窗口的方法来维护f(j)的值,但是这里要注意一下,s_i可能是负数,$

$所以对于每个不能走到的格子我们都要设成负无穷.$

$\quad \quad 考虑优化,当g = a时,如果f(i) >= k有解,那么g > 时,f(j) >= k$

$也一定有解,那么我们就可以用二分答案来优化枚举g的过程.这样就可以把时间复杂度降到O(nlogn).$


C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
ll f[N];
ll n, d, k;
ll x[N], s[N];
inline bool check(int p){
    ll now = 0;
    memset(f, 0 ,sizeof(f));
    deque<int>q;
    ll lg = max(1 * 1ll, d - p), rg = d + p;
    for(int i = 1;i <= n;i ++){
        while(x[now] + lg <= x[i]){
            while(!q.empty() && f[q.back()] < f[now])
                q.pop_back();
            q.push_back(now);
            now ++;
        }
        while(!q.empty() && x[q.front()] + rg < x[i])
            q.pop_front();
        if(!q.empty())
            f[i] = f[q.front()] + s[i];
        else
            f[i] = -1e18;
        if(f[i] >= k)
            return true;
    }
    return false;
}
int main(){
    scanf("%lld%lld%lld",&n,&d,&k);
    for(int i = 1;i <= n;i ++)
        scanf("%lld%lld",&x[i],&s[i]);
    int l = 0, r = x[n] + 1;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld", (l == x[n] ? -1 : l));
    return 0;
}




题目描述

$首先,我们要知道单调队列有两个性质:$

$1.队列中的元素对应在原来的列表中的顺序必须是单调递增的。$

$2.队列中的元素的大小必须是单调的。$

$以求最大值为例(求最小值同理),我们这样维护序列的值:$

$ \quad 维护队首:如果队首元素下标在当前下标的k个之前,弹出队首。$

$ \quad 维护队尾:比较当前元素与队尾元素的下标大大小,若当前元素更优,弹出队尾元素,$

$直到可以满足队列单调性后加入当前元素。因为如果对于两个元素a_x, a_y, x < y 且$

$a_x < a_y,那么在窗口的右端滑到y之后,a_x再也不可能成为最大值.$

$对于这道题,我们模拟窗口右移的过程,每右移一个单位,就将若干个元素弹出队首或队尾$

$并且将新的元素加入队尾。$


算法1

C++ 代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

typedef long long ll;

const int N = 1e7 + 1;
const int M = 1e4 + 1;
const int MAXN = 1e3 + 1;
int h, t;
int n, k, a[N], w[N], v[N];
void maxx(){
    h = 1, t = 0;
    for(int i = 1;i <= n;i ++){
        while(t >= h && w[t] < a[i]) -- t;
        w[++ t] = a[i];
        v[t] = i;
        while(v[h] <= i - k) ++ h;
        if(i >= k) printf("%d ", w[h]); 
    }
}
void minn(){
    for(int i = 1;i <= n;i ++){
        while(t >= h && w[t] > a[i]) -- t;
        w[++ t] = a[i];
        v[t] = i;
        while(v[h] <= i - k && h < t) ++ h;
        if(i >= k) printf("%d ", w[h]);
    }
    printf("\n");
}
int main(){
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    minn();
    maxx();
    return 0;
}




题目描述

$这题需要转化为三进制,然后从k往前dp,再从k往后dp,两个方案数相乘即是答案。$


算法1

C++ 代码

#include<cstdio>
using namespace std;
const int N = 1e4 + 1;
const int mod = 1e6;
#define ll long long
ll dp[N][251];
ll mp[N];
ll n, m, k, cnt;
ll sta;
ll st[N];
bool check(ll a){
    ll tmp = -1, last = -1;
    for(int i = 1;i <= m;i ++){
        tmp = a % 3;
        if(tmp == last)
        return false;
        last = tmp;
        a /= 3;
    }
    return true;
}
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a;
        a = 1ll * a * a;
        b >>= 1;
    }
    return res;
}
bool judge(ll a, ll b){
    for(int i = 1;i <= m;i ++){
        if(a % 3 == b % 3) return false;
        a /= 3;
        b /= 3;
    }
    return true;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i = 1;i <= m;i ++){
        scanf("%lld",&mp[i]);
        sta = sta * 3 + mp[i] - 1;
    }
    ll maxx = qmi(3, m);
    cnt = 0;
    for(int i = 0;i < maxx;i ++){
        if(check(i))
        st[++cnt] = i;
    }
    ll pos = -1;
    for(int i = 1;i <= cnt;i ++){
        if(st[i] == sta){
            pos = i;
            break;
        }
    }
    if(pos == -1){
        puts("0");
        return 0;
    }
    dp[k][pos] = 1;
    for(int i = k - 1;i >= 1;i --)
    for(int j = 1;j <= cnt;j ++)
    for(int k = 1;k <= cnt;k ++)
        if(judge(st[j], st[k]))
            dp[i][j] = (dp[i][j] + dp[i + 1][k]) % mod;
    for(int i = k + 1;i <= n;i ++)
    for(int j = 1;j <= cnt;j ++)
    for(int k = 1;k <= cnt;k ++)
        if(judge(st[j], st[k]))
            dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
    ll ans1 = 0, ans2 = 0;
    // ans1为第k行上方的方案数,ans2是第k行下方的方案数目
    for(int i = 1;i <= cnt;i ++)
        ans1 = (ans1 + dp[1][i]) % mod;
    for(int i = 1;i <= cnt;i ++)
        ans2 = (ans2 + dp[n][i]) % mod;
    if(k == 1)
        printf("%lld\n", ans2);
    else if(k == n)
        printf("%lld\n", ans1);
    else
        printf("%lld\n", ans1 * ans2 % mod);
    return 0;
}







题目描述

$设f[0][1]表示处理到第j个结点,所有结点的访问状态为i.很显然$

$有:f[i][j] = min(f[(i 异或 (1 << j)][k] + a[k][j])$

$注意循环顺序,首先枚举按从小到大状态i,再枚举当前到达的点j,再枚举$

$下一个到达的结点k.并且注意状态是否与当前结点i,k符合.$

$最后的答案就是:f[(1 << n) - 1][n - 1];$


算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, f[1 << N][N + 1];
int a[N + 1][N + 1];
int main(){
    memset(f, 0x3f, sizeof(f));
    cin >> n;
    for(int i = 0;i < n;i ++)
        for(int j = 0;j < n;j ++)
            cin >> a[i][j];
    f[1][0] = 0;
    for(int i = 1;i < (1 << n);i ++)
        for(int j = 0;j < n;j ++)
            if((i >> j) & 1)
                for(int k = 0;k < n;k ++)
                    if((i ^ (1 << j)) >> k & 1)
                        f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + a[k][j]);
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}




$算法分析:$

$如果没有附件的话,这道题就是一道0/1背包的模板题$

$但是题目又说一个主件最多有两个附件,那么对于每$

$个主件,都有5种情况:$

$1.什么都不买$

$2.只买主件$

$3.买一个主件和第一个附件$

$4.买一个主件和第二个附件$

$5.买一个主件和两个附件全买$

$所以我们枚举主件,对这5种情况分别转移即可。$

样例

样例输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出

2200



算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
const int M = 5e3 + 1;
int n, m;
int mw[N], mc[N], aw[M][M], ac[M][M];
int f[N];
int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        int v, p, q;
        cin >> v >> p >> q;
        if(!q){
            mw[i] = v;
            mc[i] = v * p;
        }
        else{
            ++ aw[q][0];
            aw[q][aw[q][0]] = v;
            ac[q][aw[q][0]] = v * p;
        }
    }
    for(int i = 1;i <= m;i ++)
        for(int j = n;mw[i] != 0 && j >= mw[i];j --){
            f[j] = max(f[j], f[j - mw[i]] + mc[i]);
            if(j >= mw[i] + aw[i][1])
                f[j] = max(f[j], f[j - mw[i] - aw[i][1]] + mc[i] + ac[i][1]);
            if(j >= mw[i] + aw[i][2])
                f[j] = max(f[j], f[j - mw[i] - aw[i][2]] + mc[i] + ac[i][2]);
            if(j >= mw[i] + aw[i][1] + aw[i][2])
                f[j] = max(f[j], f[j - mw[i] - aw[i][1] - aw[i][2]] + mc[i] + ac[i][1] + ac[i][2]);
        }
    cout << f[n] << endl;
    return 0;
}