1 /*
2 * File: 100.cpp
3 * Author: GongZhi
4 * Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
5 * Created on 2009年7月25日, 下午9:01
6 */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18 *
19 */
20 int f(int i) {
21 if (i == 1)
22 return 1;
23 else if (i % 2)
24 return f(i * 3 + 1) + 1;
25 else
26 return f(i / 2) + 1;
27 }
28
29 int main() {
30 int i, j;
31 int r, l, t;
32 int rr, ll;
33 int ans;
34 while (scanf("%d%d", &r, &l) != EOF) {
35 rr = r;
36 ll = l;
37 if (r > l) {
38 t = r;
39 r = l;
40 l = t;
41 }
42 ans = 0;
43 for (i = r; i <= l; i++)
44 if (f(i) > ans) ans = f(i);
45 printf("%d %d %d\n", rr, ll, ans);
46 }
47 return 0;
48 }
49
50
51
在對元素進行字典序組合排列時可以使用STL提供的next_permutation()和prev_permutation()。這里例舉兩種簡單的應用。
POJ 1731 Orders （使用默認比較方法）
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int i,j,k,m,n;
char a[210];
while(gets(a) && a[0])
{
n=strlen(a);
sort(a,a+n); //先排序
printf("%s\n",a);
while(next_permutation(a,a+n)) //返回bool，若無更大的字典序排列返回false
printf("%s\n",a);
}
return 0;
}
POJ 1256 Anagram （需要自定義cmp函數）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctype.h>
using namespace std;
int cmp(char a, char b) //自定義cmp函數
{
if(tolower(a)==tolower(b))
return a<b;
return tolower(a)<tolower(b);
}
int main()
{
char s[15];
int i,j,k,m,n;
cin>>n;
cin.ignore();
while(n--)
{
cin.getline(s,15);
k=strlen(s);
sort(s,s+k,cmp);
cout<<s<<endl;
while(next_permutation(s,s+k,cmp))
cout<<s<<endl;
}
return 0;
}
就是判斷一個坐標系里面的三角形內有多少個整數點
就是枚舉所有的整數點然后判斷是否在三角形內就是了。
判斷是否在三角形內的方法就是求一下三部分的面積是否等于那個大三角形的面積
求面積可以用叉乘或者海倫公式
最好不要用實數來判等
因為三角形的面積乘以2以后是個整數
所以判等的過程中就要使用整數來就可以了
注意輸出格式
1
#include<stdio.h>
2#include<string.h>
3#include<math.h>
4char map[50][50];
5int S(int a,int b,int c,int d)
6
{
7
int k;
8 k=a*d-b*c;
9 if(k<0)k=-k;
10 return k;
11
}
12int main()
13{
14// freopen("aaaaaaa.txt","w",stdout);
15 int x1,x2,x3,y1,y2,y3,mx,my,mmx,mmy,minx,miny,maxx,maxy,ss,s1,s2,s3,i,j,t;
16 while(scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF)
17
{
18 minx=1000000;maxx=-100000;
19 miny=1000000;maxy=-100000;
20 ss=S(x2-x1,y2-y1,x3-x1,y3-y1);
21 memset(map,0,sizeof(map));
22 mx=x1;if(x2>mx)mx=x2;if(x3>mx)mx=x3;
23 my=y1;if(y2>my)my=y2;if(y3>my)my=y3;
24 mmx=x1;if(x2<mmx)mmx=x2;if(x3<mmx)mmx=x3;
25 mmy=y1;if(y2<mmy)mmy=y2;if(y3<mmy)mmy=y3;
26 for(i=mmx;i<=mx;i++)
27 for(j=mmy;j<=my;j++)
28 {
29 s1=S(x1-i,y1-j,x2-i,y2-j);
30 s2=S(x1-i,y1-j,x3-i,y3-j);
31 s3=S(x2-i,y2-j,x3-i,y3-j);
32 if(s1 && s2 && s3 && (s1+s2+s3)==ss)
33 {
34 map[i+10][j+10]=1;
35 if(i+10<minx)minx=i+10;
36 if(i+10>maxx)maxx=i+10;
37 if(j+10>maxy)maxy=j+10;
38 if(j+10<miny)miny=j+10;
39
}
40 }
41 for(j=maxy;j>=miny;j--)
42 {
43 for(i=minx;i<=maxx;i++)if(map[i][j])t=i;
44 for(i=minx;i<=t;i++)
45 {
46 if(i!=minx)printf(" ");
47 if(map[i][j])printf("(%2d, %2d)",i-10,j-10);
48 else printf(" ");
49 }
50 printf("\n");
51 }
52 printf("\n");
53 }
54 return 0;
55}
56
Source: Rocky Mountain 2000
題目就是要問從起點時刻第一次走到終點時刻的過程中分針和時針相遇了多少次
我們知道時針每分鐘走動0.5度分鐘每分鐘走動6度
t為從00：00到當前時刻走了多少分鐘
那么分針就比時針多走了5.5t度
當沒多走360就說明分針與時針相遇了一次
然后我們就算起點時刻和終點時刻分別對00:00來說相遇了時針多少次
然后他們的差值就是這段區間內相遇了多少次
如果起點時刻小于終點時刻那么就是這個差值加上11
因為一個周期內最多相遇11次
1#include<stdio.h>
2int a[100];
3int main()
4{
5 int a,b,c,d,l1,l2,ans,aa,cc;
6 printf("Initial time Final time Passes\n");
7
8 while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
9 {
10 aa=a;cc=c;
11 if(a==12)aa=0;
12 if(c==12)cc=0;
13 l1=aa*60+b;l2=cc*60+d;
14 ans=((l2*11)/720)-((l1*11)/720);
15 if(l1>l2)ans+=11;
16 printf(" %02d:%02d %02d:%02d %2d\n",a,b,c,d,ans);
17 }
18 return 0;
19}
20
Source: Rocky Mountain 2000
比較煩人的字符串處理問題
題目對于數據范圍也沒有給出明確的說明
只能開一個大數組來模擬了。
然后每次借走了就標記一下
當還回來的時候就要把這個書在隊列最后再新加入了。
輸出就按照題目的就可以了
多注意就是了
第一次提交忘記了去掉freopen了
1#include<map>
2#include<string.h>
3#include<stdio.h>
4#include<string>
5using namespace std;
6char cz[40],str[40],use[1000];
7char data[1000][40];
8map<string,int> name;
9string now,t;
10int l,N,n,num[1000];
11void PRINT()
12{
13 int i;
14 for(i=l-1;i>=0;i--)
15 if(use[i])
16 {
17 printf("%s%4d\n",data[i],num[i]);
18
19 }
20 printf("AVAILABLE SHELF SPACE: %4d\n\n",N-n);
21 gets(str);
22}
23void ADD()
24{
25 int k,temp=1,L=0;
26 char ch;
27 for(k=0;k<6;k++)scanf("%c",&ch);
28 gets(data[l]);
29 sscanf(data[l]+30,"%d",&L);
30 data[l][30]=0;
31 n+=L;num[l]=L;
32
33 t=data[l];
34 name[t]=l;
35 use[l]=1;
36 k=0;
37 while(n>N)
38 {
39 if(use[k])
40 {
41 use[k]=0;
42 n-=num[k];
43 }
44 k++;
45 }
46 l++;
47}
48void CHECKOUT()
49{
50 int k,i;char ch;
51 scanf("%c",&ch);
52 gets(str);
53 for(i=strlen(str);i<30;i++)str[i]=' ';
54 str[30]=0;
55 t=str;
56 k=name[t];
57 use[k]=0;
58 n-=num[k];
59}
60void RETURN()
61{
62 int k,i;
63 char ch;
64 for(i=0;i<3;i++)scanf("%c",&ch);
65 gets(str);
66 for(i=strlen(str);i<30;i++)str[i]=' ';
67 str[30]=0;
68 t=str;
69 k=name[t];
70 for(i=0;i<31;i++)data[l][i]=data[k][i];
71 use[l]=1;num[l]=num[k];
72 n+=num[l];
73 k=0;
74 while(n>N)
75 {
76 if(use[k])
77 {
78 use[k]=0;
79 n-=num[k];
80 }
81 k++;
82 }
83 l++;
84}
85int main()
86{
87 //freopen("bbbbbbbbbb.txt","w",stdout);
88 scanf("%d",&N);n=0;l=0;
89 name.clear();
90 memset(use,0,sizeof(use));
91 while(scanf("%s",cz)!=EOF)
92 {
93 now=cz;
94 if(now=="PRINT")PRINT();
95 else if(now=="ADD")ADD();
96 else if(now=="CHECKOUT")CHECKOUT();
97 else if(now=="RETURN")RETURN();
98 }
99 return 0;
100}
101
數學問題。
題目很難讀懂。
給定的一個周期的時間表是的是
左下那個點到右下那個點的時間
然后那個圓的周長占一個位置
然后就是要注意一下這兩個點是在偏左的位置還是偏右的位置相遇
只需要判斷一下從第一個點順序走到第二個點的距離是否小于一半的總距離就好了
答案就出來了
1#include<stdio.h>
2int main()
3{
4 int n,l,a,b,f,L;
5 double t,p,ans,min;
6 scanf("%d%lf",&n,&t);
7 f=n/2;
8 p=t/(f-0.5);
9 printf("N =%4d, T =%6.1lf\n",n,t);
10 while(scanf("%d%d",&a,&b)!=EOF)
11 {
12 l=a-b;
13 L=a-b;
14 if(l<0)
15 {
16 l=-l;
17 L+=n;
18 }
19 ans=(l-0.5)*p;
20 if((ans/2)>(t-ans/2))min=(t-ans/2);
21 else min=(ans/2);
22 printf("Chair%4d meets chair%4d, remaining time =",a,b);
23 if(L<f)printf("%6.1lf\n",min);
24 else printf("%6.1lf\n",t-min);
25
26 }
27 return 0;
28
29}
先開始一直想著很復雜的題目
想了很久
后來看那么多人都過了
感覺應該很簡單
然后就想著貪心應該就可以
然后就貪心了一下
順序往下掃描然后看到這個點是1
那么就把這點為左上角的點的矩形方塊操作一下啊
然后一直這樣往后就可以了
1#include<stdio.h>
2
3char str[110][110];
4
5int main()
6{
7 int x,y,len,wide,i,c,p1,p2,j;
8 while(1)
9 {
10 scanf("%d %d %d %d", &x,&y,&len,&wide);
11 if(x == 0 && y == 0 && len == 0 && wide == 0)
12 break;
13 for(i = 0; i < x; i++)
14 scanf("%s",str[i]);
15 c = 0;
16 for(i = 0; i < x; i++)
17 {
18 for(j = 0; j < y; j++)
19 {
20 if(str[i][j] == '1')
21 {
22 if(i+len-1 >= x || j+wide-1 >= y) break;
23 c++;
24 for(p1 = i; p1 < i+len; p1++)
25 for(p2 = j; p2 < j+wide; p2++)
26 {
27 if(str[p1][p2] == '1')
28 str[p1][p2] = '0';
29 else
30 str[p1][p2] = '1';
31 }
32 }
33 }
34 if(j != y) break;
35 }
36 if(i != x || j != y)
37 printf("-1\n");
38 else
39 printf("%d\n",c);
40 }
41 return 0;
42}
43
44
學過英語的就都知道怎么做
沒學過的題目也看不懂的。
我這種水平的都能看懂所以感覺沒什么好注意的了
1#include<stdio.h>
2#include<map>
3#include<string>
4using namespace std;
5
6map<string,int>p1;
7
8int main()
9{
10 char str1[50],str2[50][50],str[50];
11 string s;
12 int m,n,len,i;
13 scanf("%d %d", &m, &n);
14 for(i = 0; i < m; i++)
15 {
16 scanf("%s %s",str1,str2[i]);
17 s = str1;
18 p1[s] = i;
19 }
20 while(n--)
21 {
22 scanf("%s",str);
23 s = str;
24 if(p1.count(s) == 1)
25 {
26 printf("%s\n",str2[p1[s]]);
27 continue;
28 }
29 len = strlen(str);
30 if(len == 1 && str[len-1] == 'y')
31 {
32 str[len-1] = 'i';
33 str[len] = 'e';
34 str[len+1] = 's';
35 str[len+2] = '\0';
36 }
37 else if(len > 1 && str[len-1] == 'y' && str[len-2] != 'a' && str[len-2] != 'i' && str[len-2] != 'o' && str[len-2] != 'e' && str[len-2] != 'u')
38 {
39 str[len-1] = 'i';
40 str[len] = 'e';
41 str[len+1] = 's';
42 str[len+2] = '\0';
43 }
44 else if(len > 1 && str[len-1] == 'h' && (str[len-2] == 's' || str[len-2] == 'c'))
45 {
46 str[len] = 'e';
47 str[len+1] = 's';
48 str[len+2] = '\0';
49 }
50 else if(str[len-1] == 's' || str[len-1] == 'o' || str[len-1] == 'x')
51 {
52 str[len] = 'e';
53 str[len+1] = 's';
54 str[len+2] = '\0';
55 }
56 else
57 {
58 str[len] = 's';
59 str[len+1] = '\0';
60 }
61 printf("%s\n",str);
62 }
63 return 0;
64}
65
66