说在前面：

最近一直在刷NOIP历年的题目，感觉还好，快刷完了，最近时间很紧，大概做了一些规划。期中考试又必须要参加，感觉真的药丸，马上就要NOIP了，加油吧！

在11月之前需要完成的问题：

  1. 解决过去NOIP可以解决的问题。
  2. 学习LCA并做一些题目练习。
  3. 学习欧拉函数，乘法逆元和中国剩余定理，并练习。

然后十一月份之后就要复习了，复习以前所学过的算法模板和题目。

NOIP2012国王游戏

题目描述：

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右 手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排 成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每 位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序， 使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入:

  1. 第一行包含一个整数 n，表示大臣的人数。
  2. 第二行包含两个整数 a 和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
  3. 接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手
    和右手上的整数。

输出：

输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

题解：

  • 其实这道题的难点在于高精度和贪心算法上面，高精度就不用说，直接上模拟就行，说说关于贪心算法吧。这道题保证最大的最小的方案其实就是把左手乘以右手的权值拍一个序就行了，证明过程如下：

证明：

  1. 已知，如果相邻的两个人交换位置，只会影响到这两个人的值，不会影响他人
  2. 假设相邻的两个人i, i + 1。设A[i] * B[i] <= A[i + 1] * B[i + 1]，i之前所有人的左手乘积为S。
    则，ans1 = max{S / B[i], S * A[i] / B[i + 1]}
    若交换
    则，ans2 = max{S / B[i + 1], S * A[i + 1] / B[i]}
    因为，A[i] * B[i] <= A[i + 1] * B[i + 1]
    所以，S * A[i] / B[i + 1] <= S * A[i + 1] / B[i]
    又因为，S / B[i + 1] <= S * A[i] / B[i + 1]
    所以，ans2 = S * A[i + 1] / B[i]
    ans1 = max{S / B[i], S * A[i] / B[i + 1]}
    所以，ans1 <= ans2
    证毕。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<cstdio>
using namespace std;
struct man
{
    int Left;
    int Right;
    int Mul;
}a[2000],King;
struct Number
{
    int Num[20000];
    int Longth;
    int ans[20000];
}b[3],Full;
int n;
bool mycmp(man x,man y)
{ return x.Mul<y.Mul; }
inline int Read()
{
    int F=true;
    int This=false;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
bool Chack(int And)
{
    for(int i=And;i>=1;i--)
    {
        if(b[2].ans[i]>Full.ans[i]) return true;
        if(b[2].ans[i]<Full.ans[i]) return false;
    }
    return false;
}
void Switch()
{
    for(int i=1;i<=b[2].Longth;i++)
    {
        b[1].Num[i]=b[2].Num[i];
        b[2].Num[i]=false;
    }
    b[1].Longth=b[2].Longth;
}
void GetMul(int ID)
{
    long long Now=false;
    long long Plus=false;
    while(a[ID].Left)
    {
        Plus++;
        Now=a[ID].Left%10;
        a[ID].Left/=10;
        for(int i=1;i<=b[1].Longth;i++)
        {
            b[2].Num[i+Plus]+=(b[1].Num[i]*Now)/10;
            b[2].Num[i+Plus-1]+=(b[1].Num[i]*Now)%10;
            b[2].Num[i+Plus]+=b[2].Num[i+Plus-1]/10;
            b[2].Num[i+Plus-1]=b[2].Num[i+Plus-1]%10;
        }
    }
    while(!b[2].Num[b[1].Longth+Plus+1]) Plus--;
    b[2].Longth=b[1].Longth+Plus+1;
    Switch();
}
void Change(int Last)
{
    for(int i=1;i<=Last;i++)
    Full.ans[i]=b[2].ans[i];
    Full.Longth=Last;
}
void Div(int ID)
{
    bool Flag=false;
    long long Now=false;
    long long Plus=false;
    long long Last=false;
    for(int i=b[1].Longth;i>=1;i--)
    {
        Now*=10;
        Now+=b[1].Num[i];
        b[2].ans[i]=Now/a[ID].Right;
        Now%=a[ID].Right;
        if(b[2].ans[i]&&!Flag)
        { Last=i; Flag=true; }
    }
    if(Chack(Last)) Change(Last);
}
int main()
{
    n=Read();
    King.Left=Read();
    King.Right=Read();
    for(int i=1;i<=n;i++)
    {
        a[i].Left=Read();
        a[i].Right=Read();
        a[i].Mul=a[i].Left*a[i].Right;
    }
    sort(a+1,a+n+1,mycmp);
    while(King.Left)
    {
        b[1].Longth++;
        b[1].Num[b[1].Longth]=King.Left%10;
        King.Left/=10;
    }
    for(int i=1;i<=n;i++)
    {
        Div(i);
        GetMul(i);
    }
    for(int i=Full.Longth;i>=1;i--)
    cout<<Full.ans[i];
    return 0;
}

NOIP2015子串

题目描述：

有两个仅包含小写英文字母的字符串 A和B。现在要从字符串 A中取出 k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串 B相等？注意：子串取出的位置不同也认为是不同的方案。

输入：

  1. 第一行是三个正整数n，m，k，分别表示字符串A的长度，字符串 B的长度，以及问题描述中所提到的k，每两个整数之间用一个空格隔开。
  2. 第二行包含一个长度为n的字符串，表示字符串A。
  3. 第三行包含一个长度为m的字符串，表示字符串B。

输出：

输出共一行，包含一个整数，表示所求方案数。由于答案可能很大，所以这里要求输出答案对1,000,000,007取模的结果。

题解：

  • 这道题其实是很难想到的，尤其是状态设置和增加一个记录的DP式子来帮助转移主要的DP式子，我感觉到了考场上面根本不会写QAQ。
  • 首先我们设状态F[i][j][k]，来表示对于A串的前i个分成k个子串来构成B串的前j个的方案数。那么F[i][j][k]其实就是分为是否选择i作为B串的组成的两个方案，第一个是选择A串的第i个来组成B串和不选择A串的第i个来组成B串。我们分开来讨论，对于选择i来说，我们设置一个状态S[i][j][k]来表示对于A串的前i个在一定选择i的情况下分成k个子串来构成B串的前j个的方案数。如果A[i]!=B[j]的话，毫无疑问，这个式子的值为零。如果A[i]==B[j]的时候，一定选择i且有k个子串有两种方式，一种是i作为独立的一个子串的方案数：F[i-1][j-1][k-1]，另外一种是i和前面的融合成一个的方案数：S[i-1][j-1][k]。两个加起来就是S[i][j][k]了。
  • 上面的一定选择i的方案已经得出了方案数，然后就是不选择i的方案数，这个比较好求，就是F[i-1][j][k]，也就是同样是k个子串来组成j之前的B串，但是不包括i。这样我们把选择和不选择两种方案数加起来就是F[i][j][k]的值了。
  • 还有比较重要的是初始化，F[i][0][0]的值都是1，用前i个A串不构成B串的方案永远是1。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
using namespace std;
#define Mod 1000000007
int n,m,k,S[3][2000][2000];
int F[3][2000][2000];
char A[2000],B[400];
inline int Read()
{
    int F=true;
    int This=false;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
int main()
{
    n=Read(); m=Read(); k=Read();
    scanf("%s",&A);
    scanf("%s",&B);
    F[0][0][0]=true;
    for(int i=n;i>=1;i--) A[i]=A[i-1];
    for(int i=m;i>=1;i--) B[i]=B[i-1];
    for(int i=1;i<=n;i++)
    {
        F[i&1][0][0]=true;
        for(int j=1;j<=m;j++)
        for(int l=1;l<=k;l++)
        {
            if(A[i]==B[j]) S[i&1][j][l]=(F[(i-1)&1][j-1][l-1]+S[(i-1)&1][j-1][l])%Mod;
            else S[i&1][j][l]=false;
            F[i&1][j][l]=(S[i&1][j][l]+F[(i-1)&1][j][l])%Mod;
        }
    }
    cout<<F[n&1][m][k]<<endl;
    return 0;
}

NOIP2016 蚯蚓

题目描述：

本题中，我们将用符号[c]表示对c向下取整，例如：[3.0」= [3.1」=[3.9」=3。

  • 蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有n只蚯蚓（n为正整数)。每只蚯蚓拥有长度，我们设第i只蚯蚓的长度为a_i(i=1,2,…,n)，并保证所有的长度都是非负整数（即:可能存在长度为0的蚯蚓）。

  • 每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定，设这只蚯蚓长度为x，神刀手会将其切成两只长度分别为[px]和x-[px]的蚯蚓。特殊地，如果这两个数的其中一个等于0，则这个长度为0的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加q(是一个非负整常数)。

  • 蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要m秒才能到来……(m为非负整数）

蛐蛐国王希望知道这m秒内的战况。具体来说，他希望知道：

  1. m秒内，每一秒被切断的蚯蚓被切断前的长度（有m个数）
  2. m秒后，所有蚯蚓的长度（有n+m个数)。

输入：

第一行包含六个整数n,m,q,u,v,t (你需要自己计算p = u/v)
第二行包含n个非负整数，为al,a2,…,an，即初始时n只蚯蚓的长度。

保证1<n<10^5 , 0<m<7*10^6，0<u<v< 10^9 , 0<q<200，1<t<71，0<a_i<10^8

输出：

  1. 第一行输出[m/t]个整数，按时间顺序，依次输出第t秒，第2t秒，第3t秒……被切断蚯蚓（在被切断前）的长度。
  2. 第二行输出[(n+m)/t]个整数，输出m秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第t，第2t，第3t……的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要 输出，你也应输出一个空行。

题解：

  • emmmm，想当年，我在第一次参加NOIP的时候，不知道去用sort写QAQ，真的是垃圾啊，当时听说用堆可以水70分，sort强行50分。如果写了的话恐怕就不会太惨了吧。当年我还是太年轻，什么都不懂，太垃圾了。
  • 去年NOIP的事情就不说了QAQ，说了就伤心。说说这道题吧，最开始接触是觉得比较难的，就尝试用堆写了写，果然70分，然后想不出来正解，就看了题解，发现其实代码实现是比较简单的，仅仅只是维护三个单调队列就可以了，好难受。
  • 其实解决这道题的核心就是如何在O(1)的情况下确定哪一只蚯蚓要被割掉，如果用堆来维护的话，复杂度是O(logN)的，肯定要GG。所以说我们就可以试一试单调队列，我们通过建立三个单调队列，分别为主队列，大队列和小队列。主队列就是在读入数据的时候，排个序，然后从大到小进入队列，这个时候主队列一定是单调的队列，队头一定是最长的。但是每次把最长的蚯蚓切成两段的时候，就会多出来两条蚯蚓，那么如果进入主队列一定会破坏单调性的，所以我们可以让长的进入大队列里面，短的进入小队列里面。如何确保大队列和小队列一定是单调的呢？
  • 其实这个问题是比较简单的，因为每次切得蚯蚓的长度一定小于上一个被切的蚯蚓加上每秒增长的长度，并且每只蚯蚓切出来的比例都是一样的，所以后面切的蚯蚓所出来的一长一短小蚯蚓长度一定小于前面切的蚯蚓所形成的一长一短的两个小蚯蚓，那么直接添加到大队列和小队列的队尾就行了，可以保证队列的单调性的。
  • 对于所有蚯蚓每秒增长的长度，我们先不计，到最后被切的时候一次性加上去。加的就是已经过去的时间*每秒增加的长度。有些蚯蚓是后面形成的，在形成之前是没有增加长度的，我们就要在诞生的时候减去前面没有增加的长度，最后加长度的时候可以抵消，代码如下：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
int n,m,q,u,v,t;
int Now,A,B,all;
int a[100001];
int q1[16000000];
int q2[16000000];
int q3[16000000];
int head1=true,tail1=false;
int head2=true,tail2=false;
int head3=true,tail3=false;
inline int Read()
{
    int F=true;
    int This=false;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
int GetMax()
{
    int Maxx=-2123456789,ID=false;
    if(q1[head1]>Maxx&&head1<=tail1)
    {
        Maxx=q1[head1];
        ID=1;
    }
    if(q2[head2]>Maxx&&head2<=tail2)
    {
        Maxx=q2[head2];
        ID=2;
    }
    if(q3[head3]>Maxx&&head3<=tail3)
    {
        Maxx=q3[head3];
        ID=3;
    }
    if(ID==1) head1++;
    if(ID==2) head2++;
    if(ID==3) head3++;
    return Maxx;
}
int main()
{
    n=Read(); m=Read(); q=Read();
    u=Read(); v=Read(); t=Read();
    for(int i=1;i<=n;i++) a[i]=Read();
    sort(a+1,a+n+1);
    for(int i=n;i>=1;i--)
    q1[++tail1]=a[i];
    for(int i=1;i<=m;i++)
    {
        Now=GetMax()+all;
        if(i%t==0) printf("%d ",Now);
        A=1LL*Now*u/v-all-q;
        B=Now-1LL*Now*u/v-all-q;
        q2[++tail2]=max(A,B);
        q3[++tail3]=min(A,B);
        all+=q;
    }
    printf("\n");
    for(int i=1;i<=n+m;i++)
    {
        Now=GetMax();
        if(i%t==0)
        printf("%d ",Now+all);
    }
}