当前位置:网站首页>Abc229 summary (connected component count of the longest continuous character graph in the interval)
Abc229 summary (connected component count of the longest continuous character graph in the interval)
2022-07-04 19:42:00 【sophilex】
D - Longest X The prefix and + Double pointer
Carelessness : A string consists of "X" and "." form , Given n It's an opportunity , One at a time "." become "X".
Find the longest continuous "X" The number of
Ideas :
Prefixes and statistics "." The number of , Then run with two hands , When the number of operations is greater than or equal to "." Update the interval length as much as possible , Then take the best value .
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
ll dir[][4]={
{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
ll n,m;
ll cnt[N];
char s[N];
ll a,b;
void solve()
{
cin>>(s);
cin>>n;
ll ans=0;
ll len=strlen(s);
//cnt[0]=(s[0]=='.');
for(int i=0;i<len;++i)
{
if(s[i]=='.') cnt[i+1]=cnt[i]+1;
else cnt[i+1]=cnt[i];
}
//for(int i=0;i<len;++i) cout<<cnt[i]<<' ';
for(int l=0,r=0;l<len;++l)
{
while(r<len&&cnt[r+1]-cnt[l]<=n)
{
r++;
}
ans=max(ans,(ll)r-l);
}
cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
solve();
return 0;
}
G Follow D Are two very similar questions , So I want to talk about G
Carelessness :
It is also a string , The problem follows D It's the same thing , however G The operation of the question becomes that only characters in two adjacent positions can be exchanged , This is the only difference between the two questions .
Ideas :
The official solution is ingenious :
If s[i]=='Y',b[++cnt]=i-cnt;
Order array b The element value of is equal to each Y The position of an element minus its bit order ( It's the number one Y).
If it is two consecutive Y, Their positions are continuously increased 1, The bit order is also added continuously 1, So the two b[i] The values will be equal
Then the problem turns into :
There's a number b, Each operation can make b The elements inside +1 perhaps -1, Then ask what can make b How many elements are equal in .
Observe carefully b Construction process of , You can find b The elements in are not reduced , That is, they are monotonous , Then we can consider and divide .
The binary object is naturally the interval length of the equivalent element that can be obtained at the maximum , that judge(x) The content of the function is whether it can be in k A length of x The interval of is unified into a value .
To do this , The best strategy must be to move the elements on both sides closer to the elements in the middle , that judge Our judgment is
among mid Is the midpoint of the interval .
The formula on the left can be optimized , Use prefix and preprocessing , Then calculate the contribution of the left and right parts of the formula respectively
The contribution of the left :sum1=(mid-l+1)*b[mid]-(sum[mid]-sum[l-1])
The contribution on the right :sum2=sum[r]-sum[mid-1]-b[mid]*(r-mid+1)
A very simple elementary school mathematics
Then we can be happy ac La
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
string s;
ll n;
ll b[N];
ll cnt=0;
ll sum[N];//b And
bool judge(ll x)
{
for(int l=1;l+x-1<=cnt;++l)
{
ll r=l+x-1;// Left and right boundary
ll mid=l+r>>1;// Extreme points
ll s1=(mid-l+1)*b[mid]-(sum[mid]-sum[l-1]);
ll s2=(sum[r]-sum[mid-1])-(r-mid+1)*b[mid];
if(s1+s2<=n) return 1;
}
return 0;
}
void solve()
{
cin>>(s);
cin>>n;
for(int i=0;i<s.size();++i)
{
if(s[i]=='Y')
{
b[++cnt]=i+1-cnt;
}
}
for(int i=1;i<=cnt;++i)
{
sum[i]=sum[i-1]+b[i];
}
ll l=0,r=cnt;
while(l<=r)
{
ll mid=l+r>>1;
if(judge(mid)) l=mid+1;
else r=mid-1;
}
cout<<l-1<<endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
solve();
return 0;
}
Carelessness :
There is a picture , from 1 To n Start deleting vertices , Remove all edges connected to the vertex each time , And output the number of connected blocks in the figure below .
Ideas :
To calculate the number of connected blocks , You will think of and search the collection , However, the only operation that can be realized by merging sets is adding , And the topic is minus , So we should consider reverse thinking .
Inverted statistical set . Traverse from big to small to i a.m. , First update the number of connected blocks +1, Its edges must be connected to larger points , If the two are in a set , Then the number of connecting blocks will be reduced 1, Otherwise, put them into a set .
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
ll dir[][4]={
{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
ll n,m;
ll a,b;
ll fa[N];
vector<ll> vt[N];
ll vis[N];
ll ans[N];
ll find(ll x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void solve()
{
cin>>n>>m;
ll cnt=0;
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i)
{
cin>>a>>b;
vt[a].push_back(b);
}
ll sd=0;
for(int i=n;i;--i)
{
sd++;
for(ll k:vt[i])
{
ll fx=find(i);ll fy=find(k);
if(fx!=fy)
{
sd--;
fa[fx]=fy;
}
}
ans[i]=sd;
}
for(int i=2;i<=n;++i) cout<<ans[i]<<endl;
cout<<0;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
solve();
return 0;
}
边栏推荐
- BCG 使用之CBCGPProgressDlgCtrl進度條使用
- Shell 编程核心技术《三》
- “只跑一趟”,小区装维任务主动推荐探索
- 黑马程序员-软件测试--07阶段2-linux和数据库-09-24-linux命令学习步骤,通配符,绝对路径,相对路径,文件和目录常用命令,文件内容相关操作,查看日志文件,ping命令使用,
- Shell programming core technology "three"
- Add namespace declaration
- 欧拉函数
- 牛客小白月赛7 I 新建 Microsoft Office Word 文档
- 测试工程师如何“攻城”(下)
- 有关架构设计的个人思考(本文后续不断修改更新)
猜你喜欢
Introduction to polyfit software
大div中有多个div,这些div在同一行显示,溢出后产生滚动条而不换行
Online sql to excel (xls/xlsx) tool
西门子HMI下载时提示缺少面板映像解决方案
联想首次详解绿色智城数字孪生平台 破解城市双碳升级难点
C # use stopwatch to measure the running time of the program
欧拉函数
Explore the contour drawing function drawcontours() of OpenCV in detail with practical examples
The explain statement in MySQL queries whether SQL is indexed, and several types in extra collate and summarize
MySQL数据库基本操作-DDL | 黑马程序员
随机推荐
长城证券开户安全吗 买股票怎么开户
生成XML元素
在线文本行固定长度填充工具
线上数据库迁移的几种方法
1008 Elevator(20 分)(PAT甲级)
Shell 编程核心技术《四》
The page element is vertically and horizontally centered, realizing the vertical and horizontal centering of known or unknown width.
Shell programming core technology "four"
PolyFit软件介绍
socket编程demo二
Lenovo explains in detail the green smart city digital twin platform for the first time to solve the difficulties of urban dual carbon upgrading
明明的随机数
Pytorch学习(四)
1003 emergency (25 points) (PAT class a)
1009 product of polynomials (25 points) (PAT class a)
勾股数规律(任意三个数能够满足勾股定理需要满足的条件)
页面元素垂直水平居中、实现已知或者未知宽度的垂直水平居中。
【毕业季】绿蚁新醅酒,红泥小火炉。晚来天欲雪,能饮一杯无?
node_ Exporter deployment
双冒号作用运算符以及命名空间详解