除了DP和搜索的题解

1000
poj2121模拟
把相应的数字存起来，按照模拟打印出相应的数字
#include
#include
#include
char arr[10000];
int brr[10000];
char crr[10000][100];
int flag;
char drr[33][15]={"zero","one","two","three","four","five","six",
"seven","eight","nine","ten","eleven","twelve","thirteen",
"fourteen","fifteen","sixteen","seventeen","eighteen",
"nineteen","twenty","thirty","forty","fifty","sixty","seventy",
"eighty","ninety","hundred","thousand","million","negative"};
int err[32]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,30,40,50,60,70,80,90,100,1000,1000000};
int main()
{
while(gets(arr))
{
if(strcmp(arr,"")==0){break;}
// memset(crr,0,sizeof(crr));
flag=0;
int k;
k=1;
int A=strlen(arr);
brr[0]=0;
for(int i=0;i{
if(arr[i]==' ')
brr[k++]=i;
}
for(int i=0;isscanf(arr+brr[i],"%s",crr[i]);
if(strcmp(crr[0],drr[31])==0)
flag=1;
int t=0;
if(!flag)
{
// printf("0000\n");
for(int j=0;j{
for(int i=0;i<32;i++)
{
if(strcmp(crr[j],drr[i])==0)
{
brr[t++]=err[i];
}
}
}
}
else
{
// printf("1111\n");
for(int j=1;j{
for(int i=1;i<32;i++)
{
if(strcmp(crr[j],drr[i])==0)
{
brr[t++]=err[i];
}
}
}
}
int sum=0;
int baiwei=0;
int qianwei=0;
int baiwanwei=0;
for(int i=0;i{
if(brr[i]==100)
{

baiwei=sum*100;
sum=0;
}
else if(brr[i]==1000)
{
qianwei=(baiwei+sum)*1000;
baiwei=0;
sum=0;
}
else if(brr[i]==1000000)
{
baiwanwei=(qianwei+baiwei+sum)*1000000;
baiwei=0;
qianwei=0;
sum=0;
}
else
{
sum+=brr[i];
}
}
if(flag)
{
printf("%d\n",(sum+baiwei+qianwei+baiwanwei)*-1);
}
else
{
printf("%d\n",sum+baiwei+qianwei+baiwanwei);
}
}
return 0;
}


1001
zoj3622打表找规律
大家多半会忘记了125这个数
#include
#include
#include
#include
#include
#include
using namespace std;
long long a[100]={
1,2,5,10,20,25,50,100,
125,200

,250,500,1000,
1250,2000,2500,5000,10000,
12500,20000,25000,50000,100000,
125000,200000,250000,500000,1000000,
1250000,2000000,2500000,5000000,10000000,
12500000,20000000,25000000,50000000,100000000,
125000000,200000000,250000000,500000000,1000000000,
1250000000,2000000000,2500000000,5000000000,10000000000,
12500000000,20000000000,2500000000,50000000000,100000000000};
int main(){
long long n,m;
while(scanf("%lld%lld",&n,&m)!=EOF){
int i,cnt=0;
for(i=0;i<100;i++){
if(a[i]>=n&&a[i]<=m)
cnt++;
if(a[i]>m) break;
}
printf("%d\n",cnt);
}
return 0;
}



1005
poj3522图论
克鲁斯卡尔求生成树+暴力循环替换边枚举每一棵树。
这道题简单的来说就是求一棵生成树使最大的边和最小的边差值最小。

换个角度想就是用n-1条（n个点）数值相差不多的边，组成一棵生成树。
在生成树的prim和kruskal两个算法中很容易就会觉得kruskal的贪心思想会更加适合这道题。
kruskal算法一开始会对边进行排序，然后枚举最小的边。
比如第一个样例：
4 5
1 2 3 （1）
1 3 5 （2）
1 4 6 （3）
2 4 6 （4）
3 4 7 （5）
因为样例已经按边长排好序

第一次kruskal从（1）边开始直到组成一颗生成树，求出最大最小边差值。
第二次把（1）边扔掉，kruskal从（2）边开始直到组成一颗生成树，再求出最大最小边差值。
以此类推。（注意不可能剩下的边比n-1小）





题意：求最大边与最小边差值最小的生成树

解题分析：

最小生成树有一个很重要的性质：在构造生成树时有可能选择不同的边，但最小生成树的权是唯一的！所以在用kruskal算法时第一次加入的必然是最小生成树的最小边权值，最小边确定后，最小生成树的最大边的权值是所以生成树中最小的，于是只要枚举最小边，然后求最小生成树，就可以得到最大边，只要每次更新最优解就行了。

#include
#include
#include
#include

using namespace std;

const int VM=110;
const int INF=999999999;

struct Edge{
int u,v;
int cap;
}edge[VM*VM];

int n,m,ans,father[VM];

void makeSet(){
for(int i=1;i<=n;i++){
father[i]=i;
}
}

int findSet(int x){
if(x!=father[x]){
father[x]=findSet(father[x]);
}
return father[x];
}

int cmp(Edge a,Edge b){
return a.cap}

void Kruskal(){
sort(edge,edge+m,cmp);
for(int i=0;imakeSet();
int cnt=0,tmp=INF;
for(int j=i;jint fx=findSet(edge[j].u);
int fy=findSet(edge[j].v);
if(fx!=fy){
father[fy]=fx;
cnt++;
if(cnt==n-1){
tmp=edge[j].cap-edge[i].cap;
break;
}
}
}
if

(tmpans=tmp;
}
}

int main(){

//freopen("input.txt","r",stdin);

while(~scanf("%d%d",&n,&m)){
if(n==0 && m==0)
break;
for(int i=0;iscanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cap);
ans=INF;
Kruskal();
if(ans!=INF)
printf("%d\n",ans);
else
printf("-1\n");
}
return 0;
}


1007
poj1364 图论 SPFA
解题思路 白色图论书查分约束章，按照表达式规则，带入SPFA模板，不用改什么直接就可以过
#include
#include
#include
#include
#define INF 1000000000
using namespace std;

int cnt;
int n,m;
int head[105];
int queue[105*105];
int outque[105];
int visit[105];
int dist[105];
char daxiao[5];
int si,ni,ki;

struct node
{
int to;
int huafei;
int next;
}arr[1100];

void add(int x,int y,int z)
{
arr[cnt].to=y;
arr[cnt].huafei=z;
arr[cnt].next=head[x];
head[x]=cnt;
cnt++;
}

bool spfa(int s)
{
int i,k;
int iq;
int top;
for(i=0;i<=n;i++)
{
dist[i]=INF;
}
memset(visit,0,sizeof(visit));
memset(outque,0,sizeof(outque));
iq=0;
queue[iq++]=s;
visit[s]=true;
dist[s]=0;
i=0;
while(i!=iq)
{
top=queue[i];
visit[top]=false;
outque[top]++;
if(outque[top]>n)
return false;
k=head[top];
while(k>=0)
{
if(dist[arr[k].to]-arr[k].huafei>dist[top])
{
dist[arr[k].to]=dist[top]+arr[k].huafei;
if(!visit[arr[k].to])
{
visit[arr[k].to]=true;
queue[iq]=arr[k].to;
iq++;
}
}
k=arr[k].next;
}
i++;
}
return true;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
scanf("%d",&m);
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
add(n+1,i,0);
}
for(int i=0;i{
// scanf("%d %d %s %d",&si,&ni,daxiao,&ki);
cin>>si>>ni>>daxiao>>ki;
if(daxiao[0]=='g')
add(si+ni,si-1,-ki-1);
else
add(si-1,si+ni,ki-1);
}
if(spfa(n+1))
printf("lamentable kingdom\n");
else
printf("successful conspiracy\n");
}
return 0;
}

1008
hdu4004 贪心+二分
思路每次二分距离。找到满足跳跃的条件并且最小的值，注意细节，难想到的是二分解决此题。
#include
#include
#include
#include
#include
using namespace std;
int l,n,m;
int arr[500005];
int tanxin(int x)
{
int t=0;
int g;
for(int i=0;i{
if(arr[t+1]-

arr[t]>x)
{
return false;
}
g=t+1;
while(arr[g]-arr[t]<=x)
{
if(g==n+1)
return true;
g+=1;
}
t=g-1;
}
return false;
}
int main()
{
while(scanf("%d %d %d",&l,&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&arr[i]);
arr[0]=0;
arr[n+1]=l;
sort(arr,arr+n+2);
int x=1;
int y=l;
while(x{
int middle=x+(y-x)/2;
if(tanxin(middle))
y=middle;
else
x=middle+1;
}
printf("%d\n",y);
}
}


1010
hdu4009
图论 有向图求最短路
思路，建图成功套朱刘算法以后直接就能过。
#include
#include
#include
#include
#define maxn 1005
#define inf 1000000000
struct Edge
{
int s,t;
int cost;
}edge[maxn*maxn];
struct node{
int x,y,z;
}a[maxn];
int E,nv,ne;
int pre[maxn],Id[maxn],vis[maxn];
int in[maxn];
//最小树形图邻接表版本，三步走，找最小入弧，找有向环，缩环为点
int Directed_MST(int root)//点和边都是从0开始的
{//返回-1 为无最小树形图 返回为最小树形图值
int i,s,t;
nv++;
int ret = 0;
while(1)
{
//find the smallest in-arc
for(i=0;ifor(i = 0;i < ne;i++)
{
s = edge[i].s;
t = edge[i].t;
if(edge[i].cost>=in[t] || s == t)continue;
pre[t] = s;
in[t] = edge[i].cost;

}
in[root] = 0; pre[root]=root;
for(i = 0;i < nv;i++)
{
ret += in[i];
if(in[i] == inf)
return -1;
//there are some nodes other than root with no in-arc connected to it
}
//find the dir circle
int Idx = 0;
for(i = 0;i < nv;i++)if(vis[i]==-1)
{
t = i;
while(vis[t]==-1)
{
vis[t] = i;
t = pre[t];
}
if(vis[t]!=i||t==root)continue;
for(int s = pre[t]; s != t;s = pre[s])
Id[s] = Idx;
Id[t] = Idx++;
}
if(Idx == 0) break;//no circle
for(i = 0;i < nv;i++) if(Id[i] == -1)
Id[i] = Idx++;
//compress the nodes;
for(i = 0;i < ne;i++)
{
int v = edge[i].t;
edge[i].s = Id[edge[i].s];
edge[i].t = Id[edge[i].t];
edge[i].cost -= in[v];
}
nv = Idx;
root = Id[root];
}
return ret;
}
void add(int s,int t,int cost)
{
edge[ne].s=s;
edge[ne].t=t;
edge[ne++].cost=cost;
}
int dist(int i,int j)
{
return abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)+abs(a[i].z-a[j].z);
}
int main()

{
int i,j,x,y,z,k,temp;
while(scanf("%d%d%d%d",&nv,&x,&y,&z)!=EOF)
{
ne=0;
if(nv==0) break;
for(i=1;i<=nv;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
add(0,i,a[i].z*x);
}
for(i=1;i<=nv;i++)
{
scanf("%d",&k);
for(j=0;j{
scanf("%d",&temp);
if(temp==i) continue;
if(a[i].z>=a[temp].z)
add(i,temp,dist(i,temp)*y);
else add(i,temp,dist(i,temp)*y+z);
}
}
printf("%d\n",Directed_MST(0));
}
return 0;
}

1011
poj2356
数论简单的鸽巢原理。此题必有解，n=5 元素a1,a2,a3,a4,a5 且题中告诉每个元素都大于1。考虑最坏情况5个数都相同，则会出现以下不同的值a1,a1+a2
a1+a2+a3,a1+a2+a3+a4,a1+a2+a3+a4+a5这不同的5个值。如果说一个数n1是另外一个数n2的倍数则,n1%n2==0。根据之前的数据产生5个不同的数，最坏情况%5
余数为0 1 2 3 4。则取到0的即为结果。或者为任意组合,但肯定会有两个%5余数相同的结果。则相减即为结果。

#include
#include
#include
int arr[100050];
int brr[100050];
int crr[100050];
int n;
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
//printf("0000000\n");
memset(crr,0,sizeof(crr));
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
brr[1]=arr[1];
crr[brr[1]%n]=1;
if(brr[1]%n==0)
{
printf("1\n");
printf("%d\n",arr[1]);
continue;
}
for(int i=2;i<=n;i++)
{
brr[i]=brr[i-1]+arr[i];
if(crr[brr[i]%n])
{
printf("%d\n",i-crr[brr[i]%n]);
for(int j=crr[brr[i]%n]+1;j<=i;j++)
{
printf("%d",arr[j]);
printf("\n");
}
break;
}
else if(brr[i]%n==0)
{
printf("%d\n",i);
for(int j=1;j<=i;j++)
{
printf("%d",arr[j]);
printf("\n");
}
break;
}
else
{
crr[brr[i]%n]=i;
}
}
}
return 0;
}