|
常用链接
留言簿(4)
随笔分类
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
Powered by: 博客园
模板提供:沪江博客
|
|
|
|
|
发新文章 |
|
|
STL里的next_permutation和strchr的配合使用,很方便
#include <iostream> #include <string> #include <vector> #include <cmath> #include <algorithm> using namespace std;
int main() { int n; char input[100][6]; while (scanf("%d",&n)!=EOF) { if (n==0) break; char team[6]={'A','B','C','D','E'}; for (int i=0;i<n;i++) { scanf("%s",input[i]); } int count,min=9999; char output[6]; do { count=0; for (int i=0;i<n;i++) { for (int j=0;j<4;j++) { for (int k=j+1;k<5;k++) { if (strchr(input[i],team[j])>strchr(input[i],team[k])) { count++; } } } } if (count<min) { min=count; memcpy(output,team,6); } } while (next_permutation(team,team+5)); printf("%s is the median ranking with value %d.\n",output,min); } }
计算Ted后代的年龄并排序 第一次用结构,居然一次AC了,很爽。。 运用递归查找相应节点的上一代年龄,没有则再向上查
#include <iostream> #include <string> #include <vector> #include <cmath> using namespace std;
struct descedant { char father[20]; char child[20]; int age; //child的年龄 int differ; void init(); };
void descedant::init() //初始化 { age=0; differ=0; }
descedant des[100];
void getAge(descedant& d,int n) //递归计算出年龄 { for (int j=0;j<n;j++) { if (strcmp(d.father,des[j].child)==0) { if (des[j].age==0) //未计算则递归算上一代 { getAge(des[j],n); } d.age=des[j].age-d.differ; break; } } }
int cmp(const void* a,const void* b) //排序,年龄从大到小,若年龄相同则按字典顺序 { descedant* c=(descedant*)a; descedant* d=(descedant*)b; if (c->age==d->age) return strcmp(c->child,d->child); return d->age-c->age; } int main() { int n,num,count=1; scanf("%d",&n); while (n--) { scanf("%d",&num); int k=0; for (int i=0;i<num;i++) { des[k].init(); scanf("%s %s %d",des[k].father,des[k].child,&des[k].differ); if (strcmp(des[k].father,"Ted")==0) { des[k].age=100-des[k].differ; } k++; } for (int i=0;i<num;i++) { if (des[i].age==0) { getAge(des[i],num); } } qsort(des,num,sizeof(descedant),cmp); printf("DATASET %d\n",count++); for (int i=0;i<num;i++) { printf("%s %d\n",des[i].child,des[i].age); } } }
实现《算法导论》里的算法,一步一步来。。。 合并过程中的变量容易搞错,特别不能忽略合并过程中数组边界的改变!!!
#include <iostream> #include <string> #include <vector> #include <cmath> using namespace std;
void Merge(int a[],int p,int k,int q) { int num1=k-p+1; int num2=q-k; int i; int* b1=new int[num1+1]; int* b2=new int[num2+1]; for (i=0;i<num1;i++) { b1[i]=a[p+i]; } b1[i]=9999; for (i=0;i<num2;i++) { b2[i]=a[k+i+1]; } b2[i]=9999; int j=0;i=0; for(int kk=p;kk<=q;kk++) //注意!!! { if (b1[i]<=b2[j]) a[kk]=b1[i++]; else a[kk]=b2[j++]; } delete [] b1; delete [] b2; } void MergeSort(int a[],int p,int q) { if (p<q) { int k=(p+q)/2; MergeSort(a,p,k); MergeSort(a,k+1,q); Merge(a,p,k,q); } } int main() { int n; scanf("%d",&n); int* input=new int[n]; for (int i=0;i<n;i++) { scanf("%d",&input[i]); } MergeSort(input,0,n-1); for (int i=0;i<n;i++) { printf("%d ",input[i]); } delete [] input; }
计算h个a的b次幂的和,然后对m取余。。。直接pow是不行的 查找《算法导论》后得到算法,太牛逼了 先将b转换成2进制,存放在一个数组bin里面 d<-1 for i=0 to k-1 k为bin中存放的个数 d<-d*d mod m if bin[i]==1 d<-d*a mod m 以上是a的b次幂的算法
#include <iostream> #include <string> #include <vector> using namespace std;
vector<int> bin,rev;
void GetBinary(long long int b) { long long int temp; while (b) { bin.push_back(b%2); b=b/2; } for (int i=bin.size()-1;i>=0;i--) { rev.push_back(bin[i]); } } int main() { int num; long long int d,sum,h,m,a,b; scanf("%d",&num); while (num--) { sum=0; scanf("%lld",&m); scanf("%lld",&h); while (h--) { scanf("%lld %lld",&a,&b); bin.clear();rev.clear(); GetBinary(b); d=1; for(int index=0;index<(size_t)rev.size();index++) { d=(d*d)%m; if (rev[index]==1) d=(d*a)%m; } sum+=d; } printf("%lld\n",sum%m); } }
|
|