| |
常用链接
留言簿(4)
随笔分类
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
Powered by: 博客园
模板提供：沪江博客
|
|
|
|
|
发新文章 |
|
 |
传说中的暴力搜索。。。 直接双重循环。。。
 #include"stdio.h"
  struct rec {
 int x1,x2,y1,y2;
 }rec [5001];
bool cover(int i,int j)
{
if((rec[i].x1>=rec[j].x1)&&(rec[i].x2<=rec[j].x2)&&(rec[i].y1>=rec[j].y1)&&(rec[i].y2<=rec[j].y2))return true;
else return false;
}
int main()
{
int n,i,k,j;
while(scanf("%d",&n)!=EOF)
  {
k=0;
for(i=1;i<=n;i++)
scanf("%d%d%d%d",&rec[i].x1,&rec[i].x2,&rec[i].y1,&rec[i].y2);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j&&cover(i,j)){k++;break; }
printf("%d\n",k);
 }
}
摘要: 类似手机智能英文输入法我的算法很复杂，虽然在自己电脑上实现了，但是在OD上居然出现了runtime error。。。先把说有输入的单词按使用频率排序，然后根据输入数字逐个查找。。用了n个循环。。。
#include <iostream>#include <vector>#include <string>#include ... 阅读全文
2个球,大小同,其中一个重量不同。现有一个天平,要用这个天平称3次找出这个不同重量的球,如何称?
将所有球编号为1-12；
第一步，将1-4号放左边，5-8号放右边：
若倾斜，假设右重（左重雷同）：
第二步[0]，将2-4移走，6-8移入左边，9-11移入右边：
若仍倾斜，则不同的那个为编号1或5号：
第三步[0][0]，将1号与2号比较，若相等，则5号偏重，反之，2号球偏轻；
若不倾斜，则不同的那个在编号2-4中，且偏轻；
第三步[0][1]，任取2-4种两球可得结果；
若不倾斜，则不同的在9-12中：
第二步[1]，移走6-8球，移入9-11球：
若倾斜，假设右重（左重雷同）：
第三步[1][0]，任取9-11种两球可得结果；
若不倾斜，则12号球异常：
第三步[1][1]，将12号球与其它任意球比较可知是轻是重；
类似冒泡程序 如果所有人是线性排列,那我们的工作就是类似冒泡程序做的工作:1,2,3,4,5变为5,4,3,2,1 ,耗时n(n-1)/2 但是出现了环,也就是说1,2,3,4,5变为3,2,1,5,4也可满足条件 我们可以把这个环等分成两个部分 ,每个部分看成是线性的,再把它们花的时间加起来. 当n是偶数时, 每份人数n/2 ,即 2*(n/2 )*(n/2 -1)/2; 当n是奇数时,两份的人数分别是n/2和n/2+1,即(n/2)*(n/2 -1)/2 + (n/2 +1)*(n/2)/2 ; 这思路太强了。。。
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
using namespace std;
int main()
{
int n,num,rnum;
vector<int> re;
cin>>n;
while (n>0)
{
cin>>num;
if (num%2==0)
{
rnum=(num/2-1)*(num/2)*2/2;
re.push_back(rnum);
}
if (num%2==1)
{
rnum=(num/2-1)*(num/2)/2+ (num/2+1)*(num/2)/2;
re.push_back(rnum);
}
n--;
}
for (size_t i=0;i<re.size();i++)
{
cout<<re[i]<<endl;
}
}
这是我同学的思路，比我的好多了。。。
一次判断各球的重量，如假设轻，若在重的一边或平衡端出现则假设错
Source Code
Problem: 1013 User: lnmm
Memory: 64K Time: 0MS
Language: C++ Result: Accepted
Source Code
#include"stdio.h"
#include"string.h"
char left[3][7],right[3][7],result[3][5];
bool isHeavy(char x )
{
int i;
for(i=0;i<3;i++)
{
switch(result[i][0])
{
case 'u':if(strchr(left[i],x)==NULL)return false;break;
case 'e':if(strchr(left[i],x)!=NULL||strchr(right[i],x)!=NULL)return false;break;
case 'd':if(strchr(right[i],x)==NULL)return false;break;
}
}
return true;
}
bool isLight(char x )
{
int i;
for(i=0;i<3;i++)
{
switch(result[i][0])
{
case 'u':if(strchr(right[i],x)==NULL)return false;break;
case 'e':if(strchr(left[i],x)!=NULL||strchr(right[i],x)!=NULL)return false;break;
case 'd':if(strchr(left[i],x)==NULL)return false;break;
}
}
return true;
}
void main()
{
int n;
char c;
int i;
scanf("%d",&n);
while(n>0)
{
for( i=0;i<3;i++)
scanf("%s%s%s",left[i],right[i],result[i]);
for(c='A';c<='L';c++)
{
if(isLight(c))
{
printf("%c is the counterfeit coin and it is light.\n",c);
break;
}
if(isHeavy(c))
{
printf("%c is the counterfeit coin and it is heavy.\n",c);
break;
}
}
n--;
}
}
输入三个数m,a,b,求出p,q使得a/b<=p/q<=1且p*q<m时，p,q的最大值 我是先求出sqrt(99999)中的所有质数，然后通过2个循环求出相应条件的极值 我不知道为啥错，反正自己电脑上是可以出来的。。。
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
using namespace std;
vector<int> prime; //存储质数
void prim()
{
bool pr;
for (int i=(int)sqrt((double)99999);i>1;i--)
{
pr=true;
for (int j=(int)sqrt((double)i);j>1;j--)
{
if (i%j==0)
{
pr=false;
break;
}
}
if (pr==true)
{
prime.push_back(i);
}
}
}
int main()
{
int m;prim();
double a,b;
while (scanf("%d %lf %lf",&m,&a,&b)!=EOF)
{
if (m==0&&a==0&&b==0)
{
break;
}
if(m<=4||a>b||m>100000||a>1000||b>1000||a<1||b<1)
{
break;
}
int p,q,pmax=0,qmax=0;
double ratio=a/b;
for (int i=0;i<prime.size();i++)
{
if (prime[i]>m/2)
{
continue;
}
if(prime[i]<=m/2)
{
for (int j=i;j<prime.size();j++)
{
p=prime[j];
q=prime[i];
double newratio=(double)p/(double)q;
if (newratio<ratio||p*q>=m)
{
continue;
}
if (p*q>pmax*qmax&&newratio>=ratio)
{
pmax=p;
qmax=q;
}
}
}
}
cout<<pmax<<" "<<qmax<<endl;
}
}
|
|