第一题：就是把字符串按照它要求的输出。
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char op[100];
char out[100][100];
int main()
{
while(~scanf("%s",op))
{
int len=strlen(op);
int a=(len+2)/3;
int b=(len+2)-2*a;
int fr=0,ed=len-1;
for(int i=1;i<a;i++)
{
for(int j=1;j<=b;j++)
{
if(j==1) out[i][j]=op[fr++];
else if(j==b) out[i][j]=op[ed--];
else out[i][j]=' ';
}
}
for(int j=1;j<=b;j++) out[a][j] = op[fr++];
for(int i=1;i<=a;i++)
{
for(int j=1;j<=b;j++)
{
printf("%c",out[i][j]);
}
printf("\n");
}
}
return 0;
}
第二题：有多个单词，现在给你两个单词的首地址，和很多字母的节点。
一开始以为只有2个单词，所以有测试数据过不去。
其实只要把所有单词拼接起来成一个静态链表，然后再从给的两个首地址
遍历一次找到共同点就行了。
这里实现上学到了些东西：
1. 就是%d 会忽略前导 0 。
2. 可以用 %05d 来控制输出。 0会在前面补上0。
参考代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node{
int next;
char ch;
};
Node node[100005];
int vis[100005];
int main(){
int start1,start2,N,a,b;
char c;
scanf("%d%d%d",&start1,&start2,&N);
memset(vis,0,sizeof(vis));
for(int i=0;i<N;i++){
scanf("%d %c %d",&a,&c,&b);
node[a].ch=c;
node[a].next=b;
}
while(start1!=-1){
vis[start1]=1;
start1=node[start1].next;
}
bool flag=false;
int ans;
while(start2!=-1){
if(vis[start2]==1){
flag=true;
ans=start2;
break;
}
start2=node[start2].next;
}
if(flag)
printf("%05d\n",ans);
else
printf("-1\n");
//system("pause");
return 0;
}
第三题：
一开始用 DP 做，WA。。
其实就是一贪心题，想清楚情况就行了。
参考下面一人的，已经很详细了。。
http://www.cnblogs.com/XBWer/p/3866486.html
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef struct
{
double pos;
double price;
}gasstation;
gasstation gasst[502];
bool cmp(gasstation a,gasstation b)
{
if(a.pos<b.pos)
return true;
return false;
}
int main()
{
double Cmax,D,Davg;
int N;
scanf("%lf%lf%lf%d",&Cmax,&D,&Davg,&N);
int i;
for(i=0;i<N;i++)
scanf("%lf%lf",&gasst[i].price,&gasst[i].pos);
sort(gasst,gasst+N,cmp);
if(D==0)
{
printf("0.00\n");
return 0;
}
if(gasst[0].pos!=0)
{
printf("The maximum travel distance = 0.00\n");
return 0;
}
int curstnum=0; //当前所处的油站编号,即当前的位置
double curgas=0; //当前的油量
double curcost=0; //当前的花费
bool flag=false; //是否达到目的
double maxrundis=Cmax*Davg; //邮箱加满最远能行驶的距离
while(!flag)
{
bool tag=false; //最大距离内是否有加油站
bool ifcheaper=false; //是否有便宜的
double cheapestprice=10000; //找出最便宜的
int cheapestnum; //没有更便宜的情况下，找出最便宜的
for(i=curstnum+1;i<N;i++)
{
if((gasst[i].pos-gasst[curstnum].pos)<=maxrundis) //范围内
{
tag=true; //有加油站
if(gasst[i].price<gasst[curstnum].price) //情况3-a
{ //且有更便宜的
ifcheaper=true;
double dist=gasst[i].pos-gasst[curstnum].pos;
double needgas=dist/Davg-curgas;
curgas=0;
curcost+=(needgas*gasst[curstnum].price);
curstnum=i;
break;
}
if(gasst[i].price<cheapestprice)
{
cheapestprice=gasst[i].price;
cheapestnum=i;
}
}
else
break;
}
if(!ifcheaper&&(maxrundis>=(D-gasst[curstnum].pos))) //说明已经可以到达目的地了,情况1
{
double dist=D-gasst[curstnum].pos;
double needgas=dist/Davg-curgas;
curcost+=needgas*gasst[curstnum].price;
printf("%.2lf\n",curcost);
return 0;
}
if(tag&&!ifcheaper) //情况3-b
{
double needgas=Cmax-curgas;
curcost+=(needgas*gasst[curstnum].price);
double dist=gasst[cheapestnum].pos-gasst[curstnum].pos;
curgas=Cmax-dist/Davg;
curstnum=cheapestnum;
}
else if(!tag) //情况2
{
printf("The maximum travel distance = %.2lf\n",gasst[curstnum].pos+maxrundis);
return 0;
}
}
return 0;
}
第四题：
题意： 找出一个团伙的首领，现在如果 AAA 与 BBB 打电话，则AAA 与 BBB 属于同一个团伙。
并且每个人都有一个权值 为他与其他人通话时间的总长度。每个团伙的总权值为每对人通话时间的总长度。
现在你要输出的团伙要满足一下条件：
1. 团伙人数大于2个人
2. 团伙的总通话时间大于给的 k
分析：
就是一个并查集，一开始我没考虑到 团伙 合并的情况，总有一组测试数据错误。
我们来看一个数据
AAA BBB 30
我们需要把 AAA自身权值 和 它的 团伙（祖先）权值 + 30
同理BBB 也一样。
并且一定要注意维护下团伙的头领 。因为AAA BBB 的权值改变了，就有可能成为头领。
然后 BBB 的团伙 合并到 AAA的团伙里去。
需要更新这个新团伙的
1. 总通话时间。
2. 总人数。
3. 头领。
思路出来了，具体实现就可以用到
map容器来映射。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
#define MAXN 2000
struct node
{
int num,sum,self;
string head;
string fa;
bool operator<(const node&a)const
{
return head<a.head; //字典序输出
}
}ans[MAXN];
string v[MAXN];
map<string,int> vis;
map<string,node> gang;
int coun;
void init_node(string a)
{
gang[a].sum=0;
gang[a].num=1;
gang[a].head=a;
gang[a].self=0;
gang[a].fa=a;
}
string find(string a,int key)
{
if(gang[a].fa!=a) return gang[a].fa=find(gang[a].fa,key);
else
{
gang[a].sum+=key;
return gang[a].fa;
}
}
void merge(string a,string b)
{
string fa=gang[a].fa;
string fb=gang[b].fa;
if(gang[gang[fa].head].self < gang[a].self)
gang[fa].head=a;
if(gang[gang[fb].head].self < gang[b].self) //先维护一下各自的头领。
gang[fb].head=b;
if(fa==fb) return; //如果是同一团伙 , 就不要合并了。
gang[fb].fa=fa;
gang[fa].sum+=gang[fb].sum;
gang[fa].num+=gang[fb].num;
int t1=gang[gang[fa].head].self;
int t2=gang[gang[fb].head].self;
gang[fa].head=t1>t2?gang[fa].head : gang[fb].head;
}
void init()
{
coun=0;
vis.clear();
gang.clear();
}
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
{
string a,b;
int c;
init();
for(int i=1;i<=n;i++)
{
cin>>a>>b>>c;
if(gang[a].num==0) init_node(a);
if(gang[b].num==0) init_node(b);
gang[a].self+=c;
gang[b].self+=c;
find(a,c);
find(b,0);
merge(a,b);
v[coun++]=a;
v[coun++]=b;
}
int num=0;
for(int i=0;i<coun;i++)
{
string fa=find(v[i],0);
if(vis[fa]) continue;
if(gang[fa].num>2&&gang[fa].sum>k)
{
ans[num].head=gang[fa].head;
ans[num++].num=gang[fa].num;
}
vis[fa]=1;
}
if(num==0) printf("0\n");
else
{
cout<<num<<endl;
sort(ans,ans+num);
for(int i=0;i<num;i++)
{
cout<<ans[i].head<<" "<<ans[i].num<<endl;
}
}
}
return 0;
}