当前位置:网站首页>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進度條使用
- Niuke Xiaobai monthly race 7 I new Microsoft Office Word document
- 1008 elevator (20 points) (PAT class a)
- 92.(cesium篇)cesium楼栋分层
- Stream stream
- kotlin 基本数据类型
- 生成XML元素
- Online text line fixed length fill tool
- Lm10 cosine wave homeopathic grid strategy
- Technologie de base de la programmation Shell IV
猜你喜欢
FPGA时序约束分享01_四大步骤简述
Opencv functions and methods related to binary threshold processing are summarized for comparison and use
Introduction to polyfit software
Some thoughts on whether the judgment point is located in the contour
PointNeXt:通过改进的模型训练和缩放策略审视PointNet++
English grammar_ Noun - use
西门子HMI下载时提示缺少面板映像解决方案
黑马程序员-软件测试--09阶段2-linux和数据库-31-43修改文件权限字母发的说明,-查找链接修改文件,查找文件命令,链接文件,压缩解压方式,vi编辑器基本使用,
Cbcgpprogressdlg progress bar used by BCG
There are multiple divs in the large div, which are displayed on the same line. After overflow, scroll bars are generated without line breaks
随机推荐
Siemens HMI download prompts lack of panel image solution
【毕业季】绿蚁新醅酒,红泥小火炉。晚来天欲雪,能饮一杯无?
BCG 使用之CBCGPTabWnd控件(相当于MFC TabControl)
数据集划分
Introduction to polyfit software
1005 Spell It Right(20 分)(PAT甲级)
YOLOv5s-ShuffleNetV2
Shell 编程核心技术《二》
Is it safe to open an account at Great Wall Securities? How to open an account when buying stocks
“只跑一趟”,小区装维任务主动推荐探索
1009 product of polynomials (25 points) (PAT class a)
添加命名空间声明
HDU 1097 A hard puzzle
Online sql to excel (xls/xlsx) tool
C# 使用StopWatch测量程序运行时间
线上数据库迁移的几种方法
1003 Emergency(25 分)(PAT甲级)
勾股数规律(任意三个数能够满足勾股定理需要满足的条件)
92.(cesium篇)cesium楼栋分层
Online text line fixed length fill tool