2020牛客寒假算法基础集训营4
A-欧几里得
题面：
本题思路：本题容易误导人去使用简单模拟办法来做，但这样容易超时，之后找出规律，就比较简单了，
#include<iostream>
using namespace std;
//#define ll long long
long long dp[100]={0};
int main(){
dp[0]=1;
dp[1]=3;
dp[2]=5;
long long T,n;
cin>>T;
while(T--){
cin>>n;
for(long long i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
cout<<dp[n]<<endl;
}
return 0;
} B-括号序列
题面：
解题思路：本题是练习使用堆栈的入门题，可用一维数组模拟堆栈，实现其基本功能。
#include<iostream>
#include<string>
#include<stack>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
return a>b;
}
ll read(){
ll x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return w*x;
}
bool IsPrimeNumber(int n){
if (n==2){
return true;
}
if (n%2==0||n==1){
return false;
}
int sqrtn=(int)sqrt((double)n);
bool flag=true;
for (int i=3;i<=sqrtn;i+=2){
if (n%i==0){
flag=false;
}
}
return flag;
}
void reversea(int t[],int n){
int temp[n];
for(int i=0;i<n;i++){
temp[i]=t[i];
}
int r=0;
for(int i=n-1;i>=0;i--){
t[r++]=temp[i];
}
}
ll T,n,ans=0,x,num=0;;
int gcd(ll a,ll b){
if(b==0){
return b;
}else{
num++;
return gcd(b,a%b);
}
}
int main(){
string ptr;
getline(cin,ptr);
if(ptr==""){
cout<<"Yes"<<endl;
}else{
char arr[1000005];
int t=0,e=0;
arr[t++]=ptr[0];
for(int i=1;i<ptr.length();i++){
e=t-1;
if(arr[e]=='['&&ptr[i]==']'||arr[e]=='('&&ptr[i]==')'||arr[e]=='{'&&ptr[i]=='}'){
t--;
}else{
arr[t++]=ptr[i];
}
}
if(t==0){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
} D-子段异或
题面：
解题思路：异或前缀和
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int main(){
int q[N], n;
int all[N];
ll ans = 0;
cin>>n;
for(int i = 1; i <= n; i++){
cin>>q[i];
all[i] = all[i - 1] ^ q[i];
}
sort(all + 1, all + 1 + n);
for(int i = 0; i <= n; ) {
int j = i + 1;
ll t = 1;
while(j <= n && all[i] == all[j]){
j++;
t++;
}
ans =ans+ (t - 1) * t / 2;
i = j;
}
cout<<ans<<endl;
return 0;
} 
