首页 > 其他分享 >Atcoder-Beginner-Contest-312 A~Ex

Atcoder-Beginner-Contest-312 A~Ex

时间:2023-07-30 12:55:47浏览次数:50  
标签:Atcoder Contest int 312 bound mid 括号 Ex text

\(Atcoder-Beginner-Contest-312\)

AB过于简单,在此略去。

\(C-Invisible\) \(Hand\)

题意:给定长为 \(n\) 的数组 \(a\),长为 \(m\) 的数组 \(b\),找到最小的非负整数 \(x\),使得 \(\sum_{i=1}^n[a_i\le x]\ge \sum_{i=1}^m[b_i\ge x]\)

题解:

容易发现,随着 \(x\) 的增大,右式单调不升,左式单调不降,故答案具有单调性。

将两数组排序,二分答案。可以使用 lower_boundupper_bound 快速统计出左右两式。

sort(a+1,a+n+1);sort(b+1,b+m+1);
	int l=0,r=0x3f3f3f3f;
	while(l<r){
		int mid=l+r>>1;
		int x=upper_bound(a+1,a+n+1,mid)-a-1;
		int y=lower_bound(b+1,b+m+1,mid)-b;
		y=m+1-y;
		if(x>=y)r=mid;
		else l=mid+1;
	}
	cout<<l<<"\n";

\(D-Count\) \(Bracket\) \(Sequences\)

题意:给定一个残缺的由 \(\text{(,?,)}\) 构成的括号序列 \(s\),有若干位置不确定,要求将其补全为完整的括号序列,求方案数,\(n\le 3000\)。

合法括号序列的充要条件是在任意前缀中左括号数量不小于右括号数量,且左括号总数量等于右括号总数量

复杂度要求 \(O(n^2)\),显然是动态规划。

考虑设 \(f_{i,j}\) 表示前 \(i\) 个符号里,左括号数量减去右括号数量为 \(j\) 的方案数。

初始化:\(f_{0,0}=1\)

目标:\(f_{n,0}\)

转移:

\[f_{i,j}= \begin{cases} f_{i-1,j-1} & s_i=\text{(}\\ f_{i-1,j+1} & s_i=\text{)}\\ f_{i-1,j-1}+f_{i-1,j+1} & s_i=\text{?} \end{cases} \]

注意边界。

    f[0][0]=1;
	for(int i=1;i<=n;i++){
		if(a[i]=='(') for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1];
		else if(a[i]==')') for(int j=0;j<n;j++)f[i][j]=f[i-1][j+1];
		else for(int j=1;j<=n;j++)f[i][j]=(f[i-1][j+1]+f[i-1][j-1])%p;
	}
	cout<<f[n][0]<<"\n";

\(E-Tangency\) \(of\) \(Cuboids\)

\(F-Cans\) \(and\) \(Openers\)

\(G-Avoid-Straight-Line\)

\(Ex-snukesnuke\)

\(Trick\) 总结

标签:Atcoder,Contest,int,312,bound,mid,括号,Ex,text
From: https://www.cnblogs.com/oierpyt/p/17591294.html

相关文章

  • abc312e <暴力>
    题目E-TangencyofCuboids思路意识到本题的数据规模可以暴力去做!\(N=100\),\(N^3\)直接遍历整个空间可做;立方体间不相交,也就是可以直接遍历立方体中的所有点进行标记,不会超过整体空间体积;立方体不相交,也就是说同一个位置尽可能被标记一次;将空间中每个立方体所占点进行标......
  • abc312d <dp, 括号匹配方案数>
    题目D-CountBracketSequences思路dp[i][j]为考虑前\(i\)个位置,待匹配的(有\(j\)个的方案数;代码点击查看代码#include<iostream>#include<algorithm>#include<vector>#include<cstring>usingnamespacestd;usingLL=longlong;usingPII=pair<......
  • HDU 1312 Red and Black 题解
    //注意边界判断,调了好久#include<iostream>#include<queue>usingnamespacestd;#definecheck(x,y)(x<wx&&x>=0&&y<hy&&y>=0)structnode{intx,y;};charroom[23][23];intn,m,wx,hy,num;intdir[4][2]={......
  • abc312c <二分答案>
    题目C-InvisibleHand思路二分X,同时二分得到buyer和seller的人数(很精巧的二分~);当然,从复杂度角度,\(O(N\logN)\)也是可以的;实际上可以写成\(O(N)\)的形式?感觉线性扫描也可?代码点击查看代码#include<iostream>#include<algorithm>#include<vector>#include<cst......
  • ABC312
    T1:Chord模拟代码实现s=input()ifsin'ACE,BDF,CEG,DFA,EGB,FAC,GBD':print('Yes')else:print('No')T2:TaKCode模拟代码实现#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<(n);++i)using......
  • 【PY】pandas 处理 Excel 中错别字修正
    前言今天有友友问起来,如何对Excel进行操作,对里面的内容进行错别字修正,那接下来由博主来为各位读者细细讲解一番;首先想到的是用xlrd去读取Excel里面的内容,不过呢,最新版的xlrd已经不支持.xlsx了,使用xlrd读取.xlsx文件时,会报错:XLRDError:Excelxlsxfile;notsupporte......
  • latex算法取消endfor输入
    一、方法使用以下的包取消enfor,endif等输出,使算法更加的整洁。\usepackage[noend]{algorithmic}二、结果展示直接使用algorithmic使用后三、参考网址tex问答网站......
  • EasyExcel使用
    Java解析、生成Excel比较有名的框架有Apachepoi、jxl。但他们都存在一个严重的问题就是非常的耗内存,poi有一套SAX模式的API可以一定程度的解决一些内存溢出的问题,但POI还是有一些缺陷,比如07版Excel解压缩以及解压后存储都是在内存中完成的,内存消耗依然很大。easyexcel重写了poi对......
  • (AtCoder Beginner Contest 312)
    (AtCoderBeginnerContest312)A-Chord#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128typedefpair<int,int>PII;typedefpair<string,int>PSI;typedefpair<string,string>PSS;constintN......
  • C++中的exec()函数
    exec()函数在C++中是一个进程控制函数,用于创建新进程执行其他程序或命令行指令。exec()函数可以替换当前进程的代码和数据,创建新的进程运行其他程序。exec()函数有多个版本,例如execl、execv、execle、execve等,根据不同的参数类型和个数来使用。前言fork函数之后,如果想要把子进程换......