首页 > 其他分享 >【题解】CF1710 合集

【题解】CF1710 合集

时间：2023-10-23 21:02:30浏览次数：37  
标签：NN int 题解 over ans oplus 合集 ll CF1710

CF1710A Color the Picture

标签：思维题 \(C^-\)

典型的有图有真相，嘻嘻（抽风了？

显然有一个结论，我们颜色要么一行一行天，要么一列一列填。

并且填进去的颜色必须不少于两行/列

然后就是记一个 ans 和 一个 over 表示如果每个颜色都两行/列填进去能填的最多列数，以及两行/列填进去后还能填多少行/列

最后就按行/列填进去判断一下即可

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 1e5 + 8;
int T;
int n,m,k;
int a[NN];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		ll ans = 0,over = 0;
		for(int i = 1; i <= k; ++i){
			scanf("%d",&a[i]);
			ans += a[i] / n >= 2 ? 2 : 0;
			over += a[i] / n >= 2 ? (a[i]/n-2) : 0;
		}
		if(ans == m){puts("Yes");continue;}
		if(ans >= m && ((ans&1) == (m&1))){puts("Yes");continue;}
		if(ans + over >= m && over){puts("Yes");continue;}
		
		ans = 0;over = 0;
		for(int i = 1; i <= k; ++i){
			ans += a[i] / m >= 2 ? 2 : 0;
			over += a[i] / m >= 2 ? (a[i]/m-2) : 0;
		}
		if(ans == n){puts("Yes");continue;}
		if(ans >= n && ((ans&1) == (n&1))){puts("Yes");continue;}
		if(ans + over >= n && over){puts("Yes");continue;}
		puts("No");
	}
}

CF1710B Rain

标签：DS \(C\) | 思维题 \(C^+\)

考虑我的方法是预处理 \(O(n\log n)\)，最后求答案 \(O(n)\) 的

考虑我们显然可以先从左到右扫一遍，对于每一个 \(x_i\) 记录它左边的下雨对于它的雨水的深度产生的影响

然后这显然是很好维护的，就是记录当前点的水的深度影响和影响当前点的下雨天的数量，用数学语言表示就是记录当前点的点值和斜率

然后我们需要用一个小根堆记录最近的和 \(x\) 轴的交点，方便将直线退出影响，然后 \(x_i\) 的右边的下雨的影响也可以类比

最后求答案，显然可以找出所有的需要减去的位置和高度，显然我们可以将位置为 \(x\) 高度为 \(h\) 的需求抽象成 \([x-h,x+h]\) 的区间

最后就是判断去掉某一天的下雨的对应的区间能否包含所有区间，这就是维护所有需求区间的最左边和最右边 \(O(n)\) 扫一遍，然后就可以对每个询问 \(O(1)\) 求解了。

考虑代码里面后面的需求区间的最左端点和最右端点的求解有一点麻烦，希望能看懂 QWQ。

code:

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

int n,m;
struct Rep{
	ll x,p;
	int num;
	bool operator < (const Rep &A)const{
		return x < A.x;
	}
}a[NN],b[NN];
int top;

priority_queue<ll,vector<ll>,greater<ll> > Q; 
priority_queue<ll> R;

bool ans[NN];
bool res[NN];
ll f[NN];

void solve(){
	memset(f,0,sizeof(f));top = 0;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; ++i)
		scanf("%lld%lld",&a[i].x,&a[i].p),a[i].num = i,ans[i] = 1;
	
	sort(a+1,a+1+n);
	
	ll now = 0,cnt = 0;
	while(!Q.empty())Q.pop();
	for(int i = 1; i <= n; ++i){
		while(!Q.empty() && Q.top() <= a[i].x){
			now -= Q.top() - a[i-1].x;
			--cnt;
			Q.pop();
		}
		if(i != 1) now -= (a[i].x - a[i-1].x) * cnt;
		++cnt;
		now += a[i].p;
		Q.push(a[i].x+a[i].p);
		f[i] += now;
	}
	while(!R.empty())R.pop();
	now = 0,cnt = 0;
	for(int i = n; i >= 1; --i){
		while(!R.empty() && R.top() >= a[i].x){
			now -= a[i+1].x - R.top();
			--cnt;
			R.pop();
		}
		if(i != n) now -= (a[i+1].x - a[i].x) * cnt;
		f[i] += now;
		++cnt;
		now += a[i].p;
		R.push(a[i].x-a[i].p);
	}
//	for(int i = 1; i <= n; ++i){
//		printf("%lld:%lld\n",a[i].x,f[i]);
//	}
//	puts("====================/");
	
	for(int i = 1; i <= n; ++i){
		if(f[i] > m){
			b[++top] = {a[i].x,f[i]-m};
		}
	}
	
	ll lmin = 1e18;
	for(int i = 1,j = 1; i <= n; ++i){
		while(j <= top && b[j].x <= a[i].x) lmin = min(lmin,b[j].x-b[j].p), ++j;
		if(lmin < a[i].x - a[i].p) ans[i] = 0;
	}
	ll rmax = -1e18;
	for(int i = n, j = top; i >= 1; --i){
		while(j >= 1 && b[j].x >= a[i].x) rmax = max(rmax,b[j].x + b[j].p),--j;
		if(rmax > a[i].x + a[i].p) ans[i] = 0;
	}
	for(int i = 1; i <= n; ++i){
		res[a[i].num] = ans[i];
	}
	for(int i = 1; i <= n; ++i)  printf("%d",res[i]);
	puts("");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		solve();
	}
}

CF1710C XOR Triangle

标签：DP \(C^+\) | 数学 \(C\)

我们显然可以想到异或的性质：

  • \(a + b \geq a \oplus b\)

  • \(a + b > a \oplus b\) 当且仅当 \(a,b\) 有交集（\(a|b \neq 0\)）

我们应用到这一道题目上就是:

  • 若满足 \((a\oplus b) + (b \oplus c) \geq (a \oplus c)\) 当且仅当 \((a\oplus b)\) 与 \((b \oplus c)\) 有交

又因为我们的限制是对 \(a,b,c\) 的，而不是对 \(a\oplus b,b\oplus c,c\oplus a\) 的，所以说我们显然 数位DP 是枚举 \(a,b,c\)

我们设 \(f_{i,j,k}\) 表示前 \(i\) 位，\(j(0\sim 7)\) 表示三种亦或值相互之间有没有交，\(k(0\sim 7)\) 表示有没有顶上限(显然不同于普通的 数位DP 这里要枚举有没有顶上限，不然复杂度是假的)

转移很显然，直接记忆化搜索即可

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 2e5 + 8, MOD = 998244353;

int f[NN][8][8];
string s;
int a[NN];
inline int Calc(int i,int j,int k){
	return ((i^j) & (j^k)) + (((i^k) & (j^k)) << 1) + (((i^j) & (i^k)) << 2);
}
inline int Calc2(int x,int i,int j,int k){
	return (a[x] == i) + ((a[x] == j) << 1) + ((a[x] == k) << 2);
}

ll dfs(int x,int now,int up){
	if(x == s.size()) return now == 7;
	if(f[x][now][up] != -1) return f[x][now][up];
	int ua = (up&1) ? a[x]:1, ub = (up>>1&1)?a[x]:1, uc = (up>>2&1)?a[x]:1;
	ll ans = 0;
	for(int i = 0; i <= ua; ++i){
		for(int j = 0; j <= ub; ++j){
			for(int k = 0; k <= uc; ++k){
				ans = (ans + dfs(x+1,now | Calc(i,j,k),up & Calc2(x,i,j,k))) % MOD;
			}
		}
	}
	return f[x][now][up] = ans;
}
void solve(){
	memset(f,-1,sizeof(f));
	s = ' ' + s;
	for(int i = 1; i < s.size(); ++i) a[i] = s[i] - '0';
	printf("%lld\n",dfs(1,0,7));
}
int main(){
	cin >> s;
	solve();
}

CF1710D Recover the Tree

标签：思维题 \(B\) | 图论 \(B^-\)

一道比较好的构造题目，我们先需要从小到大去对区间排序，然后就是我们会发现

如果对于一个区间 \([l,r]\)，\(l,r\) 分别在两个连通块区间之内，然后中间有 \(k\) 个连通块，我们的构造方案需要满足两个相邻的连通块之间不能直接相连（\(l,r\) 所在连通块可以直接相连，即使相邻）

所以当 \(k = 1\) 时，显然是无解的。

所以我们让 \(l\) 连向 \(r\) 左边的第一个连通块中的任意位置，\(r\) 连向剩下的其他 \(k - 1\) 个连通块即可

至于连通块的维护？？？并查集即可

#include<bits/stdc++.h>
using namespace std;
const int NN = 2e3 + 8;

char s[NN][NN];
int fa[NN];

void solve(){
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 1; i <= n; ++i) scanf("%s",s[i]+i);
	for(int i = 1; i <= n; ++i){
		for(int j = i-1; j >= 1; --j)if(s[j][i] == '1' && fa[i] > j){
			printf("%d %d\n", j, i);
			if(fa[fa[i] - 1] > j)
			{
				printf("%d %d\n", j, fa[i] - 1);
				for(int k = fa[fa[i] - 1] - 1; k > j; --k) if(fa[k] == k) printf("%d %d\n",k,i);
			}
			for(int k = j; k <= i; ++k) fa[k] = fa[j];
		}
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		solve();
	}
}

标签：NN,int,题解,over,ans,oplus,合集,ll,CF1710
From： https://www.cnblogs.com/rickylin/p/CF1710.html

相关文章

  • Educational Codeforces Round 144（CF1796 D~E） 题解
    D.MaximumSubarray题目链接十分钟秒了一道*2000，非常爽，但是个人感觉确实非常简单。下面令\(b_i=a_{i}-x\)，\(b_i'=a_i+x\)。因为\(k<=20\)，因此考虑一个复杂度与\(k\)相关的做法。不妨dp：设\(f_{i,j,0/1}\)表示考虑了前\(i\)个数，对\(j\)个数加上了\(x\)，第\(i\)......
  • CF1893E题解
    分析第一眼：博弈论。第二眼：呃……贪心？实际：DP。首先想这个游戏大抵存在必胜策略，否则不会让我们求。思考先手必胜条件，就是如何让这个数组最后只剩下一个数。设数列之和为\(sum\)。发现每次操作给两个数减的数字是一样的。那么对于每次操作，\(\Deltasum\)都为两者之间更少的......
  • CSP-S 2023 种树-题解
    CSP-S2023种树-题解闲话Mark.Down看错题面了，我一直以为树是倒着长的。题目描述给定一棵树，每天可以选择一个与已种树的地块相连的地块种树，每棵树每天会长\(max(1,c_i\timesx+b_i)\)米（\(x\)代表从任务开始第一天的天数），问最少多少天可以使\(\foralli\inn,Height_i\gea_i\)......
  • P8820（csp-s 2022 T4）题解
    背景：由于FZ考试因疫情取消，于是我们学校组织了线上测试。赛场连假做法都没打完，然后暴力忘记交了。。。题目链接参考博客题目评价：场切有点困难，但是76分比较容易。解法一眼\(ddp\)，没话说。下面假设树以\(1\)为根。一次传输称作从一个点跳到另一个点。设询问的两个点为\(......
  • 模拟赛总结合集
    20231023:NOIP2023-div2模拟赛24A.公园题意给一个无向图\(G=(V,E)\),求一个\(X\),使得\(D\timesX+\sum\limits_{e\inG,dist(1,e.u)>Xordist(1,e.v)>X}cost(e)\)最小,求最小值赛时思路非常的简单啊算法概述处理出一号点到所有点的最短路,按最短路从大到小排序依......
  • 题解合集
    CF1846:CF1846ACF1846BCF1846CCF1846DCF1846E......
  • CF1839D题解
    分析啊这道题就做得很难受了……手玩一下样例，不难发现答案就是分出\(k\)段不是单调上升序列的序列，求这些序列的最小长度和。显然有状态\(f_{l,r,k}\)表示\([l,r]\)序列分成\(k\)段的最小长度和。转移很好想，即枚举\(x\)，\(y\)分别表示左区间的右端点以及段数，空间复杂度\(\math......
  • 题解：【CF1888E】 Time Travel
    题目链接刚从modinte那里学到的广义dijkstra。注意到一定不会有路径形如\(x\toy\tox\)，这样等价于\(x\)在原地等上两个时刻，我们记\(d_i\)表示到达\(i\)节点需要的最少时间。建图，边权为当前这一条边在哪一个历史时刻。然后用一个set来存下每个历史时刻在第几次时间......
  • CSP-S 2023 消消乐-题解
    CSP-S2023消消乐-题解闲话省流：longlong模拟pair好抽象的题，可惜考场上没做出来。感觉其实是一个挺有趣的题的。题目描述小L现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两个相邻的元素。现在，他有一个长度为\(n\)且仅由小写字母构成的字符串。我......
  • CF1839A题解
    分析可以很容易地想到如果只有1要求的话答案就是\(\lceil\frac{n}{k}\rceil\)。最优策略显然是在每个整除分块的第一位放一个1。思考加入2条件如何修改。显然当最后一块的大小不为1时，大于1的部分后缀和为0。所以需要在最后一位加入一个1。所以答案为\(\begin{cases}\lc......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99