比赛详情 - 蒙青创OJ

已结束 OI 开始于: 2026-8-26 13:00 4 小时主持人:

kcs007 10

A. 简单数学题

算法一

按照题意模拟分数加减和乘法，期望通过 subtask1(30pts)

算法二

对于 subtask2，算法一可能会有两个问题：

分数加减时可能会爆 long long
太多次 gcd 可能导致复杂度太高

通过适当的改变运算顺序可以解决上述两个问题通过 subtask2(40pts)

算法三

对于和我们可以直接用一个变量 sum 记录前 $i$ 个元素的和

对于平均值可以直接计算 $B_i=\operatorname{sum} / i$ 并输出

对于方差，有 $\frac{1}{i} \sum_{j=1}^i\left(A_j-B_i\right)^2=\frac{1}{i}\left(\sum_{j=1}^i A_j^2-2 \sum_{j=1}^i A_j B_i+\sum_{j=1}^i B_i^2\right)$ $=\frac{1}{i}\left(\sum_{j=1}^i A_j^2\right)-B_i^2$

再记录一个元素表示平方和即可直接计算方差。同时容易发现通过该式计算方差不会导致分子爆 long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long ull;
ull gcd(ull a,ull b){ return b>0?gcd(b,a%b):a; }
void print(ull a,ull b,char end='\n'){
	ull d=gcd(a,b);
	a/=d; b/=d;
	if(b==1) printf("%lld",a);
	else printf("%lld/%lld",a,b);
	printf("%c",end);
}
int main(){
	int n; scanf("%d",&n);
	ull sum=0,sum2=0;
	for(int i=1;i<=n;++i){
		int x; scanf("%d",&x);
		sum+=x; sum2+=1ll*x*x;
		print(sum,1,' ');
		print(sum,i,' ');
		print(sum2*i-sum*sum,1ll*i*i,'\n');
	}
	return 0;
}

B. 简单算法题

算法一

暴力还原括号串然后暴力枚举区间判断是否合法，8pts

算法二

暴力还原括号串，然后考虑使用数据结构维护。

考虑将 ( 视为 1，将 ) 视为 -1，做前缀和得到数组 $s$ ，区间 $[l, r]$ 合法当且仅当 $s_r=s_{l-1}$ 且对于任意 $k \in[l, r]$ ，有 $s_k \geq s_r$

这意味着如果有 $i<j$ 且 $s_j<s_i$ ，则对于任意 $k \geq j$ ，区间 $[i, k]$ 都不合法。所以我们可以尝试用一个栈维护可能合法的左端点。

当加入一个新的元素 $s_i$ 时，我们只需要弹出栈顶大于 $s_i$ 的元素然后将等于 $s_i$ 的元素贡献进答案。

为了保证复杂度我们可以把值相同的元素一起处理。

能过 subtask1,2, 24pts。

算法三

对于 $c_i$ 大的情况，可以将枚举左端点所在块和右端点所在块，然后计算中间部分至少要在左侧加几个左括号，至少要在右侧加几个右括号。

复杂度 $\Theta\left(n^3\right)$ 或 $\Theta\left(n^2\right)$ 。

然后 subtask5 可以随便特判一下，最高可以得56pts。

算法四

结合算法二和算法三，把公差为 1 的 $s_i$ 等差数列合在一起处理。复杂度 $O(n)$ ，可以 $\mathrm{AC}$ 。

顺便提一下，结合代码可以发现答案不会超过 $n\left(n+\max \left\{m_0, m_1\right\}\right)$ ，所以不会爆 longlong。

其它想法

可以用线段树之类的方法做到 $O(n \lg n)$ ，这样会TLE。数据是随机的，说不定随便写个乱搞能过。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull pop_back(stack<pair<ull,int> >& stk,ull c){
	ull ans=0;
	while(c>0){
		pair<ull,int> x=stk.top(); stk.pop();
		ull d=min(c,x.first);
		x.first-=d;
		c-=d;
		if(x.first>0) stk.push(x);
		ans+=1llu*d*x.second;
	}
	return ans;
}
int main(){
	int n; scanf("%d",&n);
	vector<int> c(n);
	int x,y,z,m[2]; scanf("%d%d%d%d%d%d%d",&x,&y,&z,&m[0],&m[1],&c[0],&c[1]);
	for(int i=2;i<n;++i) c[i]=(1ll*c[i-1]*x+1ll*c[i-2]*y+z)%m[i%2]+1;
//	for(int i=0;i<n;++i) cerr<<c[i]<<" ";
	stack<pair<ull,int> > stk;
	stk.push(make_pair((ull)1e18,0));
	stk.push(make_pair(1,1));
	ull ans=0;
	ull ss1=0,ss2=0;
	for(int i=0;i<n;++i){
		if(~i&1){
			ss1+=c[i];
			stk.push(make_pair(c[i],1));
		}else{
			ss2+=c[i];
			pop_back(stk,1);
			ans+=pop_back(stk,c[i]-1);
			int t=stk.top().second;
			ans+=pop_back(stk,1);
			stk.push(make_pair(1,t+1));
//			printf("<%lld>",ans);
		}
	}
	printf("%lld\n",ans);
//	cerr<<ss1<<" "<<ss2<<endl;
	return 0;
}

C. 子序列计数

算法一

爆搜，能过 subtask1，15pts。

算法二

随手写个 $\mathrm{dp}$ ，比如 $f(i, x, y, z)$ 表示决策前 $i$ 个元素，最后一个取了 $x$ ，倒数第二个取了 $y$ ，倒数第三个取了 $z$ 。转移的话如果下一个加进去不合法就不取，否则枚举下一个取不取。

复杂度 $\Theta\left(n^4\right)$ ，可以过前两个subtask，35pts。

算法三

压缩一下之前的状态， $f(x, y, z)$ 表示最后一个取的是 $x$ ，倒数第二个是 $y$ ，倒数第三个是 $z$ 的方案数。

考虑一般情况，可以有转移：

$$f(x, y, z)=\sum_{i<z, a_x \oplus a_y \oplus a_z \oplus a_i \neq s} f(y, z, i)$$

可以考虑把 $\sum_{i<z, a_i=a_x \oplus a_y \oplus a_z \oplus s} f(y, z, i)$ 的部分用另外一个数组维护一下，即可 $O(1)$ 转移。

复杂度 $\Theta\left(n^3+n 2^m\right)$ ，可以过 subtask1,2,3，60pts。

算法四

考虑发掘一些性质，由于 $a_i$ 互不相同，所以对于子序列中连续的 5 个元素，如果前四个异或和为 $s$ ，那么后四个异或和一定不为 $s$ 。

根据这个性质考虑再次压缩状态： $f(x, y)$ 表示最后一个取的是 $x$ ，倒数第二个是 $y$ 的方案数。那么有转移方程：

$$f(x, y)=\sum_{z<y}\left(f(y, z)-\sum_{i<z, a_x \oplus a_y \oplus a_z \oplus a_i=s} f(z, i)\right)$$

考虑拆一下：

$$f(x, y)=\sum_{z<y} f(y, z)-\sum_{i<z<y, a_i \oplus a_y \oplus a_z \oplus s=a_x} f(z, i)$$

两部分都可以拿个数组维护一下，复杂度 $\Theta\left(n\left(n+2^m\right)\right)$ ，可以 $\mathrm{AC}$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=1<<12|5,MOD=998244353;
inline void mo(int& x){ x>=MOD?x-=MOD:0; }
inline int mo1(int x){ return x>=MOD?x-MOD:x; }
int a[N],n,f[N][N],g[N],h[N][N],s;
int main(){
	int n,m,s; scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	int ans=n;
	for(int i=1;i<=n;++i){
		g[i]=0;
		for(int j=1;j<i;++j){
			f[i][a[j]]=(1ll+g[j]+MOD-h[j-1][a[i]^a[j]^s])%MOD;
			mo(g[i]+=f[i][a[j]]);
		}
		mo(ans+=g[i]);
		for(int t=0;t<1<<m;++t)
			h[i][t]=(h[i-1][t]+f[i][a[i]^t])%MOD;
	}
	printf("%d\n",ans);
	return 0;
}

D. 邮递员

首先，当 $n, m \leq 6$ 时，我们爆搜出所有合法的解。接下来，不妨设 $\max (n, m)>6$ 。

若行数大于 6，且最顶部两行中不包含起点与终点，则我们可以直接删除顶端两行，并将得到的合法方案进行拼接即可：

同样地，若最左侧、最右侧、最底侧不包含起点与终点，我们同样可以进行上述操作。而当起点与终点位于这些区域时，由于 $\max (n, m) \leq 6$ ，因此必有两行只包含了起点或终点，我们同样进行调整，得到新的起点后删除上述两行即可。

可以证明，只要步数的奇偶性正确，在 $n, m \geq 4$ 时一定有解，因此我们通过上述操作后一定能得到合法的解。

时间复杂度为 $O(\mathrm{~nm})$ 。

#include <bits/stdc++.h>

std::mt19937 hua(20041115);

const int N = 1005;

int n, m, sx, sy, tx, ty;
const int dx[5] = { 1, 0, -1, 0, 0x3f3f3f3f };
const int dy[5] = { 0, 1, 0, -1, 0x3f3f3f3f };
const char* dir = "RDLU"; // Polish character??
int st[N][N];
bool vis[N][N];

int get_id(int x, int y) {
	for (int i = 0; i < 4; ++i)
			if (dx[i] == x && dy[i] == y)
				return i;
	throw;
}
int parse_en(char ch) {
	// I don't understand Polish
	if (ch == 'R')
		return 0;
	if (ch == 'D')
		return 1;
	if (ch == 'L')
		return 2;
	if (ch == 'U')
		return 3;
	throw;
}
bool inside(int lx, int rx, int ly, int ry, int x, int y) {
	return lx <= x && x <= rx && ly <= y && y <= ry;
}
bool ok(int lx, int rx, int ly, int ry, int x, int y) {
	return inside(lx, rx, ly, ry, x, y) && !vis[x][y];
}

bool dfs(int lx, int rx, int ly, int ry, int sx, int sy, int tx, int ty, int steps) {
	if (sx == tx && sy == ty) {
		if (steps == 1)
			return true;
		return false;
	}
	if (steps == 1)
		return false;
	for (int o = 0; o < 4; ++o) {
		int nx = sx + dx[o], ny = sy + dy[o];
		if (!ok(lx, rx, ly, ry, nx, ny))
			continue;
		st[sx][sy] = o;
		vis[nx][ny] = true;
		if (dfs(lx, rx, ly, ry, nx, ny, tx, ty, steps - 1))
			return true;
		vis[nx][ny] = false;
	}
	return false;
}

int cur_x, cur_y;
void set_dir(int x1, int y1, int x2, int y2, bool visited = false) {
	//printf("set dir %d %d %d %d\n", x1, y1, x2, y2);
	assert(cur_x == x1);
	assert(cur_y == y1);
	st[x1][y1] = get_id(x2 - x1, y2 - y1);
	if (vis[x2][y2] != visited) {
		throw;
	}
	vis[x2][y2] = true;
	cur_x = x2, cur_y = y2;
}
void cancel(int x, int y) {
	if (!vis[x][y]) {
		throw;
	}
	int nx = x + dx[st[x][y]];
	int ny = y + dy[st[x][y]];
	vis[nx][ny] = false;
	st[x][y] = 0;
}
void move(int lx, int rx, int ly, int ry, int dx, int dy, bool mode) {
	/* mode:
			0: move one step
			1: keep moving
	*/
	//fprintf(stderr, "move %d %d %d %d %d %d %d\n", lx, rx, ly, ry, dx, dy, mode);
	//fprintf(stderr, "curx = %d, cury = %d\n", cur_x, cur_y);
	int o = get_id(dx, dy);
	if (mode == false) {
		set_dir(cur_x, cur_y, cur_x + dx, cur_y + dy);
	}
	else {
		while (ok(lx, rx, ly, ry, cur_x + dx, cur_y + dy)) {
			set_dir(cur_x, cur_y, cur_x + dx, cur_y + dy);
		}
	}
}

void solve(int lx, int rx, int ly, int ry, int sx, int sy, int tx, int ty) {
	if (rx - lx + 1 <= 6 && ry - ly + 1 <= 6) {
		//for (int cx = lx; cx <= rx; ++cx)
		//	for (int cy = ly; cy <= ry; ++cy)
		//		assert(!vis[cx][cy]);
		if (!dfs(lx, rx, ly, ry, sx, sy, tx, ty, (rx - lx + 1) * (ry - ly + 1))) {
			puts("NIE"); // gg
			exit(0);
		}

		return;
	}
	auto go = [&](int dx, int dy, bool mode) {
		move(lx, rx, ly, ry, dx, dy, mode);
	};
	auto gogo = [&](char ch, int len) {
		int o = parse_en(ch);
		assert(len >= -1);
		int total_steps = 0;
		if (len == -1) {
			while (ok(lx, rx, ly, ry, cur_x + dx[o], cur_y + dy[o])) {
				++total_steps;
				go(dx[o], dy[o], false);
			}
			return total_steps;
		}
		else {
			for (int i = 0; i < len; ++i) {
				go(dx[o], dy[o], false);
			}
			return len;
		}
	};
	auto extend_path = [&](std::string s) {
		bool mode = false;
		for (auto ch : s) {
			int o = parse_en(ch);
			go(dx[o], dy[o], mode);
			mode = !mode;
		}
	};
	auto remake = [&](int x, int y) {
		cancel(x, y);
		cur_x = x, cur_y = y;
	};
	auto bounded = [&](int lx, int rx, int ly, int ry) {
		return inside(lx, rx, ly, ry, sx, sy) 
			&& inside(lx, rx, ly, ry, tx, ty);
	};
	auto ensure = [&](int x0, int y0) {
		if (x0 != cur_x || y0 != cur_y) {
			// 锟斤拷
			throw;
		}
	};
	auto ensure_R = [&](int x0, int x1, int y0, int y1) {
		if (!(x0 <= cur_x && cur_x <= x1 && y0 <= cur_y && cur_y <= y1)) {
			throw;
		}
	};
	auto validate_shrink = [&](int l, int r) {
		return r - l + 1 > 6;
	};
	if (validate_shrink(lx, rx) && bounded(lx + 2, rx, ly, ry)) {
		// Case 1A: Left Free
		solve(lx + 2, rx, ly, ry, sx, sy, tx, ty);
		bool ok = false;
		for (int j = ly; j <= ry; ++j) {
			if (dy[st[lx + 2][j]] == 1) {
				assert(j < ry);
				remake(lx + 2, j);
				extend_path("LULDRUR");
				ensure(lx + 2, j + 1);
				ok = true;
				break;
			}
			else if (dy[st[lx + 2][j]] == -1) {
				assert(j > ly);
				remake(lx + 2, j);
				extend_path("LDLURDR");
				ensure(lx + 2, j - 1);
				ok = true;
				break;
			}
		}
		assert(ok);
	}
	else if (validate_shrink(lx, rx) && bounded(lx, rx - 2, ly, ry)) {
		// Case 1B: Right Free
		solve(lx, rx - 2, ly, ry, sx, sy, tx, ty);
		bool ok = false;
		for (int j = ly; j <= ry; ++j) {
			if (dy[st[rx - 2][j]] == 1) {
				remake(rx - 2, j);
				extend_path("RURDLUL");
				ensure(rx - 2, j + 1);
				ok = true;
				break;
			}
			else if (dy[st[rx - 2][j]] == -1) {
				remake(rx - 2, j);
				extend_path("RDRULDL");
				ensure(rx - 2, j - 1);
				ok = true;
				break;
			}
		}
		assert(ok);
	}
	else if (validate_shrink(ly, ry) && bounded(lx, rx, ly + 2, ry)) {
		// Case 1C: Up Free
		solve(lx, rx, ly + 2, ry, sx, sy, tx, ty);
		bool ok = false;
		for (int j = lx; j <= rx; ++j) {
			if (dx[st[j][ly + 2]] == -1) {
				remake(j, ly + 2);
				extend_path("URULDRD");
				ensure(j - 1, ly + 2);
				ok = true;
				break;
			}
			else if (dx[st[j][ly + 2]] == 1) {
				remake(j, ly + 2);
				extend_path("ULURDLD");
				ensure(j + 1, ly + 2);
				ok = true;
				break;
			}
		}
		assert(ok);
	}
	else if (validate_shrink(ly, ry) && bounded(lx, rx, ly, ry - 2)) {
		// Case 1D: Down Free
		solve(lx, rx, ly, ry - 2, sx, sy, tx, ty);
		bool ok = false;
		for (int j = lx; j <= rx; ++j) {
			if (dx[st[j][ry - 2]] == -1) {
				remake(j, ry - 2);
				extend_path("DRDLURU");
				ensure(j - 1, ry - 2);
				ok = true;
				break;
			}
			else if (dx[st[j][ry - 2]] == 1) {
				remake(j, ry - 2);
				extend_path("DLDRULU");
				ensure(j + 1, ry - 2);
				ok = true;
				break;
			}
		}
		assert(ok);
	}
	// Case 2-5: keep moving until the length of each border <= 6
	else if (validate_shrink(lx, rx) && inside(lx, lx, ly, ry, sx, sy)) {
		// Case 2A: left bound
		// Note that (ry - ly + 1) >= 4
		cur_x = sx, cur_y = sy;
		if (sy == ry) {
			// Case 2AA
			gogo('U', -1);
			gogo('R', 1);
			gogo('D', -1);
			gogo('R', 1);
			ensure_R(lx + 2, rx, ly, ry);
			solve(lx + 2, rx, ly, ry, cur_x, cur_y, tx, ty);
		}
		else if (sy + 1 == ry) {
			// Case 2AB
			gogo('D', 1);
			gogo('R', 1);
			gogo('U', 2);
			gogo('L', 1);
			gogo('U', -1);
			gogo('R', 1);
			gogo('D', -1);
			gogo('R', 1);	
			ensure_R(lx + 2, rx, ly, ry);
			solve(lx + 2, rx, ly, ry, cur_x, cur_y, tx, ty);
		}
		else {
			// Case 2AC
			int len = gogo('U', -1);
			gogo('R', 1);
			gogo('D', len + 1);
			gogo('L', 1);
			gogo('D', -1);
			gogo('R', 1);
			gogo('U', -1);
			gogo('R', 1);
			ensure_R(lx + 2, rx, ly, ry);
			solve(lx + 2, rx, ly, ry, cur_x, cur_y, tx, ty);
		}
	}
	else if (validate_shrink(lx, rx) && inside(lx + 1, lx + 1, ly, ry, sx, sy)) {
		// Case 2B: left strip
		cur_x = sx, cur_y = sy;
		if (sy == ry) {
			// Case 2BA
			gogo('L', 1);
			gogo('U', -1);
			gogo('R', 1);
			gogo('D', -1);
			gogo('R', 1);
			ensure_R(lx + 2, rx, ly, ry);
			solve(lx + 2, rx, ly, ry, cur_x, cur_y, tx, ty);
		}
		else {
			// Case 2BB
			gogo('U', -1);
			gogo('L', 1);
			gogo('D', -1);
			gogo('R', 1);
			gogo('U', -1);
			gogo('R', 1);
			ensure_R(lx + 2, rx, ly, ry);
			solve(lx + 2, rx, ly, ry, cur_x, cur_y, tx, ty);
		}
	}
	else if (validate_shrink(lx, rx) && inside(rx, rx, ly, ry, sx, sy)) {
		// Case 3A: right bound
		cur_x = sx, cur_y = sy;
		if (sy == ry) {
			// Case 2AA
			gogo('U', -1);
			gogo('L', 1);
			gogo('D', -1);
			gogo('L', 1);
			ensure_R(lx, rx - 2, ly, ry);
			solve(lx, rx - 2, ly, ry, cur_x, cur_y, tx, ty);
		}
		else if (sy + 1 == ry) {
			// Case 2AB
			gogo('D', 1);
			gogo('L', 1);
			gogo('U', 2);
			gogo('R', 1);
			gogo('U', -1);
			gogo('L', 1);
			gogo('D', -1);
			gogo('L', 1);
			ensure_R(lx, rx - 2, ly, ry);
			solve(lx, rx - 2, ly, ry, cur_x, cur_y, tx, ty);
		}
		else {
			// Case 2AC
			int len = gogo('U', -1);
			gogo('L', 1);
			gogo('D', len + 1);
			gogo('R', 1);
			gogo('D', -1);
			gogo('L', 1);
			gogo('U', -1);
			gogo('L', 1);
			ensure_R(lx, rx - 2, ly, ry);
			solve(lx, rx - 2, ly, ry, cur_x, cur_y, tx, ty);
		}
	}	
	else if (validate_shrink(lx, rx) && inside(rx - 1, rx - 1, ly, ry, sx, sy)) {
		// Case 3B: right strip
		cur_x = sx, cur_y = sy;
		if (sy == ry) {
			// Case 3BA
			gogo('R', 1);
			gogo('U', -1);
			gogo('L', 1);
			gogo('D', -1);
			gogo('L', 1);
			ensure_R(lx, rx - 2, ly, ry);
			solve(lx, rx - 2, ly, ry, cur_x, cur_y, tx, ty);
		}
		else {
			// Case 3BB
			gogo('U', -1);
			gogo('R', 1);
			gogo('D', -1);
			gogo('L', 1);
			gogo('U', -1);
			gogo('L', 1);
			ensure_R(lx, rx - 2, ly, ry);
			solve(lx, rx - 2, ly, ry, cur_x, cur_y, tx, ty);
		}
	}
	else if (validate_shrink(ly, ry) && inside(lx, rx, ly, ly, sx, sy)) {
		// Case 4A: Up bound
		cur_x = sx, cur_y = sy;
		if (sx == rx) {
			// Case 4AA
			gogo('L', -1);
			gogo('D', 1);
			gogo('R', -1);
			gogo('D', 1);
			ensure_R(lx, rx, ly + 2, ry);
			solve(lx, rx, ly + 2, ry, cur_x, cur_y, tx, ty);
		}
		else if (sx + 1 == rx) {
			gogo('R', 1);
			gogo('D', 1);
			gogo('L', 2);
			gogo('U', 1);
			gogo('L', -1);
			gogo('D', 1);
			gogo('R', -1);
			gogo('D', 1);
			ensure_R(lx, rx, ly + 2, ry);
			solve(lx, rx, ly + 2, ry, cur_x, cur_y, tx, ty);
		}
		else {
			int steps = gogo('L', -1);
			gogo('D', 1);
			gogo('R', steps + 1);
			gogo('U', 1);
			gogo('R', -1);
			gogo('D', 1);
			gogo('L', -1);
			gogo('D', 1);
			ensure_R(lx, rx, ly + 2, ry);
			solve(lx, rx, ly + 2, ry, cur_x, cur_y, tx, ty);
		}
	}
	else if (validate_shrink(ly, ry) && inside(lx, rx, ly + 1, ly + 1, sx, sy)) {
		// Case 4B: Up strip
		cur_x = sx, cur_y = sy;
		if (sx == rx) {
			gogo('U', 1);
			gogo('L', -1);
			gogo('D', 1);
			gogo('R', -1);
			gogo('D', 1);
			ensure_R(lx, rx, ly + 2, ry);
			solve(lx, rx, ly + 2, ry, cur_x, cur_y, tx, ty);
		}
		else {
			gogo('L', -1);
			gogo('U', 1);
			gogo('R', -1);
			gogo('D', 1);
			gogo('L', -1);
			gogo('D', 1);
			ensure_R(lx, rx, ly + 2, ry);
			solve(lx, rx, ly + 2, ry, cur_x, cur_y, tx, ty);
		}
	}
	else if (validate_shrink(ly, ry) && inside(lx, rx, ry, ry, sx, sy)) {
		// Case 5A: Down bound
		cur_x = sx, cur_y = sy;
		if (sx == rx) {
			// Case 5A
			gogo('L', -1);
			gogo('U', 1);
			gogo('R', -1);
			gogo('U', 1);
			ensure_R(lx, rx, ly, ry - 2);
			solve(lx, rx, ly, ry - 2, cur_x, cur_y, tx, ty);
		}
		else if (sx + 1 == rx) {
			gogo('R', 1);
			gogo('U', 1);
			gogo('L', 2);
			gogo('D', 1);
			gogo('L', -1);
			gogo('U', 1);
			gogo('R', -1);
			gogo('U', 1);
			ensure_R(lx, rx, ly, ry - 2);
			solve(lx, rx, ly, ry - 2, cur_x, cur_y, tx, ty);
		}
		else {
			int steps = gogo('L', -1);
			gogo('U', 1);
			gogo('R', steps + 1);
			gogo('D', 1);
			gogo('R', -1);
			gogo('U', 1);
			gogo('L', -1);
			gogo('U', 1);
			ensure_R(lx, rx, ly, ry - 2);
			solve(lx, rx, ly, ry - 2, cur_x, cur_y, tx, ty);
		}
	}
	else if (validate_shrink(ly, ry) && inside(lx, rx, ry - 1, ry - 1, sx, sy)) {
		// Case 4B: Up strip
		cur_x = sx, cur_y = sy;
		if (sx == rx) {
			gogo('D', 1);
			gogo('L', -1);
			gogo('U', 1);
			gogo('R', -1);
			gogo('U', 1);
			ensure_R(lx, rx, ly, ry - 2);
			solve(lx, rx, ly, ry - 2, cur_x, cur_y, tx, ty);
		}
		else {
			gogo('L', -1);
			gogo('D', 1);
			gogo('R', -1);
			gogo('U', 1);
			gogo('L', -1);
			gogo('U', 1);
			ensure_R(lx, rx, ly, ry - 2);
			solve(lx, rx, ly, ry - 2, cur_x, cur_y, tx, ty);
		}
	}
	else {
		puts("TBD");
		exit(0);
	}
}

void check_NIE() {
	int steps = n * m - 1;
	int parity = (sx ^ sy) ^ (tx ^ ty);
	if ((steps & 1) != (parity & 1)) {
		fprintf(stderr, "gg1\n");
		puts("NIE");
		exit(0);
	}
	if (steps % 2 == 0) {
		if ((sx ^ sy) & 1) {
		fprintf(stderr, "gg2\n");
			puts("NIE");
			exit(0);
		}
	}
}

void construct_solution() {
	while (sx != tx || sy != ty) {
		int o = st[sx][sy];
		putchar(dir[o]);
		sx += dx[o];
		sy += dy[o];
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin >> n >> m >> sx >> sy >> tx >> ty;
	check_NIE();
	vis[sx][sy] = 1;
	st[tx][ty] = 4;
	solve(1, n, 1, m, sx, sy, tx, ty);
	construct_solution();
}

状态: 已结束
规则: OI
题目: 4
开始于: 2026-8-26 13:00
结束于: 2026-8-26 17:00
持续时间: 4 小时
主持人: kcs007
参赛人数: 10

0826

A. 简单数学题

算法一

算法二

算法三

B. 简单算法题

算法一

算法二

算法三

算法四

其它想法

C. 子序列计数

算法一

算法二

算法三

算法四

D. 邮递员

登录