Jove's Blog

I love what I do

发表于 更新于

题目链接：http://poj.org/problem?id=2215

解释下题意，本题给出一个矩阵，然后每给出一个子矩阵的四个坐标，求子矩阵的和。

说下思路，每次输入数据的时候顺便做个简单的运算，来算出这个点到原点的所有的数的和，

在计算给定子矩阵的时候我们运用个简单的数学原理，如图

我们可以计算子矩阵的和，同面积的一种计算方法，利用r2s2-r1s2-r2s1+r1s1这样就行了，现开始错了几遍因为r1s1算的时候要减去1不然就没有算上上和左两条边！

这个题不敢用输入流，看到这种输入多的题，我就感觉要超时，虽然麻烦点，不过还是稳点把！！！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*Problem: 2215		User: awq123
**Memory: 4096K		Time: 63MS
**Language: C++		Result: Accepted
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int t,n,i,j,r,s,r1,r2,s1,s2,temp,a[1001][1001];
	scanf("%d",&n;);
	while(n--)
	{
		memset(a,0,sizeof(a));
		scanf("%d%d",&r;,&s;);
		for(i=1;i<=r;i++)
			for(j=1;j<=s;j++)
			{
				scanf("%d",&temp;);
				a[i][j]=temp+a[i][j-1]+a[i-1][j]-a[i-1][j-1];
			}
		scanf("%d",&t;);
		while(t--)
		{
			scanf("%d%d%d%d",&r1;,&s1;,&r2;,&s2;);
			r1--;s1--;
			temp=a[r2][s2]-a[r1][s2]-a[r2][s1]+a[r1][s1];
			printf("Absolutni hodnota pohodlnosti je %d bodu.n",temp);
		}
		printf("n");
	}
}

发表于 更新于

题目链接：http://poj.org/problem?id=2211

先解释下题意，由n个人一起合影，每张照片可以容下k个人，问给出的排列是第几个照相的，也就是排列问题。

比如第三个例子

3 3
1 2 3

那么只用照一次就够了

比如给出数据

3 2
3 2

那么照相的顺序为

1 2
1 3
2 1
2 3
3 1
3 2

所以输出为6

讲下思路，我也是在discuss里看的，没想到有这么简单的思路，这个方法应该用的是贪心。
首先利用数组输入数据，然后由第一个数开始依次判断，假设这个数为t那么前面的t-1个数的情况都是完整的全排列，比如第四个例子是一个5 3的数据，第一个数5，那么前面可能的数1 2 3 4，都有全排列的种数，每种4×3。
关键是接下来的思路，对后面的数扫描如果大于t那么都减去1，这样从下一个开始就转化为了一个4 2的数据，每次只判断第一个的全排列，一直到最后，所有的加起来就是所有的排列数了！

原来排列都是通过先排列在计数的方式，时间慢，切复杂，这个题给了我全新的思路，强烈推介下，虽然代码不长，但绝对的好题！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*Problem: 2211		User: awq123
**Memory: 252K		Time: 141MS
**Language: C++		Result: Accepted
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int t,n,i,j,k,num,temp,m,a[13];
	cin>>t;
	for(i=1;i<=t;i++)
	{
		cin>>n>>k;
		num=1;
		for(j=1;j<=k;j++)
			cin>>a[j];
		for(j=1;j<=k;j++)
		{
			temp=a[j]-1;
			for(m=n-j;m>=n-k+1;m--)
				temp*=m;
			num+=temp;
			for(m=j+1;m<=k;m++)
				if(a[m]>a[j])
					a[m]--;		
		}
		cout<<"Variace cislo "<<i<<" ma poradove cislo "<<num<<"."<<endl;
	}
}

发表于 更新于

题目链接：http://poj.org/problem?id=1922

题意简单讲下，有个男的比较怪，喜欢跟着快的走，然后给出，几个人的速度和出发时间，求出这个男的到的时间；

其实题意很容易想到算法，那么这个男的必然和第一个到达的同时到达，当然要去掉时间为负数，提前出发的人。

这个题不难，主要是纠结了两个问题，

一个是，当是时间为不为整数的时候应该，统一取大于大的那个整数，但是自动转换会取小的，我利用了一个简单的算法，想了半天

1
2
3
4
5
6
7
8
int temp=min;
if(temp==min)
	cout<<temp<<endl;
else 
	cout<<temp+1<<endl;



1
2
3
cout<<ceil(min)<<endl;


1
2
3
ts=4500/(v/3.6)+t;


综合来说题目不难，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*Problem: 1922		User: awq123
**Memory: 256K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int n,i,t,v;
	double ts,min;
	while(cin>>n&&n;)
	{
		min=4500*3.6;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&v;,&t;);
			if(t>=0)
			{
				ts=4500*3.6/v+t;
				if(ts<min)
					min=ts;
			}
		}
		int temp=min;
		if(temp==min)
			cout<<temp<<endl;
		else 
			cout<<temp+1<<endl;
	}
}

发表于 更新于

题目链接：<http://poj.org/problem?id=1147

参考：http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

压缩算法为：给出一个2进制的字符串，依次左移一个数，得到多个字符串，给这些字符串排序，然后输出排列矩阵的最后一竖列

题目要求我们进行解压操作，也就是给我们答案，求给出的2进制字符串。

现开始以为只要排个序就行了，但是只能WA，看了解题报告才懂了一点，算法不介绍了上面讲得很详细了！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*Problem: 1147		User: awq123
**Memory: 276K		Time: 32MS
**Language: C++		Result: Accepted
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int a[3001],b[3001],n,i,j,k;
	cin>>n;
	k=0;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]==0)
			k++;
	}
	j=1;
	k++;
	for(i=1;i<=n;i++)
		if(a[i])
			b[k++]=i;
		else
			b[j++]=i;
	k=1;
	for(i=1;i<=n;i++)
	{
		k=b[k];
		cout<<a[k]<<" ";
	}	
}

发表于 更新于

题目链接：http://poj.org/problem?id=1118

这个题要我们求出在2维坐标系内，共线的点的最大数值。

对于这样的题，最大的困难就是超时，这个也不利外，我的最先的思路是对于每两个点求k和b再对于一组k和b验证每一个，TLE！

后来优化了下，分别取i=0,j=i+1,m=j+1这样就很好的去除的重复的状况，另外验算的方法也改成了，比较三者斜率，一样则计数+1.

我第一次AC用了1625MS很大，后来试了改了下一段代码居然594MS，不过我觉得其实改了后应该是错的，因为我改的是，left和right的类型，本来是float改为int这样会由误差，但是可能OJ系统的数据比较好把，

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*Problem: 1118		User: awq123
**Memory: 260K		Time: 594MS
**Language: C++		Result: Accepted
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct point
{
	int x,y;
}p[700];

int main()
{
	int n,i,j,m,max,temp;
	while(cin>>n&&n;)
	{
		max=0;
		for(i=0;i<n;i++)
			scanf("%d%d",&p;[i].x,&p;[i].y);
		for(i=0;i<n;i++)	
			for(j=i+1;j<n;j++)
			{
				temp=0;
				for(m=j+1;m<n;m++)
				{
					int left=(p[i].x-p[m].x)*(p[j].y-p[m].y);
					int right=(p[j].x-p[m].x)*(p[i].y-p[m].y);
					if(left==right)
						temp++;
				}
				if(temp>max)
					max=temp;
			}	
		cout<<max+2<<endl;
	}
}

发表于 更新于

题目链接：http://poj.org/problem?id=1700

题意就是我们以前听过的过桥的故事。但是这里时过河，一条船每次只能过两个人，问过去的最小路程

查阅相关资料，利用贪心算法解题，具体思路时这样的：

设i=人数；
i<3时，直接过去；
i=3时，设速度为ABC升序，那么A护送C过去，再回来，再送B过去最短，也就是t[0]+t[1]+t[2]
i>=4时，设最快的A，次快的B，次慢的C，最慢的D，
（1）如果用最小的来送:d+a+c+a+b=d+c+b+2a
（2）如果先让最小的两个过河,再让其中一个回来,
让最大的两个过河,再让前一步过去留下的那个回来,
再让最小的2个过河
也就是说小的两个过去2次,再单独回来一次.
2b+b+a+d=d+3b+a
比较两种方法，选小的；

我们分析每次的情况人数从N开始倒数回去，每次选取最优解，则得到的时最小值！

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*Problem: 1700		User: awq123
**Memory: 256K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
	int m,n,i,max,t[1001];
	cin>>m;
	while(m--)
	{
		cin>>n;
		for(i=0;i<n;i++)
			cin>>t[i];
		max=0;
		sort(t,t+n);
		for(i=n-1;i>2;i-=2)
			if(t[0]+2*t[1]+t[i]>2*t[0]+t[i]+t[i-1])
				max+=2*t[0]+t[i]+t[i-1];
			else
				max+=t[0]+2*t[1]+t[i];
		if(i==2)
			max+=t[0]+t[1]+t[2];
		else if(i==1)
			max+=t[1];
		else
			max+=t[0];
		cout<<max<<endl;
	}
}

发表于 更新于

题目链接：http://poj.org/problem?id=1132

一个简单的模拟题，这个题目题意很容易理解，依据给出的坐标，按照给出的线路行走，然后输出围绕这个线路的方块。

我们可以拿笔纸画一画。
E就是这个点的右下方的那个方块，N就是这个点右上方的那个方块，W就是左上方的那个方块，S就是左下方的那个方块。

这样看来我们可以清楚的发现，根据字符串的每一个字母都能确认一个方块那么依次扫描就是了，其中遇到重复的也不要紧。

先开始一直PE我就是不懂，还数了半天点点，也对啊。后来才看到题目中这样一句话

Output a blank line after each bitmap.

这才AC，尴尬啊！！！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
	char map[33][33];
	char ch[1000];
	int n,x,y,len,i,t,j;
	cin>>n;
	for(t=1;t<=n;t++)
	{
		memset(map,'.',sizeof(map));
		cin>>x>>y;
		cin>>ch;
		len=strlen(ch);
		for(i=0;i<len;i++)
		{
			switch(ch[i])
			{
				case 'E':map[++x][y]='X';break;
				case 'N':map[x+1][++y]='X';break;
				case 'W':map[x--][y+1]='X';break;
				case 'S':map[x][y--]='X';break;
				default:break;	
			}
		}
		cout<<"Bitmap #"<<t<<endl;
		for(i=32;i>0;i--)
		{
			for(j=1;j<33;j++)
				cout<<map[j][i];
			cout<<endl;
			
		}
		cout<<endl;
	}
}

发表于 更新于

题目链接：http://poj.org/problem?id=1126

这个题给出几条语法要求，让我们判断词汇是否符合语法要求，大概可以描述成：
1.单个从p到z的字符满足条件；
2.如果字符串s（注意是字符串，我现开始以为是字母s）满足条件，Ns也满足条件。
3.如果字符串s和字符串t满足条件，Cst,Dst,Est,Ist也满足条件。

思路是这样的，给每一个字母一个值，由后往前，类似递归的查看方式，倒推出这一个字符串是否符合，若结果为-1，则正好满足题目要求的嵌套方式，输出yes。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*Problem: 1126		User: awq123
**Memory: 208K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    char data[260];
    int i,top,list[260];
    bool flag;
    while(cin>>data)
    {
	top=strlen(data)-1;
	flag=1;
	for(i=0;i<=top;i++)
	{
	    if(data[i]=='N')
	        list[i]=1;
	    else if(data[i]=='C'||data[i]=='D'||data[i]=='E'||data[i]=='I')
	        list[i]=2;
	    else if(data[i]>='p'&&data;[i]<='z')
	        list[i]=-1;
	    else 
	    {    
	        flag=0;
	        break;
	    }
	}
	if(flag==0)
	    cout<<"NO"<<endl;
	else
	{
	    int sum=0;
	    while(top>=0)
	    {
	        sum+=list[top];
	        if(sum>0)
	            break;
	        if(list[top]>0)
	            sum--;
	        top--;
	    }
	    if(sum==-1)
	        cout<<"YES"<<endl;
	    else 
	        cout<<"NO"<<endl;
	}
    }
}

发表于 更新于

在做1209的时候需要带空格的输入字符串，但是scanf会以空格结束输入，这个很不方便，查了点资料后发现gets函数可以实现带空格的输入因为gets是以回车结束的。

gets（）函数的原型：char * gets(char *str)
函数功能：从标准输入流读取字符串并回显，读到回车符时退出

但是同时有人说不推荐使用gets（）函数。因为它有个能致命的缺陷，就是不能指定缓冲区，当输入的字符大于缓冲区写入的空间，会使缓冲区溢出，这将有可能会导致不可预料的错误，这种错误可能是非常严重的。

还看到一种scanf的用法，我很是喜欢，虽然不是很懂原理但是还是先记下了

1
2
3
4
scanf("%[^n]",str)；



1
2
3
4
5
6
7
8
9
#include <cstdio>
int main()
{
	char str[10];
	scanf("%[^n]", str);
	printf("%s", str);
}


记录下，以后一定会有用的！

发表于 更新于

题目链接：http://poj.org/problem?id=2371

水题 没什么好解释的，题意要求先输入一个数N在输入N个数，以###分开，排序后，输入数N，再输入N个数，每输入一个数，求这个数位置上的数，本来题意很简单的，不理解为什么写这么复杂。

一大早起来作个题娱乐下，无提升。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*Problem: 2371		User: awq123
**Memory: 608K		Time: 63MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int m,n,i;
	char s[3];
	vector<int> num(100000);
	scanf("%d",&m;);
	for(i=0;i<m;i++)
		scanf("%d",&num;[i]);
	sort(num.begin(),num.begin()+m);
	cin>>s;
	scanf("%d",&n;);
	while(n--)
	{
		scanf("%d",&i;);
		printf("%dn",num[i-1]);
	}

}