| |
常用鏈接
留言簿(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);
}
}
|
|