天天看點
傳回

2015弱校連萌寒假專題一(熱身) 題解(K-T)

比賽位址

弱校連萌寒假專題一

題解前繼

2015弱校連萌寒假專題一 題解(A-J)

K. Alignment of Code

題意：

給定n行文章，每行是由空格分隔的一些單詞，請你适當地增删空格，使得每一列的單詞在每一行的開始位置相同，且每一列最長的單詞和它後面的單詞隻有一個空格分隔。

n <= 1000, 單詞長度 <= 80, 一行文章長度 <= 180。

題解：

讀入n行文章之後計算每列最長單詞長度，按要求輸出即可。注意不能有多餘的行末空格。時間複雜度O(字元數)。

代碼：

#include <cstdio>
#include <cstring>
const int maxn = 1010, maxl = 200;
int t, n, cnt[maxn], sta[maxn][maxl], end[maxn][maxl], maxlen[maxl];
char str[maxn][maxl];
int max(int x, int y)
{
	return x < y ? y : x;
}
int main()
{
	scanf("%d\n", &t);
	while(t--)
	{
		memset(cnt, 0, sizeof cnt);
		memset(maxlen, 0, sizeof maxlen);
		for(n = 0; gets(str[n]) != NULL; ++n)
			if(str[n][0] == '@' && str[n][1] == '\0')
				break;
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0, k = 0; str[i][j]; j = k)
			{
				while(str[i][j] == ' ')
					++j;
				k = j;
				while(str[i][k] && str[i][k] != ' ')
					++k;
				if(j < k)
				{
					sta[i][cnt[i]] = j;
					end[i][cnt[i]] = k;
					maxlen[cnt[i]] = max(maxlen[cnt[i]], k - j);
					++cnt[i];
				}
			}
		}
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0; j < cnt[i]; ++j)
			{
				if(j)
					putchar(' ');
				str[i][end[i][j]] = '\0';
				if(j + 1 == cnt[i])
					printf("%s", str[i] + sta[i][j]);
				else
					printf("%-*s", maxlen[j], str[i] + sta[i][j]);
			}
			putchar('\n');
		}
	}
	return 0;
}

L. Ducci Sequence

題意：

給定長度為n的數列{a_n}，每次将{a_1, a_2, ..., a_n}變成{|a_1 - a_2|, |a_2 - a_3|, ..., |a_n - a_1|}，問這樣的操作是否會變成{0, 0, ..., 0}，還是會一直循環下去。

n <= 15, 若有循環節則一定在1000步操作内出現。

題解：

直接模拟前1000次操作，每次檢查目前數列是否出現過，利用Hash可以做到時間複雜度O(kn)，k >= 1000。

代碼：

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 16;
int n;
struct DucciSeq
{
	int a[maxn];
	bool operator < (const DucciSeq &x) const
	{
		for(int i = 0; i < maxn; ++i)
			if(a[i] != x.a[i])
				return a[i] < x.a[i];
		return 0;
	}
	bool empty() const
	{
		for(int i = 0; i < n; ++i)
			if(a[i])
				return 0;
		return 1;
	}
} x;
map<DucciSeq, int> Hash;
int abs(int x)
{
	return x < 0 ? -x : x;
}
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		memset(&x, 0, sizeof x);
		Hash.clear();
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
			scanf("%d", &x.a[i]);
		if(x.empty())
		{
			puts("ZERO");
			continue;
		}
		Hash[x] = 1;
		for(int t = 1; t <= 1000; ++t)
		{
			int tmp = x.a[0];
			for(int i = 0; i < n - 1; ++i)
				x.a[i] = abs(x.a[i] - x.a[i + 1]);
			x.a[n - 1] = abs(x.a[n - 1] - tmp);
			if(x.empty())
			{
				puts("ZERO");
				break;
			}
			else if(Hash[x])
			{
				puts("LOOP");
				break;
			}
			Hash[x] = 1;
		}
	}
	return 0;
}

M. The Letter Carrier's Rounds

題意：

給定SMTP的工作方式，模拟MTA發送方的SMTP操作，包括MTA接收方的回饋資訊。

題解：

記錄每個MTA的使用者名便于快速查找，然後按照題意模拟即可。

代碼：

#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef map<string, int> Users;
map<string, Users> MTA;
string sender, text;
map<string, int> idx, vis;
vector<vector<string> > recver;
int main()
{
	ios::sync_with_stdio(0);
	while(cin >> text && text != "*")
	{
		int cnt;
		Users tmp;
		tmp.clear();
		cin >> text >> cnt;
		while(cnt--)
		{
			cin >> sender;
			tmp[sender] = 1;
		}
		MTA[text] = tmp;
	}
	while(cin >> sender && sender != "*")
	{
		int cnt = 0;
		string::size_type pos = sender.find('@');
		string senderMTA = sender.substr(pos + 1), recverMTA, tmp;
		idx.clear();
		vis.clear();
		for(vector<vector<string> >::iterator it = recver.begin(), jt = recver.end(); it < jt; ++it)
			(*it).clear();
		recver.clear();
		while(cin >> tmp && tmp != "*")
		{
			recverMTA = tmp.substr(tmp.find('@') + 1);
			if(vis.find(tmp) != vis.end())
				continue;
			vis[tmp] = 1;
			if(idx.find(recverMTA) == idx.end())
			{
				idx[recverMTA] = cnt++;
				vector<string> name;
				name.clear();
				name.push_back(tmp);
				recver.push_back(name);
			}
			else
				recver[idx[recverMTA]].push_back(tmp);
		}
		text = "";
		getline(cin, tmp);
		while(getline(cin, tmp) && tmp != "*")
			text += "     " + tmp + "\n";
		Users List = MTA[senderMTA];
		if(List.find(sender.substr(0, sender.find('@'))) == List.end())
			continue;
		for(vector<vector<string> >::iterator it = recver.begin(), jt = recver.end(); it < jt; ++it)
		{
			vector<string> &temp = *it;
			recverMTA = temp[0].substr(temp[0].find('@') + 1);
			List = MTA[recverMTA];
			cout << "Connection between " + senderMTA + " and " + recverMTA << endl;
			cout << "     HELO " + senderMTA << endl;
			cout << "     250" << endl;
			cout << "     MAIL FROM:<" + sender + ">" << endl;
			cout << "     250" << endl;
			bool flag = 0;
			for(vector<string>::iterator it = temp.begin(), jt = temp.end(); it < jt; ++it)
			{
				cout << "     RCPT TO:<" + *it + ">" << endl;
				if(List.find((*it).substr(0, (*it).find('@'))) != List.end())
				{
					flag = 1;
					cout << "     250" << endl;
				}
				else
					cout << "     550" << endl;
			}
			if(flag)
			{
				cout << "     DATA" << endl;
				cout << "     354" << endl;
				cout << text << "     ." << endl;
				cout << "     250" << endl;
			}
			cout << "     QUIT" << endl;
			cout << "     221" << endl;
		}
	}
	return 0;
}

N. Symmetry

題意：

給定平面上n個點，問是否存在一條直線x = k使得這n個點關于x = k對稱。

n <= 1000。

題解：

若存在該直線，則k一定為這n個點橫坐标的平均值，算出來之後檢驗這n個點的對稱點是否存在即可，時間複雜度O(n)。

由于這n個點都是整點，k一定是0.5的倍數，如果想規避浮點數運算的誤差，可以将坐标全部放大兩倍進行整數運算。

代碼：

#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> point;
map<point, int> Hash;
int t, n, minx, maxx, xx;
int main()
{
	scanf("%d", &t);
	while(t--)
	{
		Hash.clear();
		minx = ~0u >> 1, maxx = -minx;
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			++Hash[make_pair(x <<= 1, y <<= 1)];
			if(x < minx)
				minx = x;
			if(maxx < x)
				maxx = x;
		}
		xx = minx + maxx;
		bool flag = 0;
		for(map<point, int>::iterator it = Hash.begin(), jt = Hash.end(); it != jt; ++it)
		{
			point tmp = it -> first;
			tmp.first = xx - tmp.first;
			if(Hash.find(tmp) == jt || Hash[tmp] != it -> second)
			{
				flag = 1;
				break;
			}
		}
		puts(flag ? "NO" : "YES");
	}
	return 0;
}

O. Printer Queue

題意：

給定一個長度為n的操作隊列，對于隊首元素，若優先級為最高，則做該事件，否則将之置于隊尾等待以後操作，現在求第k位的事件會是第幾個被操作的。

題解：

統計每個優先級還剩多少個操作，按照隊列的定義模拟即可，每次找到需要做的操作至多将隊列元素全部周遊一遍，是以時間複雜度O(n^2)。

由于任意時刻隊列的元素個數不超過n，是以可以用循環隊列做到空間複雜度O(n)。

代碼：

#include <cstdio>
const int maxn = 110;
int t, n, pos, que[maxn], l, r, now, cnt[11], ans;
int main()
{
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n, &pos);
		l = 0, r = n, now = 1, ans = 0;
		for(int i = 1; i <= 9; ++i)
			cnt[i] = 0;
		for(int i = 0; i < n; ++i)
		{
			scanf("%d", que + i);
			if(now < que[i])
				now = que[i];
			++cnt[que[i]];
		}
		while(l != r)
			if(que[l] == now)
			{
				++ans;
				if(l == pos)
					break;
				--cnt[que[l++]];
				if(l >= maxn)
					l -= maxn;
				while(now && !cnt[now])
					--now;
			}
			else
			{
				if(l == pos)
					pos = r;
				que[r++] = que[l++];
				if(l >= maxn)
					l -= maxn;
				if(r >= maxn)
					r -= maxn;
			}
		printf("%d\n", ans);
	}
	return 0;
}

P. Borrowers

題意：

現在有一個圖書館，藏書按照(作者名, 書名)的形式按字典序排序，現在請你維護三種操作：借書，從藏書中删去某書；還書，将某書放入待整理區；整理，将待整理區的書排序後依次插入藏書，每次輸出插入的位置在哪本書之後，或是插到最前面。

題解：

記錄每本書的作者，待整理區需要整理時排序即可，藏書庫用平衡樹維護，每次查找插入位置即可。

代碼懶得手寫平衡樹，使用了STL的set。設操作數為n，可以做到時間複雜度O(nlogn)。

代碼：

#include <map>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<string, string> Book;
map<string, string> Dict;
set<Book> Lib, Rcv;
string tmp1, tmp2;
int main()
{
	ios::sync_with_stdio(0);
	while(getline(cin, tmp1) && tmp1 != "END")
	{
		string::size_type pos = tmp1.rfind("\"");
		tmp2 = tmp1.substr(pos + 5);
		tmp1 = tmp1.substr(1, pos - 1);
		Dict[tmp1] = tmp2;
		Lib.insert(make_pair(tmp2, tmp1));
	}
	while(getline(cin, tmp1) && tmp1 != "END")
		if(tmp1[0] == 'B')
		{
			tmp2 = tmp1.substr(8, tmp1.size() - 9);
			Lib.erase(make_pair(Dict[tmp2], tmp2));
		}
		else if(tmp1[0] == 'R')
		{
			tmp2 = tmp1.substr(8, tmp1.size() - 9);
			Rcv.insert(make_pair(Dict[tmp2], tmp2));
		}
		else
		{
			for(set<Book>::iterator it = Rcv.begin(), jt = Rcv.end(); it != jt; ++it)
			{
				set<Book>::iterator pos = Lib.insert(*it).first;
				if(pos == Lib.begin())
					cout << "Put \"" + it -> second + "\" first" << endl;
				else
					cout << "Put \"" + it -> second + "\" after \"" + (--pos) -> second + "\"" << endl;
			}
			cout << "END" << endl;
			Rcv.clear();
		}
	return 0;
}

Q. Bug Hunt

題意：

給定一篇特定的代碼，請你檢查它是否有特定的BUG，若有輸出第一個BUG的行數，若無輸出0。

代碼隻包含一下兩種語句：

<array_name>[<expression>]，表示定義一個數組，數組名叫<array_name>，長度為<expression>，下标從0開始。

<array_name>[<expression1>]=<expression2>，表示對數組<array_name>的第<expression1>的位置的元素指派為<expression2>。

其中<array_name>必須是英文字母，<expression>、<expression1>、<expression2>表示表達式，表達式可以是數組元素，也可以是非負整數。

特定的BUG包括下标越界，數組元素未定義，數組未定義三種。

題解：

遞歸求解expression，注意三種BUG的情況即可。

數組可以用map的映射功能代替。

代碼：

#include <map>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int size[52], now, ans;
map<int, int> array[52];
int trans(char ch)
{
	return ch <= 'Z' ? ch - 'A' + 26 : ch - 'a';
}
int GetValue(string a)
{
	if(a.find('[') == string::npos)
	{
		int ret = 0;
		for(int i = 0, j = a.size(); i < j; ++i)
			ret = (ret << 3) + (ret << 1) + a[i] - '0';
		return ret;
	}
	int name = trans(a[0]), idx = GetValue(a.substr(2, a.size() - 3));
	if(idx == -1 || idx >= size[name] || array[name].find(idx) == array[name].end())
		return -1;
	return array[name][idx];
}
int main()
{
	ios::sync_with_stdio(0);
	string tmp;
	while(cin >> tmp)
		if(tmp == ".")
		{
			if(now)
				cout << ans << endl;
			ans = now = 0;
			for(int i = 0; i < 52; ++i)
				if(size[i])
				{
					array[i].clear();
					size[i] = 0;
				}
		}
		else
		{
			++now;
			if(ans)
				continue;
			string::size_type pos = tmp.find('=');
			if(pos == string::npos)
			{
				int name = trans(tmp[0]), idx = GetValue(tmp.substr(2, tmp.size() - 3));
				if(idx == -1)
				{
					ans = now;
					continue;
				}
				size[name] = idx;
			}
			else
			{
				int name = trans(tmp[0]), idx = GetValue(tmp.substr(2, pos - 3)), value = GetValue(tmp.substr(pos + 1));
				if(idx == -1 || idx >= size[name] || value == -1)
				{
					ans = now;
					continue;
				}
				array[name][idx] = value;
			}
		}
	return 0;
}

R. Searching the Web

題意：

給定n篇文章，單詞由英文字母組成，有m個單詞查找操作，操作分為四種：

word，查找帶有word的文章，輸出對應文章内含有term的行。

NOT word，查找不帶有word的文章，輸出整篇文章。

word1 AND word2，查找既帶有word1又帶有word2的文章，輸出對應文章内含有word1或word2的行。

word1 OR word2，查找帶有word1或帶有word2的文章，輸出對應文章内含有word1或word2的行。

查詢結果為空輸出"Sorry, I found nothing."，單次查詢中不同文章之間由一行"----------"分隔，每次查詢末尾帶一行"=========="。

n < 100, m <= 50000, 一行字元數不超過80, 文章行數之和不超過1500。

題解：

對每個單詞記錄每一行是否出現過，按照四種邏輯直接操作即可。

設文章行數之和為k，時間複雜度為O(mk)。

代碼：

#include <map>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxr = 1510, maxc = 88;
bitset<maxr> ZERO(0), ONE(1);
map<string, int> Hash;
int n, r, m, mark[maxr], tot;
vector<bitset<maxr> > mask;
char str[maxr][maxc];
bitset<maxr> flip(bitset<maxr> tmp)
{
	return tmp.flip();
}
void Find(string s, bool flag) // ·Ç = 1 
{
	bitset<maxr> mass(0);
	bitset<maxr> &res = Hash.find(s) != Hash.end() ? mask[Hash[s]] : ZERO;
	for(int i = 0; i < r; ++i)
		mass[mark[i]] = mass[mark[i]] | res[i];
	bool flag2 = 1;
	for(int i = 0; i < n; ++i)
		flag2 &= mass[i];
	if(!flag && mass.none() || flag && flag2)
	{
		puts("Sorry, I found nothing.\n==========");
		return;
	}
	for(int i = 0, last = -1; i < r; ++i)
		if(!flag && mass[mark[i]] && res[i] || flag && !mass[mark[i]])
		{
			if(last != -1 && last != mark[i])
				puts("----------");
			puts(str[i]);
			last = mark[i];
		}
	puts("=========="); 
}
void Find(string s, string t, bool flag) // Óë = 0 »ò = 1 
{
	bitset<maxr> mass1(0), mass2(0), mass(0);
	bitset<maxr> &res1 = Hash.find(s) != Hash.end() ? mask[Hash[s]] : ZERO;
	bitset<maxr> &res2 = Hash.find(t) != Hash.end() ? mask[Hash[t]] : ZERO;
	for(int i = 0; i < r; ++i)
	{
		mass1[mark[i]] = mass1[mark[i]] | res1[i];
		mass2[mark[i]] = mass2[mark[i]] | res2[i];
	}
	for(int i = 0; i < n; ++i)
		mass[i] = flag ? mass1[i] | mass2[i] : mass1[i] & mass2[i];
	if(mass.none())
	{
		puts("Sorry, I found nothing.\n==========");
		return;
	}
	for(int i = 0, last = -1; i < r; ++i)
		if(mass[mark[i]] && (res1[i] || res2[i]))
		{
			if(last != -1 && last != mark[i])
				puts("----------");
			puts(str[i]);
			last = mark[i];
		}
	puts("=========="); 
}
int main()
{
	char op[5], tmp[maxc << 2], tmp1[maxc], tmp2[maxc];
	scanf("%d\n", &n);
	for(int t = 0; t < n; ++t)
		while(gets(str[r]) != NULL)
		{
			if(strcmp(str[r], "**********") == 0)
				break;
			int i, j;
			for(i = 0, j = 0; str[r][i]; ++i)
				if(str[r][i] >= 'A' && str[r][i] <= 'Z')
					tmp[j++] = str[r][i] - 'A' + 'a';
				else if(str[r][i] >= 'a' && str[r][i] <= 'z')
					tmp[j++] = str[r][i];
				else if(j)
				{
					tmp[j] = '\0';
					string temp = tmp;
					if(Hash.find(temp) == Hash.end())
					{
						Hash[temp] = tot++;
						mask.push_back(ZERO);
					}
					mask[Hash[temp]][r] = 1;
					j = 0;
				}
			if(j)
			{
				tmp[j] = '\0';
				string temp = tmp;
				if(Hash.find(temp) == Hash.end())
				{
					Hash[temp] = tot++;
					mask.push_back(ZERO);
				}
				mask[Hash[temp]][r] = 1;
				j = 0;
			}
			mark[r++] = t;
		}
	scanf("%d\n", &m);
	while(m--)
	{
		gets(tmp);
		if(strncmp(tmp, "NOT ", 4) == 0)
		{
			sscanf(tmp,"%*s%s", tmp1);
			Find(tmp1, 1);
		}
		else if(strchr(tmp, ' ') == NULL)
			Find(tmp, 0);
		else
		{
			sscanf(tmp, "%s%s%s", tmp1, op, tmp2);
			if(strcmp(op, "AND") == 0)
				Find(tmp1, tmp2, 0);
			else
				Find(tmp1, tmp2, 1);
		}
	}
	return 0;
}

S. Exchange

題意：

有n個操作，操作有三種：

買操作(價格, 數量)，添加一個買訂單，并檢查是否有賣訂單比買訂單價格低，按賣訂單價格盡量低、挂訂單時間盡量早的靠前的順序快速買進，輸出交易情況。

賣操作(價格, 數量)，添加一個賣訂單，并檢查是否有買訂單比賣訂單價格高，按買訂單價格盡量高、挂訂單時間盡量早的靠前的順序快速賣出，輸出交易情況。

删除操作(标号)，删除一個買或賣的訂單，已經交易的部分不做撤銷。

每次操作後輸出目前買訂單最高價以及最高價的産品數量、目前賣訂單最低價以及最低價的産品數量，無訂單時預設買訂單最高價為0，賣訂單最低價為99999。

n <= 10000。

題解：

對于買操作，維護賣訂單以價格排序的小根堆，存儲對于價格的産品數量和按時間戳排序的訂單清單，将買訂單對着賣訂單進行嘗試，嘗試完畢後加入買訂單的堆。

對于賣操作，維護買訂單以價格排序的大根堆，存儲對于價格的産品數量和按時間戳排序的訂單清單，将賣訂單對着買訂單進行嘗試，嘗試完畢後加入賣訂單的堆。

對于删除操作，直接找訂單對應的價格，更新訂單清單和産品數量，訂單清單内的查找可以用二分查找但比較麻煩，可以直接寫一個平衡樹來維護。

時間複雜度O(nlogn)，直接用map寫的話常數不是一般的大。

代碼：

#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 16384;
typedef map<int, int> Order;
typedef pair<int, Order> Orders;
map<int, Orders, greater<int> > Buy;
map<int, Orders, less<int> > Sell;
int n, id, p, q, P[maxn];
template<class A, class B> void Maintain(map<int, Orders, A> &act, map<int, Orders, B> &pass)
{
	while(q > 0)
	{
		if(pass.empty())
			break;
		map<int, Orders, less<int> >::iterator it = pass.begin();
		int pp = it -> first;
		B cmp;
		if(cmp(p, pp))
			break;
		Orders &tmp = it -> second;
		Order::iterator jt = tmp.second.begin();
		int qq = min(q, jt -> second);
		printf("TRADE %d %d\n", qq, pp);
		q -= qq;
		jt -> second -= qq;
		tmp.first -= qq;
		if(!jt -> second)
			tmp.second.erase(jt -> first);
		if(!tmp.first)
			pass.erase(it -> first);
	}
	if(q > 0)
		if(act.find(p) != act.end())
		{
			Orders &tmp = act[p];
			tmp.first += q;
			tmp.second[id] = q;
		}
		else
		{
			Order tmp;
			tmp.clear();
			tmp[id] = q;
			act[p] = make_pair(q, tmp);
		}
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		char op[10];
		scanf("%s", op);
		if(op[0] == 'B' || op[0] == 'S')
		{
			scanf("%d%d", &q, &p);
			P[i] = p;
			id = i;
			if(op[0] == 'B')
				Maintain(Buy, Sell);
			else
				Maintain(Sell, Buy);
		}
		else
		{
			scanf("%d", &id);
			if(Buy.find(P[id]) != Buy.end())
			{
				Orders &tmp = Buy[P[id]];
				if(tmp.second.find(id) != tmp.second.end())
				{
					tmp.first -= tmp.second[id];
					tmp.second.erase(id);
				}
				if(!tmp.first)
					Buy.erase(P[id]);
			}
			if(Sell.find(P[id]) != Sell.end())
			{
				Orders &tmp = Sell[P[id]];
				if(tmp.second.find(id) != tmp.second.end())
				{
					tmp.first -= tmp.second[id];
					tmp.second.erase(id);
				}
				if(!tmp.first)
					Sell.erase(P[id]);
			}
		}
		int bq = 0, bp = 0, sq = 0, sp = 99999;
		if(!Buy.empty())
		{
			map<int, Orders, greater<int> >::iterator it = Buy.begin();
			bq = it -> second.first;
			bp = it -> first;
		}
		if(!Sell.empty())
		{
			map<int, Orders, less<int> >::iterator it = Sell.begin();
			sq = it -> second.first;
			sp = it -> first;
		}
		printf("QUOTE %d %d - %d %d\n", bq, bp, sq, sp);
	}
	return 0;
}

T. Database

題意：

給定n行m列的字元串，每行的字元串之間由','分隔，問是否存在兩行的兩列是一樣的字元串，輸出任意一種可能的情況。

n <= 10000, m <= 10。

題解：

對于每個字元串求出Hash，枚舉答案的兩列，将每一行的兩個字元串Hash值捆綁起來再Hash，看是否存在兩行Hash一樣。

時間複雜度O(nm^2)，常數較大，和字元數有關。

代碼：

#include <cstdio>
#include <cstring>
const int maxn = 10010, maxm = 11, maxl = 81, mod1 = 233, mod2 = 23333, mod = 199669;
typedef unsigned long long ULL;
int n, m, tot;
char str[maxl];
ULL Hash1[maxn][maxm];
struct Node
{
	int row, nxt;
	ULL H1, H2;
} e[maxn];
int Hash[mod];
int main()
{
	while(scanf("%d%d\n", &n, &m) == 2)
	{
		for(int i = 0; i < n; ++i)
		{
			gets(str);
			for(int j = 0, k = 0; j < m && str[k]; ++j)
			{
				Hash1[i][j] = 0;
				for( ; str[k] && str[k] != ','; ++k)
					Hash1[i][j] = Hash1[i][j] * mod1 + str[k];
				if(str[k] == ',')
					++k;
			}
		}
		bool flag = 0;
		for(int j = 0; j < m; ++j)
		{
			for(int k = j + 1; k < m; ++k)
			{
				tot = 0;
				memset(Hash, 0, sizeof Hash);
				for(int i = 0; i < n; ++i)
				{
					int HH = (Hash1[i][j] * mod2 + Hash1[i][k]) % mod, res;
					for(int it = Hash[HH]; it; it = e[it].nxt)
						if(e[it].H1 == Hash1[i][j] && e[it].H2 == Hash1[i][k])
						{
							flag = 1;
							res = e[it].row;
							break;
						}
					if(flag)
					{
						puts("NO");
						printf("%d %d\n%d %d\n", res + 1, i + 1, j + 1, k + 1);
						break;
					}
					else
					{
						e[++tot] = (Node){i, Hash[HH], Hash1[i][j], Hash1[i][k]};
						Hash[HH] = tot;
					}
				}
				if(flag)
					break;
			}
			if(flag)
				break;
		}
		if(!flag)
			puts("YES");
	}
	return 0;
}

小記

做題順序是GHINDLOKTJBESFPQRAMC，其中FKPRS是FB，沒有按照難度升序來做，看到幾個偏資料結構的題目先做了，模拟題放到了後面慢慢解決。寫代碼還是很慢。

線上比賽 模拟 hash 隊列 平衡樹 堆
上一篇: leetcode-198-打家劫舍(house robber)-java
下一篇: 批量學習和線上學習的差別

繼續閱讀