首页 > 其他分享 >ABC266总结

ABC266总结

时间：2022-08-27 22:44:36浏览次数：176  
标签：总结 ch Contest int ABC266 Limit dp getchar

比赛情况

AC：6 / 8
排名：830

题目分析

A（语法）

直接输出 \(s_{n/2+1}\) 即可

点击查看代码 
// Problem: A - Middle  Letter
// Contest: AtCoder - AtCoder Beginner Contest 266
// URL: https://atcoder.jp/contests/abc266/tasks/abc266_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
//#define M
//#define mo
//#define N
int n, m, i, j, k, T; 
char s[1000010]; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
//	T=read(); 
//	while(T--) {
//		
//	}
	scanf("%s", s+1); n=strlen(s+1); 
	printf("%c", s[n/2+1]); 
	return 0; 
}

B（简单数论）

\(n-x\) 为 \(998244353\) 倍数，即 \(n-x\equiv 0\pmod {998244353}\)移项得 \(n\equiv x\pmod {998344353}\)，所以 \(x\) 是 \(n\) 模 \(998244353\) 的余数

点击查看代码 
// Problem: B - Modulo Number
// Contest: AtCoder - AtCoder Beginner Contest 266
// URL: https://atcoder.jp/contests/abc266/tasks/abc266_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
//#define M
#define mo 998244353
//#define N
int n, m, i, j, k, T; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
//	T=read(); 
//	while(T--) {
//		
//	}
	n=read(); 
	printf("%lld", (n%mo+mo)%mo); 
	return 0; 
}

C（平面几何）

如果一个四边形是凸四边形，则必然存在一个点在另外三个点组成的三角形中

判断一个点是否在一个三角形中，只需要判断这个点和三角形三边组成的三角形面积之和是否等于大三角形面积之和，如下图

image

关于坐标系中三角形面积求法，见这里

点击查看代码 
// Problem: C - Convex Quadrilateral
// Contest: AtCoder - AtCoder Beginner Contest 266
// URL: https://atcoder.jp/contests/abc266/tasks/abc266_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
//#define M
//#define mo
//#define N
struct node
{
	int x, y; 
}A, B, C, D; 
int n, m, i, j, k, T; 

int S(node A, node B, node C)
{
	return abs((B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y)); 
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
//	T=read(); 
//	while(T--) {
//		
//	}
	A.x=read(); A.y=read(); 
	B.x=read(); B.y=read(); 
	C.x=read(); C.y=read(); 
	D.x=read(); D.y=read(); 
	if(S(A, B, C)==S(A, B, D)+S(A, C, D)+S(C, B, D)) return printf("No"), 0; 
	if(S(A, B, D)==S(A, B, C)+S(A, C, D)+S(C, B, D)) return printf("No"), 0; 
	if(S(A, C, D)==S(A, B, D)+S(A, B, C)+S(C, B, D)) return printf("No"), 0; 
	if(S(D, B, C)==S(A, B, D)+S(A, C, D)+S(C, B, A)) return printf("No"), 0; 
	printf("Yes"); 
	return 0; 
}

D（基础DP）

显然dp，设 \(dp(i,j)\) 为 \(i\) 时刻在坐标 \(j\) 的最大价值

显然因为可以从左右走过来或者不懂，所以 \(dp(i,j)=\max(dp(i-1, j-1), dp(i-1, j), dp(i-1, j+1))\)

当 \(i=t\) 时，\(dp(i,x)+=a\)

初始值所有为无穷小，且 \(dp(0,0)=0\)

代码中默认坐标+1

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

点击查看代码 
// Problem: D - Snuke Panic (1D)
// Contest: AtCoder - AtCoder Beginner Contest 266
// URL: https://atcoder.jp/contests/abc266/tasks/abc266_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
//#define M
//#define mo
#define N 100010
int n, m, i, j, k, T; 
int dp[N][10], a, t, x; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
//	T=read(); 
//	while(T--) {
//		
//	}
	memset(dp, 0x80, sizeof(dp)); 
	dp[0][1]=0;  
	n=read(); 	
	for(i=k=1; i<=n; ++i)
	{
		t=read(); x=read()+1; a=read(); 
		while(k<=t)
		{
			for(j=1; j<=5; ++j)
				dp[k][j]=max(dp[k-1][j], max(dp[k-1][j-1], dp[k-1][j+1])); 
			++k; 
		}
		dp[t][x]+=a; 
	}
	
	for(i=1; i<=5; ++i) m=max(m, dp[t][i]); 
	printf("%lld\n", m); 
	return 0; 
}

E（期望DP）

设 \(f(i)\) 代表后 \(i\) 轮的最大期望。

考虑当前骰到 \(j\)，该不该继续呢？

如果 \(j>dp(i+1)\)，说明继续骰期望更小，不继续，否则继续

于是可以推出式子，\(dp(i)=\sum_{j=1}^6\frac{\max(j,dp(i+1))}{6}\)

时间复杂度 \(O(1)\)

点击查看代码 
// Problem: E - Throwing the Die
// Contest: AtCoder - AtCoder Beginner Contest 266
// URL: https://atcoder.jp/contests/abc266/tasks/abc266_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
//#define M
//#define mo
#define N 110
int n, m, i, j, k, T; 
double dp[N]; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
//	T=read(); 
//	while(T--) {
//		
//	}
	n=read(); 
	for(i=n; i>=1; --i)
	{
		for(j=1; j<=6; ++j)
		{
			if(j>=dp[i+1]) dp[i]+=(double)j/6; 
			else dp[i]+=dp[i+1]/6; 
		}
	}
	printf("%.9lf", dp[1]); 
	return 0; 
}

F（环套树）

题目给定的图本质上是一个树加一条边，也就是环套树，如下图所示

image

显然，两点之间的路径如果经过环则路径不唯一，因此只需要判断两点之间是否在环上即可

此处讲述一下作者复杂的实现方法：

  1. 利用并查集找出多余的那条边，\(O(n\log n)\)
  2. 去掉此边dfs一遍，求出每个点的父亲节点，\(O(n)\)
  3. 暴力往上跳求出刚刚那条边连接两点的lca，\(O(n)\)
  4. 标记这两点到lca的所有点，\(O(n)\)
  5. 用标记的点分别dfs，不经过环上路径，\(O(n)\)
  6. 每次dfs过程中分别用并查集合并，\(O(n\log n)\)
  7. 回答询问，两点在同一并查集里则方案唯一，\(O(q)\)

总复杂度 \(O(n\log n)\)

点击查看代码 
// Problem: F - Well-defined Path Queries on a Namori
// Contest: AtCoder - AtCoder Beginner Contest 266
// URL: https://atcoder.jp/contests/abc266/tasks/abc266_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
//#define M
//#define mo
#define N 5000010
struct node
{
	int x, y, n, id; 
}d[N<<1]; 
int n, m, i, j, k, T; 
int u[N], v[N], rx, ry, f[N], F[N]; 
int x, y, c[N], q, b[N], h[N]; 

void cun(int x, int y)
{
	d[++k].x=x; d[k].y=y; d[k].id=i;  
	d[k].n=h[x]; h[x]=k; 
}

int fa(int x)
{
	if(x==f[x]) return x; 
	return f[x]=fa(f[x]); 
}

void dfs(int x, int fa)
{
	F[x]=fa; 
	int g, y; 
	for(g=h[x]; g; g=d[g].n)
	{
		y=d[g].y; 
		if(y==fa) continue; 
		if(d[g].id==i) continue; 
		dfs(y, x); 
	}
}

void DFS(int x)
{
	int g, y, rx, ry; 
	for(g=h[x]; g; g=d[g].n)
	{
		y=d[g].y; 
		if(c[y]) continue; 
		// if(d[g].id==i) continue; 
		c[y]=1; 
		rx=fa(x); ry=fa(y); 
		f[rx]=ry; DFS(y); 
	}
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
//	T=read(); 
//	while(T--) {
//		
//	}
	n=read(); 
	for(i=1; i<=n; ++i) 
	{
		u[i]=read(); v[i]=read();  
		cun(u[i], v[i]); cun(v[i], u[i]); 
		f[i]=i; 
	}
	for(i=1; i<=n; ++i) 
	{
		rx=fa(u[i]); ry=fa(v[i]); 
		if(rx==ry) break; 
		else f[rx]=ry; 
	}
	dfs(1, 0); 
	x=u[i]; y=v[i]; 
	while(x) b[x]=1, x=F[x]; 
	while(!b[y]) y=F[y]; 
	c[y]=1; 
	x=u[i]; y=v[i]; 
	while(!c[x]) c[x]=1, x=F[x]; 
	while(!c[y]) c[y]=1, y=F[y]; 
	for(i=1; i<=n; ++i) f[i]=i; 
	for(i=1; i<=n; ++i) 
		if(c[i]) DFS(i); 
	q=read(); 
	while(q--)
	{
		x=read(); y=read(); 
		rx=fa(x); ry=fa(y); 
		printf(rx==ry ? "Yes\n" : "No\n");  
	}
	return 0; 
}

赛后总结

惊险AC6题

开题前先去Acwing那边玩了一玩，结果罚时一大堆，rp--

开局AB很顺利，然后C卡住了，不知道怎么判凸多边形

纸上推了10分钟，推不出，上网查资料，千篇一律是三角函数，不会

终于找到一种方法，然后wa了，检查发现某个地方打错A了，卡了半小时

D一眼题，初始化那里调了一下，10分钟内过

E题看一眼就期望，随便推了小式子，5分钟内过

F题看完题后发现 \(n\) 条边，显然环套树，然后推了推性质，代码有点长，提交后挂了

然后最后5分钟随手一拼，再交一次，A了

赛后发现是某个dfs用了全局变量，但全局变量一直在改变

终于上Cray了

晚上没力打cf了，30号看看有没有时间吧（就算有也div.4 unrated啊，呜呜）

下个月2号看看有没有时间吧

ATC正常发挥的话9月中旬能打上1300

标签：总结,ch,Contest,int,ABC266,Limit,dp,getchar
From： https://www.cnblogs.com/zhangtingxi/p/16631668.html

相关文章

  • 算法总结
    1.二叉树的右侧视图给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。题解：根之前二叉树解题类似，用广度优先搜索或......
  • 每周总结（22/8/27）
    HBase定义HBase是一种分布式、可扩展、支持海量数据存储的NoSQL数据库。1.2HBase数据模型逻辑上，HBase的数据模型同关系型数据库很类似，数据存储在一张表中，有行有列......
  • 5 - 自动化测试常见面试题总结
    一、测试时接口调不通，如何去排查1、接口没有任何响应很多时候在做接口测试时，会发现接口没有任何返回，比如浏览器一直在转圈，或者返回一个空白页面。用接口工具测试时，工具......
  • 「闲话」NOI2022 考试总结
    NOI2022考试总结Day1Day1前一晚的感觉就不太好。考前又兴奋跃跃欲试，又有点紧张，完全控制不住自己的脑子。晚上睡觉的时候，呆在被子里面莫名燥热，又不敢随便掀开怕感冒，......
  • 常见性能优化实践总结
    常见性能优化实践总结一：代码这一点最容易引起技术人员的忽视。很多技术人员拿到一个性能优化的需求以后，言必称缓存、异步、JVM等。有一些性能问题，完全是由于代码写的不合......
  • 总结
    l1=[23,33,65,'barry']l1.pop()print(l1)#默认删除最后一个remove按照元素删除clear清空del索引，切片（步长）查：索引，切片，for循环元组：只读列表（）拆包range:自己控制范围......
  • 物体碰撞与摩擦的方法总结
    本文禁止转载B站：Heskey0ContactandFrictionSimulationforComputerGraphics(Siggraphcourse2022)相关的course：SIGGRAPH'20Course:AnIntroductiontoPhysics......
  • 打了一场模拟赛的心态，总结
       今天打了一场模拟赛总结一下：题目比较简单（我后面一个题目100一个90都是暴力的功/dogen）Frist problem：   总结：一道伪装成5⭐的打卡题目用时：2~3min思路：每......
  • AMBA　AHB总结
    AMBAAHB（高级高性能总线）介绍一、AHB简介AHB是为提出高性能可综合设计的要求而产生的新一代AMBA总线。它是一种支持多总线主机和提供高带宽操作的高性能总线。AMBAAHB......
  • 【pytest】Hook钩子函数完整API总结
    pytest的钩子函数有很多，通过钩子函数的学习可以了解到pytest在执行用例的每个阶段做什么事情，也方便后续对pytest二次开发学习。详细文档可以查看pytest官方文档https://d......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99