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;
}
