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