01/10/2018, 09:31

Xin cách khắc phục "time limit exceeded" trên SPOJ

link đề: http://www.spoj.com/problems/TOANDFRO/
code của mình;

#include <iostream>
#include<string.h>
using namespace std;

int main() 
{
	int col;
	cin>>col;
	cin.ignore(1);
	while(col)
	{
		char s[300];
		cin.get(s,300);
		int row = strlen(s)/col;
		int i,j,k=0;
		char matrix_string[20][20];
		for(i=0; i<row; i++)
		{
			if(i%2)
			{	for(j=col-1; j>=0; j--)
					matrix_string[i][j]= s[k++];}
			else 
			{	
				for(j=0; j<col; j++)
					matrix_string[i][j]=s[k++];}
		}
		for(j=0; j<col; j++)
		{	for(i=0; i<row; i++)
				cout<< matrix_string[i][j];}
		cout<<endl;
		cin>>col;
	}
	return 0;
}

rogp10 viết 11:40 ngày 01/10/2018

Bạn thử cách khác không dùng đến mảng hai chiều xem sao

Nguyễn Duy Hùng viết 11:40 ngày 01/10/2018

Có lẽ nên đổi qua quản lý bằng string thì tốt hơn. Giảm số vòng for lại
Giải thuật mới như thế này, cũng gần tương tự như của bạn thôi

Đọc số w, và str
Chia str ra thành (len(str)/w) chuỗi con subtrs mỗi substrs có chiều dài w, và bỏ vào một vector ls hoặc có thể dùng mảng string @.@. Nếu substrs(i) với i là lẻ thì đảo chuỗi em nó.

string res = "";
for(j = 0; j < w: j++){
    for(i = 0; i < ls.size(); i++){
        res += substrs[i][j];
    }
}
print res

@.@ Vì đã lâu không đụng đến C++ nên khá ngại sửa code, nên chỉ đóng góp ý tưởng vậy thôi. Có thể tham khảo code python.

while True:
        w = int(raw_input())
        if w == 0:
            break
        t = raw_input()
        l = len(t)
        ls = [t[i:i+w] if (j)%2==0 else t[i:i+w][::-1] for j,i in enumerate(xrange(0,l,w))]
        r = ''
        for i in zip(*ls):
            r+=''.join(i)
        print r

rogp10 viết 11:41 ngày 01/10/2018

: Input: enc_s[0..len-1]: string, no_col
: Output: dec_s: string

{do chia chẵn nên viết khá dễ}

: scan_step = 2*no_col
: dec_s = ""
for i:=1 to no_col do
   for j:=0 to len STEP scan_step do dec_s += "$enc_s[j+i]$enc_s[j+1+scan_step-i]"
{nếu no_col = 5 thì các vị trí sau liền nhau: 1/10, 2/9, 3/8, 4/7, 5/6}

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

huyentrang

0 chủ đề

0 bài viết

Tác giả nổi bật