829test
当教练说今天的题很难，而我却觉得很简单的时候——往往是我做错了
【准备】
Description
Alien的战舰不能搭载太多人，他需要在战舰上安装一些乘客客舱。可以安装的客舱有2p个型号，分别能搭载1至2p个乘客，每种型号有且仅有一个。为了方便搭载的过程，Alien希望恰好安装p个乘客客舱，且可搭载的乘客数量和必须为p的倍数。Alien想知道共有几种方案？
Input
本题有多组数据。第一行为数据组数n。
接下来n行每行包含一个奇质数p。
Output
对于每组数据输出一行，表示方案数。
Sample Input
2
3
5 Sample Output
8
52 数据范围
对于30%的数据 n⩽10,p⩽10
对于70%的数据 n⩽100,p⩽30
对于100%的数据 0⩽n⩽100,3⩽p⩽1000
题解
当年瞎DP乱做的可以水70，实在不想高精度了。如果非要AC的话，DP高精度肯定不好写亚。。。那还有别的办法吗？？
匆匆赶去开会的老师留下一个神秘的公式就离开了：
\frac{C_{2p}^{p}-2}{p}+2
真是让人百思不得其解。于是OIER们决定自己证明（听了老师开完会后的详细讲解）：
定义区间[1,2p]，由于p是一个奇质数，可以证得：
\sum_1^pi|p , \sum_{p+1}^{2p}|p
即分别取区间[1,p]和区间[p+1,2p]内的p个数都符合要求，当前的方案数就为2了。剩下的就是跨区间的情况，比如在区间[1,p]选k个，在区间[p+1,2p]选p-k个。来举个栗子：
当p=7,k=3时：
假设当前选定的数为2,3,5,那么这三个数的和与7的余数是3。这里记作 f(2,3,5)=3 。如果让我们选的每个数都往后挪一个，可以得到如下式子：
f(2,3,5)=3
f(3,4,6)=6
f(4,5,7)=2
f(5,6,1)=5
f(6,7,2)=1
f(7,1,3)=4
f(1,2,4)=0
f(2,3,5)=3
观察一下，如果将原k个数中的每个数 + t ,（0<=t<=p-1），再与p取模，可以得到所有余数（0,1,2...,5,6）。如果记原来的和为sum，现在的和为sum+t*k（0<=t,k<=p-1），由于t与k中都没有质数p的因子，所以现在的和与原来的和模p的余数肯定是不一样的，换句话说，对于区间[1,p]内选k个数的方案，没有一种方案的数字之和模p的余数是相同的。
这里看懂了，后面就很简单了。如果我们在[p+1,2p]的选择是固定的，就要在[1,p]内找一个方案与之相匹配。记在[1,p]内选的k个数的和为sum1，记在[p+1,2p]内选的p-k个数的和sum2，则两种选择相匹配当且仅当 p| (sum1%p+sum2%p)。由于sum2%p是固定的，而刚刚证明过sum1%p在区间内是唯一的。所以对于其中一个区间内的选择如果固定，那么在另一个区间内的p种选择中只有唯一的一种可以与之相匹配。
于是我们就成功地证明了这个神奇的式子：
\frac{C_{2p}^{p}-2}{p}+2
最后别忘了写高精度压位哦（4位最佳）。
Code
#include<bits/stdc++.h>
#define maxn 2000
using namespace std;
int a[maxn+5],b[maxn+5],c[maxn+5];
int res[105][maxn+5],v[1005];
char tmp[maxn+5];
int n,p,cnt=0;
void bigOutput(int *a){
printf("%d",a[a[0]]);
for(int i=a[0]-1;i>0;i--){
printf("%04d",a[i]);
}
printf("\n");
}
int bigCmp(int *a,int *b){
if(a[0]>b[0])return 1;
if(a[0]<b[0])return -1;
for(int i=a[0];i>0;i--){
if(a[i]>b[i])return 1;
if(a[i]<b[i])return -1;
}
return 0;
}
void bigPlus(int *a,int *b,int *c){
int g=0,k=max(a[0],b[0]);
for(int i=1;i<=k;i++){
c[i]=a[i]+b[i]+g;
g=c[i]/10000;
c[i]%=10000;
}
if(g>0){
c[++k]=g;
}
c[0]=k;
}
void bigMinus(int *a,int *b,int *c){
int g=0,k=a[0];
for(int i=1;i<=k;i++){
c[i]=a[i]-b[i]-g;
if(c[i]<0){
c[i]+=10000;
g=1;
}
else g=0;
}
while(k>1 && c[k]==0)k--;
c[0]=k;
}
void bigMulInt(int *a,int b,int *c){
int k=a[0],g=0;
for(int i=1;i<=k;i++){
c[i]=a[i]*b+g;
g=c[i]/10000;
c[i]%=10000;
}
while(g>0){
k++;
c[k]=g%10000;
g/=10000;
}
c[0]=k;
}
void bigMulBig(int *a,int *b,int *c){
int k=a[0]+b[0];
for(int i=1;i<=a[0];i++){
for(int j=1;j<=b[0];j++){
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/10000;
c[i+j-1]%=10000;
}
}
while(k>1 && c[k]==0)k--;
c[0]=k;
}
void bigDivBig(int *a,int b,int *c){
int k=a[0];
int g=0;
for(int i=a[0];i>0;i--){
g=g*10000+a[i];
c[i]=g/b;
g%=b;
}
while(k>1 && c[k]==0)k--;
c[0]=k;
}
int main(){
freopen("preparing.in","r",stdin);
freopen("preparing.out","w",stdout);
scanf("%d",&n);
while(n--){
scanf("%d",&p);
if(v[p]){
bigOutput(res[v[p]]);
continue;
}
cnt++;
v[p]=cnt;
memset(a,0,sizeof(a));
a[0]=1,a[1]=p+1;
for(int i=p+2;i<=2*p;i++){
memset(c,0,sizeof(c));
b[0]=1,b[1]=i;
bigMulBig(a,b,c);
memcpy(a,c,sizeof(a));
}
for(int i=1;i<=p;i++){
memset(c,0,sizeof(c));
bigDivBig(a,i,c);
memcpy(a,c,sizeof(a));
}
memset(c,0,sizeof(c));
b[0]=1,b[1]=2;
bigMinus(a,b,c);
memcpy(a,c,sizeof(a));
memset(c,0,sizeof(c));
bigDivBig(a,p,c);
memcpy(a,c,sizeof(a));
memset(c,0,sizeof(c));
b[0]=1,b[1]=2;
bigPlus(a,b,c);
bigOutput(c);
memcpy(res[cnt],c,sizeof(res[cnt]));
}
return 0;
} 【奖学金】
Description
为了选拔合适的学生入学，某大学发明了一种学术能力测试（简称SAT），这种测试的分数异常精确，每个学生的成绩可以用1到2,000,000,000之间的一个整数表示。
该大学的学费很贵，很多学生都负担不起，他们需要申请一些奖学金（1 ≤ 奖学金 ≤ 10000）。奖学金的预算都必须要从学校自身有限的基金中间扣除（设基金总额为F，0 ≤ F ≤ 2,000,000,000）。
很糟的是，该大学的只有N (1 ≤ N ≤ 19999)间教室，N是一个奇数，而一共有 C (N ≤ C ≤ 100,000) 名学生申请入学，为了让最多的学生接受教育，学校打算接受N个学生的申请，而且还想让这些学生的SAT 成绩的中位数尽可能地高。
所谓中位数，就是在一堆数字在排序后处在最中间的那个数字，比如{3,8,9,7,5}的中位数就是7。
给定每头学生的SAT 成绩和打算申请的奖学金数目，以及基金总数，确定接受哪些学生的申请才可以使成绩的中位数达到最大。
Input
第一行：三个用空格分开的整数：N，C和F。
第二行到C + 1行：每行有两个用空格分开的整数。第一个数是该学生的SAT 成绩，第二个数是其想申请的奖学金。
Output
第一行：一个整数，最大的中位数，如果现有基金不够资助N个学生，则输出-1。
Sample Input
3 5 70
30 25
50 21
20 20 5 18
35 30Sample Output
35数据范围
题目中已经给了丫。
题解
先将学生根据成绩降序排列，枚举中位数，只要满足基金条件就是我们想要的答案。
每次枚举到一个中位数s[i].val，要保证在其左边和右边分别选 (n-1)/2个学生，且这些学生申请的奖学金数目最少。可以先预处理出第i个学生的成绩为中位数时，ta左边应该选的学生的最小奖学金总和pre[i]和ta右边的最小奖学金总额nex[i]。这个操作用大根堆来实现。
Code
#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
int n,m;
long long F,mx=0,pre[maxn+5],nex[maxn+5];
priority_queue<long long> q;
struct students{
long long cost;
long long val;
}s[maxn+5];
bool cmp1(students a,students b){
return a.cost<b.cost;
}
bool cmp2(students a,students b){
return a.val==b.val?a.cost<b.cost:a.val>b.val;
}
int main(){
freopen("scholarship.in","r",stdin);
freopen("scholarship.out","w",stdout);
scanf("%d%d%lld",&n,&m,&F);
for(int i=1;i<=m;i++){
scanf("%lld%lld",&s[i].val,&s[i].cost);
}
sort(s+1,s+1+m,cmp1);
for(int i=1;i<=n;i++)mx+=s[i].cost;
if(mx>F){
printf("-1\n");
return 0;
}
sort(s+1,s+1+m,cmp2);
int k=(n-1)/2;
for(int i=1;i<=k;i++){
q.push(s[i].cost);
pre[k+1]+=s[i].cost;
}
for(int i=k+2;i<=m-k;i++){
long long x=q.top();
if(s[i-1].cost<x){
q.pop();
q.push(s[i-1].cost);
pre[i]=pre[i-1]-x+s[i-1].cost;
}
else pre[i]=pre[i-1];
}
for(int i=m;i>=m-k+1;i--){
q.push(s[i].cost);
nex[m-k]+=s[i].cost;
}
for(int i=m-k-1;i>=k+2;i--){
long long x=q.top();
if(s[i+1].cost<x){
q.pop();
q.push(s[i+1].cost);
nex[i]=nex[i+1]-x+s[i+1].cost;
}
else nex[i]=nex[i+1];
}
for(int i=k+1;i<=m-k;i++){
long long sum=s[i].cost;
sum+=pre[i];
if(sum>F)continue;
sum+=nex[i];
if(sum>F)continue;
printf("%lld\n",s[i].val);
break;
}
return 0;
}【The Chocolate Spree】
Description
众所周知，Alice 和 Bob 是一对宿敌，每次博弈游戏中 Alice 和 Bob 总绞尽 脑汁企图战胜对手，而且很不公平地，每次都是 Alice 先手。然而他们都看上了大 M 种的一棵巧克力树，为了取得更多的巧克力，他们决 定联手合作。 大 M 的巧克力树由 n 个节点组成，每个节点 i 上都有 v[i]个巧克力，巧克 力树上有 n-1 条树枝连接这整棵树（保证任意两点间存在一条路径）。Alice 和 Bob 一开始都可以选择一个出发起点并获得该节点上的所有巧克 力，当然，Alice 先选。接下来，Alice 和 Bob 会依次移动到自己节点相邻的节 点上，并获得该节点上的所有巧克力。但是，任意节点都只能被经过一次，若 Alice 走过某个节点 x，则 Bob 不能到达这个节点，当然 Alice 也不能走回 x。请问他们总共最多能获得多少巧克力？
Input
第一行 1 个整数 n，表示节点个数；
第二行 n 个整数，表示 v[1..n]；
接下来 n-1 行，每行两个整数 x 和 y，表示节点 x 与节点 y 之间有一条树枝相连。
Output
输出一行一个数，为总共能获得的最多的巧克力数。
Sample Input 1
9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9Sample Output 1
25Sample Input 2
2
10 20
1 2Sample Output 2
30数据范围
对于 20%的数据，n<=50；
对于 50%的数据，n<=5000；
对于 100%的数据，n<=100000，1<=v[i]<=10^9。
题解
一道关于树的双直径的神奇树上DP？？？竟然是道CF 633 F。
主要是，这道题的数组有那么一点点多（得不得了），需要仔细消化一下：
f(i,0)记录以i结点为根的子树中选两条不相交链的最大和。
f(i,1)记录以i结点为根的子树的直径。
son[i]记录以i结点的儿子为根的子树中最大的直径。
dis[i]记录从i开始能走到的最远的点，这条路径的权值。
p[i]记录dis[i]加上另外一条链的最大值。
看懂了吗？？？（没看懂也不管了自己画图意会一下）
Code
#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
long long val[maxn+5],f[maxn+5][2],p[maxn+5],son[maxn+5],dis[maxn+5];
int n,head[maxn+5],newp=0;
struct node{
int u,v,nex;
}e[2*maxn+5];
void add(int a,int b){
newp++;
e[newp].u=a;
e[newp].v=b;
e[newp].nex=head[a];
head[a]=newp;
}
void dfs(int x,int fa){
f[x][0]=f[x][1]=dis[x]=p[x]=val[x];
son[x]=0;
for(int i=head[x];i;i=e[i].nex){
int y=e[i].v;
if(y==fa)continue;
dfs(y,x);
f[x][0]=max(f[x][0],f[y][0]);//记录x树的两条不相交链的最大和
f[x][0]=max(f[x][0],f[x][1]+f[y][1]);
f[x][0]=max(f[x][0],dis[x]+p[y]);
f[x][0]=max(f[x][0],p[x]+dis[y]);
f[x][1]=max(f[x][1],f[y][1]);//记录x树的直径
f[x][1]=max(f[x][1],dis[x]+dis[y]);
p[x]=max(p[x],val[x]+dis[y]+son[x]);//记录从x到叶子节点加上另外一条链的最大和
p[x]=max(p[x],val[x]+p[y]);
p[x]=max(p[x],dis[x]+f[y][1]);
son[x]=max(son[x],f[y][1]);//记录以x结点的儿子为根的子树中最大的直径
dis[x]=max(dis[x],val[x]+dis[y]);//记录x到最远的点的路径
}
}
int main(){
freopen("chocolate.in","r",stdin);
freopen("chocolate.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&val[i]);
int x,y;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
printf("%lld\n",f[1][0]);
return 0;
}