C - Brackets Stack Query
题目大意
一个字符串 被称为好的括号序列，当且仅当它满足以下条件：
-
可以通过对以下操作进行零次或多次连续执行以得到空字符串：
- 选择一个作为连续子串的
()，并将其删除。
例如，()、(()()) 和空字符串都是好的括号序列，但 )()( 和 ))) 则不是好的括号序列。
有一个字符串 。初始时，
是一个空字符串。
请按顺序处理 个查询，在每次查询之后，判断
是否是一个好的括号序列。
查询共有两种类型：
-
1 c：给出一个字符，
(或)中的一个。将的末尾。
-
2：删除
题目标签
括号序列
题解
括号序列的一个性质：将 ( 视为 ，
) 视为 ，则对于一个好的括号序列，其前缀和时时刻刻不会小于
，且最终前缀和为
。
维护当前字符串的前缀和即可得到是否存在前缀和小于 的情况，以及当前字符串的前缀和是否为
。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int q;
cin>>q;
int cnt_n=0,pre=0;//统计前缀为负数的个数，前缀和
vector<int> tmp;
while(q--){
int op;
cin>>op;
if(op==1){
char c;
cin>>c;
if(c=='('){
pre++;
tmp.push_back(1);
}
else{
pre--;
tmp.push_back(-1);
}
if(pre<0) cnt_n++;
}
else{
int c=tmp.back();
tmp.pop_back();
if(c==-1){
if(pre<0) cnt_n--;
pre++;
}
else{
if(pre<0) cnt_n--;
pre--;
}
}
cout<<((cnt_n||pre!=0)?"No\n":"Yes\n");
}
return 0;
}
D - 183184
题目大意
对于正整数 和
，定义函数
如下：
- 将
和
以十进制表示的字符串形式按顺序拼接，得到字符串
，将
。
例如，，
。
现给出正整数 和
，请找出满足以下条件的整数
的个数：
-
是一个完全平方数。
你需处理 组测试数据，对每组数据都输出对应的答案。
题解
设 ，且
的位数为
，则有：
由于 的位数为
，故
的取值范围为：
即 的取值范围为：
令 ，
，则
的取值范围为：
故 的可行方案数即
内完全平方数的个数，即
内整数的个数。
参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int qpow(int b,int p){
int res=1;
while(p){
if(p&1) res=res*b;
b=b*b;
p>>=1;
}
return res;
}
int cal(int x){
int bit=0;
while(x){
x/=10;
bit++;
}
return bit;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int c,d;
cin>>c>>d;
int l=cal(c+1),r=cal(c+d);
int ans=0;
for(int i=l;i<=r;i++){
int xl=max(qpow(10,i-1)-c,(long long)1);
int xr=min(qpow(10,i)-c-1,d);
int fl=ceill(sqrt((long double)xl+c*(qpow(10,i)+1)));
int fr=floorl(sqrt((long double)xr+c*(qpow(10,i)+1)));
ans+=max((long long)0,fr-fl+1);
}
cout<<ans<<'\n';
}
return 0;
}
E - Farthest Vertex
题目大意
给定一棵包含 个顶点的树，顶点编号为
到
。第
条边连接顶点
和
。
定义两个顶点 和
之间的距离为连接这两个顶点的唯一简单路径上的边的数量。（这样的路径是唯一的。）
题解
树的直径的经典性质：对于任意结点 ，距离
最远的结点
一定是任意一条树的直径的一个端点。
故求出编号最大的两个直径端点 和
，对于每个结点
，若：
-
，则输出
-
，则输出
-
，则输出
。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int h[N],ne[N<<1],to[N<<1],idx=0;
void add(int a,int b){
to[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
}
int dis1[N],dis2[N];
void dfs(int u,int fa){
for(int i=h[u];~i;i=ne[i]){
int v=to[i];
if(v==fa) continue ;
dis1[v]=dis1[u]+1;
dfs(v,u);
}
}
void dfs2(int u,int fa){
for(int i=h[u];~i;i=ne[i]){
int v=to[i];
if(v==fa) continue ;
dis2[v]=dis2[u]+1;
dfs2(v,u);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) h[i]=-1;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
}
dfs(1,0);
int sta=0,ed=0;
int mx_d=0;
for(int i=1;i<=n;i++)
if(dis1[i]>=mx_d){
sta=i;
mx_d=dis1[i];
}
dis1[sta]=0;
dfs(sta,0);
for(int i=1;i<=n;i++)
if(dis1[i]>=mx_d){
ed=i;
mx_d=dis1[i];
}
dfs2(ed,0);
for(int i=1;i<=n;i++){
if(dis1[i]>dis2[i]) cout<<sta<<'\n';
else if(dis1[i]<dis2[i]) cout<<ed<<'\n';
else cout<<max(ed,sta)<<'\n';
}
return 0;
}
