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>
4
char map[50][50];
5
int S(int a,int b,int c,int d)
6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
7
int k;
8
k=a*d-b*c;
9
if(k<0)k=-k;
10
return k;
11
}
12
int main()
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
43
for(i=minx;i<=maxx;i++)if(map[i][j])t=i;
44
for(i=minx;i<=t;i++)
45![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Source: Rocky Mountain 2000
题目就是要问从起点时刻第一次走到终点时刻的过程中分针和时针相遇了多少次
我们知道时针每分钟走动0.5度分钟每分钟走动6度
t为从00:00到当前时刻走了多少分钟
那么分针就比时针多走了5.5t度
当没多走360就说明分针与时针相遇了一次
然后我们就算起点时刻和终点时刻分别对00:00来说相遇了时针多少次
然后他们的差值就是这段区间内相遇了多少次
如果起点时刻小于终点时刻那么就是这个差值加上11
因为一个周期内最多相遇11次
1
#include<stdio.h>
2
int a[100];
3
int main()
4![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
5
int a,b,c,d,l1,l2,ans,aa,cc;
6
printf("Initial time Final time Passes\n");
7![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
8
while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Source: Rocky Mountain 2000
比较烦人的字符串处理问题
题目对于数据范围也没有给出明确的说明
只能开一个大数组来模拟了。
然后每次借走了就标记一下
当还回来的时候就要把这个书在队列最后再新加入了。
输出就按照题目的就可以了
多注意就是了
第一次提交忘记了去掉freopen了
1
#include<map>
2
#include<string.h>
3
#include<stdio.h>
4
#include<string>
5
using namespace std;
6
char cz[40],str[40],use[1000];
7
char data[1000][40];
8
map<string,int> name;
9
string now,t;
10
int l,N,n,num[1000];
11
void PRINT()
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
13
int i;
14
for(i=l-1;i>=0;i--)
15
if(use[i])
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
printf("%s%4d\n",data[i],num[i]);
18![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
19
}
20
printf("AVAILABLE SHELF SPACE: %4d\n\n",N-n);
21
gets(str);
22
}
23
void ADD()
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
33
t=data[l];
34
name[t]=l;
35
use[l]=1;
36
k=0;
37
while(n>N)
38![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
39
if(use[k])
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
41
use[k]=0;
42
n-=num[k];
43
}
44
k++;
45
}
46
l++;
47
}
48
void CHECKOUT()
49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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
}
60
void RETURN()
61![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
76
if(use[k])
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
78
use[k]=0;
79
n-=num[k];
80
}
81
k++;
82
}
83
l++;
84
}
85
int main()
86![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
数学问题。
题目很难读懂。
给定的一个周期的时间表是的是
![](http://acm.tju.edu.cn/toj/vcontest/2093_chairlift2.gif)
左下那个点到右下那个点的时间
然后那个圆的周长占一个位置
然后就是要注意一下这两个点是在偏左的位置还是偏右的位置相遇
只需要判断一下从第一个点顺序走到第二个点的距离是否小于一半的总距离就好了
答案就出来了
1
#include<stdio.h>
2
int main()
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
12
l=a-b;
13
L=a-b;
14
if(l<0)
15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
26
}
27
return 0;
28![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
29
}
先开始一直想着很复杂的题目
想了很久
后来看那么多人都过了
感觉应该很简单
然后就想着贪心应该就可以
然后就贪心了一下
顺序往下扫描然后看到这个点是1
那么就把这点为左上角的点的矩形方块操作一下啊
然后一直这样往后就可以了
1
#include<stdio.h>
2![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3
char str[110][110];
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
int main()
6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
7
int x,y,len,wide,i,c,p1,p2,j;
8
while(1)
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
18
for(j = 0; j < y; j++)
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
20
if(str[i][j] == '1')
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
44![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
学过英语的就都知道怎么做
没学过的题目也看不懂的。
我这种水平的都能看懂所以感觉没什么好注意的了
1
#include<stdio.h>
2
#include<map>
3
#include<string>
4
using namespace std;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
map<string,int>p1;
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
int main()
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
16
scanf("%s %s",str1,str2[i]);
17
s = str1;
18
p1[s] = i;
19
}
20
while(n--)
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
22
scanf("%s",str);
23
s = str;
24
if(p1.count(s) == 1)
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
26
printf("%s\n",str2[p1[s]]);
27
continue;
28
}
29
len = strlen(str);
30
if(len == 1 && str[len-1] == 'y')
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
52
str[len] = 'e';
53
str[len+1] = 's';
54
str[len+2] = '\0';
55
}
56
else
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
58
str[len] = 's';
59
str[len+1] = '\0';
60
}
61
printf("%s\n",str);
62
}
63
return 0;
64
}
65![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
66![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)