水题 or 难题 QAQ
T1 东东的蚂蚱
考查知识点：模拟；
题目描述：
东东爸给东东带回来一只聪明的蚂蚱，据说这个蚂蚱认识英文字母，好神奇的事情哦~~
为了测试这件事情，东东拿来一条长长的纸带，上面有N个格子排成一列，每一个格子中都有一个大写的字母。东东每次把聪明的蚂蚱放在地纸带最前端的外面，聪明的蚂蚱就会一直向前跳，跳到它喜欢的字母的格子中，最后跳出纸带。
经过观察，东东发现蚂蚱只喜欢特定的M个大写字母；并且聪明的蚂蚱的弹跳能力极强，每次跳越的距离为[1,X]区间中的某一个正整数。
现给出一条新的纸带，以及蚂蚱喜欢的特定的字母。东东想知道X的最小值为多少？
输入格式
第一行两个正整数N和Ｍ
第二行Ｍ个大写字母组成的字符串，为聪明的蚂蚱喜欢的那Ｍ个字母（M个字母互不相同）。
第三行为N个大写字母的组成的字符串，表示纸带上每个格子中的字母。
输出格式
一行一个正整数，表示最小的X值。
思路：
开两个字符串，一个存储蚂蚱喜欢的数字，一个存储纸带上的字母，从头到尾O（n）时间扫一遍，记录下相邻两个蚂蚱喜欢的数字之间的最大值，最后注意：要求的是蚂蚱跳跃的最长距离，它最后需要跳出纸带的长度也需要比较；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n,nmp,ans;
char a[11000];
char f[30];
int tmp[30];
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",&f[0]);
scanf("%s",&a[0]);
for(int i=0;i<m;i++)
{
tmp[f[i]-'A'+1]=1;
}
for(int i=0;i<n;i++)
{
if(tmp[a[i]-'A'+1]==1)
{
ans=max(ans,i+1-nmp);
nmp=i+1;
}
}
ans=max(ans,n+1-nmp);
printf("%d",ans);
return 0;
}T2 东东被困沼泽地
考查知识点：DP
题目描述
东东和东东爸跑出去野外穿越，结果不想东东被困在了一处沼泽地里。东东爸通过观察这片沼泽地是一个N*M的矩阵A，每一个位置要么是泥沼，要么是坚硬的石头。如果Ai,j <0表示的泥沼，否则就是石头。
初始东东爸在（1,1）位置，并且只能向右和向下走，因为这样才能最快的接近被困在（N,M）位置的东东。每走到一个位置就得到这个位置的值，问如何确定方案，东东爸才能在获得最大的值的情况下救出东东呢？
规定的行走方案由下面3条组成：
- 每次可以向右走一格。例如：（x,y）->( x,y+1 )
- 每次可以向下走一格。例如：（x,y）->( x+1,y )
- 每次可以向右走到当前列编号的整数倍的编号的格子。例如：（x,y）->( x,y*k )，其中k为合法的正整数。
输入格式
第一行两个正整数N和M。
接下来N行，每行M个整数。用来描述矩阵A。其中位置（1,1）和（N,M）的值为0。
输出格式
一行一个正整数，表示东东爸救出东东的情况下获得的最大值。
这道题还是很水的，需要注意的是原本a[i][j]小于0，被f[0][j]或f[i][0]更新为0；这时我们只需要特判一下，这道题就AC了；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int f[400][400];
int a[400][400];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1)f[i][j]=f[i][j-1];
else if(j==1)f[i][j]=f[i-1][j];
else f[i][j]=max(f[i][j-1],f[i-1][j]);
for(int k=1;k<=j-1;k++)
{
if(j%k==0) f[i][j]=max(f[i][j],f[i][k]);
}
f[i][j]+=a[i][j];
}
}
printf("%d",f[n][m]);
return 0;
}T3东东爸建机房
考查知识点：并查集or最小生成树
题目描述：
吉林省的信息学奥林匹克竞赛的成绩越来越好，吸引了非常多的有志学生选择学习信息学竞赛。但是现有机房的电脑明显是不够用了，东东爸就建议再建立一个超级大的机房。但是预算却非常有限，逼的东东爸在能省的地方绝对不会多花一分钱。
现在已知一共N个设备，编号为1到N。设备分两种，交换机或者电脑。上网规则如下：
- 所有的交换机都连了外网。
- 如果某台电脑i直连了交换机那么电脑i就能上网。
- 如果电脑i能上网，电脑j连接了电脑i，那么电脑j也能上网。
但是布线的施工方却是个奸商，虽然最后保证了所有的电脑都能上网了，但是布线时布了非常多的没有用的网线，甚至居然有几台电脑都成了环状拓扑结构了。东东爸火冒三丈，要求施工方撤掉尽可能多的网线，还得保证所有的机器都能上网。
怕施工方耍滑头，你能先帮东东爸算算最多能撤销的网线的长度么？
输入格式：
第一行三个正整数N、Ｍ和K，表示有N个设备，M条网线，K台交换机。
第二行有K个正整数，表示交换机的编号。
接下来M行三个正整数x,y,z。表示x号设备到y号设备的网线长度为z。
输出格式：
一个整数表示最多能撤销的网线的总长度。
思路：
一道裸的并查集，造一个原点0，（就是外网），把交换机连在上面，然后先将边从小到大排序，再加边枚举，如果加上这条边出现了环，就把它去掉，累计便是答案；
迷之错误：结构体排序时应严格大于或小于！！！否则-50分；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k,ans;
int f[2000];
struct your
{
int x,y,c;
}a[11000];
bool cmp(your j,your k)
{
//return j.c<=k.c;
return j.c<k.c;
}
int find(int x)
{
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=n;i++) f[i]=i;
for(int i=1;i<=k;i++)
{
int tmp;
scanf("%d",&tmp);
f[tmp]=0;
}
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
{
int dx=find(a[i].x);
int dy=find(a[i].y);
if(dx==dy) ans+=a[i].c;
else f[dx]=dy;
}
printf("%d",ans);
return 0;
}这是一套本来可以AK的题,让我硬生生的写挂了QAQ
