UOJ Round #15

大部分题目没有AC，我只是水一下部分分的题解...

---

225【UR #15】奥林匹克五子棋

• 题意：在n*m的棋盘上构造k子棋的平局

• 题解：

  玩一下发现k=1, k=2无解，然后间隔着，上下两行相同：

  010101
  
  010101
  
  101010
  
  101010
  

  这样构造下来就行了。

  然后要特判n=1 或 m=1，这时候k=2可以有解

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 505;

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, m, k, a[N][N], t[N][N];

void paint(int *a, int f) {for(int j=1; j<=m; j++) a[j] = (j&1) ^ f;}

inline void _walk(int &x, int &y) {

	y++;

	if(y == m+1) x++, y=1;

}

void walk(int &x, int &y, int f) {

	while(a[x][y] != f) _walk(x, y);

}

void solve1() {

	if(k == 1) {puts("-1"); return;}

	if(n == 1) for(int i=1; i<=m; i++) printf("%d %d\n", 1, i);

	else for(int i=1; i<=n; i++) printf("%d %d\n", i, 1);

}

int main() {

	freopen("in", "r", stdin);

    //freopen("out", "w", stdout);

	n = read(); m = read(); k = read();

	if(min(n, m) == 1) {solve1(); return 0;}

	if(k == 1 || k == 2) {puts("-1"); return 0;}

    int flag = 0;

    if((m&1) && (~n&1)) swap(n, m), flag = 1;

    int lim = (n>>1) + 1;

    for(int i=1; i <= lim; i++) paint(a[(i<<1)-1], i&1), paint(a[i<<1], i&1);

    if(flag) {

        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) t[j][i] = a[i][j];

        swap(n, m);

        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[i][j] = t[i][j];

    }

    int b = 0, w = 0;

    for(int i=1; i<=n; i++)

        for(int j=1; j<=n; j++) {

            if(a[i][j] == 1) b++;

            else w++;

        }

    if(b < w) b = 0, w = 1; else b = 1, w = 0;

    int bx = 1, by = 1, wx = 1, wy = 1;

    lim = n * m;

	for(int i=1; i <= lim; i++) {

        if(i & 1) walk(bx, by, b), printf("%d %d\n", bx, by), _walk(bx, by);

        else walk(wx, wy, w), printf("%d %d\n", wx, wy), _walk(wx, wy);

    }

    //puts("\ntest");

    //for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) printf("%d%c", a[i][j], j==m ? '\n' : ' ');

}

---

226【UR #15】奥林匹克环城马拉松

• 题意：有向 树 / 环 / 基环树 的欧拉回路计数
• 题解：题解太神了看不懂啊，我只能看懂树的...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

const int N = 1e5+5, P = 998244353;

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, m, u, v, w, de[N], t[N];

struct edge {int v, ne;} e[N<<1];

int cnt, h[N];

inline void ins(int u, int v, int w) {

	e[++cnt] = (edge) {v, h[u]}; h[u] = cnt;

	e[++cnt] = (edge) {u, h[v]}; h[v] = cnt;

}

ll inv[N*10], fac[N*10], facInv[N*10];

inline ll C(int n, int m) {return fac[n] * facInv[m] %P * facInv[n-m] %P;}

int main() {

	freopen("in", "r", stdin);

	n = read(); m = read();

	int flag = 1, lim = 0;

	for(int i=1; i<=m; i++) {

		u = read(), v = read(), w = t[i] = read(), de[u] += w, de[v] += w;

		lim = max(lim, w);

		if(w & 1) flag = 0;

	}

	for(int i=1; i<=n; i++) {

		if(de[i] & 1) {puts("0"); return 0;}

		de[i] >>= 1;

		lim = max(lim, de[i]);

	}

	inv[1] = fac[0] = facInv[0] = 1;

	for(int i=1; i <= lim; i++) {

		if(i != 1) inv[i] = (P - P/i) * inv[P%i] %P;

		fac[i] = fac[i-1] * i %P;

		facInv[i] = facInv[i-1] * inv[i] %P;

	}

	if(m == n-1) {

		if(!flag) {puts("0"); return 0;}

		ll ans = 1;

		for(int i=1; i<=n; i++) ans = ans * fac[de[i] - 1] %P; //printf("ans %lld\n", ans);

		for(int i=1; i<=m; i++) ans = ans * C(t[i], t[i] >> 1) %P * (t[i] >> 1) %P;

		printf("%lld\n", ans);

	}

}

---

227【UR #15】奥林匹克数据结构

• 题意：长为n的序列a，Q次询问，给出一个长m的序列b，求a有多少长m的子序列和b的相对大小关系相同

• 题解：

  太神了不会写啊，看了题解之后写了一下午一晚上才有50部分分

  一开始想的是把a的子序列离散化然后和b判断相等

  这样对于\(m_i \le 25\)的点可以哈希一下，预处理\(O(nm^2)\)，结果T了

  发现题解里的这些点的预处理是\(O(nm\log n)\)的！

  想了一下，发现不需要离散化，可以定义每个点的名次为前面比它小的个数+1，照样可行！

  然后用树状数组+异或哈希就可以拿这20分啦

  试着写了一下AC自动机+主席树的离线做法，还是有细节不会处理啊，又去写了kmp的做法。

  其实就是匹配b的名次序列在a中出现次数，只不过a中元素的名次依赖于序列的起始位置。

  kmp的border是单调递减的，所以用bit维护当前的border，移动now时暴力修改，求名次用bit求

  好喵啊！

  #include <iostream>
  
  #include <cstdio>
  
  #include <cstring>
  
  #include <algorithm>
  
  #include <map>
  
  #include <ctime>
  
  double tim() {return (double) clock() / CLOCKS_PER_SEC;}
  
  using namespace std;
  
  typedef long long ll;
  
  const int N = 1e5+5;
  
  inline int read() {
  
      char c=getchar(); int x=0,f=1;
  
      while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
  
      while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
  
      return x*f;
  
  }
  
  int type, n, Q, a[N], b[N * 5];
  
  void decode(int *b, int m, int ans) {
  
  	static int c[N];
  
  	for(int i=1; i<=m; i++) c[(i+ans-1) % m + 1] = b[i];
  
  	for(int i=1; i<=m; i++) b[i] = c[i];
  
  }
  
  	namespace bit {
  
  		int c[N], t[N], T;
  
  		inline void add(int p, int v) {
  
  			for(; p <= n; p += p&-p) {
  
  				if(t[p] != T) t[p] = T, c[p] = v;
  
  				else c[p] += v;
  
  			}
  
  		}
  
  		inline int sum(int p) {
  
  			int ans = 0;
  
  			for(; p; p -= p&-p)
  
  				if(t[p] == T) ans += c[p];
  
  			return ans;
  
  		}
  
  	}
  
  namespace m_25 {
  
  	int s[26][N];
  
  	int h[N];
  
  	using bit::add; using bit::sum;
  
  	void ini_hash() {
  
  		srand(317);
  
  		for(int i=1; i<=25; i++) h[i] = rand() << 15 ^ rand();
  
  		for(int i=1; i<=n; i++) {
  
  			int ans = 0; bit::T++;
  
  			for(int m = 1; m <= 25 && i+m-1 <= n; m++)
  
  				ans = ans << 1 ^ h[sum(a[i+m-1])], s[m][++s[m][0]] = ans, add(a[i+m-1], 1);
  
  		}
  
  		for(int m = 1; m <= 25; m++) sort(s[m] + 1, s[m] + s[m][0] + 1);
  
  	}
  
  	int get_hash(int *b, int m) {
  
  		int ans = 0; bit::T++;
  
  		for(int i=1; i<=m; i++) ans = ans << 1 ^ h[sum(b[i])], add(b[i], 1);
  
  		return ans;
  
  	}
  
  	int Count(int *a, int x) {
  
  		return upper_bound(a + 1, a + a[0] + 1, x) - lower_bound(a + 1, a + a[0] + 1, x);
  
  	}
  
  	int ans;
  
  	void solve() {
  
  		ini_hash();
  
  		for(int i=1; i<=Q; i++) {
  
  			int m = read();
  
  			for(int i=1; i<=m; i++) b[i] = read();
  
  			if(type) decode(b, m, ans);
  
  			int x = get_hash(b, m);
  
  			ans = Count(s[m], x);
  
  			printf("%d\n", ans);
  
  		}
  
  	}
  
  }
  
  namespace kmp {
  
  	int fail[N], rnk[N], _a[N];
  
  	void build(int *s, int n) {
  
  		bit::T++;
  
  		for(int i=1; i<=n; i++) rnk[i] = bit::sum(s[i]) + 1, bit::add(s[i], 1);
  
  		bit::T++;
  
  		fail[1] = 0;
  
  		for(int i=2; i<=n; i++) {
  
  			int now = fail[i-1];
  
  			//printf("iiii %d  %d\n", i, now);
  
  			while(now && bit::sum(s[i]) + 1 != rnk[now+1]) {
  
  				for(int j = i-now; j <= i-fail[now]-1; j++) bit::add(s[j], -1);
  
  				now = fail[now];
  
  			}
  
  			if(rnk[now+1] == bit::sum(s[i]) + 1) fail[i] = now+1, bit::add(s[i], 1);
  
  			else fail[i] = 0;
  
  		}
  
  		//for(int i=1; i<=n; i++) printf("%d ", rnk[i]); puts("  rnk");
  
  		//for(int i=1; i<=n; i++) printf("%d ", fail[i]); puts("  fail");
  
  	}
  
  	void walk(int *a, int n, int *b, int m) {
  
  		bit::T++;
  
  		int now = 0, ans = 0;
  
  		for(int i=1; i<=n; i++) { //printf("-----i %d   %d\n", i, now);
  
  			while(now && bit::sum(a[i]) + 1 != rnk[now+1]) {
  
  				//printf("lose [%d, %d]\n", i-now, i-fail[now]-1);
  
  				for(int j = i-now; j <= i-fail[now]-1; j++) bit::add(a[j], -1);
  
  				now = fail[now];
  
  			}
  
  			if(bit::sum(a[i]) + 1 == rnk[now+1]) now++, bit::add(a[i], 1);
  
  			if(now == m) ans++;
  
  		}
  
  		printf("%d\n", ans);
  
  	}
  
  }
  
  namespace type_0 {
  
  	void solve() {
  
  		for(int i=1; i<=Q; i++) {
  
  			int m = read();
  
  			for(int j=1; j<=m; j++) b[j] = read();
  
  			kmp::build(b, m);
  
  			kmp::walk(a, n, b, m);
  
  			for(int i=1; i<=m; i++) kmp::fail[i] = kmp::rnk[i] = 0;
  
  		}
  
  	}
  
  }
  
  int main() {
  
  	freopen("in", "r", stdin);
  
  	freopen("out", "w", stdout);
  
  	type = read();
  
  	n = read(); Q = read();
  
  	for(int i=1; i<=n; i++) a[i] = read();
  
  	if(type == 0) type_0::solve();
  
  	else m_25::solve();
  
  	return 0;
  
  }
  
  

  下面这个不会写的代码只是留作纪念

  #include <iostream>
  
  #include <cstdio>
  
  #include <cstring>
  
  #include <algorithm>
  
  #include <map>
  
  #include <ctime>
  
  double tim() {return (double) clock() / CLOCKS_PER_SEC;}
  
  using namespace std;
  
  typedef long long ll;
  
  const int N = 1e5+5;
  
  inline int read() {
  
      char c=getchar(); int x=0,f=1;
  
      while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
  
      while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
  
      return x*f;
  
  }
  
  int type, n, Q, a[N], b[N * 5];
  
  void decode(int *b, int m, int ans) {
  
  	static int c[N];
  
  	for(int i=1; i<=m; i++) c[(i+ans-1) % m + 1] = b[i];
  
  	for(int i=1; i<=m; i++) b[i] = c[i];
  
  }
  
  	namespace bit {
  
  		int c[N], t[N], T;
  
  		inline void add(int p, int v) {
  
  			for(; p <= n; p += p&-p) {
  
  				if(t[p] != T) t[p] = T, c[p] = v;
  
  				else c[p] += v;
  
  			}
  
  		}
  
  		inline int sum(int p) {
  
  			int ans = 0;
  
  			for(; p; p -= p&-p)
  
  				if(t[p] == T) ans += c[p];
  
  			return ans;
  
  		}
  
  	}
  
  namespace m_25 {
  
  	int s[26][N];
  
  	int h[N];
  
  	using bit::add; using bit::sum;
  
  	void ini_hash() {
  
  		srand(317);
  
  		for(int i=1; i<=25; i++) h[i] = rand() << 15 ^ rand();
  
  		for(int i=1; i<=n; i++) {
  
  			int ans = 0; bit::T++;
  
  			for(int m = 1; m <= 25 && i+m-1 <= n; m++)
  
  				ans = ans << 1 ^ h[sum(a[i+m-1])], s[m][++s[m][0]] = ans, add(a[i+m-1], 1);
  
  		}
  
  		for(int m = 1; m <= 25; m++) sort(s[m] + 1, s[m] + s[m][0] + 1);
  
  	}
  
  	int get_hash(int *b, int m) {
  
  		int ans = 0; bit::T++;
  
  		for(int i=1; i<=m; i++) ans = ans << 1 ^ h[sum(b[i])], add(b[i], 1);
  
  		return ans;
  
  	}
  
  	int Count(int *a, int x) {
  
  		return upper_bound(a + 1, a + a[0] + 1, x) - lower_bound(a + 1, a + a[0] + 1, x);
  
  	}
  
  	int ans;
  
  	void solve() {
  
  		ini_hash();
  
  		for(int i=1; i<=Q; i++) {
  
  			int m = read();
  
  			for(int i=1; i<=m; i++) b[i] = read();
  
  			if(type) decode(b, m, ans);
  
  			int x = get_hash(b, m);
  
  			ans = Count(s[m], x);
  
  			printf("%d\n", ans);
  
  		}
  
  	}
  
  }
  
  namespace tr {
  
  	#define lc(x) t[x].l
  
  	#define rc(x) t[x].r
  
  	struct meow {int l, r, size;} t[N];
  
  	int sz, root[N];
  
  	void insert(int &x, int l, int r, int p) {
  
  		t[++sz] = t[x]; x = sz;
  
  		t[x].size ++;
  
  		if(l == r) return;
  
  		int mid = (l+r) >> 1;
  
  		if(p <= mid) insert(lc(x), l, mid, p);
  
  		else insert(rc(x), mid+1, r, p);
  
  	}
  
  	int sum(int x, int y, int l, int r, int ql, int qr) {
  
  		//if(ql > qr) return 0;
  
  		if(ql <= l && r <= qr) return t[y].size - t[x].size;
  
  		else {
  
  			int mid = (l+r) >> 1, ans = 0;
  
  			if(ql <= mid) ans += sum(lc(x), lc(y), l, mid, ql, qr);
  
  			if(mid < qr)  ans += sum(rc(x), rc(y), mid+1, r, ql, qr);
  
  			return ans;
  
  		}
  
  	}
  
  }
  
  using tr::root;
  
  inline int rank(int x, int l, int r) {return tr::sum(root[l-1], root[r], 1, n, 1, a[x]);}
  
  namespace ac {
  
  	#define fir first
  
  	#define sec second
  
  	int pos[N];
  
  	struct meow {
  
  		map<int, int> ch;
  
  		map<int, int> mp;
  
  		int fail, cnt, rnk;
  
  		int count(int c) {return ch.count(c);}
  
  		int has(int x) {return mp.count(x);}
  
  	} t[N * 5];
  
  	map<int, int>::iterator it;
  
  	int sz, deep[N];
  
  	void insert(int *s, int m, int id) { printf("\ninsert %d\n", id);
  
  		int u = 0;
  
  		bit::T++;
  
  		for(int i=1; i<=m; i++) {
  
  			int c = s[i];
  
  			if(!t[u].ch[c]) {
  
  				t[u].ch[c] = ++sz;
  
  				deep[sz] = deep[u] + 1;
  
  				t[sz].rnk = bit::sum(s[i]) + 1;
  
  				t[u].mp[t[sz].rnk] = sz;
  
  			}
  
  			bit::add(s[i], 1);
  
  			u = t[u].ch[c];
  
  			printf("u %d  %d %d\n", u, deep[u], t[u].rnk);
  
  		}
  
  		pos[id] = u;
  
  	}
  
  	void build() {
  
  		static int q[N], head = 1, tail = 1;
  
  		for(it = t[0].ch.begin(); it != t[0].ch.end(); it++) q[tail++] = it -> sec;
  
  		while(head != tail) {
  
  			int u = q[head++];
  
  			for(it = t[u].ch.begin(); it != t[u].ch.end(); it++) {
  
  				int v = it -> sec, rnk = t[v].rnk, now = t[u].fail;
  
  				while(now && !t[now].has(rnk)) now = t[now].fail;
  
  				if(t[now].has(rnk)) t[v].fail = t[now].mp[rnk];
  
  				q[tail++] = v;
  
  			}
  
  		}
  
  	}
  
  	void walk(int *a, int n) { puts("\nwalk");
  
  		int u = 0;
  
  		for(int i=1; i<=n; i++) {
  
  			int l = i - deep[u], r = i, rnk = rank(i, l, r);
  
  			while(u && !t[u].has(rnk)) u = t[u].fail;
  
  			if(t[u].has(rnk)) u = t[u].mp[rnk];
  
  			t[u].cnt ++; printf("u %d\n", u);
  
  		}
  
  	}
  
  	int f[N * 5];
  
  	void dfs(int u) { //printf("dfs %d\n", u);
  
  		f[u] = t[u].cnt;
  
  		for(map<int, int>::iterator it = t[u].ch.begin(); it != t[u].ch.end(); it++)
  
  			dfs(it -> sec), f[u] += f[it -> sec];
  
  	}
  
  }
  
  namespace type_0 {
  
  	void solve() {
  
  		for(int i=1; i<=n; i++) root[i] = root[i-1], tr::insert(root[i], 1, n, a[i]);
  
  		//puts("rank");
  
  		//for(int l=1; l<=n; l++) for(int r=l; r<=n; r++) printf("rank [%d, %d]    %d\n", l, r, rank(r, l, r));
  
  		for(int i=1; i<=Q; i++) {
  
  			int m = read();
  
  			for(int j=1; j<=m; j++) b[j] = read();
  
  			ac::insert(b, m, i);
  
  		}
  
  		ac::build();
  
  		ac::walk(a, n);
  
  		ac::dfs(0); //puts("hi");
  
  		using ac::f; using ac::pos;
  
  		for(int i=1; i<=Q; i++) printf("%d\n", f[pos[i]]);
  
  	}
  
  }
  
  int main() {
  
  	freopen("in", "r", stdin);
  
  	//freopen("out", "w", stdout);
  
  	type = read();
  
  	n = read(); Q = read();
  
  	for(int i=1; i<=n; i++) a[i] = read();
  
  	if(type == 0) type_0::solve();
  
  	else m_25::solve();
  
  	return 0;
  
  }
  

  ​