2019 CSP-S 题目整理
A-格雷数
思路简介
思路很简单，如果编号在中点的左边那么就输出0，否则输出1，同时还要改变编号。
代码实现
#include<bits/stdc++.h>
#define maxn 80
using namespace std;
typedef __int128 int1;
int1 n,k;
__int128 read(){
char ch=getchar();
__int128 s=0,f=1;
while(ch>'9'||ch<'0'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*f;
}
void dfs(int cur,int1 x){//cur位，x号
int1 mid=(int1)pow(2,cur-1)-1;
//cout<<cur<<' '<<mid<<' '<<x<<endl;
if(cur==1){
if(x==0)cout<<0;
else if(x==1)cout<<1;
return;
}
if(x<=mid){
cout<<0;
dfs(cur-1,x);
}
else {
cout<<1;
dfs(cur-1,(int1)pow(2,cur)-x-1);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
n=read();k=read();
//cout<<k<<endl;
dfs(n,k);
return 0;
}
——int128
这道题数据给的太毒瘤，\(2^{64}-1\)，卡着\(unsigned\ long\ long\)的范围，稍微超过一点就要溢出，所以还是开\(\_int128\)大大的好
因此读入必须使用快读
_int rd(){
_int f=1,sum=0;
char ch;
ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
sum=(sum<<3)+(sum<<1)+ch-'0';
ch=getchar();
}
return sum*f;
输出必须使用快写
void write(_int n){
if(n<0)putchar('-'),n=-n;
if(n>9)write(n/10);
putchar(n%10+'0');
}
B-括号树
题目大意
有一棵树，树上的每个节点是半个括号，要求从树根1到节点\(i\)，路径上经过的完全不同的合法子串的个数。
题目中对合法括号串的定义如下：
1.() 是合法括号串。
2.如果 A 是合法括号串，则 (A) 是合法括号串。
3.如果 A，B 是合法括号串，则 AB 是合法括号串。
思路简介
设\(sum[i]\)表示从1到节点\(i\)路径上经过的合法子串个数，\(f[i]\)表示第\(i\)个节点对答案的贡献。
来看下面这个例子
括号串的中间部分是四个相包含的括号，在与另外两个括号组合时他等价于1个括号，所以
\[(A)=() \]简化完括号串以后，再来分析。对于
\[A(B)=A() \]右括号对于答案的贡献一定为对应左括号上一个字符的贡献+1，因为多了去本身的一种方案，即
\[f[x]=f[fa[t]]+1 \]注意！！在深搜时如果往栈里压进数，在回溯时要弹出；在深搜时如果弹出数，在回溯时要压回栈里。
代码实现
#include<bits/stdc++.h>
#define maxn 500010
#define ll long long
using namespace std;
struct edge{
int to,next;
}e[maxn];
int n;
int cnt=0,fa[maxn],head[maxn];
char ch[maxn];
ll f[maxn],sum[maxn],ans=0;
stack<int>st;
void add(int x,int y){
e[++cnt].next=head[x];
e[cnt].to=y;
head[x]=cnt;
}
void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
void dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to,cur=-1;
if(ch[v]=='('){
st.push(v);
}
else if(ch[v]==')'){
if(!st.empty()){
cur=st.top();
f[v]=f[fa[cur]]+1;
st.pop();
}
}
sum[v]=sum[u]+f[v];
dfs(v);
if(cur!=-1)st.push(cur);
else if(!st.empty())st.pop();
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
ch[i]=getchar();
while(ch[i]!='('&&ch[i]!=')'){
ch[i]=getchar();
}
}
add(0,1);
for(int i=1;i<n;i++){
int x,y=i+1;
cin>>x;
add(x,y);
fa[y]=x;
}
dfs(0);
for(int i=1;i<=n;i++){
ans^=i*sum[i];
//cout<<sum[i]<<' ';
}
write(ans);
return 0;
}