杭州赛区小结 —— by edward_mj@eternal reality

虽然是不是正式参赛,但是总结还是要有的。

开场看了E、F、G,然后猛犸期间看了H问了一下我怎么做,然后当时猛犸告诉我的题意是错的,但是也可以做- -b,初步推断是莫比乌斯反演弄一下,应该不太好搞。

看完后知道F是set蘑菇题,G是xor的数据结构题,E是数论题。看了一个H,发现题意理解错了,就是算算区间,树状数组就可以了。

board上A,B,C都过了好多,猛犸一下子就都秒了。

稍微推了一下E,发现好像只要解一个由两个方程构成的同余方程组就可以了,然后看到范围都是1018,一乘就爆64位整数,感觉能比H快一点,上去就用Java写……然后Java快写完了,发现悲剧了,同余方程前面的系数推的时候忘了乘。但是有了系数模板就用不了……

然后有了系数以后做法有点变化,稍微思考了一下,好像就麻烦起来了。跟肚子白说了题意。然后肚子白问这个东西是素数吗?然后我又看了一下,发现M是素数。又推了一会儿,似乎推出解法……期间猛犸又把I过了,然后由于不太确定解法,先去把H很快写掉了。然后回头权衡了一下E和G,G是一个树上求第k大异或路径的题目,其实只要把从根上来的路径异或值存下来,两个点之间的路径直接xor一下就可以得到了,根本不需要求lca之类的……当时我其实已经想到了不在树上的解法了(也就是已经知道正解了),但是突然就脑残了,以为两个从根过来的异或值异或一下以后,还要弄一下lca的值。于是就不会做了。

跑去弄坑了一半的E,继续刚才的思路,又上机写回了C++,结果发现写完sample过不了,自己看看推导过程,- -b发现有一步推错了。但是已经没有多少时间了,然后就没再摸机器了。然后这时候看了一眼G,突然发现了刚才想的时候脑残的地方,一下子就会做了……但是却没有时间了,真是我了个去。

赛后我坑了一场的E题成为了全场没人过的题目……

然后比赛之后我看了K题的题意,刚看完就会做了……裸的费用流,然而这题我比赛的时候就只有肚子白看过,然后肚子白觉得条件太多了也一下子就弃坑了,估计也没有仔细想。然而实际上我觉得这是比EFG都简单的题目。

总得来说这场我坑队友坑得飞起,做了一整场的E还没坑出来。其实GK没脑残都是能一下就能过掉的。为什么会这样呢……我觉得还是太缺少讨论了。总结下来有那么几点是做得不够好的。

  1. K题只有肚子白知道题目,而且大概也没仔细想。这和上一年final差不多是同一个情况。最起码应该保证有人过但是没有秒掉的题至少两个人看过,不能就这样一个人粗略地看了一下。
  2. G题没有出纯粹是我脑残,实际上我都已经会做了……但是没有仔细在纸上画出来。导致没有看出和树这个结构根本没有关系。其实当时我只要和肚子白稍微讨论一下,就肯定会发现是哪个地方SB了。其实这题也好像只有我看过题目。
  3. E题全场就只有1个提交,而且还没有过(感觉是交错题了)。跟跟board其实还是很科学的。再就是,相比于数论,无疑我更懂的是数据结构。弃G写E完全不应该。今后在自己不那么擅长的领域,还是跟跟别人比较好。其实这题我会企图去碰的一个重要原因是很像我两三年前推过的同余方程并,结果就忘了当时怎么推的了。当然有点想抢FB大概也是一个原因。比赛里,还是先做自己熟悉的东西吧。不是说我搞不出来,重要的是不知道要花多少时间。
  4. 猛犸写了一场的题,这时候我和肚子白在遇到困难时没有很积极地讨论算法,演变成各自为战真的是很不应该。其实特别在没有题有很靠谱搞法的前提下,两个人合力攻一题多人过的才是比较正确的策略。也许彼此手上的题都差一点点,但是人SB的时候别人不点醒一下往往是会一直SB下去的。又想起上一年final回来,shi哥他们说的,每道题写之前如果不是很水,至少两个人知道算法和题目。如果没有这么做,WA了后20分钟或者花了好久写的还不清不楚的,再没人讨论基本就注定悲剧了。
  5. 猛犸赛后提到了为何我会产生E能过的错觉,其实这种错觉每个人都会犯。比如猛犸写J题的时候也会出现写一半不知道怎么写的情况。提防的方法无非是锻炼在上机前就能“看到”程序长什么样的能力。在摸机器前把每一步都想清楚,不要急。但是即使如此,产生这种感觉还是不可避免的。这也正是上面提到的,写之前要让队友知道算法的重要性。
  6. 世事大多如此,成王败寇。如果我一下子把E推对了,大家都不会喷我。悲剧的就是我推导的过程不够谨慎,每一步看起来都有理有据,结果还是有一步想当然了。但是不能就因为这次悲剧了,之后就畏首畏尾。如果下一次又推出一个自认为正确的结论,场上没人碰的,我还是会去交的。我觉得我们该做的是想办法通过合作等方式减少这种失误带来的影响,而不是全盘否定这样的决策。

其实这套题如果我今天发挥正常8题应该还是比较妥的。final前的训练和比赛无非就是三个目的。

  1. 保持手感
  2. 涨知识
  3. 磨合出对应各种情况下有效的策略

前两条都是可以自己练的,唯独第三条,是最重要也是最容易被忽略的。真心觉得最近我们训练的时候配合不多。我觉得有必要制定固定的队规,这样才能减少在脑袋发昏的时候造成的影响。这和肥羊说的要写小结并在比赛前看一遍是类似的,本质无非是对经验的总结。但我感觉凝练的若干条比零散的小结起到的作用可能更大。

能总结出错误也是一个很重要的能力,组队集训的时候我就觉得很多时候xpy的队伍总结不出自己犯的到底是什么错。虽然这次圡了,但该否定什么,不该否定什么,很多人心里好像没有数。人犯错很多时候是不可避免的,不应该被别人、前辈或者大家认为的大牛开两句玩笑,就觉得自己全盘做错了。每个人都肯定会有自己的想法,认真分析以后觉得别人的意见不合理就不要接受好了。在这里鄙视一下搞学长- -b,新人总结的时候就不要随便乱喷了,你的话很可能在他们眼里是权威。最后,奉上《激战》里的一句台词:怕,你就会输一辈子。

SRM 593 1000pt

给定一个size不超过2*106的string,里面仅包含w, o, ?三种字符。问有多少种填写?的方式使得最终的串是一个合法的样式。合法的样式定义为:

  1. n个w和n个o连接成的串是一个合法的串
  2. 两个合法的串连接也是一个合法的串

递推方程是裸的。
\[ f_i = \begin{cases} 1 &\mbox{i = 0} \\ \sum{f_j} &\mbox{s[j, i) is a string like w^no^n} \end{cases} \]
求$$f_n$$即可。

关键在于如何转移。其实能加速转移的方法我遇见过的总结起来就那么几种。离不开两个关键词,连续和凸性。

稍微看了一下感觉不满足凸性,于是就找连续性。然而直接看转移区间是不满足连续性的。找了好久发现对于一个给定的对称轴,往两边增长的时候,合法的pattern是满足连续性的(即小于某一长度都是合法pattern,超出的都不合法)。想了很久,发现还是没法转移。大概这种二维关系能做优化的也只有固定一个值再去考虑别的值的影响了。于是去看了题解,发现他将可以形成$$w^no^n$$的字符串分成了两种情况考虑,而这两种情况分别满足连续性。

为了方便讨论,我们设legal(i, j)表示s[i, j)可以形成形如$$w^no^n$$的字符串。

  1. 前一半全是?的。这种情况对于一个固定的i,legal(i, j)随着j的增长,值是单调的。(由true变false),所以f[i]往后的影响是某一个区间,这用树状数组或者直接加delta值在起点和终点的办法就可以实现快速转移。
  2. 前一半包含有w的。这种情况对于一个固定的j,legal(i, j)虽然i的递减,值是单峰的。(由false变true再变false)这个的证明并不是那么显然,但是只要考虑到j前面第一个出现的w就会发现是有上下界限制的。具体限制包含4个,上界两个,下界两个,取交即可。然后就可以用f的部分和来快速求出答案。

实现起来还是有一点细节的。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int MAXN = 2000005;
int f[MAXN / 2 + 10];
int fsum[MAXN / 2 + 10];
int Tr[MAXN / 2 + 10];
int prevw[MAXN], prevo[MAXN], nextw[MAXN], nexto[MAXN];
const int Mod = 1e9 + 7;
string s;

void add(int i, int x) {
	x %= Mod;
	x += Mod;
	x %= Mod;
	for (++i; i < MAXN / 2 + 10; i += i & -i) {
		Tr[i] += x;
		Tr[i] %= Mod;
	}
}

int get(int i) {
	int res = 0;
	for (++i; i; i -= i & -i) {
		res += Tr[i];
		res %= Mod;
	}
	return res;
}

int Next(int x, int i) {
	if (x == 1)
		return s[i] == 'w' ? i : nextw[i];
	else
		return s[i] == 'o' ? i : nexto[i];
}

int gao() {
	int n = s.size();
	if (n & 1) return 0;
	memset(f, 0, sizeof(f));
	memset(fsum, 0, sizeof(fsum));
	f[0] = fsum[1] = 1;
	fsum[0] = 0;
	int wp = -1, op = -1;
	rep (i, n + 1) {
		prevw[i] = wp;
		prevo[i] = op;
		if (i < n && s[i] == 'w') wp = i;
		if (i < n && s[i] == 'o') op = i;
	}
	wp = n; op = n;
	for (int i = n; i >= 0; i--) {
		nextw[i] = wp;
		nexto[i] = op;
		if (i < n && s[i] == 'w') wp = i;
		if (i < n && s[i] == 'o') op = i;
	}
	rep (i, n / 2 + 1) {
		int &res = f[i] += get(i), lhs, rhs;
		int p;
		lhs = (p = prevw[i * 2]) == -1 ? n : max((i * 2 - p + 1) / 2, i * 2 - nexto[p]);
		rhs = (p = prevw[i * 2]) == -1 ? -9 : min(i * 2 - p, (i * 2 - prevo[p] + 1) / 2);
		if (lhs < rhs)
			res += (fsum[i - lhs + 1] - fsum[i - rhs + 1] + Mod) % Mod;
		res %= Mod;
		if (i * 2 == n) break;
		int len = min((Next(1, i * 2) - i * 2) / 2, Next(0, i * 2) - i * 2);
		add(i + 1, res);
		add(i + 1 + len, -res);
		fsum[i + 1] = (fsum[i] + res) % Mod;
	}
	return f[n / 2];
}

class WolfDelaymasterHard {
public:
	int countWords(int, int, int, int, int, int, int, int, int);
};

int WolfDelaymasterHard::countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd) {
	s.resize(N);
	rep (i, N) s[i] = '?';
	ll x = w0;
	for(int i=0;i<wlen;i++){
		s[x] = 'w';				// Rewrite the x-th (0-based) character of s
		x = (x * wmul + wadd) % N;
	}
	x = o0;
	for(int i=0;i<olen;i++){
		s[x] = 'o';				// Rewrite the x-th (0-based) character of s
		x = (x * omul + oadd) % N;
	}
	memset(Tr, 0, sizeof(Tr));
	return gao();
}

SRM 594 950pt

给定n, w, x(n ≤ 3000)表示把n个物品放进宽为w的矩形内。其中第i号物品放在第(i – 1) / w行,第(i – 1) % w列上。每次能圈取一个平行坐标轴的矩形把里面的物品全部删除掉。删除以后,对应的物品会往前往上凑上空掉的位置。问至少要多少次操作可以使得最后只剩第x号物品。

这题其实有三个point,都发现了就好做了。

  1. 答案最多是4。做法是先删掉所有行号小于x的物品,然后x被放到第一行了。接着删掉所有行号大于第一行的。最后删除一左一右即可。
  2. 离达到目标只剩一步的时候,是可以O(1)判断出来的。
  3. 对于同样的x和w,随着n的递减,答案不增。

比赛的时候想到第一条和第二条,但是第三条没有注意到。
有了第一条,那么只需要能判断3次以内能不能做到即可。再根据第二条,只要能枚举两步的行为,问题就能够得到顺利解决。
本来一个r*c=n的矩形里,子矩形的数目是$$r^2 * c^2 \leq n^2$$级别的。但是由于第三点,分x的上下左右分别考虑的时候,会发现都可以少掉一维r和一维c。于是枚举一次操作的复杂度就是O(r*c=n)的了。这样就足够pass这道题目。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int w, ans;

bool isOne(int n, int x) {
	if (x % w == 0 && x + 1 == n)
		return 1;
	else if (w == 1 && !x)
		return 1;
	else if (n <= w && x + 1 == n)
		return 1;
	else if (n <= w && !x)
		return 1;
	else if (n < 2 * w && x + 1 == w && !(x / w))
		return 1;
	else
		return 0;
}

void solve(int n, int x, int cur) {
	if (n == 1) {
		ans = cur;
		return;
	}
	if (isOne(n, x)) {
		ans = cur + 1;
		return;
	}
	if (cur + 2 >= ans) return;
	int r = (n - 1) / w + 1;
	int c = w;
	int xr = x / w;
	int xc = x % w;
	for (int i = 1; i <= xr; i++)
		for (int j = 1; j <= w; j++)
			solve(n - i * j, x - i * j, cur + 1);
	if (xr + 1 != r) solve(c * (xr + 1), x, cur + 1);
	for (int i = 0; i <= xr; i++) {
		for (int j = 1; j <= xc; j++) {
			int d = (r - xr) * j + i * j - max(0, j - 1 - (n - 1) % w);
			solve(n - d, x - (i + 1) * j, cur + 1);
		}
	}
	for (int i = 0; i <= xr; i++) {
		for (int j = 1; j <= w - xc - 1; j++) {
			int d = (r - xr) * j - max(0, min(xc + j - (n - 1) % w, j));
			d += i * j;
			solve(n - d, x - i * j, cur + 1);
		}
	}
}

int gao(int n, int w, int x) {
	::w = w;
	x--;
	ans = 4;
	solve(n, x, 0);
	return ans;
}

class FoxAndAvatar {
public:
	int minimalSteps(int, int, int);
};

int FoxAndAvatar::minimalSteps(int n, int width, int x) {
	return gao(n, width, x);
}

[HDU4742 Pinball Game 3D] 分治、KD树

传送门

三维LIS。即每个点有个三维坐标,两个点能放在一前一后当且仅当$$x_i < x_j, y_i < y_j, z_i < z_j$$,求最长的序列,并该条件下的方案数。

网络赛的题,比赛的时候一想二维的,直接上了KD树就过了。
赛后听别人说,都是树套树或者CDQ分治的。于是就去cxlove大大的博客学习了一下CDQ分治。
这种分治的大致思路是每次把区间分两半,先做左边,然后把左边对右边的影响(在这题里相当于dp值的转移)计算好,然后再右边递归下去算。
这种复杂度很容易计算,T(n) = 2T(n / 2) + O(xxxn),最终复杂度肯定是xxxn lg n(想想每个元素被碰的次数就好了)。
我目前对这种分治的理解大致有这么两条:

  1. 在第i号位置的元素其实被更新了popcount(i)次(popcount表示这个值在二进制下包含的1的个数),就是二进制下看,每有一个1,就会被对应长度的块更新一次。
  2. 若i < j,则在通过f[i]影响f[j]的时候,f[i]总是已经计算好了的。

在这题里显然先对x排序,然后变成一个二维查询的问题,利用这个思想结合树状数组就可以达到$$O(n lg^2 n)$$的复杂度。

KD树的做法就更为直观,直接按x排序后,动态求左上角的那个块的值就好了。大概是写得太奔放的原因,我的KD树比这个分治的要快

今天写的时候WA了好久,原因有两个

  1. 分治的时候sort了原数组在处理后要还原回去。
  2. 我是每个区间分别离散化的,结果离散化了以后,被离散化的值没有还原回去,导致在别的区间内再离散化的的时候,值的大小相对关系就不对了…

分治的代码:

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
typedef pair <int, unsigned int> PII;
const int N = 100005;
const unsigned int Mod = 1 << 30;
struct Point {
	int x, y, z, nz;
	PII res;
	void read() { scanf("%d%d%d", &x, &y, &z); }
}a[N];
PII Tr[N];

bool cmpx(Point a, Point b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z);
}

bool cmpy(Point a, Point b) {
	return a.y < b.y || (a.y == b.y && a.z < b.z);
}

void up(PII &r, PII x) {
	if (x.first > r.first)
		r = x;
	else if (x.first == r.first)
		r.second += x.second;
}

void add(int i, int n, PII c) {
	for (i++, n++; i < n; i += i & -i)
		up(Tr[i], c);
}

PII get(int i) {
	PII res(0, 0);
	for (i++; i; i -= i & -i)
		up(res, Tr[i]);
	return res;
}

void gao(int l, int r) {
	if (l + 1 >= r) return;
	int mid = (l + r) / 2;
	gao(l, mid);
	sort(a + l, a + mid, cmpy);
	sort(a + mid, a + r, cmpy);
	vector <int> v;
	for (int i = l; i < r; i++) v.push_back(a[i].z);
	sort(v.begin(), v.end());
	for (int i = l; i < r; i++) a[i].nz = lower_bound(v.begin(), v.end(), a[i].z) - v.begin();
	fill(Tr + 1, Tr + r - l + 1, PII(0, 0));
	for (int j = l, i = mid; i < r; i++) {
		while (j < mid && a[j].y <= a[i].y) {
			add(a[j].nz, r - l, a[j].res);
			j++;
		}
		PII cur = get(a[i].nz);
		cur.first++;
		up(a[i].res, cur);
	}
	sort(a + mid, a + r, cmpx);
	gao(mid, r);
}

int main() {
	int Tc;
	scanf("%d", &Tc);
	while (Tc--) {
		int n;
		scanf("%d", &n);
		rep (i, n) a[i].read();
		rep (i, n) a[i].res = PII(1, 1);
		sort(a, a + n, cmpx);
		gao(0, n);
		PII res = PII(0, 1);
		rep (i, n) up(res, a[i].res);
		cout << res.first << " " << (res.second & (Mod - 1)) << endl;
	}
}

KD树的代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
typedef pair <int, int> PII;
typedef unsigned int ui;
const int N = 100005;
const int INF = 0x7FFFFFFF;
const ui mask = (1 << 30) - 1;
int Tc, n, m;
struct Node {
    PII e, sub, cur;
    int o;
    Node *lc, *rc;
}*C, pool[N];

struct TPoint {
    int x, y, z;
    TPoint() {}
    TPoint(int x, int y, int z): x(x), y(y), z(z) {}
}a[N];
PII b[N];

bool cmp(const TPoint &a, const TPoint &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z);
}

bool cmpX(const PII &a, const PII &b) {
    return a.first < b.first || (a.first == b.first && a.second < b.second);
}

bool cmpY(const PII &a, const PII &b) {
    return a.second < b.second || (a.second == b.second && a.first < b.first);
}

Node *build(PII *b, int l, int r, int o) {
    if (l >= r) return NULL;
    Node *p = C++;
    p->o = o;
    int mid = (l + r) / 2;
    nth_element(b + l, b + mid, b + r, o ? cmpY : cmpX);
    p->e = b[mid];
    p->cur = p->sub = PII(0, 0);
    p->lc = build(b, l, mid, o ^ 1);
    p->rc = build(b, mid + 1, r, o ^ 1);
    return p;
}

inline void update(PII &cur, const PII &v) {
    if (v.first > cur.first) {
        cur = v;
    } else if (cur.first == v.first) {
        cur.second = cur.second + v.second;
    }
}

void add(Node *p, const PII &e, const PII &v) {
    update(p->sub, v);
    if (e == p->e) {
        update(p->cur, v);
        return;
    } else {
        bool c = p->o ? cmpY(e, p->e) : cmpX(e, p->e);
        if (c) {
            add(p->lc, e, v);
        } else {
            add(p->rc, e, v);
        }
    }
}

PII ans;

void get(Node *p, const PII &e, int maxx = INF, int maxy = INF) {
    if (!p) return;
    if (p->sub.first < ans.first) return;
    if (maxx <= e.first && maxy <= e.second) {
        update(ans, p->sub);
    } else {
        if (p->e.first <= e.first && p->e.second <= e.second) update(ans, p->cur);
        if (p->o) {
            if (p->e.second <= e.second) get(p->rc, e, maxx, maxy);
            get(p->lc, e, maxx, min(maxy, p->e.second));
        } else {
            if (p->e.first <= e.first) get(p->rc, e, maxx, maxy);
            get(p->lc, e, min(maxx, p->e.first), maxy);
        }
    }
}

int main() {
#ifdef cwj
    freopen("E.in", "r", stdin);
#endif
    scanf("%d", &Tc);
    rep (ri, Tc) {
        scanf("%d", &n);
        rep (i, n) {
            scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
            b[i] = make_pair(a[i].y, a[i].z);
        }
        sort(b, b + n);
        m = unique(b, b + n) - b;
        C = pool;
        Node *root = build(b, 0, m, 0);
        sort(a, a + n, cmp);
        rep (i, n) {
            ans = PII(0, 0);
            get(root, PII(a[i].y, a[i].z));
            PII cur;
            if (ans.first == 0) {
                cur.first = 1;
                cur.second = 1;
            } else {
                cur.first = ans.first + 1;
                cur.second = ans.second;
            }
//            printf("cur %d %d %d\n", i, cur.first, cur.second);
            add(root, PII(a[i].y, a[i].z), cur);
        }
        printf("%d %d\n", root->sub.first, root->sub.second & mask);
    }
    return 0;
}

[长沙网络赛 I] 二分图最大匹配 强连通分量

[Link]

给定一个二分图,问你哪些边永远不可能成为最大匹配的边。

比赛的时候全败在题上了……
这道题我见过三次,第一次在上一年训练的时候见到,随便YY一下全手写花了不到1小时就过了;第二次在多校见少考虑了一种情况WA全场;第三次,hopcroft karp模板右边不能匹配居然match2不是-1而是n,直接又WA全场,把-1改成n立马过了。我简直不能再蠢……
实际这题还是很简单的(多校那个解题报告的解法要加各种边还得匹配两次感觉很不科学……)
做法就是先匹配,然后匹配边先排除这是肯定的。
然后匹配边从右往左连,非匹配边从左往右连。做强连通。
最后如果一条边符合下面三种情况之一就是可以作为匹配边的。

  1. p0
    这个的意思是要连的边两个点在同一个强连通分量。具体换边的方法就是沿着到彼此的路径交替互换就行了。
  2. P1
    左边的点被左边一个未被匹配的空点可达,换边的方法就是从空点一直走过来,交替互换。
  3. p2
    右边的点可达一个右边未被匹配的空点,换边的方法就是沿着这条路径一直走到空点,然后交替互换。

所以思路就明确了,SCC以后判连通性即可。
本来模块不能外传……但是想到我们的模块已经落后别人10条街了,而且网络赛本来就公开了代码……

#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
typedef pair <int, int> PII;
typedef long long ll;
const int MAXN = 100005;
int n, m, e;
int match1[MAXN], match2[MAXN];
int Q[MAXN], D1[MAXN], D2[MAXN];
vector <int> E[MAXN];

inline bool bfs() {
    int s = 0, t = 0, u, v;
    memset(D1, -1, sizeof(D1));
    memset(D2, -1, sizeof(D2));
    for (int i = 0; i < n; i++)
        if (match1[i] == -1)
            Q[t++] = i, D1[i] = 0;
    while (s != t)
        if ((u = Q[s++]) != n)
            for (int i = 0; i < (int)E[u].size(); i++)
                if (D2[v = E[u][i]] == -1) {
                    D2[v] = D1[u] + 1;
                    if (D1[match2[v]] == -1)
                        D1[Q[t++] = match2[v]] = D2[v] + 1;
                }
    return D1[n] != -1;
}

bool dfs(int u) {
    for (int i = 0, v; i < (int)E[u].size(); i++)
        if (D2[v = E[u][i]] == D1[u] + 1 && (D2[v] = -1) && (match2[v] == n || dfs(match2[v]))) {
            match1[u] = v;
            match2[v] = u;
            D1[u] = -1;
            return true;
        }
    D1[u] = -1;
    return false;
}

inline int hopcroft_karp() {
    memset(match1, -1, sizeof(match1));
    for (int i = 0; i < m; i++)
        match2[i] = n;
    int ret = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0, u; j < (int)E[i].size(); j++)
            if (match2[u = E[i][j]] == n) {
                match1[i] = u;
                match2[u] = i;
                ret++;
                break;
            }
    while (bfs())
        for (int i = 0; i < n; i++)
            if (match1[i] == -1 && dfs(i))
                ret++;
    return ret;
}

int toNum(char c) {
	if (c >= '0' && c <= '9') return c - '0';
	return c - 'A' + 10;
}

int trans(char *s) {
	return toNum(s[0]) * 32 * 32 + toNum(s[1]) * 32 + toNum(s[2]);
}

struct SCC_T {
	int n;
	int dfn[MAXN], low[MAXN], id[MAXN], num, st[MAXN], top, in[MAXN], tot; 
	vector <int> E[MAXN];
	int come[MAXN], go[MAXN];

	void clear(int _n) {
		n = _n;
		rep (i, n) E[i].clear();
		memset(dfn, 0, sizeof(int) * n); 
		memset(low, 0, sizeof(int) * n); 
		memset(in, 0, sizeof(int) * n); 
		memset(id, 0xff, sizeof(int) * n); 
		memset(come, 0, sizeof(int) * n);
		memset(go, 0, sizeof(int) * n);
	}

	void addedge(int x, int y) {
		E[x].push_back(y);
	}
 
	void tarjan(int now){ 
		in[st[top++] = now] = true; 
		dfn[now] = low[now] = ++tot;
		int i; 
		for (int ii = E[now].size() - 1; ii >= 0; --ii){ 
			i = E[now][ii]; 
			if (!dfn[i]){ 
				tarjan(i); 
				low[now] = min(low[now], low[i]);
			}
			else if (in[i]) 
				low[now] = min(low[now], dfn[i]); 
		}
		if (dfn[now] == low[now]){
			do{
				i = st[--top];
				in[i] = false;
				id[i] = num;
			}while (i != now);
			++num;
		}
	}
	void gao() { 
		for (int i = top = num = tot = 0; i < n; ++i) 
			if (!dfn[i]) 
				tarjan(i); 
	}

	void bfs(int (&vis)[MAXN], const vector <int> (&E)[MAXN]) {
		static int Q[MAXN];
		int qh = 0, qt = 0;
		rep (i, n)
			if (vis[i])
				Q[qt++] = i;
		while (qh < qt) {
			int u = Q[qh++];
			rep (i, E[u].size()) {
				int v = E[u][i];
				if (!vis[v]) {
					vis[v] = 1;
					Q[qt++] = v;
				}
			}
		}
	}

	void calc() {
		bfs(come, E);
		static vector <int> E2[MAXN];
		rep (i, n) E2[i].clear();
		rep (i, n) rep (j, E[i].size()) E2[E[i][j]].push_back(i);
		bfs(go, E2);
	}
}SCC;

int main() {
	while (scanf("%d%d%d", &n, &m, &e) != EOF) {
		static map <int, int> id[MAXN];
		rep (i, n) E[i].clear(), id[i].clear();
		rep (i, e) {
			char s[10];
			scanf("%s", s);
			int u = trans(s);
			int v = trans(s + 3);
			E[u].push_back(v);
			assert(!id[u].count(v));
			id[u][v] = i;
		}
		hopcroft_karp();
		SCC.clear(n + m);
		rep (u, n) {
			if (match1[u] != -1) SCC.addedge(match1[u] + n, u);
			rep (i, E[u].size()) {
				int v = E[u][i];
				if (v != match1[u]) SCC.addedge(u, v + n);
			}
		}
		SCC.gao();
		rep (i, m)
			if (match2[i] == n)
				SCC.go[n + i] = 1;
		rep (i, n)
			if (match1[i] == -1)
				SCC.come[i] = 1;
		SCC.calc();
		vector <int> ans;
		rep (u, n) rep (i, E[u].size()) {
			int v = E[u][i];
			if (SCC.come[u] || SCC.go[v + n] || SCC.id[u] == SCC.id[v + n] || match1[u] == v) continue;
			ans.push_back(id[u][v]);
		}
		sort(ans.begin(), ans.end());
		printf("%d\n", (int)ans.size());
		rep (i, ans.size()) {
			if (i) putchar(' ');
			printf("%d", ans[i]);
		}
		puts("");
	}
}