技术标签: CF ACM算法日常 Educational67 ACM 二次换根法 Codeforce
ACM题集:https://blog.csdn.net/weixin_39778570/article/details/83187443
题目链接:https://codeforces.com/contest/1187
题意: 有n个蛋,蛋里放着物品A,或者物品B,或者物品A和B,A有s个,B有t个,问至少拿多少个蛋才能拿到A和B。
解法:模拟~画一条线,长度为n,A从左边开始,B从右边开始,中间是重叠部分,左右两边是不重叠部分,取大的一边,再加一就是答案了…
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
int T;
int main(){
cin>>T;
while(T--){
ll n,s,t;
cin>>n>>s>>t;
ll ans = max(n-s,n-t)+1;
cout<<ans<<endl;
}
return 0;
}
题意:有一个字符串s,有N个字符串t,问要包含字符串t的所有字母,至少去字符串s的前缀多长。
解法:统计字符串s的信息,cnt[‘a’][x]=num:表示a出现x次在位置num.如cnt[‘a’][1000]=1005表示a的第1000次 出现在位置1005
对于每个t,统计它的字母出现的次数。然后根据这些次数在cnt里面查找答案。
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=2e5+5;
int n,m,cnt[33][N],cnt1[33],cnt2[33];
char s[N],t[N];
void init(){
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1; i<=n; i++){
cnt[s[i]-'a'][++cnt1[s[i]-'a']]=i; // s[i]出现cnt1次在位置i
}
}
int main(){
init();
scanf("%d",&m);
while(m--){
scanf("%s",t+1);
int len = strlen(t+1);
int ans = 0;
memset(cnt2,0,sizeof(cnt2));
for(int i=1; i<=len; ++i){
cnt2[t[i]-'a']++;
}
for(int i=0; i<26; i++){
ans=max(ans, cnt[i][cnt2[i]]);
}
cout<<ans<<endl;
}
return 0;
}
题目:有一个长度为n的未知数列A,这里有m条信息,包含三个信息(t,l,r)
当t=1,表示A[l,r]是上升数列
当t=0,表示A[l,r]是非上升数列,也就是这是有一对相邻的对前者大于后者
如果数列存在,输出数列,否则输出NO
解法:n比较小,只有1000。
对于t=1来说,这是必须上升的,所以我们可以先把t=1的情况处理了,把上升的位置全都标记出来s[i]=1表示A[i]<A[i-1],数据比较小,直接暴力标记了,也可以用差分,最后再一次性标记
对于t=0来说,我们只有能找到一个s[i]!=1的就行 l < = i < r l<=i<r l<=i<r,否则就无法构造数列
然后构造数列
非暴力法,就是差分之后确定了上升序列的位置后,然后构造数列
接着使用t=0的来进行验证
code略微暴力
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=1e3+5;
int n,m,s[N],ans[N];
struct node{
int t,l,r;
bool operator < (const node &p)const{
return t>p.t;
}
}a[N];
int main(){
cin>>n>>m;
fo(i,1,m){
int t,l,r;
cin>>a[i].t>>a[i].l>>a[i].r;
}
sort(a+1,a+m+1);
fo(i,1,m){
if(a[i].t==1){
for(int j=a[i].l; j<a[i].r; j++){
s[j]=1; // 上升
}
}else{
bool flag = 0;
for(int j=a[i].l; j<a[i].r; j++){
if(s[j]!=1){
// 只要有非上升就标记为下降
s[j]=2;
flag = 1;
break;
}
}
if(!flag){
cout<<"NO"<<endl;
return 0;
}
}
}
ans[1]=1005;
for(int i=2; i<=n; i++){
if(s[i-1]==2){
ans[i]=ans[i-1]-1;
} else{
ans[i]=ans[i-1]+1;
}
}
cout<<"YES"<<endl;
fo(i,1,n){
cout<<ans[i]<<" ";
}
return 0;
}
code差分优化
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=1e3+5;
int n,m,s[N],ans[N],d[N];
struct node{
int t,l,r;
bool operator < (const node &p)const{
return t>p.t;
}
}a[N];
int main(){
cin>>n>>m;
fo(i,1,m){
int t,l,r;
cin>>a[i].t>>a[i].l>>a[i].r;
}
sort(a+1,a+m+1);
fo(i,1,m){
if(a[i].t==1){
d[a[i].l] += 1;
d[a[i].r] -= 1;
}
}
fo(i,1,n){
d[i] += d[i-1];
}
// 构造答案
ans[1]=n;
for(int i=2; i<=n; i++){
if(d[i-1]>0){
ans[i]=ans[i-1]+1;
}else{
ans[i]=ans[i-1]-1;
}
}
// 检查答案
fo(i,1,m){
if(a[i].t==0){
if(ans[a[i].r]-ans[a[i].l] == a[i].r-a[i].l){
// 完全上升
cout<<"NO"<<endl;
return 0;
}
}
}
cout<<"YES"<<endl;
fo(i,1,n){
cout<<ans[i]<<" ";
}
return 0;
}
题意:有一个无向图(树),第一次选择一个点作为根,
(之后选择的点是已经选过的点的子节点)每选择一个点,对答案的贡献为树的大小
问:怎么选使得答案最大
解法:
暴力:n遍dfs统计出来(T)
优化:二次扫描和换根法
二次换根法简单介绍:先一次统计出确定了一个根的答案(由所有子节点的答案加自己的和),换根:把新根的答案(在旧根里是子儿子,在新根里它已经成为一棵树的根了)去掉,然后加上旧根的答案(旧根原来是一刻树的根,现在变成子节点了)
code
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=2e5+5,M=N*2;
int n;
int head[N],Next[M],ver[M],tot;
void add(int x, int y){
ver[++tot]=y;
Next[tot]=head[x], head[x]=tot;
}
int son[N];
ll ans;
void dfs(int x, int fa){
son[x]=1;
for(int i=head[x]; i; i=Next[i]){
int y=ver[i];
if(y==fa)continue;
dfs(y,x);
son[x]+=son[y];
}
ans+=son[x]; // 每个选择的点对答案的贡献
}
void DFS(int x, int fa, ll now){
ans = max(ans, now);
for(int i=head[x]; i; i=Next[i]){
int y = ver[i];
if(y==fa)continue;
DFS(y, x, now-son[y]+(n-son[y]));
}
}
int main(){
cin>>n;
int x,y;
fo(i,2,n){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,-1);
DFS(1,-1,ans);
cout<<ans<<endl;
return 0;
}
文章浏览阅读3.4k次,点赞5次,收藏8次。废话不多说,直接上代码代码如下:nums = [1, 3, 5, 8, 8, 9, 10, 14, 15, 19, 19, 20, 25, 28, 29, 35, 37, 44, 49]w = int(input('请输入要查找的数据:'))while True: if w in nums: print(f'{w}的下标为{nums.index(w)}') break else: print('找不到该数据') .._python编写函数,根据关键字查询列表,返回下标。
文章浏览阅读701次。题目描述:PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名_一个企鹅船新体验
文章浏览阅读1k次。LuaXml使用版本Lua 5.3写入再读取XML操作xml = require('LuaXml')local xNewFile = xml.new()-- 一级标题xNewFile[0] = "CATALOG"--[[-- 再增加一级标题写法local describ = {"Empire Burlesque"}local price = {30}local title..._lua操作xml格式文件
文章浏览阅读942次。一,开窗函数:为了解决复杂的子查询引入进来的,开窗函数也是对行集组进行聚合计算的,并且它返回是多个值,目前oracle db2 sqlserver都支持,但是mysql不支持1.row number() over partition by :分组排名SELECT ORDER_NUMBER, PRODUCT_TYPE, ROW_NUMBER() OVER ( PARTITION BY O..._listagg over partition
文章浏览阅读6.8k次,点赞35次,收藏8次。Hello!你好哇,我是灰小猿!最近在做聊天室相关项目的开发的时候,需要对文本框中的字体进行区别显示,但是由于JTextArea文本框属于纯文本形式的,无法对其中的文本进行不同格式的显示,所以这个时候就需要使用JTextPane文本域进行文本内容的显示了。其主要原因是:JTextPane文本域中可以设置html样式JTextArea文本框不可以设置html样式这就造成了JTextPane文本域中的内容可以根据需要自行设置属性,从而实现不同文字内容的颜色、字号等属性。通过以下函数可以直_java编写多线程聊天室时改变不同信息的字体颜色
文章浏览阅读3k次。Ubuntu 16.04无法登录图形界面0、分析个人猜测,这个问题,有可能是图形界面文件受损,或者没有安装图形界面,或者图形界面没有设置默认Ubuntu开机启动1、方法1:重装Ubuntu图形界面(1)、如果不知道是否安装了图形界面,可以通过下面指令测试出:sudo apt-get install ubuntu-desktop如果存在安装了的图形界面,那么会有信息提示(2)、卸载图形界面sudo apt-get --purge remove ubuntu-desktop上面这条命令操作_ubuntu16.04图形界面登录失败
文章浏览阅读1.7k次。Samba服务器原理及安装简介Samba是在Linux系统上实现SMB(Session MessageBlock)协议的一个免费软件,以实现文件共享和打印机服务共享。服务器组件samba有两个主要的进程smbd和nmbd。smbd进程提供了文件和打印服务,而nmbd则提供了NetBIOS名称服务和浏览支持,帮助SMB客户定位服务器,处理所有基于UDP的协议。安装[root@..._linux操作系统samba的工作原理
文章浏览阅读273次。对其他网友的代码进行了改进纠正,使代码更加完整,并用vivado2020.1进行了仿真测试源代码(不到100行):`timescale 1ns/1psmodule test #(parameter data_width =4,depth =8,addr_width=3)( wclk,rst_w,w_en,din,w_ptr, rclk,rst_r,r_en,dout,r_ptr, fifo_empty,fifo_full);input wclk,rst_w,w_en;i_verilog 简单fifo
文章浏览阅读2.1k次。今天刷leetcode,遇到了一道题,很有意思,就是给了俩字符串,一个A,一个B,字符串B是这样子的,先把字符串A打乱,然后随机在A中加入一个任意字母,就变成了B。问加入的是啥字母? 举个例子: A:“abc” B:“cbea” 那么很明显,加入的字母是e。如何求出来呢? 这里介绍一种非常简答的方法,就是使用异或。 因为字母是char类型,char类型可以当做in_已知异或怎么求字符
文章浏览阅读5.7k次。c盘空间不足怎么办?尽管现在的硬盘普通都已以T记,但系统分区一般我们还是分得比较小的,电脑久用未清理时较常出现安装软件或运行程序时会提示空间不足,或磁盘空间不够的提示,那么出现c盘空间不足怎么解决呢?下面就来简单介绍一下。c盘空间不足解决一: 将页面分区文件移到其它分区1、将系统页面文件从C盘移走,该文件比较大:2、右击“计算机”,选择“属性”:3、在弹出的“系统属性”对话框中,选择“高级”选项卡..._驱动器c空间不足怎么办
文章浏览阅读2.2k次。一, CSS3 盒子 阴影 属性 box- shadow 也是 CSS3 新增 的 一个 重要 属性, 用来 定义 元素 的 盒子 阴影。inset: 阴影 类型, 可选 值。 如果不 设置, 其 默认 的 投影 方式 是 外 阴影; 如果 取其 唯一 值“ inset”, 就是 给 元素 设置 内 阴影。 x- offset: 阴影水平偏移量, 其值可以是正负值。 如果取正值, 则..._css3模块包括:盒子模型、列表模块、
文章浏览阅读5.4k次,点赞2次,收藏2次。upload.js中://防止事件重复绑定 if(options.elem.data('haveEvents')) return; …… options.elem.data('haveEvents', true);第一次render之后,button '#selectFileBtn' 会被添加属性haveEvents 值为true;下一次render,haveEvents的值依然为tru..._layui upload 超时时间