A-HDU-#2087 剪花布条--https://vjudge.net/contest/232807#problem/A
题目大意：给出一个字符串，以及模板串，求字符串中有多少个模板串即子串？
解法：本题因为数据样例比较小所以可以直接使用两个for嵌套暴力匹配，每一次匹配成功便cnt++，进行下一段匹配.
但如果数据范围较大用暴力就会超时，则需要使用KMP算法，我看到题目也没多想直接模板KMP (T_T)。
暴力解法代码如下（百度找的）：
#include<stdio.h>
#include<string.h>
int main()
{
char a[1001],b[1001];
int lena,lenb,i,j,sum;;
while(scanf("%s",a)!=EOF&&a[0]!='#')
{
scanf("%s",b);
sum=0;
lena=strlen(a);
lenb=strlen(b);
for(i=0;i<lena;)
{
if(!strncmp(&a[i],b,lenb)) //strncmp代替了一个for
{
sum++;
i+=lenb;
}
else
i++;
}
printf("%d\n",sum);
}
return 0;
} 我的kmp代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int maxn=1000030;
int next1[10030];
char s[maxn];
char p[10030];
int cnt=0;
void prefix_next(){
next1[0]=0;
next1[1]=0;
int j;
for(int i=1;p[i]!='\0';i++){
j = next1[i];
while(j && p[j] != p[i]) j = next1[j];
next1[i+1] = p[j] == p[i] ? j + 1: 0;
}
return;
}
void kmp(){
int j=0,m=strlen(p),n=strlen(s);
for(int i=0;s[i]!='\0';i++){
while(j && p[j] != s[i]) j = next1[j];
if(p[j] == s[i]) j ++;
if(j == m) {
cnt++;
if(i+m<n)
j=0;
else
return;
}
}
return;
}
int main(){
/* #ifdef LOCAL
freopen("C:/Users/Administrator/Desktop/input.txt","r",stdin);
#endif*/
while(~scanf("%s",s),strcmp(s,"#")){
cnt=0;
cin>>p;
prefix_next();
kmp();
cout<<cnt<<endl;
}
} C-hdu-2090-算菜价-https://vjudge.net/contest/232807#problem/C
本题比较简单，就是将输入的每种菜价乘购买个数，对于中文菜名直接用字符串储存，不用对其进行处理，注意四舍五入。
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
int main()
{
string str;
double i,j,sum = 0;
while(cin >> str >> i >> j)
{
sum = sum + i * j ;
}
cout << fixed << setprecision(1) << sum << endl;
return 0;
} G-HDU 2094 产生冠军-https://vjudge.net/contest/232807#problem/G
思路：这个可以用set容器来做，每输入一场比赛都将名两个字inset入总的容器中，讲失败的人insert入失败的容器中，如果能分出胜负，那总的容器的长度=失败的容器+1；因为胜者是不会进入失败的容器的！！！这样就不用模拟整个过程那么复杂了！！
#include<algorithm>
#include<set>
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int n,m;
set<string>zon; //总参赛人
set<string>shu; //比赛输过的人
int main()
{
int n;
while(cin>>n&&n){
zon.clear();
shu.clear();
string a,b;
int k=1,u,v;
for(int i=1;i<=n;i++){
cin>>a>>b;
zon.insert(a);
zon.insert(b); //将赢和输的人都加入容器，若容器里面已经存在这个人，则不加入，否则加入
shu.insert(b); //将输的人都加入容器，若容器里面已经存在这个人，则不加入，否则加入
}
if(zon.size()-1==shu.size())
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
} J-HDU 2098分拆素数和-https://vjudge.net/contest/232807#problem/J
题解：这题先打一个素数表，然后进行枚举符合计数器++就可以，水题。
#include<cstdio>
#include<iostream>
using namespace std;
int su[10100]={1,1};
int main()
{
int i,j;
for(i=2;i<10000;i++)
{
if(su[i]==1)
continue;
for(j=i*2;j<10000;j+=i)
su[j]=1;
}
long long int n;
int cnt;
while(cin>>n&&n)
{
cnt=0;
for(i=2;i<n/2;i++)
{
if(su[i]==0&&su[n-i]==0)
cnt++;
}
cout<<cnt<<endl;
}
} K-hdu 2099 - 整除的尾数 -https://vjudge.net/contest/232807#problem/K
题解：这题好像是书上例题，直接暴力求解，比较简单，注意输出格式为%02d。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
int a,b,c[105];
while(cin>>a>>b)
{
int j;
if(a==0&&b==0)break;
for(int i=0;i<102;i++)c[i]=-1;
for(int i=0;i<100;i++)
if((a*100+i)%b==0)
{
c[i]=i;
j=i;
}
for(int i=0;i<100;i++)
{
if(c[i]!=-1)
{ printf("%02d",c[i]);
if(i!=j)
cout<<" ";
}
}
cout<<endl;
}
return 0;
}
L-洛谷1223排队接水-https://vjudge.net/contest/232807#problem/L
题解：先排序，然后计算总等待时间，最后输出顺序和平均等待时间。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
int x[505];
int main()
{
int n;
int sum=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x[i];
}
sort(x,x+n);
for(int i=0;i<n;i++)
{
sum+=x[i]*(n-i);
}
cout<<sum<<endl;
}
M-51nod 1212——无向图最小生成树-https://vjudge.net/contest/232807#problem/M
解题思路：这道题在这套题里面我感觉是相对较难的一道题，是一道最小生成树的模板题，用Kruskal算法来写。将每条路的信息存储起来，并将边的权值按从小到大进行排序，每次选择权值最小的边加入树中，并把边的两个顶点加入到一个集合中，若这两个顶点本身就在一个集合中（即加入这条边就构成了回路），就舍弃这条边判断下一个。直到选取了n-1条边加入树中，最小生成树构造完成。具体看代码。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f //定义极大值INF
using namespace std;
int n, m, sum, ans;
int f[1010]; //数组f判断点的集合状态
struct node
{
int x;
int y; //存储边的两个顶点以及权值
int z;
} Q[50010];
bool cmp( node a, node b )
{
return a.z < b.z; //将权值从小到大排列
}
int getf( int v )
{
if( v != f[v] )
f[v] = getf(f[v]); //查找父节点
return f[v];
}
int lian( int t1, int t2 )
{
int v1 = getf(t1);
int v2 = getf(t2);
if( v1 != v2 )
{ //若两个顶点不在同一集合中，这条边加入树
f[v1] = v2;
return 1;
}
return 0;
}
void Kruskal()
{
for( int i = 0; i < m; i++ )
{
if( lian(Q[i].x,Q[i].y) )
{
ans++;
sum = sum + Q[i].z;
if( ans == n-1 ) //当选取n-1条边时最小生成树构造完成
break;
}
}
}
int main()
{
while( ~scanf("%d%d",&n,&m) )
{
for( int i = 0; i < m; i++ )
cin>>Q[i].x>>Q[i].y>>Q[i].z;
sort(Q,Q+m,cmp);
sum = ans = 0;
for( int i = 1; i <= n; i++ )
f[i] = i; //初始化父节点都是本身
Kruskal();
cout<<sum<<endl;
}
return 0;
} N-给n个数进行排序-https://vjudge.net/contest/232807#problem/N
题解：水题
#include<iostream>
#include<algorithm>
using namespace std;
int num[50050];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>num[i];
sort(num,num+n);
for(int i=0;i<n;i++)cout<<num[i]<<endl;
return 0;
} O-矩阵相乘-https://vjudge.net/contest/232807#problem/O
题解：这是到题目并不难，直接公式套上去直接AC
#include<iostream>
#include<cmath>
using namespace std;
int a[105][105];
int b[105][105];
int main(){
int n;int tmp[105][105]={0};
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)cin>>a[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)cin>>b[i][j];
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
for(int k=0;k<n;++k)
tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j]);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++){
cout<<tmp[i][j];
if(j!=n-1)cout<<" ";
}
cout<<endl;
}
} P-51nod 1283 最小周长-https://vjudge.net/contest/232807#problem/P
题解：就考了一个数学公式，a+b>=2*sqrt(a*b);其实当a==b时，周长最短，因为题意要求
都是整数，我们需要枚举一下就行了
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int s;
cin>>s;
int a=(int)sqrt(s)*100;
a/=100;
for(int i=a;i<=s;i++)
{
if(s%i==0)
{
a=i;
break;
}
}
int b=s/a;
cout<<(b+a)*2<<endl;
return 0;
} Q-51nod 1381 硬币游戏-https://vjudge.net/contest/232807#problem/Q
题解：半径为r的硬币相交的直线的的条数有2*r和2*r+1,其中2r+1的情形只有一种就是硬币和直线相切，而硬币落在桌子上的情形有无数种，故概率为0，所以另一种情形的概率是1，所以答案就是2*r
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int s;
cin>>s;
int a=(int)sqrt(s)*100;
a/=100;
for(int i=a;i<=s;i++)
{
if(s%i==0)
{
a=i;
break;
}
}
int b=s/a;
cout<<(b+a)*2<<endl;
return 0;
} 因为U,V题目基本一样相差一行代码所以直接一起给出题解
U-求A,B最小公倍数-https://vjudge.net/contest/232807#problem/U
V-求A,B最大公约数-https://vjudge.net/contest/232807#problem/V
题解：因为数据范围比较大，直接暴力求会超时，所以需要使用辗转相除法
# include<cstdio>
#include<iostream>
using namespace std;
int main()
{
long long int a,b,c,x,y;
cin>>a>>b;
x=a;
y=b;
if (a<b)
{
c=a;
a=b;
b=c;
}
while (b!=0)
{
c=a;
a=b;
b=c%b;
}
c=x*y/a;
cout<<c<<endl;//U题打印C，删除对a的打印
cout<<a<<endl;//V题打印a，删除对c的打印
return 0;
}
京公网安备 11010502036488号