2019 计蒜之道初赛第三场

喜欢ヅ旅行 2022-01-23 05:49 163阅读 0赞

A.  
[淘宝商品价格大PK][PK]

思路：暴力解决，先算出序列的最长上升子序数，然后遍历删除一个数的最长上升子序数，如果比原序列的小，则+1。

AC代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int mmax=1e6+10;
    const int eps=1e-8;
    ll a[110],dp[110],b[110];
    int main()
    {
     	ll n,ans=0,ans1=1;
     	cin>>n;
     	for(int i=0;i<n;i++)
     	 cin>>a[i];
    	 if(n==1)
      		cout<<"1"<<endl;
     	else
    	 {  
     		 for(int i=0;i<n;i++)
      		{
       			dp[i]=1;
       			for(int j=0;j<i;j++)
       			{
        				if(a[i]>a[j])
        				{
         					dp[i]=max(dp[i],dp[j]+1);
        				}
        				ans1=max(ans1,dp[i]);
       			}
      		}
     		ll count=0;
      		for(int k=0;k<n;k++)
      		{
    	   		memset(dp,0,sizeof(dp));
    	  	 	memset(b,0,sizeof(b));
    	   		ll o=0;
    	  		 for(int i=0;i<n;i++)
    	  		 {
    	    			if(i!=k)
    	    			b[o++]=a[i];
    	  		 }
    	   		ans=1;
       			for(int i=0;i<o;i++)
      	 		{
        				dp[i]=1;
        				for(int j=0;j<i;j++)
       			 	{		
         					if(b[i]>b[j])
       				  	{
    				      	dp[i]=max(dp[i],dp[j]+1);
         					}
         				ans=max(ans,dp[i]);
       			 }
       		}
       		if(ans<ans1)
        			count++;
      	} 
      	cout<<count<<endl;
    	 }
    	 return 0;}

B.C.D  
[阿里巴巴协助征战SARS（困难][SARS]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]题解：这是官方题解给的公式，其中a代表的是A和C的总数，b代表A或C的数量，G T的排列有2 ^ (n -a) 种，乘上C（n, a）代表G T和（A C）的总排列数，A C还得排列就是C（b,a），这是a!=0的情况（你会发现计算的时候把a=0算进来了，所以在计算 C（n, a）代表G T和（A C）的总排列数的时候需要-1）.当a=0的时候 2^n，

数据很大，运用到欧拉函数性质（素数的欧拉函数是素数-1）和欧拉降幂公式。

AC代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int mmax=1e6+10;
    const int eps=1e-8;
    const int mod=1e9+7;
    ll quick_pow(ll a,ll b,ll c)
    {
     	ll temp=a,ans=1;
     	while(b)
    	 {	
      	if(b&1)
       		ans=(ans*temp)%c;
      	temp=(temp*temp)%c;
      	b>>=1;
     	}
    	 return ans;
    }
    int main()
    {
    	 string n;
    	 while(cin>>n)
    	 {
    	  if(n[0]=='0'&&n.size()==1)
    	   	break;
    	  ll num=0;
    	  for(int i=0;i<n.size();i++)
    	  {
    	   	num=(num*10+(n[i]-'0'))%(mod-1);// 欧拉函数+降幂公式 
    	  }
    	  cout<<(quick_pow(2,num-1+mod-1,mod)*(quick_pow(2,num-1+mod-1,mod)+1))%mod<<endl;  
    	 }
    	 return 0;
    }

[PK]: https://nanti.jisuanke.com/t/39344
[SARS]: https://nanti.jisuanke.com/t/38352
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]: /images/20220123/53c1e40dbbd74b289d8034fa8fb09bad.png