标签：ch int LL cin Codeforces 数组 Div include 815

比赛链接

C

题意：给定一个大小为n*m的01矩阵，每次操作你可以消除一个L形(\(2*2\)矩阵 )内的所有1，每次必须保证消除至少一个1，求操作数的最大值。

核心思路：这个其实我们需要模拟两到三个样例来观察下规律，这里有个很重要的性质：当我们进行完第一次操作之后，我们会发现我们每次都可以消除一个1.并不是只能消除一个1，因为我们需要保证操作数最大，所以我们每次只能消除一个1.

接下来就是对于第一次操作的的一个贪心操作了，我们可以发现因为我们每次都是L式消1，所以我们可以枚举一个\(2*2\)的矩阵。因为其实就只有一下这几种情况:

1 1   1 0  1 1 1 0
1 1   1 0  1 0 0 0

下面细节看代码：

#include<bits/stdc++.h>
#include<unordered_map>
#define IOS std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long LL;
const int N =550,M=50050;
LL inf = (1LL << 30)-1 ;
typedef pair<int, int> PII;
int  a[N][N];
int n, m;
int getNum()
{
	char ch;
	while (ch = getchar(), ch != '0' && ch != '1')
		return ch - 48;
}
void solve()
{
	cin >> n >> m;
	LL sum = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1;j <= m;j++)
		{
			scanf("%1d", &a[i][j]);
			sum += a[i][j];
		}
	int cur = 4;
	for (int i = 1;i <= n - 1;i++)
		for (int j = 1;j <= m - 1;j++)
			cur = min(cur, a[i][j]+a[i + 1][j]+ a[i][j + 1]+ a[i + 1][j + 1]);
	cout << sum - max(0, cur - 2) << endl;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

---

D1

题意：给定一个a数组，定义b数组是a的子数组当且仅当b数组由a的下标递增而形成。要求一个美丽的b数组满足\(a_{b_p}\bigoplus b_{p+1}<a_{b_{p+1}} \bigoplus b_p\)  ，a[i]的范围是0 <= a[i] <= 200，求最长的美丽数列。

核心思路：首先我们需要明白最重要的点，那就是b数组即代表a数组中的下标，也代表a数组中的值。于是我们就把这个问题转化一个线性dp问题。

1. 集合定义：f[i]为以i结尾的最长长度。

2. 集合划分：线性dp问题一般都之和前一个状态有关系。所以我们只需要关注哪个状态可以转为这个状态。

3. 状态转移方程：f[j]==max(f[j],f[i]+1).这个限制条件就是题目给的。

这里我们需要注意下j的一个枚举长度。因为\(x-y<x\bigoplus y<x+y\).然后我们可以根据一个限制条件来递推:

\[a[i]\bigoplus j<a[i]+j \\\\\\a[j]\bigoplus i<a[j]+i \\所以j<a[j]-a[i]+i \]

又因为a<200,所以j<400+i.

#include<bits/stdc++.h>
#include<unordered_map>
#define IOS std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long LL;
const int N = 2e6+ 10;
LL inf = (1LL << 30)-1 ;
typedef pair<int, int> PII;
int a[N];
int n, m;
int f[N];
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 0;i < n;i++)
			cin >> a[i];
		for (int i = 0;i < n;i++)
			f[i] = 1;
		for(int i=0;i<n-1;i++)//这里需要注意，因为后面的j=i+1，所以要给j留余地
			for (int j = i + 1;j < min(n, i + 400);j++)
			{
				if ((a[i] ^ j) < (a[j] ^ i))
					f[j] = max(f[j], f[i] + 1);
			}
		int ans = f[0];
		for (int i = 1;i < n;i++)
			ans = max(ans, f[i]);
		cout << ans << endl;
	}
}

标签：ch,int,LL,cin,Codeforces,数组,Div,include,815
From： https://www.cnblogs.com/xyh-hnust666/p/16948370.html