2015-08-12NOIP模拟赛
考试，跪了……但是分析才是最重要滴。
第一题：
Description
"蓝猫淘气三千问，看蓝猫，我有姿势我自豪！"话说能考上SDFZ的孩纸们肯定都是很有姿势的孩纸们，但是大家普遍偏科，都只有一门科目考得好。已知SDFZ 的入学考试科目数量小于等于10^9，而有n 个学生参加了入学考试。现在SDFZ 要刷人了，招生办每一次刷人会把一个科目考得好的人全部刷掉，但是最多不能刷超过K 次。（刷就是不录取）而SDFZ 的校长看录取名单时，最喜欢看的就是连续都是同一个科目考得好的人。他定义完美学生序列为连续且考得好的科目都为同一门的学生序列。现在招生办主任想让你帮他设计一种录取方案，使得最长的完美学生序列尽量长。
Input
共N+1 行，第一行2 个正整数n，K，n 表示入学考试人数，K 表示刷人次数上限。
接下来N 行，每行仅一个正整数Ai，为 i 号学生所考得好的科目。
接下来N 行，每行仅一个正整数Ai，为 i 号学生所考得好的科目。
Output
仅1 个正整数，为最长的最长完美学生序列。
Sample Input
9 1
2
7
3
7
7
3
7
5
7
2
7
3
7
7
3
7
5
7
Sample Output
4
Sample Explanation
总共有9 个学生，最多只能刷一次学生。
若不刷，最长完美学生序列长度为2
若刷掉考第3 门考得好的学生，则学生序列变成2 7 7 7 7 5 7，最长完美学生序列长度为4.
若不刷，最长完美学生序列长度为2
若刷掉考第3 门考得好的学生，则学生序列变成2 7 7 7 7 5 7，最长完美学生序列长度为4.
Hint
10%的数据：n≤10；
30%的数据：n≤1000；
100%的数据：1≤n≤100000。
30%的数据：n≤1000；
100%的数据：1≤n≤100000。
Analyse
很显然 30%的数据暴力枚举是可以通过的。
但是100%的数据怎么办呢？
这里我们采用类似于单调队列的方法：
用队列维护一个区间，使得这个区间的擅长科目数量不超过 K+1，那么统计出来的每个合法区间的众数的数量的最大值便为答案。具体操作如下：
(1).首先添加第一个元素入队列，此时 Head=Tail=1
(2).接下来不断添加元素入队，当队列内元素种类不大于 K+1 时统计答案。
(3).当队列里的元素种类大于 K+1 时，不断将队列头部的元素出队，直到队列内元素种类小于等于 K+1，这时要记得也要统计答案。
这便是这道题的算法。时间复杂度 O(n)。
(1).首先添加第一个元素入队列，此时 Head=Tail=1
(2).接下来不断添加元素入队，当队列内元素种类不大于 K+1 时统计答案。
(3).当队列里的元素种类大于 K+1 时，不断将队列头部的元素出队，直到队列内元素种类小于等于 K+1，这时要记得也要统计答案。
这便是这道题的算法。时间复杂度 O(n)。
第二题：
Description
此百团大战非彼百团大战也。这指的是SDFZ 的社团开始招人了。若若的LMZ现在站在操场上，有很多很多个社团在操场上排成一排。有些社团为了吸引人们加入，会表演节目。而现在LMZ 拿到了节目单，有n 个节目，其描述了在Ti 时刻Xi号社团会表演节目（持续时间忽略不计）。而LMZ 在一单位时间内最多也只能跑过V 个社团的距离（比如从1 号社团跑到V+1 号社团），而最少则可以不动，跑步的左右方向任意。他想知道：
1. 当他初始时刻是站在0 号社团的情况下，他最多能看到多少节目？
2. 当他初始时刻可以站在任意位置的情况下，他最多能看到多少节目？
注：初始时刻指的是时间为0。
1. 当他初始时刻是站在0 号社团的情况下，他最多能看到多少节目？
2. 当他初始时刻可以站在任意位置的情况下，他最多能看到多少节目？
注：初始时刻指的是时间为0。
Input
第一行仅1 个正整数n，为节目数量。
接下来n 行每行2 个正整数Xi，Ti，为第i 个节目的属性。输入数据保证不会有重复的节目。
最后一行一个正整数V，表示LMZ 的速度上限。
接下来n 行每行2 个正整数Xi，Ti，为第i 个节目的属性。输入数据保证不会有重复的节目。
最后一行一个正整数V，表示LMZ 的速度上限。
Output
仅2 个正整数，分别为问题1 和问题 2 的答案。
Sample Input
3
6 1
1 3
4 4
4
6 1
1 3
4 4
4
Sample Output
2 3
Sample Explanation
若一开始LMZ 站在0 号位置，那么在时间为1 时是不可能跑到6 号社团的，但是后面的2 个表演可以看得到；而若一开始便站在6 号社团处，便3 个表演都看得到。
Hint
10%的数据：n≤10；
40%的数据：n≤3000；
100%的数据：1≤n≤100000，-2*10^8≤Xi≤2*10^8，1≤V≤1000，1≤Ti≤10^6。
40%的数据：n≤3000；
100%的数据：1≤n≤100000，-2*10^8≤Xi≤2*10^8，1≤V≤1000，1≤Ti≤10^6。
Analyse
40%，不说了，DP。
设 F[i]表示刚刚看到了第 i 场节目（即满足 T=Ti，X=Xi）的情况下最多看了多少节目。那么 F[i]=max(F[j]+1)，其中 j 和 i 必须满足一下条件：
（1）. Ti>Tj
（2）. (Ti-Tj)*V≥|Xi-Xj|
至于两个询问的区别便是 dp 的初值不同，具体自己讨论，差别不大。时间复杂度 O(n^2)。
（1）. Ti>Tj
（2）. (Ti-Tj)*V≥|Xi-Xj|
至于两个询问的区别便是 dp 的初值不同，具体自己讨论，差别不大。时间复杂度 O(n^2)。
100%算法：显然，满足(2)就必须满足(1)，因此条件(1)是无用的。那么我们把(2)拆开成如下两个不等式：
（3）. Ti*V-Xi≥ Tj*V-Xj
（4）. Ti*V+Xi≥Tj*V+Xj
注：这个地方不用讨论 Xi 与 Xj 的大小，因为|Xi-Xj|≥±(Xi-Xj)那么我们按照权值 Ti*V-Xi 从小到大排序以后，然后按照 Ti*V+Xi 这个权值去做最长不下降序列就行了。至于对于两个询问的初值依然自己研究，本题解不做探讨。
时间复杂度 O(nlog2n)，用经典的二分求 LIS 解决问题。
（3）. Ti*V-Xi≥ Tj*V-Xj
（4）. Ti*V+Xi≥Tj*V+Xj
注：这个地方不用讨论 Xi 与 Xj 的大小，因为|Xi-Xj|≥±(Xi-Xj)那么我们按照权值 Ti*V-Xi 从小到大排序以后，然后按照 Ti*V+Xi 这个权值去做最长不下降序列就行了。至于对于两个询问的初值依然自己研究，本题解不做探讨。
时间复杂度 O(nlog2n)，用经典的二分求 LIS 解决问题。
第三题：
Description
你真的认为选课是那么容易的事吗？SDFZ 的ZY 同志告诉你，原来选课也会让人产生一种想要回到火星的感觉。假设你的一周有n 天，那么ZY 编写的选课系统就会给你n 堂课。但是该系统不允许在星期i 和星期i+1 的时候选第i 堂课，也不允许你在星期n 和星期一的时候选第n 堂课。然后连你自己也搞不清哪种选课方案合法，哪种选课不合法了。你只想知道，你到底有多少种合法的选课方案。
Input
有多组数据，请读到文件末结束。
对于每组数据仅一行，1 个正整数n。
对于每组数据仅一行，1 个正整数n。
Output
对于每组输出只有一行，1 个非负整数，为选课方案数量mod (10^9+7).
Sample Input
2
4
4
Sample Output
0
2
2
Sample Explanation
对于样例二：
周一上第二堂课，周二上第三堂课，周三上第四堂课，周四上第一堂课；
周一上第三堂课，周二上第四堂课，周三上第一堂课，周四上第二堂课。
共2 种选课方案。
周一上第二堂课，周二上第三堂课，周三上第四堂课，周四上第一堂课；
周一上第三堂课，周二上第四堂课，周三上第一堂课，周四上第二堂课。
共2 种选课方案。
Hint
第i 组数据：n≤10*i, 1≤i≤3；
100%的数据：1≤n≤100000。
100%的数据：1≤n≤100000。
Analyse
对于这题，我们可以把天和课建立节点利用Dinic计数暴力跑答案，也可以用容斥原理。
题解是这样的：
容斥原理，假设有 1 堂课所在的天数是错误的情况数是 W(1)，则每个错误的课程 i 可以放在 i 或 i+1 天，剩下的选课方法数是(n-1)!。所以 w(1)=C(n,1)*2*(n-1)!，这一步很容易想到，有点坑的是 2 个以上的
情况，假设有 k 堂课所在的天数是错误的情况数是 W(K)，总共 n 堂课分别记为 1,2,...n,它们可放的天数可以表示为(1，2)(2，3)(3，4)...(n，1)现在我们把括号去掉即得到一个数列 1，2，2，3，3，4，....n，1，现在我们从里面取出 K 个数，分别表示 k 堂课所在的天数，现在只要求出满足这个条件的取法数就可以了。
定理：假定数n个顶点沿一圆周排列，则从其中选取k个不相邻顶点的方法数是n/k*C(n-k-1,k-1)
证明：对于任意一个顶点A，先取A，然后再从不和A相邻的n-3个其他顶点中取k-1个不相邻顶点，显然可得到符合定理要求的组合，这个组合的个数为C((n-3)-(k-1)+1,k-1)=C(n-k-1,k-1)。一共有n个顶点，而且在每个组合中有k个元素，即可完成证明。
那么W(K)=(n-k)!*C(2n-k-1,k-1)*2n/k
有少数人会问为什么要乘(n-k)!，因为我们只选了K堂错的课，剩余(n-k)堂课可以随意选。
W(K)确定以后就是最裸的容斥原理了。
什么？容斥原理不会写？找老师要课件去吧，孩纸们。
在实现细节的时候，我们可以发现我们可以事先预处理好 n!，因此对于每组数据的时间复杂度为 O(n)，即总时间复杂度为 O(nq)，空间复杂度为 O(n)但是在实现细节的时候，若有人把时间复杂度写成 O(nlog2n*q)的话，就只有 60 分了。
情况，假设有 k 堂课所在的天数是错误的情况数是 W(K)，总共 n 堂课分别记为 1,2,...n,它们可放的天数可以表示为(1，2)(2，3)(3，4)...(n，1)现在我们把括号去掉即得到一个数列 1，2，2，3，3，4，....n，1，现在我们从里面取出 K 个数，分别表示 k 堂课所在的天数，现在只要求出满足这个条件的取法数就可以了。
定理：假定数n个顶点沿一圆周排列，则从其中选取k个不相邻顶点的方法数是n/k*C(n-k-1,k-1)
证明：对于任意一个顶点A，先取A，然后再从不和A相邻的n-3个其他顶点中取k-1个不相邻顶点，显然可得到符合定理要求的组合，这个组合的个数为C((n-3)-(k-1)+1,k-1)=C(n-k-1,k-1)。一共有n个顶点，而且在每个组合中有k个元素，即可完成证明。
那么W(K)=(n-k)!*C(2n-k-1,k-1)*2n/k
有少数人会问为什么要乘(n-k)!，因为我们只选了K堂错的课，剩余(n-k)堂课可以随意选。
W(K)确定以后就是最裸的容斥原理了。
什么？容斥原理不会写？找老师要课件去吧，孩纸们。
在实现细节的时候，我们可以发现我们可以事先预处理好 n!，因此对于每组数据的时间复杂度为 O(n)，即总时间复杂度为 O(nq)，空间复杂度为 O(n)但是在实现细节的时候，若有人把时间复杂度写成 O(nlog2n*q)的话，就只有 60 分了。
但是通过打了一个长为30的表之后：
0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123 ………… (部分)
我们通过观察发现a(i) 与 i*a(i-1) 之间有类似联系，经过推算：
a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4(-1)^n)/(n-2) （ n >= 4.）
加上神奇的逆元大法（自行百度）
于是问题就迎刃而解了。
代码：
T1:
#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <string>
#include <string.h>
#include <time.h>
#include <memory.h>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdio>
#include <climits>
#define intmin -2147483640
#define intmax 2147483640
using namespace std;
const int MAXN = 100010;
int N,M,K,A[MAXN],Ans=intmin,B[MAXN];
int Ne[MAXN],cnt;
int Q[MAXN],qin=0,qout=1;
int Binary (int x)
{
int l=0,r=M,mid;
while (l<=r)
{
mid=(l+r)>>1;
if (B[mid]==x) return mid;
if (B[mid]<x) l=mid+1;
else r=mid-1;
}
return -1;
}
void init ()
{
scanf ("%d%d",&N,&K);
int i,tmp;
for (i=0;i<N;i++)
scanf ("%d",&A[i]),B[i]=A[i];
sort (B,B+N);
tmp=B[N-1];
unique (B,B+N);
for (i=0;i<N;i++)
if (B[i]==tmp) {M=i;break;}
for (i=0;i<N;i++)
A[i]=Binary(A[i]);
}
void work ()
{
int i;
for (i=0;i<N;i++)
{
Q[++qin]=A[i];
if (!Ne[A[i]]) cnt++;
Ne[A[i]]++;
while (cnt>K+1)
{
int f=Q[qout];qout++;
Ne[f]--;
if (!Ne[f]) cnt--;
}
Ans=max(Ans,Ne[A[i]]);
}
}
int main ()
{
init ();
work();
cout<<Ans;
return 0;
}
T2:
#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <string>
#include <string.h>
#include <time.h>
#include <memory.h>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdio>
#include <climits>
#define intmin -2147483640
#define intmax 2147483640
using namespace std;
const int MAXN=100010;
typedef struct Activity_Node_Tp
{
int t,x;
int v1,v2;
bool operator < (const Activity_Node_Tp &Y) const
{return (v1!=Y.v1)?(v1<Y.v1):(v2<=Y.v2);}
}act_;
act_ A[MAXN],B[MAXN];
int F[MAXN],Temp[MAXN],D[MAXN],Top,N,V;
int Binary (int x)
{
int l=0,r=Top,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(Temp[mid]>=x) r=mid-1;
else
{
l=mid;
if(Temp[l+1]>=x) return l+1;
else l++;
}
}
}
void init ()
{
scanf ("%d",&N);
int i;
for (i=1;i<=N;i++)
scanf ("%d%d",&A[i].x,&A[i].t);
scanf ("%d",&V);
for (i=1;i<=N;i++)
A[i].v1=A[i].t*V-A[i].x,
A[i].v2=A[i].t*V+A[i].x;
sort (A+1,A+N+1);
}
void clear ()
{for (int i=1;i<MAXN;i++)Temp[i]=intmax;}
void DP1 ()
{
int i;
Top=0;
clear ();
for (i=1;i<=N;i++)
{
if (A[i].v2>=Temp[Top] && !(Top==0 && V*A[i].t<abs(A[i].x)))
Temp[++Top]=A[i].v2;
else
{
int l=0,r=Top,mid;
while (l<=r)
{
mid=(l+r)>>1;
if(Temp[mid]<=A[i].v2) l=mid+1;
else r=mid-1;
}
if (!(l==1 && V*A[i].t<abs(A[i].x)))
Temp[l]=A[i].v2;
}
}
cout<<Top<<" ";
}
void DP2 ()
{
int i;
Top=0;
clear ();
for (i=1;i<=N;i++)
{
if (A[i].v2>=Temp[Top])
Temp[++Top]=A[i].v2;
else
{
int l=0,r=Top,mid;
while (l<=r)
{
mid=(l+r)>>1;
if(Temp[mid]<=A[i].v2) l=mid+1;
else r=mid-1;
}
Temp[l]=A[i].v2;
}
}
cout<<Top<<" ";
}
int main()
{
init ();
DP1();
DP2();
return 0;
}
T3:
#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <string>
#include <string.h>
#include <time.h>
#include <memory.h>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdio>
#include <climits>
#define intmin -2147483640
#define intmax 2147483640
using namespace std;
const int MAXN = 2000010;
const unsigned long long mod = 1000000007;
unsigned long long f[MAXN],ni[MAXN];
unsigned long long KSM (unsigned long long i,unsigned long long p)
{
unsigned long long a=1,b=i,c=p;
while (c)
{
if (c&1)
a=a*b%mod;
b=b*b%mod,c>>=1;
}
return a;
}
void nii ()
{
unsigned long long i,j,k;
for (i=1;i<=1000000;i++)
ni[i]=KSM (i,mod-2);
//for (i=1;i<=100000;i++)
//cout<<ni[i]<<" ";
}
int main ()
{
//freopen ("ni.out","w",stdout);
unsigned long long n;
nii ();
f[0]=0,f[1]=0,f[2]=0,f[3]=1,f[4]=2;
for (unsigned long long i=5;i<=1000000;i++)
{
f[i]=f[i-1]*i%mod;
if (i&1)
f[i]=(((i*i-2*i)*f[i-1]%mod+i*f[i-2]%mod+4)%mod)*(ni[i-2]%mod)%mod;
else
f[i]=(((i*i-2*i)*f[i-1]%mod+i*f[i-2]%mod-4+mod)%mod)*(ni[i-2]%mod)%mod;
}
while (~scanf ("%lld",&n))
printf ("%lld\n",f[n]);
return 0;
}