首先感谢NULL巨巨给大家提供了一个学习交流的机会
然后就得吐槽自己的中文读题水平了，总之，看到的基本都是能写的题，然而一直写不对就是自己弱和别人厉害的区别和差距了吧
先贴一发官方题解链接：
http://pan.baidu.com/s/1slMseWt#list/path=%2F
然后还是老规矩，对每个题的题意，解法和代码进行自己的分析
一开始看题就被题意坑了：
缺点是只能走向高处
这里从左到右，共有n个木桩，这些木桩有高有低
但是，没有说！一定要从左走到右啊！加上数据大小是1e6
相信会有很多人直接一发nlogn的LIS就丢上去了，然后返回了一个WA！
很简单：因为题目中没说行走的方向，那么我们只需要考虑：给的数值中有多少个不同的就好！
从最小的走向第二小的，然后走向第三小的……最后走向最大的
所以sort+unique一发就好
这个题是个水题，而且读题没有坑，从左到右扫一遍，挨个对字符所对应的数字加起来就好
题目太长，废话太多，其实总结起来就一句话：请从小到大输出8位长度的数字回文串
所以这个题不需要输入！！！我看到那个无字一脸懵逼，以为是不告诉我输入，要我判断输入的数字串是不是合法的8位回文
读题细节啊，可以直接四重循环搞，也可以一重循环
int main(){
for(int i=1;i<=9;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
for(int l=0;l<=9;l++)
printf("%d%d%d%d%d%d%d%d\n",i,j,k,l,l,k,j,i);
return 0;
}
int main(){
for(int i=1000;i<=9999;i++){
printf("%d",i);
printf("%d",i%10);
printf("%d",(i/10)%10);
printf("%d",(i/100)%10);
printf("%d\n",i/1000);
}
return 0;
}
就是当成蓝桥杯做，不要想太多，必定1A！
这个题是个综合性的好题（对大神来说应该很简单）
首先根据求最优值，应该能看出来是个DP，把精力值看作花费，利益值看作价值，那么就很明显：取或者不取，肯定是个DP！
结合题意，有多个物品，取或者不取，那不就是01背包吗？！
问题是，不是每个物品都能够取得到的（因为没有边到达的话，那么某个物品就取不到）
现在需要处理的问题是：如何判断，从节点1（开始节点）能够到达所有的能够取到的物品：并查集！（用图论的其他判断方法必然超时，而且并查集最经济实惠）
所以，在预处理输入之后，并查集+01背包，两个裸模板过题
#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
int a[maxn],b[maxn],dp[550];
int T,n,m,c;
int fa[maxn];
int getfa(int x){
if (fa[x]==-1) return x;
return fa[x]=getfa(fa[x]);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&c);
memset(dp,0,sizeof(dp));
memset(fa,-1,sizeof(fa));
for(int i=2;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
int fau=getfa(u);
int fav=getfa(v);
if (fau!=fav) fa[fau]=fav;
}
int root=getfa(1);
for(int i=2;i<=n;i++)
if (root==getfa(i))
for(int j=c;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
printf("%d\n",dp[c]);
}
return 0;
}
E题：音乐转换（没有题目链接，弱也不会DP，待补题）
这个题，要求的是所有数值对【L，R】，其中区间【L，R】中包含了LOVE四个大写字母（不需要按顺序出现）
枚举L，然后从左到右不断扫描，直到找到了LOVE四个字母每个至少各一个，然后这就是R的起点，R的终点肯定是字符串的末尾
剪枝：
首先可以预处理，第一个有用的字母在哪儿，不需要从前往后扫，即：找到第一个可能的L
然后找到第一个有答案的地方，即LOVE四个字母每个至少各一个的R的最小值，即：找到第一个可能的R
那么在暴力枚举指针的时候，可以少很多次枚举
（当然，这个题不需要想这么多，直接搞就好）
#include<bits/stdc++.h>
using namespace std;
int T,ans;
char s[100050];
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
int len=strlen(s+1);
int l,o,v,e,R,L;
ans=0;
for(L=1;L<=len;L++){
l=o=v=e=0;
for(R=L;R<=len;R++){
if (s[R]=='L') l++;
if (s[R]=='O') o++;
if (s[R]=='V') v++;
if (s[R]=='E') e++;
if (l&&o&&v&&e) break;
}
if (R<=len&&l&&o&&v&&e)
ans=ans+len-R+1;
}
printf("%d\n",ans);
}
return 0;
}
这个题是赛场争议最大的一道题，得看你对题目怎么理解
已知每秒有火的地方都会向周围八个格子（上下左右、左上、右上、左下、右下）蔓延火势.mengxiang000和Tabris每秒都可以选择周围四个格子（上下左右）进行移动。（假设两人这一秒行动完之后，火势才蔓延开）
首先，火是8个方向跑，人是4个方向跑，这个是固定的，没有问题
后面那个解释得这么理解才能过：
如果现在这个点是bfs的中间过程点（在图中的字符为点“.”），那么人需要比火先到这个点
如果现在这个点是bfs的终点，也就是出口点（在图中的字符为字母“E”），那么人可以和火同时到这个点
这样理解的大神，就能1A，我这种先跑火再跑人，wa了全场
这个题有个特殊性质：因为火是8个方向奔跑，而且墙对于火来说不是障碍，所以不需要去计算火的bfs，火到某个坐标点的时间可以直接用坐标计算得到
假设火的起点坐标为（fx，fy），需要判断的点的坐标为（x，y），那么花费的时间为max{abs（fx-x），abs（fy-y）}
意思是：能走对角线尽可能走对角线，走不动了再走直线，是最快的
这种方法的代码短，思路也更清晰：（因为只需要走人，一个bfs就搞定了）
#include<bits/stdc++.h>
using namespace std;
const int maxn=50;
int vis[maxn][maxn];
char mp[maxn][maxn];
int T,n,m;
int sx,sy,fx,fy,ex,ey;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
bool inmap(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m;
}
int getdis(int x,int y){
return max(abs(fx-x),abs(fy-y));
}
void bfs(){
vis[sx][sy]=0;
queue<int> q;
while(!q.empty()) q.pop();
q.push(sx);q.push(sy);
int nx,ny;
while(!q.empty()){
sx=q.front();q.pop();
sy=q.front();q.pop();
for(int i=1;i<=4;i++){
nx=sx+dx[i];
ny=sy+dy[i];
if (inmap(nx,ny)&&vis[nx][ny]==-1&&mp[nx][ny]!='#'&&mp[nx][ny]!='*'){
if (nx==ex&&ny==ey){
if (vis[sx][sy]+1<=getdis(nx,ny)){
vis[nx][ny]=vis[sx][sy]+1;
return;
}
}
else if (vis[sx][sy]+1<getdis(nx,ny)){
q.push(nx);q.push(ny);
vis[nx][ny]=vis[sx][sy]+1;
}
}
}
}
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if (mp[i][j]=='S') sx=i,sy=j;
else if (mp[i][j]=='E') ex=i,ey=j;
else if (mp[i][j]=='*') fx=i,fy=j;
memset(vis,-1,sizeof(vis));
bfs();
if (vis[ex][ey]==-1) puts("T_T");
else printf("%d\n",vis[ex][ey]);
}
return 0;
}
正常的方法就是：先把火的bfs跑出来，遍历全图；然后人在火中的地图上走，再次进行bfs，看能否找到一条有出口的路，代码如下：
#include<bits/stdc++.h>
using namespace std;
const int maxn=50;
int vis1[maxn][maxn],vis2[maxn][maxn];
int dx[]={0,1,-1,0,0,1,1,-1,-1};
int dy[]={0,0,0,1,-1,1,-1,1,-1};
char mp[maxn][maxn];
int T,n,m;
int sx1,sx2,sy1,sy2,ex,ey;
queue<int> q;
bool inmap(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m;
}
void bfsfire(){
vis1[sx2][sy2]=0;
while(!q.empty()) q.pop();
q.push(sx2);q.push(sy2);
int nx,ny;
while(!q.empty()){
sx2=q.front();q.pop();
sy2=q.front();q.pop();
for(int i=1;i<=8;i++){
nx=sx2+dx[i];
ny=sy2+dy[i];
if (inmap(nx,ny)&&vis1[nx][ny]==-1){
q.push(nx);q.push(ny);
vis1[nx][ny]=vis1[sx2][sy2]+1;
}
}
}
}
void bfspeople(){
vis2[sx1][sy1]=0;
while(!q.empty()) q.pop();
q.push(sx1);q.push(sy1);
int nx,ny;
while(!q.empty()){
sx1=q.front();q.pop();
sy1=q.front();q.pop();
for(int i=1;i<=4;i++){
nx=sx1+dx[i];
ny=sy1+dy[i];
if (inmap(nx,ny)&&vis2[nx][ny]==-1&&mp[nx][ny]!='*'&&mp[nx][ny]!='#'){
if (nx==ex&&ny==ey){
if (vis2[sx1][sy1]+1<=vis1[nx][ny]){
vis2[nx][ny]=vis2[sx1][sy1]+1;
return;
}
}
else if (vis2[sx1][sy1]+1<vis1[nx][ny]){
q.push(nx);q.push(ny);
vis2[nx][ny]=vis2[sx1][sy1]+1;
}
}
}
}
}
void debugfire(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",vis1[i][j],j==m?'\n':' ');
puts("");
}
void debugpeople(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",vis2[i][j],j==m?'\n':' ');
puts("");
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if (mp[i][j]=='E') ex=i,ey=j;
else if (mp[i][j]=='S') sx1=i,sy1=j;
else if (mp[i][j]=='*') sx2=i,sy2=j;
memset(vis1,-1,sizeof(vis1));
memset(vis2,-1,sizeof(vis2));
bfsfire();
bfspeople();
//debugfire();
//debugpeople();
if (vis2[ex][ey]==-1) puts("T_T");
else printf("%d\n",vis2[ex][ey]);
}
return 0;
}
这个题看到大数据n，哈哈，先猜一发
从小数据算出来：FIB数列，矩阵快速幂搞一发就行
说说原理：为什么这个题的答案是FIB数列，因为：
FIB（n）有两种构造方法：
方法1：在FIB（n-1）的所有构造方法后面加个字符A
方法2：在FIB（n-2）的所有构造方法后面加字符BB
得到答案
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 1000000007
typedef struct Matrix{
LL mat[2][2];
}matrix;
matrix A,B;
Matrix mul(matrix a,matrix b){
matrix c;
memset(c.mat,0,sizeof(c.mat));
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++){
c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
c.mat[i][j]%=mod;
}
return c;
}
Matrix qp(matrix a,LL k){
matrix b;
memset(b.mat,0,sizeof(b.mat));
b.mat[0][0]=b.mat[1][1]=1;
while(k){
if (k%2) b=mul(a,b);
k=k/2;
a=mul(a,a);
}
return b;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
LL n;
cin>>n;
n++;
A.mat[0][0]=A.mat[0][1]=A.mat[1][0]=1;
A.mat[1][1]=0;
B=qp(A,n);
cout<<(B.mat[0][1]+mod)%mod<<endl;
}
return 0;
}
一个很好的图论题，不难，但是很考虑思维，感谢各位大神对我的教育
题目抽象出来就是：找一条从a到b到c三个点的最长路
司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径
首先：我们需要考虑如何找任意两点之间的最短路径，需要用哪个最短路径算法？
请注意这是一个稀疏图.
注意到题目给的条件：稀疏图：说明边很少，那么意味着，我们要用以边来更新的单源最短路径算法：选择SPFA，对于每个点都单独跑一次就好了
然后，我们找从a到b到c的最长路
只需要枚举中间点，找到中间点到其他点距离最长和第二长的这两条边，取出来搞一发就好（自己写的是sort，但是其实不需要，维护最大值和次大值就可以了）
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int maxm=150050;
const int maxn=1500;
const int INF=0x3f3f3f3f;
struct node{
int from,to,nxt,w;
}edge[maxm];
int n,m,tot;
int tmp[maxn],head[maxn],vis[maxn],dis[maxn][maxn];
void init(){
tot=0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w){
edge[tot].to=v;
edge[tot].w=w;
edge[tot].nxt=head[u];
head[u]=tot++;
}
void SPFA(int s){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) dis[s][i]=INF;
dis[s][s]=0;
vis[s]=1;
queue<int> q;
while(!q.empty()) q.pop();
q.push(s);
int u,v,w;
while(!q.empty()){
u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=edge[i].nxt){
v=edge[i].to;w=edge[i].w;
if (dis[s][v]>dis[s][u]+w){
dis[s][v]=dis[s][u]+w;
if (vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
//freopen("input.txt","r",stdin);
int T,u,v,w;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1;i<=n;i++) SPFA(i);
int ans=-1;
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=1;j<=n;j++){
if (i==j) continue;
if (dis[i][j]==INF) continue;
tmp[cnt++]=dis[i][j];
}
sort(tmp,tmp+cnt);
if (cnt<=1) continue;
ans=max(ans,tmp[cnt-1]+tmp[cnt-2]);
}
printf("%d\n",ans);
}
return 0;
}
京公网安备 11010502036488号