2020牛客寒假算法基础集训营4

B 括号序列

思路：用栈去模拟，左括号进栈右括号出栈(对应括号),最后判断一下是否栈空，空说明没问题，否则不行。
代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
	string s;cin>>s;
	stack<char>st;
	bool flag=true;
	for(int i=0;i<s.size();i++){
		if(s[i]=='['||s[i]=='{'||s[i]=='(')st.push(s[i]);
		if(s[i]==']'){
			if(st.top()!='['){
				flag=false;
				break;
			}else{
				st.pop();
			}
		}
		if(s[i]==')'){
			if(st.top()!='('){
				flag=false;
				break;
			}else{
				st.pop();
			}
		}
		if(s[i]=='}'){
			if(st.top()!='{'){
				flag=false;break;
			}else{
				st.pop(); 
			}
		}
	}
	if(flag&&st.empty()){
		cout<<"Yes"<<endl;
	}else cout<<"No"<<endl;
}

A 欧几里得

思路：
通过手动枚举：

得到递推式子，就很好写代码了。
代码：

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		int p[100];
		p[0]=1;p[1]=3;p[2]=5;
		for(int i=3;i<=n;i++)p[i]=p[i-1]+p[i-2];
		cout<<p[n]<<endl;
	}
}

C 子段乘积

思路：
类似最长连续字段和的思路，定义dp[i]:表示前i个数最大连续乘积 。
状态转移方程：dp[i]=(a[i]*dp[i-1]）。
不过这题还需要求一下逆元，因为(a/b)%p = (a%p * inv(b)%p)%p。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 1e7 + 10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f; 
ll a[maxn],dp[maxn],len[maxn];
/* dp[i]:表示前i个数最大连续乘积 */
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法 
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ll ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
ll getInv(ll a,ll mod)//求a在mod下的逆元，不存在逆元返回-1 
{
    ll x,y;
    ll d=exgcd(a,mod,x,y);
    return d==1?(x%mod+mod)%mod:-1;
}
int main(){
	ll n,k;
	cin>>n>>k;
	dp[0]=1;
	for(ll i=1;i<=n;i++)cin>>a[i]; 
	for(ll i=1;i<=n;i++){
		if(a[i]==0){
			len[i]=0;
			dp[i]=1;
		}else{
			dp[i]=a[i]*dp[i-1]%mod;
			len[i]=len[i-1]+1;
		}
	}
	ll ans=0;
	for(ll i=1;i<=n;i++){
		if(len[i]>=k){
			ans=max(ans,(dp[i]%mod*getInv(dp[i-k],mod)%mod)%mod);
		}
	}
	cout<<ans<<endl;
}

E 最小表达式

思路：思路很简单，贪心数字越小的越往权位高的地方放，然后平均放一下就行了，不过这个卡了一个高精度加法。
代码：

#include<iostream>
#include<sstream>
#include<algorithm>
#include<map>
using namespace std;

typedef long long ll ;
const int maxn = 1e7+10;
char str[maxn]; 
map<ll,string>mp;
string add1(string s1,string s2)
{
    if(s1==""&&s2=="")return "0";
    else if(s1=="")return s2;
    else if(s2=="")return s1;
 
    string maxs=s1,mins=s2;
    if(s1.length()<s2.length()){
        maxs=s2;
        mins=s1;
    }
    int a=maxs.length()-1,b=mins.length()-1;
    for(int i=b;i>=0;i--)
        maxs[a--]+=mins[i]-'0';
    for(int i=maxs.length()-1;i>0;i--)
        if(maxs[i]>'9')
        {
            maxs[i]-=10;
            maxs[i-1]++;
        }
    if(maxs[0]>'9')
    {
        maxs[0]-=10;
        maxs='1'+maxs;
    }
    return maxs;
}	
int main(){
	string s;cin>>s;
	ll count=0;
	ll cnt=0;
	for(ll i=0;i<s.size();i++){
		if(s[i]=='+')count++;//统计字符+ 
		else str[cnt++]=s[i];//保存不带字符+的原数组 
	}
	count++; 
	sort(str,str+cnt);
	ll start=0;
	for(ll i=0;i<cnt;i++){
		mp[start++%count]+=str[i];
	}
	map<ll,string>::iterator it;
	string ans = "0";
	for(it=mp.begin();it!=mp.end();it++){
		ans=add1(ans,it->second);
	}
	cout<<ans<<endl;
}