这次比赛发挥得不错，264分，第二名，可能是因为今天题目的模型相对来说比较裸一点……
T1：【NOIP2015模拟10.29B组】质数
Description
定义质数为因数只含1和其本身的数，对于N组询问，试判断每个数是否为素数。
Input
第一行一个正整数N，表示有N组询问。
接下来N行，每行一个正整数M，表示询问M是否为质数。
Output
输出N行，每行一个字符串。
若是质数则输出‘Prime’，若不是质数则输出‘Not prime’。
Sample Input
5
2
10
89807289
9032482948
1000000007
Sample Output
Prime
Not prime
Not prime
Not prime
Prime
样例解释：
10=2*5
89807289=3 * 11 * 11 * 13 * 19031
9032482948=2 * 2 * 439 * 5143783
Data Constraint
20%的数据满足N≤100，1<M≤800,000。
50%的数据满足N≤1,000，1<M≤100,000,000。
100%的数据满足N≤1,000，1<M≤1,000,000,000,000。
反思&题解
比赛&正解思路： 看到 M ≤ 1 , 000 , 000 , 000 , 000 M≤1,000,000,000,000 M≤1,000,000,000,000时着实有点吓到了，刚刚想放弃，打完暴力突然想到了解法：将1000000以内（也就是根号1000000000000）的素数全部求出来，之后再拿M去除以这些数，如果有因子，则为合数，反之就是素数
反思： 还是那句话，签到题不能丢分！！！
CODE
#include<bits/stdc++.h>
using namespace std;
int su[1000005],n;
long long m;
bool f[1000005];
int main()
{
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
memset(f,true,sizeof(f));
int i,j;
f[1]=false;
for (i=2;i<=500000;i++)
{
for (j=2;j<=1000000/i;j++)
f[i*j]=false;
}
int tot=0;
for (i=1;i<=1000000;i++)
{
if (f[i])
{
tot++;
su[tot]=i;
}
}
scanf("%d",&n);
bool bz;
for (i=1;i<=n;i++)
{
scanf("%lld",&m);
if (m==2)
{
printf("Prime\n");
continue;
}
bz=true;
for (j=1;j<=tot;j++)
{
if (m%su[j]==0 && su[j]!=m)
{
bz=false;
break;
}
}
if (bz) printf("Prime\n");
else printf("Not prime\n");
}
return 0;
}
T2：【NOIP2015模拟10.29B组】平方数游戏
Description
Input
Output
Sample Input
2
Sample Output
3
1 -1
Data Constraint
反思&题解
比赛思路： 前面40分暴力，通过打表暴力找规律可以看出从 n > = 6 n>=6 n>=6开始第一行的答案就是1,0,0,1地出现，不过第二行却找不到规律，所以就拿了暴力的40分以及第一行正确的另外24分
正解思路： 第一行的规律是对的，又因为有 x 2 − ( x − 1 ) 2 − ( x − 2 ) 2 + ( x − 3 ) 2 − ( x − 4 ) 2 + ( x − 5 ) 2 + ( x − 6 ) 2 − ( x − 7 ) 2 x^2-(x-1)^2-(x-2)^2+(x-3)^2-(x-4)^2+(x-5)^2+(x-6)^2-(x-7)^2 x2−(x−1)2−(x−2)2+(x−3)2−(x−4)2+(x−5)2+(x−6)2−(x−7)2这个规律，所以后面每8个一组套上这个规律，之后前面的几个暴力处理就行了
反思： 这规律我找不出来能咋办找规律题也要从多个角度思考
CODE
#include<bits/stdc++.h>
using namespace std;
const int d[8]={-1,1,1,-1,1,-1,-1,1};
int f[25],n,ans,ans1[25];
void dg(int k,int sum,int n)
{
if (k>n)
{
int i,tot;
tot=abs(sum);
if (tot<ans)
{
ans=tot;
for (i=1;i<=n;i++)
ans1[i]=f[i];
}
}
else
{
f[k]=1;
dg(k+1,sum+k*k,n);
f[k]=-1;
dg(k+1,sum-k*k,n);
}
}
int main()
{
freopen("five.in","r",stdin);
freopen("five.out","w",stdout);
scanf("%d",&n);
int i;
ans=0x3f3f3f3f;
int tot,m;
if (n<=20)
{
dg(1,0,n);
printf("%d\n",ans);
for (i=1;i<=n;i++)
printf("%d ",ans1[i]);
}
else
{
int m=n;
m-=5;
int t=m%4;
if (t==1 || t==0) printf("1\n");
else printf("0\n");
int tot=n%8+8;
dg(1,0,tot);
for (i=1;i<=tot;i++)
printf("%d ",ans1[i]);
int j;
j=0;
for (i=tot+1;i<=n;i++)
{
printf("%d ",d[j]);
j=(j+1)%8;
}
printf("\n");
}
return 0;
}
T3：【NOIP2015模拟10.29B组】树上路径
Description
现在有一棵n个点的无向树，每个点的编号在1-n之间，求出每个点所在的最长路。
Input
输入文件名为tree.in。
第一行为一个整数n。
之后n-1行，每行三个整数u,v,w，分别表示一条边连的两个点和边权。
Output
输出文件tree.out，共n行，分别表示经过每个点的最长路。
Sample Input
4
1 2 3
1 3 4
1 4 2
Sample Output
7
7
7
6
Data Constraint
对于50%，1<=n<=1000
对于100%,1<=n<=100000,每个点的度不超过30，1<=u,v<=n,1<=w<=10000
反思&题解
比赛思路： 懵……
正解思路： 先确定一个固定根（我这里以1作为固定根），求出每个节点向下的最长路和次长路，且最这两条路不能有除了当前节点之外的相同节点，接下来，对于每个儿子节点的答案，3种方法进行计算：（这里盗用一下某大佬的图）
num（也就是祖宗的贡献）是dfs上一层的时候已经算出来的
1. 儿子节点的最长路和次长路
2. num加上当前节点到儿子节点的距离和儿子的最长路
3. 当儿子节点位于当前节点的最长路上时，及取当前节点的次长路加上儿子节点的最长路以及当前节点到儿子节点的距离；否则就取当前节点的最长路加上儿子节点的最长路以及当前节点到儿子节点的距离
可能有些绕，大家配合图理解一下就行了……
反思： 关于树的知识点我不是很擅长，要多刷题
CODE
#include<bits/stdc++.h>
using namespace std;
int n,long1[200005],long2[200005],head[200005],cnt,fa[200005],ans[200005];
struct arr
{
int next,to,w;
}edge[200005];
void add(int u,int v,int len)
{
edge[++cnt].to=v;
edge[cnt].w=len;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dg1(int now,int father)
{
int i;
fa[now]=father;
for (i=head[now];i;i=edge[i].next)
{
if (fa[now]!=edge[i].to)
{
int v=edge[i].to;
dg1(v,now);
if (long1[now]<long1[v]+edge[i].w)
{
long2[now]=long1[now];
long1[now]=long1[v]+edge[i].w;
}
else
{
if (long2[now]<long1[v]+edge[i].w) long2[now]=long1[v]+edge[i].w;
}
}
}
}
void dg2(int now,int tot)
{
int i;
for (i=head[now];i;i=edge[i].next)
{
if (fa[now]!=edge[i].to)
{
int v=edge[i].to,sum;
if (long1[v]+edge[i].w!=long1[now])
{
sum=max(tot+edge[i].w,long1[now]+edge[i].w);
sum=max(sum,long2[v]);
ans[v]=sum+long1[v];
}
else
{
sum=max(tot+edge[i].w,long2[now]+edge[i].w);
sum=max(sum,long2[v]);
ans[v]=sum+long1[v];
}
dg2(v,sum);
}
}
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d",&n);
int i;
for (i=1;i<n;i++)
{
int u,v,len;
scanf("%d%d%d",&u,&v,&len);
add(u,v,len);
add(v,u,len);
}
dg1(1,0);
ans[1]=long1[1]+long2[1];
dg2(1,0);
for (i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}
T4：【NOIP2015模拟10.29B组】抓知了
Description
深海龙王和水葫芦娃放了暑假闲的无聊，一天他们路过一棵树，听到树上的知了叫的好欢啊∼
深海龙王准备抓几只知了送给水葫芦娃。他发现面前的这棵树是一颗以1 号节点为根节点的一颗有根树，同时他又发现这颗树上的每一个节点i 上都恰好停有一只蝉，正在愉快的以ai 的响声鸣叫∼
深海龙王会从1 号节点起沿着树边一直爬，直到爬到一个叶子节点（请不要在意他怎么下来），在这途中他可以选择一些他经过的蝉并将它们抓起来。但是水葫芦娃希望深海龙王抓的知了能发出越来越响的鸣叫声，起码得要单调不减！
Input
第1 行包含一个整数n，表示树上的结点个数;
第2 行包含n − 1 个整数，分别代表第2 至n 号节点的父亲节点编号；
第3 行包含n 个整数ai，代表i 号节点知了的响声。
Output
一行一个整数，表示深海龙王最多能抓到的知了数。
Sample Input
11
1 1 1 2 2 6 7 3 3 10
6 5 2 2 6 4 3 2 10 2 3
Sample Output
3
Data Constraint
反思&题解
比赛&正解思路： 我可以说这套题模型最裸的就是这题了，就是在树上求最长不下降子序列，不过 n ≤ 100000 n≤100000 n≤100000很显然 n 2 n^2 n2求最长不下降子序列是过不了的，那么这是我们就可以用一种 n l o g n n log n nlogn时间复杂度的方法来求 （这个可以自己上网搜一搜，我太懒了不想讲） ，总之，深搜遍历整棵树之后做处理就行了，还有因为是在一棵树上做处理，所以答案不一定是最优，记得一定要回溯
反思： 这题主要考察实现能力，注意细节就没什么问题了
CODE
#include<bits/stdc++.h>
using namespace std;
struct arr
{
int next,to;
}edge[100005];
int n,a[100005],cnt,f[100005],ans,head[100005];
void add(int u,int v)
{
cnt++;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
int erfen(int x,int t)
{
int mid,l,r;
l=1;
r=x;
while (l<r)
{
mid=l+r>>1;
if (f[mid]<=t) l=mid+1;
else r=mid;
}
return l;
}
void dg(int now,int tot)
{
int v,sum,mx,tot1,w;
for (v=head[now];v;v=edge[v].next)
{
if (a[edge[v].to]>=f[tot])
{
sum=tot+1;
mx=f[tot];
tot1=tot;
f[sum]=a[edge[v].to];
}
else
{
w=erfen(tot,a[edge[v].to]);
sum=tot;
mx=f[w];
tot1=w;
f[w]=min(f[w],a[edge[v].to]);
}
dg(edge[v].to,sum);
f[tot1]=mx;
}
ans=max(ans,tot);
}
int main()
{
freopen("cicada.in","r",stdin);
freopen("cicada.out","w",stdout);
scanf("%d",&n);
int father,i;
for (i=2;i<=n;i++)
{
scanf("%d",&father);
add(father,i);
}
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1]=a[1];
dg(1,1);
printf("%d\n",ans);
return 0;
}
