当前位置：首页 > article >正文

LQ quarter 5th

article 2025/1/10 16:12:41

B. 开赛主题曲

C. BlueAI

E. 精准难度

B. 开赛主题曲

（1）两层循环枚举所有子串。第一层子串长度，第二层子串起点

（2）判子串是否合法还要一个 for，26 * 26 * 2e5 快要超时，因此计算每个字母个数只能用最朴素的数组，用 map 就超时

（3）string型字符串的 find 函数可以查找子串（连续），也可以是单个字符，若没有查找到返回 string ：： nops

（4）字符串截取 string.substr( i, len )：从第 i 个位置开始截 len 长度的子串

（5）字符串可以直接比较大小，判定升序

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;

int T, n, ans;
string s, mxs;

int f(string s)
{
	int tot = 0;
	for (int i = 0; i < s.length(); i ++)
		tot += s[i] - 'a' + 1;
	string ss = "lanqiobe";
	for (int i = 8; i > 0; i --)
		if (s.find(ss.substr(0, i)) != string :: npos)
		{
			tot += i * 10;
			break;
		}
	return tot;
}

signed main()
{
	cin >> n >> s;
	s = ' '  + s;
	for (int len = 1; len <= 26; len ++)
		for (int i = 1; i + len - 1 <= n; i ++)
		{
			int a[30] = {0};
			int p = 0;
			string t = s.substr(i, len);
			for (int i = 0; i < len; i ++)
			{
				if (++ a[t[i] - 'a'] == 2)
				{
					p = 1;
					break;
				}
			}
			if (p == 1)
				continue;
			int scr = f(t);
			if (scr > ans || (scr == ans && t < mxs))
				ans = scr, mxs = t;
		}
	cout << mxs;
	return 0;
}

C. BlueAI

（1）注意一个棋子移动，三个坐标的字符都要改，不能只把中间的 'Q' 变成 '.'

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;

int t, n, ans;
char a[20][20];

void dfs(int x, int y, int cnt)
{
	ans = max(ans, cnt);
	int dx[5] = {-1, -1, 1, 1}, dy[5] = {-1, 1, -1, 1};
	for (int i = 0; i <= 3; i ++)
	{
		int tx1 = x + dx[i], ty1 = y + dy[i], tx2 = x + dx[i] * 2, ty2 = y + dy[i] * 2;
		if (tx2 < 1 || tx2 > n || ty2 < 1 || ty2 > n)
			continue;
		if (a[tx1][ty1] == 'Q' && a[tx2][ty2] == '.')
		{
			a[x][y] = '.', a[tx1][ty1] = '.', a[tx2][ty2] = 'L';        // 一定要三个全改
			dfs(tx2, ty2, cnt + 1);
			a[x][y] = 'L', a[tx1][ty1] = 'Q', a[tx2][ty2] = '.';        // 再全部改来
		}
	}
}

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			if (a[i][j] == 'L')
				dfs(i, j, 0);
	cout << ans;
	return 0;
}

E. 精准难度

（1）对于同一个数 a，a ^ a = 0，a ^ a ^ a = a。由此可见假设有 x 个子串乘积对 2025 取余的余数为 i，若 x 为偶数，该余数异或和为 0，若为奇数，贡献为该余数

（2）那么题目难点转变成，如何求所有子数组的乘积并取余后，所有余数有多少个

（3）图中列式的关键在于，对于每一个新输入的 a[ i ]，只会附乘在以 a[ i - 1 ] 为结尾的所有子数组之后。因此我只需要用到上一次取余后的结果

（4）为什么不是上一次 i 项子数组乘积的结果，而是用上一次的余数呢？因为模运算在任何地方都可以加，可以随时随地取模。a[ 1 ] * a[ 2 ] * ... * a[ i - 1 ] * a[ i ] % 2025 就等同于 a[ 1 ] * a[ 2 ] * ... * a[ i - 1 ] % 2025 * a[ i ] % 2025，即上一次的余数 * a[ i ] 再取模

（5）题中 n 的大小有 1e5，显然开不了 dp[ 100000 ][ 2025 ] 的数组，由于只需要用到上一次的余数，由此可以使用滚动数组。dp [ i & 1 ][ j ]，i & 1 会改变奇偶性，0 和 1 交替，达到滚动数组的目的

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;

int T, n, aans, a[N], ans[2025], dp[2][2025];
string s;

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		for (int j = 0; j < 2025; j ++)
			dp[i & 1][j] = 0;
		for (int j = 0; j < 2025; j ++)
			dp[i & 1][j * a[i] % 2025] += dp[(i - 1) & 1][j];
		dp[i & 1][a[i] % 2025] ++;
		for (int j = 0; j < 2025; j ++)
			ans[j] += dp[i & 1][j];
	}
	for (int i = 0; i < 2025; i ++)
		if (ans[i] % 2 != 0)
				aans ^= i;
	cout << aans;
	return 0;
}

查看全文

http://www.kler.cn/a/481803.html