当前位置:网站首页>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;
}
边栏推荐
- 1008 Elevator(20 分)(PAT甲级)
- Pythagorean number law (any three numbers can meet the conditions of Pythagorean theorem)
- HDU 1097 A hard puzzle
- 黑马程序员-软件测试--07阶段2-linux和数据库-09-24-linux命令学习步骤,通配符,绝对路径,相对路径,文件和目录常用命令,文件内容相关操作,查看日志文件,ping命令使用,
- 指定输出的字符集
- Functional interface
- Master the use of auto analyze in data warehouse
- BCG 使用之CBCGPTabWnd控件(相当于MFC TabControl)
- Online sql to excel (xls/xlsx) tool
- What should we pay attention to when doing social media marketing? Here is the success secret of shopline sellers!
猜你喜欢
Pytorch学习(四)
Lenovo explains in detail the green smart city digital twin platform for the first time to solve the difficulties of urban dual carbon upgrading
黑马程序员-软件测试--09阶段2-linux和数据库-31-43修改文件权限字母发的说明,-查找链接修改文件,查找文件命令,链接文件,压缩解压方式,vi编辑器基本使用,
Some thoughts on whether the judgment point is located in the contour
mysql中explain语句查询sql是否走索引,extra中的几种类型整理汇总
There are multiple divs in the large div, which are displayed on the same line. After overflow, scroll bars are generated without line breaks
MySQL数据库基本操作-DDL | 黑马程序员
English语法_名词 - 使用
Lm10 cosine wave homeopathic grid strategy
BCG 使用之新建向导效果
随机推荐
Shell 编程核心技术《四》
Shell programming core technology "three"
Socket programming demo II
生成XML元素
How test engineers "attack the city" (Part 2)
1008 Elevator(20 分)(PAT甲级)
牛客小白月赛7 I 新建 Microsoft Office Word 文档
Online data migration scheme encountered in the project 1 - general idea sorting and technical sorting
HDU 1097 A hard puzzle
TCP两次挥手,你见过吗?那四次握手呢?
《工作、消费主义和新穷人》的微信读书笔记
FPGA timing constraint sharing 01_ Brief description of the four steps
1007 Maximum Subsequence Sum(25 分)(PAT甲级)
Pythagorean number law (any three numbers can meet the conditions of Pythagorean theorem)
有关架构设计的个人思考(本文后续不断修改更新)
HDU 1372 & POJ 2243 Knight moves (breadth first search)
BCG 使用之新建向导效果
Pointnet/Pointnet++点云数据集处理并训练
Oracle with as ORA-00903: invalid table name 多表报错
1011 World Cup betting (20 points) (pat a)