这一次训练总结是9月8日到9月10日。
这段时间的主要目的是参加网络赛锻炼自己，同时看线段树的相关知识。不过知识还是没看多少，大部分时间还是用在了作业上。。。那么就说一下周六参加的比赛吧。
周六下午的比赛是乌鲁木齐的一场网络赛，题目对于dalao来说好像非常简单，有34个队AK了。但是对于我们来说题目依然挺难，以至于只出了4道题。下面我来说明一下我参与的三道“水题”...
c题（送分题）：一共有n座城市，每天要喝b瓶果汁，从第一个城市出发，依次到第n座城市，到第i个城市获得ai瓶果汁，从第i个城市到第i+1个城市需要ci天，问他游览城市的时候是否每天都能喝到足够的果汁。
思路：简单暴力无需多言
代码：
#include<iostream>E题（签到题，佩尔数）：ti是（i+1）*i/2，i<1e16，给你一个n，求大于等于n的最小i使ti是平方数。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
const double PI=acos(-1.0);
using namespace std;
int a[1010];
int b[1010],c;
int t;
int n,m,flag,f,g,x,y,z,nn,mm;
int main(){
int i,j,k,l,r,mid;
int ans,sum,maxx;
while(scanf("%d",&t)==1){
for (k=1;k<=t;k++){
scanf("%d%d",&n,&c);
for (i=0;i<n;i++)scanf("%d",&a[i]);
for (i=1;i<n;i++)scanf("%d",&b[i]);
ans=a[0]; if(ans<0)printf("No\n");
else {for(i=1;i<n;i++)
{
ans=ans-b[i]*c;
if(ans<0){printf("No\n");break;}
ans+=a[i];
}
if(ans>0) printf("Yes\n");
}
}
}
return 0;
}
满足条件的数并不多，于是尝试打表，但是暴力出数太慢，最后终于发现它和佩尔数有关。佩尔数a【1】=1，a【2】=2，然后递推公式为a[i]=2*a[i-1]+a[i-2]。
题目中要求的数，奇数项为佩尔数的平方，偶数项为该项的佩尔数加上上一个佩尔数和的平方的两倍。注意超过16位就输出-1，数组开long long就可以。需要注意while scanf就错！！！方法是暴力打表，代码如下：
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
long long int a[101];
long long int b[101];
int main(){
long long int i,j,k,l,t;
long long n,m;
a[1]=1;
b[1]=1;
a[2]=2;
b[2]=8;
for (i=3;i<=23;i++){
a[i]=2*a[i-1]+a[i-2];
if (i%2){
b[i]=(a[i]+a[i-1])*(a[i]+a[i-1]);
}
else {
b[i]=a[i]*a[i]*2;
}
//cout<<b[i]<<endl;
}
scanf("%lld",&t);
for(int cas=1;cas<=t;cas++){
scanf("%lld",&n);
printf("Case #%d: ",cas);
for(i=1;i<23;i++){
if(b[i]>10000000000000000) {printf("-1\n");break;}
else if(n<=b[i]) {printf("%lld\n",b[i]);break;}
}
}
}
H题（水题，DP）：有n座岛屿，给出m种建桥方法，每种方法包括从第a个岛屿到第b个岛屿建的桥长度，问你怎么建桥最长。显然是dp，不过开二维数组会mle，用结构体就可以。
有点玄的AC代码如下：
#include<iostream>玄就玄在dp一次不过，dp100次就过了。可能是由于建桥顺序使得第一次dp不一定是最优吧。 至于线段树，仍然还在缓慢的看资料。。。状态相比于三天前好一点了，继续加油吧。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
const double PI=acos(-1.0);
using namespace std;
struct point{
int x;
int y;
int val;
bool operator<(const point&b)const{
return val<b.val;
}
}p[100010];
int dp[10010];
int main(){
int i,j,k,l,t,m,n,xx,yy,zz;
scanf("%d",&t);
for (k=1;k<=t;k++){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].val);
}
memset(dp,0,sizeof(dp));
int ans=0;
for (j=1;j<=100;j++)
for (i=1;i<=m;i++){
xx=p[i].x;
yy=p[i].y;
dp[yy]=max(dp[yy],p[i].val+dp[xx]);
if (dp[yy]>ans)ans=dp[yy];
}
cout<<ans<<endl;
}
}