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 8cin >> 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;}