天天看点
返回

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
下一篇: 批量学习和在线学习的区别

继续阅读