Codeforces Round 1019 (Div. 2) ABC

A 模拟

思路

数组y是不同的，且所以xi * yi 相同，只有x数组全不同才可以满足要求

代码

LL n,m,k;


void solve() 
{
	map<LL,LL> mp;
	cin >> n;
	for (int i = 1;i <= n;i ++)
	{
		LL x;cin >> x;
		mp[x] ++;
	}
	
	cout << mp.size() << endl;
}

B 思维 !

思路

因为初始在0的位置，所以先在每个串前添加0 (方便统计原本的操作次数)
先统计原本需要的操作的次数，如果a[i]!=a[i - 1]不同 就+2（切换当前数字并按一下）,如果a[i]==a[i-1]就+1(直接按一下)

随后考虑反转字串以减少操作次数，首找到第一个不同的数字，下标记为L，找一个后面第一个满足a[R] != a[L] 的R，且R不是最后一个数字，这样操作可使得，区间[L,R]反转后使得操作次数-2
如果R是最后一个数字时,[L,R]反转后只能使得操作次数-1,（因为R后面没有数字，使得不需要切换，直接按一下）

代码

const int N = 2e5 + 10;


LL n,m,k;

char a[N];

void solve() 
{
	//1101[0100100110111]00
	//1101[1110110010010]00
	
	//1110010010011011100
	//2112122122121221121 29
	
	//1101010010011011100
	//2122222122121221121 31
	
	//100 
	//221 5
	//001
	//112 4
	
	//10101
	//22222 10
	//01101
	//12122 8
	
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	
	LL cnt = 0;
	a[0] = '0';
	for (int i = 1;i <= n;i ++)
	{
		if (a[i] != a[i - 1]) cnt += 2;
		else cnt ++;
	}
	// cout << cnt << "==" << endl;
	
	for (int i = 1;i <= n - 1;i ++)
	{
		if (a[i] != a[i - 1])
		{
			int l = i;
			for (int r = l + 1;r <= n;r ++)
			{
				if (a[r] != a[l] &&  r != n  && a[r] != a[r + 1])
				{
					cout << cnt - 2 << endl;
					return;        
				}
				if (a[r] != a[l] && r == n)
				{
					cout << cnt - 1 << endl;
					return;
				}
			}
		}
	}
	
	cout << cnt << endl;
}

C 贪心+思维 !!

题目

是否存在l，r使得   med(med(a1,a2,…,al),med(al+1,al+2,…,ar),med(ar+1,ar+2,…,an))≤k.

med为中位数

思路

代码

const int N = 3e5 + 10;


LL n,m,k;
LL a[N],b[N];

bool check(LL a[])
{
	LL cur = 0;
	map<LL,LL> mp;
	
	for (int i = 1;i < n;i ++)//i < n的原因 :要留出一个数字作为第三块
	{
		cur += a[i];

		if (cur == 1 && (mp[0] || mp[1])) return true;
		if (cur == 0 && mp[0]) return true;
		if (cur >= 2) return true;
		
		mp[cur] ++;
	}
	return false;
}

void solve()
{
	cin >> n >> k;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	for (int i = 1;i <= n;i ++)
	{
		a[i] = (a[i] <= k ? 1 : -1);
	}
	
	
	LL l = 2,cur = a[1];
	while(cur < 0 && l <= n) cur += a[l ++];
	// cout << l << endl;
	
	LL r = n - 1;
	cur = a[n];
	while(cur < 0 && r >= 1) cur += a[r --];
	// cout << r << endl;
	
	if (l <= r)//第一种情况
	{
		cout << "YES" << endl;
		return;
	}
	
	for (int i = 1;i <= n;i ++) b[i] = a[n + 1 - i];

	//第2，3中情况，本质一样，只不过顺序反转一下
	if (check(a) || check(b))
	{
		cout << "YES" << endl;
		return;
	}
	
	cout << "NO" << endl;
	
	
}