首页 > 其他分享 >「NOI2009」管道取珠

「NOI2009」管道取珠

时间:2024-03-28 15:37:11浏览次数:36  
标签:取珠 int void 管道 cerr dp template print NOI2009

妙妙题 #dp

转换一下 \(a_i^2\),发现这个值等价于操作 \(2\) 次最后得到结果一样的方案数

那么这就是容易的了

\(dp_{k,i,j}\) 表示操作了 \(k\) 轮,第一次的上面取了 \(i\) 个,第二次的上面取了 \(j\) 个

转移分 \(4\) 种暴力就行

注意空间限制要滚动

// Author: xiaruize
#ifndef ONLINE_JUDGE
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
namespace __DEBUG_UTIL__
{
	using namespace std;
	/* Primitive Datatypes Print */
	void print(const char *x) { cerr << x; }
	void print(bool x) { cerr << (x ? "T" : "F"); }
	void print(char x) { cerr << '\'' << x << '\''; }
	void print(signed short int x) { cerr << x; }
	void print(unsigned short int x) { cerr << x; }
	void print(signed int x) { cerr << x; }
	void print(unsigned int x) { cerr << x; }
	void print(signed long int x) { cerr << x; }
	void print(unsigned long int x) { cerr << x; }
	void print(signed long long int x) { cerr << x; }
	void print(unsigned long long int x) { cerr << x; }
	void print(float x) { cerr << x; }
	void print(double x) { cerr << x; }
	void print(long double x) { cerr << x; }
	void print(string x) { cerr << '\"' << x << '\"'; }
	template <size_t N>
	void print(bitset<N> x) { cerr << x; }
	void print(vector<bool> v)
	{ /* Overloaded this because stl optimizes vector<bool> by using
		  _Bit_reference instead of bool to conserve space. */
		int f = 0;
		cerr << '{';
		for (auto &&i : v)
			cerr << (f++ ? "," : "") << (i ? "T" : "F");
		cerr << "}";
	}
	/* Templates Declarations to support nested datatypes */
	template <typename T>
	void print(T &&x);
	template <typename T>
	void print(vector<vector<T>> mat);
	template <typename T, size_t N, size_t M>
	void print(T (&mat)[N][M]);
	template <typename F, typename S>
	void print(pair<F, S> x);
	template <typename T, size_t N>
	struct Tuple;
	template <typename T>
	struct Tuple<T, 1>;
	template <typename... Args>
	void print(tuple<Args...> t);
	template <typename... T>
	void print(priority_queue<T...> pq);
	template <typename T>
	void print(stack<T> st);
	template <typename T>
	void print(queue<T> q);
	/* Template Datatypes Definitions */
	template <typename T>
	void print(T &&x)
	{
		/*  This works for every container that supports range-based loop
			i.e. vector, set, map, oset, omap, dequeue */
		int f = 0;
		cerr << '{';
		for (auto &&i : x)
			cerr << (f++ ? "," : ""), print(i);
		cerr << "}";
	}
	template <typename T>
	void print(vector<vector<T>> mat)
	{
		int f = 0;
		cerr << "\n~~~~~\n";
		for (auto &&i : mat)
		{
			cerr << setw(2) << left << f++, print(i), cerr << "\n";
		}
		cerr << "~~~~~\n";
	}
	template <typename T, size_t N, size_t M>
	void print(T (&mat)[N][M])
	{
		int f = 0;
		cerr << "\n~~~~~\n";
		for (auto &&i : mat)
		{
			cerr << setw(2) << left << f++, print(i), cerr << "\n";
		}
		cerr << "~~~~~\n";
	}
	template <typename F, typename S>
	void print(pair<F, S> x)
	{
		cerr << '(';
		print(x.first);
		cerr << ',';
		print(x.second);
		cerr << ')';
	}
	template <typename T, size_t N>
	struct Tuple
	{
		static void printTuple(T t)
		{
			Tuple<T, N - 1>::printTuple(t);
			cerr << ",", print(get<N - 1>(t));
		}
	};
	template <typename T>
	struct Tuple<T, 1>
	{
		static void printTuple(T t) { print(get<0>(t)); }
	};
	template <typename... Args>
	void print(tuple<Args...> t)
	{
		cerr << "(";
		Tuple<decltype(t), sizeof...(Args)>::printTuple(t);
		cerr << ")";
	}
	template <typename... T>
	void print(priority_queue<T...> pq)
	{
		int f = 0;
		cerr << '{';
		while (!pq.empty())
			cerr << (f++ ? "," : ""), print(pq.top()), pq.pop();
		cerr << "}";
	}
	template <typename T>
	void print(stack<T> st)
	{
		int f = 0;
		cerr << '{';
		while (!st.empty())
			cerr << (f++ ? "," : ""), print(st.top()), st.pop();
		cerr << "}";
	}
	template <typename T>
	void print(queue<T> q)
	{
		int f = 0;
		cerr << '{';
		while (!q.empty())
			cerr << (f++ ? "," : ""), print(q.front()), q.pop();
		cerr << "}";
	}
	/* Printer functions */
	void printer(const char *) {} /* Base Recursive */
	template <typename T, typename... V>
	void printer(const char *names, T &&head, V &&...tail)
	{
		/* Using && to capture both lvalues and rvalues */
		int i = 0;
		for (size_t bracket = 0; names[i] != '\0' and (names[i] != ',' or bracket != 0); i++)
			if (names[i] == '(' or names[i] == '<' or names[i] == '{')
				bracket++;
			else if (names[i] == ')' or names[i] == '>' or names[i] == '}')
				bracket--;
		cerr.write(names, i) << " = ";
		print(head);
		if (sizeof...(tail))
			cerr << " ||", printer(names + i + 1, tail...);
		else
			cerr << "]\n";
	}
	/* PrinterArr */
	void printerArr(const char *) {} /* Base Recursive */
	template <typename T, typename... V>
	void printerArr(const char *names, T arr[], size_t N, V... tail)
	{
		size_t ind = 0;
		for (; names[ind] and names[ind] != ','; ind++)
			cerr << names[ind];
		for (ind++; names[ind] and names[ind] != ','; ind++)
			;
		cerr << " = {";
		for (size_t i = 0; i < N; i++)
			cerr << (i ? "," : ""), print(arr[i]);
		cerr << "}";
		if (sizeof...(tail))
			cerr << " ||", printerArr(names + ind + 1, tail...);
		else
			cerr << "]\n";
	}
}
#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printer(#__VA_ARGS__, __VA_ARGS__)
#define debugArr(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printerArr(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#define debugArr(...)
#endif
// #define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1024523;
const int N = 5e2 + 10;

int n, m;
char s[N], t[N];
int dp[2][505][505];

void solve()
{
	cin >> n >> m;
	cin >> (s + 1) >> (t + 1);
	reverse(s + 1, s + n + 1);
	reverse(t + 1, t + m + 1);
	dp[0][0][0] = 1;
	rep(r, 1, n + m)
	{
		mms(dp[r & 1], 0);
		rep(i, 0, n)
		{
			rep(j, 0, n)
			{
				if (s[i] == s[j] && i && j)
					dp[r & 1][i][j] += dp[(r & 1) ^ 1][i - 1][j - 1];
				if (r - j > 0 && s[i] == t[r - j] && i)
					dp[r & 1][i][j] += dp[(r & 1) ^ 1][i - 1][j];
				if (r - i > 0 && t[r - i] == s[j] && j)
					dp[r & 1][i][j] += dp[(r & 1) ^ 1][i][j - 1];
				if (r - j > 0 && r - i > 0 && t[r - i] == t[r - j])
					dp[r & 1][i][j] += dp[(r & 1) ^ 1][i][j];
				dp[r & 1][i][j] %= MOD;
			}
		}
	}
	cout << dp[(n + m) & 1][n][n] << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签:取珠,int,void,管道,cerr,dp,template,print,NOI2009
From: https://www.cnblogs.com/xiaruize/p/18101834

相关文章

  • 「NOI2009」植物大战僵尸
    Dinic#网络流#拓扑排序每个点向保护的点建图,对这个图拓扑排序,然后就是求这个图的最大完全子图,就是\(dinic\)板子//Author:xiaruize#ifndefONLINE_JUDGEboolstart_of_memory_use;#else#definedebug(x)#endif#include<bits/stdc++.h>usingnamespacestd;#ifnde......
  • 「NOI2009」变换序列
    二分图最大匹配#贪心如果没有字典序最小的限制,直接二分图最大匹配就可以了考虑怎么让字典序最小倒序匹配左侧节点,对于每个节点,优先尝试字典序较小的方案,用hungary就行另,如果用费用流,需要将斐波那契的第\(10^4\)位作为费用//Author:xiaruize#ifndefONLINE_JUDGEbool......
  • 管道(NamedPipeClientStream)连接报“访问路径被拒绝”
    问题:NamedPipeClientStream对象调用Connect(毫秒)时报“访问路径被拒绝”解决:在服务端(NamedPipeServerStream)中添加PipeSecurity对象SecurityIdentifiersecurityIdentifier=newSecurityIdentifier(WellKnownSidType.AuthenticatedUserSid,null);PipeSecuritypipeSecur......
  • 【网站项目】烯烃厂压力管道管理平台
    ......
  • C#配置网站的服务和HTTP请求管道
    在前面的文章学习了如何使用ASP.NETCoreRazorPages构建网站C#使用ASP.NETCoreRazorPages构建网站(一)C#使用ASP.NETCoreRazorPages构建网站(二)C#使用ASP.NETCoreRazorPages构建网站(三)接下来了解如何配置服务和HTTP请求管道1.配置服务(ConfigureServices)打......
  • ISG立式管道离心泵
    在现代工业系统中,液体的输送是一个至关重要的环节,它涉及到能源效率、系统可靠性以及运行成本等多个方面。在众多类型的泵设备中,ISG立式管道离心泵因其卓越的性能、紧凑的设计和广泛的应用而脱颖而出。本文将深入探讨ISG立式管道离心泵的结构特点、工作原理及其在不同领域的应用......
  • 管道(蓝桥杯)
    有一根长度为\(len\)的横向的管道,该管道按照单位长度分为\(len\)段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。一开始管道是空的,位于\(L_i\)的阀门会在\(S_i\)时刻打开,并不断让水流入管道。对于位于\(L_i\)的阀门,它流入的水在\(T_i\)(\(T_i\geS_i\))时......
  • 进程间通信 之 管道
    目录什么是管道通信管道通信的特点匿名管道命名管道进程间通信的本质:让不同的进程看到同一份资源!什么是管道通信管道是Unix中最古老的进程间通信的形式。它是一种基于文件的通信形式,我们把从一个进程连接到另一个进程的一个数据流称为一个“管道”。管道文件是一种......
  • CSC209 系统故障 管道
    CSCSHELL截止时间为周日晚上11:59。积分2002月14日后12点开始发售。A3–CSCSHELLCSC2092024年冬季上次更新(3月15日):见5.7目录1.简介2.入门文件2.1.实际开始3.CSCSHELL4.限制(shell的东西你不必实现)5.实施和要求5.1.管理错误5.2.外壳变量5.2.1.创造5.2.2.用法5.2.3.路径5.2.4.......
  • RISC-V CPU管道模拟
    RISC-VCPU管道模拟1.简介RISC-V是源自伯克利的开源架构和指令集标准。该项目要求您基于标准的五阶段管道实现RISC-VCPU管道模拟器。您需要从RISC-V规范2.2中指定的RV32I指令设置中实现指令的子集。实施完整的CPU模拟器可以有效地行使系统编程功能,并加深对与建筑有关的知识......