首页 > 其他分享 >1853 Round 887 (Div. 2)

1853 Round 887 (Div. 2)

时间：2023-08-02 09:47:07浏览次数：45  
标签：const int 1853 else return -- 887 Div check

Desorting

定义一次操作为选定一个 \(i\) ，令 \(a_{1 \sim i}\) 自增， \(a_{i + 1 \sim n}\) ，自减，求使得整个序列无序的最小操作次数

若序列一开始就无序，输出 \(0\)

否则找到相邻两数差值最小的位置，在这个位置不断使用操作，可以证明这是最优方案

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 5e2 + 7;
 
int a[N];
 
int T, n;
 
inline bool check() {
	for (int i = 2; i <= n; ++i)
		if (a[i] < a[i - 1])
			return true;
	
	return false;
}
 
signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d", &n);
		
		for (int i = 1; i <= n; ++i)
			scanf("%d", a + i);
		
		if (check()) {
			puts("0");
			continue;
		}
		
		int minn = inf;
		
		for (int i = 2; i <= n; ++i)
			minn = min(minn, a[i] - a[i - 1]);
		
		printf("%d\n", minn / 2 + 1);
	}
	return 0;
}

Fibonaccharsis

给定斐波那契数列的第 \(k\) 项 \(n\) ，求 \(f_1, f_2\) 有多少种可能性

注意到斐波那契数列的增长速度十分快，且知道相邻两项之后就能快速推出 \(f_1, f_2\) ，考虑枚举第 \(k - 1\) 项，暴力递推到 \(f_1, f_2\) 即可

时间复杂度 \(O(n \log n)\)

#include <bits/stdc++.h>
using namespace std;

int T, n, K;

inline bool check(int f1, int f2, int pos) {
	int f0;
	
	while (pos--) {
		f0 = f2 - f1;
		
		if (f0 < 0)
			return false;
		
		f2 = f1, f1 = f0;
	}
	
	return f1 <= f2;
}

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d%d", &n, &K);
		int ans = 0;
		
		for (int i = 1; i <= n; ++i)
			ans += check(i, n, K - 2);
		
		printf("%d\n", ans);
	}
	
	return 0;
}

Ntarsis' Set

对于一个无限长的序列 \(1, 2, 3, \cdots\) ，每次删除前 \(a_1, a_2, \cdots, a_n\) 小的数字， \(k\) 次操作后求序列最小值

注意到对于任何一个数，只有删除比它小的数才会使得它更进一步被删掉，二分答案判断是否会被删掉即可

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;

int a[N];

int T, n, K;

inline bool check(int k, ll mid) {
	while (k--)
		mid -= upper_bound(a + 1, a + 1 + n, mid) - a - 1;
	
	return mid < 1;
}

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d%d", &n, &K);
		
		for (int i = 1; i <= n; ++i)
			scanf("%d", a + i);
		
		ll l = 1, r = 1e12, ans = 1;
		
		while (l <= r) {
			ll mid = (l + r) >> 1;
			
			if (check(K, mid))
				l = mid + 1;
			else
				ans = mid, r = mid - 1;
		}
		
		printf("%lld\n", ans);
	}
	
	return 0;
}

Imbalanced Arrays

给定一个序列 \(a_{1 \sim n}\) ，构造一个序列 \(b_{1 \sim n}\) 满足

  • \(-n \leq b_i \leq n, b_i \not = 0\)
  • \(\forall i, j \in [1, n], b_i + b_j \not = 0\)
  • 满足有 \(a_i\) 个 \(j\) 满足 \(b_i + b_j > 0\) （\(i, j\) 可以相等）

若不存在这个序列输出 NO

首先可以注意到若序列中同时出现或同时不出现 \(0\) 和 \(n\) ，则无解

于是我们可以从极端情况入手，用左右两个指针维护即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

struct Node {
	int a, b, id;
	
	inline bool operator < (const Node &rhs) const {
		return a < rhs.a;
	}
} a[N];

int ans[N];

int T, n;

inline bool solve() {
	for (int i = n, l = 1, r = n, tmp = 0; i; --i) {
		if (a[l].a == tmp && a[r].a - i == tmp)
			return false;
		
		if (a[l].a != tmp && a[r].a - i != tmp)
			return false;
		
		if (a[l].a == tmp)
			a[l].b = -i, ++l;
		else
			a[r].b = i, ++tmp, --r;
	}
	
	for (int i = 1; i <= n; ++i)
		ans[a[i].id] = a[i].b;
	
	return true;
}

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d", &n);
		
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a[i].a);
			a[i].id = i;
		}
		
		sort(a + 1, a + 1 + n);
		
		if (solve()) {
			puts("YES");
			
			for (int i = 1; i <= n; ++i)
				printf("%d ", ans[i]);
				
			puts("");
		} else
			puts("NO");
	}
	
	return 0;
}

Ina of the Mountain

定义一次操作为选定 \(l, r\) ，将 \(a_{l \sim r}\) 自减，操作过程中若 \(a_i = 0\) 则 \(a_i \leftarrow k\) ，求使得所有 \(a_i\) 均等于 \(k\) 的最小操作次数

令 \(c_i\) 为 \(a_i\) 被区间覆盖的次数，则 \(\forall i \in [1, n], a_i \equiv c_i \pmod{k}\)

令 \(b_i = a_i - a_{i - 1}, d_i = c_i - c_{i - 1}\) ，则 \(\forall i \in [1, n], b_i \equiv d_i \pmod{k}\) ，可以证明存在一组最优解满足所有 \(d_i \in (-k, k)\)

这样一来，每个 \(d_i\) 只有两种取值，设为 \(A_i < 0, B_i > 0\) 。选 \(A_i\) 不会产生代价，选 \(B_i\) 会产生 \(B_i\) 的代价，且各段前缀中选的数的和要非负

使用小根堆维护反悔贪心即可，时间复杂度 \(O(n \log n)\)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 7;

int a[N];

int T, n, K;

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d%d", &n, &K);
		
		for (int i = 1; i <= n; ++i)
			scanf("%d", a + i);
		
		ll ans = 0;
		priority_queue<int, vector<int>, greater<int> > Q;
		
		for (int i = 1, sum = 0; i <= n; ++i) {
	        int b = (a[i] - a[i - 1] + K) % K;
	
	        if (!b)
	            continue;
	
	        int x = b - K;
	
	        if (sum + x >= 0)
	            sum += x, Q.push(b);
	        else {
	            int num = Q.empty() ? inf : Q.top();
	
	            if (num < b)
	                ans += num, Q.pop(), Q.push(b), sum += x + K;
	            else
	                ans += b, sum += b;
	        }
	    }
	    
	    printf("%lld\n", ans);
	}
	
	return 0;
}

Miriany and Matchstick

用 \(A, B\) 填充一个 \(2 \times n\) 的矩阵，第一行已填好，求使得相邻两格相同的格子对数量为 \(k\) 的填的方案数

设 \(f_{i, c, j}\) 表示填了第二行的前 \(i\) 个位置，\(i\) 处的字符为 \(c \in \{ \texttt{A}, \texttt{B} \}\) （用 \(0, 1\) 表示 \(\texttt{A}, \texttt{B}\) ，填有不同字符的相邻位置是否能有 \(j\) 对

打表发现 \(\forall i \in [1, n], c \in \{ 0, 1 \}\) ，有 \(f_{i, c, 0}, f_{i, c, 1}, \cdots\) 构成的 \(01\) 串中所有 \(1\) 构成一个极长连续段或构成两个极长连续段且中间最多一个 \(0\)

令三元组 \((p, l, r)\) 表示一个状态，其中 \(p\) 为空缺位置， \(l, r\) 表示最左或最右的 \(1\) 的位置，转移即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;

struct Node {
    int p, l, r;
    
    inline bool check(int x) const {
        return l <= x && x <= r && x != p;
    }
    
    inline Node getnxt(int d) const {
        return Node{~p ? p + d : -1, l + d, r + d};
    }
} f[N][2];

int a[N], b[N];
char s[N];

int T, n, k;

inline Node merge(const Node &lhs, const Node &rhs) {
    int L = min(lhs.l, rhs.l), R = max(lhs.r, rhs.r);

    if (L <= lhs.p && lhs.p <= R && !rhs.check(lhs.p))
        return (Node) {lhs.p, L, R};
	else if (L <= rhs.p && rhs.p <= R && !lhs.check(rhs.p))
        return (Node) {rhs.p, L, R};
	else if (lhs.r + 2 == rhs.l)
        return (Node) {lhs.r + 1, L, R};
	else if (rhs.r + 2 == lhs.l)
        return (Node) {rhs.r + 1, L, R};
	else
		return (Node) {-1, L, R};
}

signed main() {
	scanf("%d", &T);

    for (; T; --T) {
    	scanf("%d%d%s", &n, &k, s + 1);
    	
    	for (int i = 1; i <= n; ++i)
	        a[i] = s[i] == 'B';
	
	    for (int i = 2; i <= n; ++i)
	        k -= a[i] != a[i - 1];
	
	    if (k < 0) {
	    	puts("NO");
	    	continue;
	    }
	
	    f[1][0] = Node{-1, 0, 0}, f[1][1] = Node{-1, 1, 1};
	
	    for (int i = 2; i <= n; ++i)
	        if (a[i - 1] == a[i]) {
	            f[i][0] = merge(f[i - 1][1].getnxt(1), f[i - 1][0]);
	            f[i][1] = merge(f[i - 1][0].getnxt(2), f[i - 1][1].getnxt(1));
	        } else {
	            f[i][0] = merge(f[i - 1][0].getnxt(1), f[i - 1][1]);
	            f[i][1] = merge(f[i - 1][1].getnxt(2), f[i - 1][0].getnxt(1));
	        }
	
	    int p = k, cnt;
	
	    if (f[n][0].check(k))
	        cnt = 0;
	    else if (f[n][1].check(k))
	        cnt = 1;
	    else {
	    	puts("NO");
	    	continue;
	    }
	
	    for (int i = n; i; --i) {
	        b[i] = a[i] ^ cnt;
	
	        if (i > 1)
		        if (a[i - 1] == a[i]) {
		            if (cnt) {
		                if (f[i - 1][0].check(p - 2))
		                    p -= 2, cnt = 0;
		                else
		                    --p;
		            } else {
		                if (f[i - 1][1].check(p - 1))
		                    --p, cnt = 1;
		            }
		        } else {
		            if (cnt) {
		                if (f[i - 1][1].check(p - 2))
		                    p -= 2;
		                else
		                    --p, cnt = 0;
		            } else {
		                if (f[i - 1][0].check(p - 1))
		                    --p;
		                else
		                    cnt = 1;
		            }
		        }
	    }
	    
    	puts("YES");

	    for (int i = 1; i <= n; ++i)
	        putchar(b[i] ? 'B' : 'A');
	
	    puts("");
    }

    return 0;
}

标签：const,int,1853,else,return,--,887,Div,check
From： https://www.cnblogs.com/hcawa/p/17599727.html

相关文章

  • 1851 Round 888 (Div. 3)
    EscalatorConversations判断两人台阶是否为\(k\)的倍数且在\((0,m)\)内即可#include<bits/stdc++.h>usingnamespacestd;signedmain(){ intT; scanf("%d",&T); for(intn,m,k,H;T;--T){ scanf("%d%d%d%d",&n,&m,&a......
  • 1848 Round 885 (Div. 2)
    VikaandHerFriends给定一张网格图，Vika在\((x,y)\)处，她的\(k\)个朋友分别在\((x_{1\simk},y_{1\simk})\)处，每次所有人都必须移动到相邻各格子，询问Vika能否永远逃离她烦人的朋友考虑对格子进行黑白染色，每次移动一定会变换格子颜色，那么只有相同颜色的人才会碰......
  • 1855 Round 889 (Div. 2)
    DaltontheTeacher给定序列\(a_{1\simn}\)，定义一次操作为交换序列中的某两个数，求使得\(\foralli,a_i\not=i\)的最少操作次数对于所有数据，\(n\leq10^5\)计算出\(a_i=i\)的位置数量\(sum\)，若\(sum\)为偶数，则让其两两配对交换即可；否则会剩下一个数，在其他......
  • Educational Codeforces Round 152 (Rated for Div. 2)
    Preface经典秒完SB题然后开始坐牢1h，写了个E的假算法T在24个点就不管了打lol去了妈的怎么稍微难点的题就是想不到呢A.MorningSandwich签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>......
  • Codeforces Round 889 (Div. 2)
    CodeforcesRound889(Div.2)T1​ 思路：我们将\(i\nep_i\)的数量记下来，再判断这个数的奇偶性，如果为偶，那么答案就为这个数/2，如果为奇，那么就是这个数/2+1。T2​ 思路：我们枚举\(1\simn\)，我们记录连续是\(n\)的因数的个数，如果不连续了就\(break\)，答案就是个数......
  • Codeforces Round 885 (Div. 2)
    CodeforcesRound885(Div.2)A.VikaandHerFriends题目大意太长了click思路可以手动模拟一下，可以发现当两个人的\(x+y\)值就行相同的就能抓到了#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;cin>>T;while(T--){......
  • Codeforces Round 887 (Div. 2)
    CodeforcesRound887(Div.2)A.Desorting题目大意给出一个长度为\(n\)的数组\(a\),可以执行这个操作任意次。选择一下标\(i\),使得\(a_{1...i}\)加上\(1\)，\(a_{i+1...n}\)减少\(1\)。问最少几次操作使得数组\(a\)无序。思路首先如果\(a\)原本就无序的......
  • Codeforces Round 885 (Div. 2) 题解
    A.VikaandHerFriends看一下样例就可以发现，Vika以及她的朋友都不能走对角线，在这种情况下Vika和朋友的距离为偶数，且朋友一定追不上Vika所以直接判断Vika和朋友的距离是否都为偶数即可B.VikaandtheBridge显然贪心，枚举颜色，找到相邻距离最大的两块木板，记该距离为\(......
  • Codeforces Round 887 (Div. 2) 题解
    A.Desorting题目的核心操作就是选定一个位置\(i\)，使得：对于所有\(j\lei\)，\(a_j\leftarrowa_j+1\)对于所有\(j>i\)，\(a_j\leftarrowa_j-1\)这样一来，操作后\(a_{i+1}-a_i\)的值就会\(-2\)因为\(a_{i+1}-a_i<0\)时，也意味着\(a_i>a_{i+1}\)，所以就达到了要求那么题......
  • Educational Codeforces Round 152 (Rated for Div. 2) D. Array Painting
    初始所有点都是蓝色的，给定一个数组，每个元素为0，1，2等值，两种操作，选定一个点花1元变红，或者选定一个为1或者2的红色点，减去一个价值，让周围的点变红，最后所有点都要变红思路：贪心，对于一个数组来说我们找寻连续的不等于0的一段，判断每一段最多所能变红的存在两种情况010，这种情况花1可以最......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99