JZTXT

2023百度之星第三场

发布时间 2023-09-25 15:23:31作者: value0

2023百度之星第三场

BD202321新材料

解题思路：

对于每一个种类的材料(该种类的材料有很多个,在不同位置)，如果存在两个个体之间距离小于等于\(k\),那么我们最终答案就要异或上该种类的编号。

滑动窗口维护一个长度为\(k\)的区间即可。

对于每个新加入的元素，判断当前窗口内是否存在同类材料，若存在答案异或上他的种类并标记，以防重复计算。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,k;
#define fi first
#define se second 
void solve()
{
	scanf("%lld %lld",&n,&k);
	vector<int> a(n + 1);
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	map<int,int> mp,cnt,st;
	vector<int> q(n + 1);
	int hh = 0;
	int tt = -1;
	ll ans = 0;
	for(int i = 1;i<=n;i++)
	{
		while(hh <= tt && tt - hh + 1 > k)
		{ 
			cnt[a[q[hh]]] --;
			hh ++;
		}
		if(tt - hh + 1 <= k)
		{
			if(cnt[a[i]] > 0 && !st[a[i]])
			{
				ans ^= a[i];
				st[a[i]] = true;
			}
			q[++tt] = i;
			cnt[a[i]]++;
		}
	}
	cout<<ans<<endl;
}

int main()
{
	int t = 1;
	while(t--)
	{
		solve();
	}
	return 0;
}

BD202319新的阶乘

解题思路:

若存在

\[a = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k} \]

我们要记录的信息，就是每个\(p_i\)和其对应的\(\alpha_i\).

则\(a^b\)对答案的贡献为

\[a^b = p_1^{\alpha_1b}p_2^{\alpha_2b}...p_k^{\alpha_kb} \]

其中的\(p_i\)不变，但是\(\alpha_i \times b\)。

由于:

\[f(x) = x^1 * (x - 1)^2 * (x - 2)^3 * ... *2^{x-1} * 1^x \]

我们只需要将每个数\(x ,x-1,...,1\)进行质因子拆分，然后将他们质因子原本的指数乘上最初的次数，然后对应累加起来就是答案。

我们设\(minp[x]\)为\(x\)的最小质因子。

那么

\[\begin{align*} x &= minp[x] * (x/minp[x]) \\ x^k &= minp[x]^k * (x/minp[x])^k \end{align*} \]

其中\(x^k对minp[x]的贡献为k，对(x/minp[x])的贡献也为k\)。

我们从大到小不断对当前数进行拆分，最终会不断拆分最小质因子，直至完成对所有质因子的累加。

开始的时候，我们要初识化所有数\((x,x-1,...2,1)\)的次数，也就是他们根据质因子唯一分解后的质因子的指数要乘的倍数。

注意：初始化所有数的次数后，质数不必再进行拆分，因为它会加到自己身上，也就是重复计算。

举例:\(12^2 = 2 ^2 *6^2 = 2^2 * 2 ^2 * 3 ^ 2 = 2 ^4 * 3 ^ 2\),其中对\(2\)的贡献分别来自第一的最小质因数转移和\(6\)的最小质因数转移，这个过程中，开始的次数\(2\)一直随之移动。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e7 + 10;
ll primes[N];
bool st[N];
int cnt = 0;
ll minp[N];
ll n;

void init()
{
	for(int i = 2;i<=N-5;i++)
	{
		if(!st[i])
		{
			primes[cnt++] = i;
			minp[i] = i;
			st[i] = true;
		}
		for(int j = 0;primes[j] <= N / i;j++)
		{
			minp[i * primes[j]] = primes[j];
			st[i * primes[j]] = true;
			if(i % primes[j] == 0)
			{
				break;
			}
		}
	}
}

void solve()
{
	ll n;
	scanf("%lld",&n);
	if(n == 1)
	{
		printf("f(1)=0\n");
		return;
	}
	vector<ll> f(n + 1,1);
	for(int i = 2;i <= n;i++)
	{
		f[i] *= (n - i + 1);
	}
	for(int i = n;i > 1;i--)
	{
		if(minp[i] == i)
		{
			continue;
		}
		f[minp[i]] += f[i];
		f[i / minp[i]] += f[i];
	}
	
	printf("f(%lld)=",n);
	bool start = false;
	for(int i = 0;i<cnt && primes[i] <= n;i++)
	{
		int p = primes[i];
		if(f[p] > 0)
		{
			if(!start)
			{
				start = true;
				
			}
			else
			{
				printf("*");
			}
			printf("%lld",p);
			if(f[p] > 1)
			{
				printf("^%lld",f[p]);
			}
		}
	}
}

int main()
{
	int t = 1;
	init();
	while(t--)
	{
		solve();
	}
	return 0;
}

BD202322与蝴蝶一起消散吧

解题思路:

我们在每一波怪物来袭开始都可能有两种情况(第一波只有一种情况)：必杀技可用和不可用。

对于第\(i\)波怪物，如果\(a_i >= k\),那么我们一定是有必杀技就放，因为放了一定就能节省\(k\)分钟。

其中，如果\(a_i > k\),那么无论我们开始是否有技能，这波怪物打完，我们手里一定是有技能的。若\(a_i == k\)，那么这波结束是否有必杀，取决于我们的开始状态和怪物数量。

如果\(a_i < k\)，那我们分情况操作。

首先，如果当前有必杀技并且需要消灭的怪物的数量是偶数，那么我们一定是有必杀放必杀。因为这样在结束时一定有必杀。既保留了必杀的选择权又最大化减少了时间。

若当前没有必杀技，那么我们只能平\(A\)。若平\(A\)后进入有必杀加偶数怪物环节，同上。否则会转入下一个情况。

若当前有必杀技且剩余怪物数量为奇数，我们有两种选择。

  1. 有必杀用必杀。这样这波结束时我们是没有必杀技的。
  2. 平\(A\)一轮，进入有必杀加偶数环节，这样能保证进入下一轮时有必杀技可用。

定义\(f[i][j][k]:在进入第i轮时状态为j，在消灭掉第i轮怪物后，状态为k的花费时间。其中状态0为有必杀，1位无必杀\)。

注意：奇偶性不同花费的时间会有变化，最终答案为\(ans = min\{f[n][0][0] ,f[n][0][1],f[n][1][0],f[n][1][1]\}\)

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,k;
const int N = 1e5 + 10;
ll f[N][4][4];
void solve()
{
	scanf("%lld %lld",&n,&k);
	vector<ll> a(n + 1),m(n + 1);
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i],&m[i]);
		
	}
	ll ans = 1e18;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 0;j<2;j++)
		{
			for(int k = 0;k<2;k++)
			{
				f[i][j][k] = 1e18;
			}
		}
	}
	//0 you
	//1 wu
	for(int i = 1;i<=n;i++)
	{
		if(a[i] > k)
		{
			f[i][0][0] = min(f[i-1][1][0],f[i-1][0][0]) + (m[i] * (a[i] - k));
			f[i][1][0] = min(f[i-1][1][1],f[i-1][0][1]) + (a[i] + (m[i] - 1) * (a[i] - k));
		}
		else if(a[i] == k)
		{
			if(m[i] & 1)
			{
				f[i][1][0] = min(f[i-1][1][1],f[i-1][0][1]) + (a[i] + (m[i] / 2) * a[i]);
				f[i][0][1] = min(f[i-1][1][0],f[i-1][0][0]) + ((m[i] / 2) * a[i]);
			}
			else
			{
				f[i][1][1] = min(f[i-1][1][1],f[i-1][0][1]) + ((m[i] / 2) * a[i]);
				f[i][0][0] = min(f[i-1][1][0],f[i-1][0][0]) + ((m[i] / 2) * a[i]);
			}
		}
		else
		{
			if(m[i] & 1)
			{
				f[i][1][0] = min(f[i-1][1][1],f[i-1][0][1]) + (a[i] + (m[i] / 2) * a[i]);
				f[i][0][1] = min(f[i-1][1][0],f[i-1][0][0]) + ((m[i] / 2) * a[i]);
				f[i][0][0] = min(f[i-1][1][0],f[i-1][0][0]) + (a[i] + (m[i] - 1) / 2 * a[i]);
			}
			else
			{
				f[i][1][1] = min(f[i-1][1][1],f[i-1][0][1]) + ((m[i] / 2) * a[i]);
				f[i][1][0] = min(f[i-1][1][1],f[i-1][0][1]) + (2 * a[i] + ((m[i] - 2) / 2) * a[i]);
				f[i][0][0] = min(f[i-1][1][0],f[i-1][0][0]) + ((m[i] / 2) * a[i]);
			}
		}
		
	}
	ans = min(ans,f[n][1][0]);
	ans = min(ans,f[n][0][1]);
	ans = min(ans,f[n][1][1]);
	ans = min(ans,f[n][0][0]);
	cout<<ans<<endl;
}

int main()
{
	int t = 1;
	while(t--)
	{
		solve();
	}
	return 0;
}