Time：2018.5.5 8:15-13:15

---

A    

题意

对每一组序列，询问是否为山峰数组

分析

模拟即可

---

B

题意

给两个长度为n的序列A_i，B_i，可以给每一个A_i+k，问最多有多少个A_i==B_i

分析

上下做差，查询出现次数最多的数即可

---

C

题意

 

分析

 

---

D

题意

给一个长度为n的括号序列，每个括号都有一个V_i，如果S_k='(' && S_k+1==')'，最终的答案可以加V_i*V_i+1，问最后的最大值

分析

ym：状态一： dp[i][j]：表示第i个(匹配到第j个)的情况下的最大值

         状态二： dp[i][j]：表示还剩下i个(和j个)的情况下的最大值，考虑从右到左确定每个( 的位置    1、他右边所有的(都固定了，2、他右边的)都不会影响后续

#include
     
      #define ll long longusing namespace std;char s[1005];ll dp[1005][1005],sum[1005],num[1005];int l[1005];int main(){    int t,n,cnt,l1,l2;    scanf("%d",&t);    while(t--){        scanf("%d",&n);        for(int i=0;i<=n;i++)            for(int j=0;j<=n;j++)            dp[i][j]=-1000000007;        scanf("%s",s+1);        cnt=l1=l2=0;        for(int i=1;i<=n;i++){            if(s[i]==')')                cnt++;            else                l[i-cnt]=cnt;        }        for(int i=1;i<=n;i++){            if(s[i]=='('){                l1++;                scanf("%lld", &num[l1]);            }            else{                l2++;                scanf("%lld",&sum[l2]);                sum[l2]+=sum[l2-1];            }        }        for(int i=0;i<=l2;i++)            dp[l1][i]=0;        for(int i=l1;i>0;i--){            for(int j=l[i];j<=l2;j++)                dp[i-1][j]=max(dp[i-1][j],dp[i][j]+(sum[j]-sum[l[i]])*num[i]),cout<
      <<' '<
       
        <
        
         =0;j--)                dp[i-1][j]=max(dp[i-1][j],dp[i-1][j+1]);        }        printf("%lld\n",dp[0][0]);    }    return 0;}
        
       
     

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define pb push_back#define fi first#define se second#define ll long long#define sz(x) (int)(x).size()#define pll pair
             
              #define pii pair
              
               #define pq priority_queuechar s[100000];ll v[100000];ll sum[100000];ll dp[1010][1010];int main(){ //freopen("in","r",stdin); //freopen("out","w",stdout); //clock_t start_time=clock(); int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); scanf("%s",s+1); int pre=0; for(int i=1;i<=n;i++){ scanf("%lld",&v[i]); if(s[i]==')')sum[i]=sum[i-1]+v[i]; else sum[i]=sum[i-1]; } for(int i=n;i>=1;i--){ if(s[i]==')')continue; for(int j=n;j>=i;j--){ dp[i][j]=dp[pre][j]+v[i]*(sum[j]-sum[i]); if(j
               
                dp[i][j])dp[i][j]=dp[i][j+1]; } for(int j=i-1;j>=1;j--){ dp[i][j]=dp[i][j+1]; } pre=i; } printf("%lld\n",dp[pre][1]); } //clock_t end_time=clock(); //cout<< "Running time is: "<
                
                 
                  (end_time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<
                 
                
               
              
             
            
           
          
         
        
       
      
     

---

E

题意

 

分析

 

---

F

题意

给出     ，现有n个A_i，m个P_i，对于每一个P_i该公式的和，问全部加起来的和 ( n,m<=5e5，A_i，P_i <= 1e9)

分析

ym：考虑到log函数变化缓慢，在此题中最大也不过32，故对于同一个p有很多数，向上取整后的值相等，预处理出分数和，二分查找即可

#include
     
      #define ll long longusing namespace std;const int maxn=5e5+7;const int mod=1e9;int n,m,a[maxn];int p[maxn];int fac[maxn][33];int main(){    int t;    cin>>t;    while(t--)    {    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);    }    for(int i=1;i<=m;i++)        scanf("%d",&p[i]);    sort(a+1,a+n+1);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=32;j++)        {            fac[i][j]=(fac[i-1][j]+a[i]/j)%mod;        }    }    ll ans=0;    int st=0;    for(int i=1;i<=m;i++)    {        st=0;        ll now=p[i];        ll sum=0;        int num=1;        while(1)        {            int id=upper_bound(a+1,a+n+1,now)-a;            if(id==n+1)                break;            sum=(sum+fac[id-1][num]-fac[st][num])%mod;            num++;            now*=p[i];            st=id-1;        }        sum=(sum+fac[n][num]-fac[st][num])%mod;        ans=(ans+sum*i)%mod;    }    printf("%lld\n", (ans+mod)%mod);    }    return 0;}
     

---

G

题意

 

分析

 

---

H

题意

 

分析

 

---

I

题意

 

分析

 

---

J

题意：将1到n分为两个阵营

ym：偶数的话一定可以分，贪心分数字即可

czh：奇数一定不能分，从后往前贪心

---

K

题意

先从3*M中抽一个麻将作为幸运牌，然后从3*M+1中抽n个麻将排序

如果n个麻将中有幸运麻将，则将幸运麻将放最左边

白板在排序时，把它的牌面当作是幸运麻将的牌面

分析

czh： 分类讨论+模拟+猜题

#include 
     
      using namespace std;const int maxn=1e5+5;int num[maxn],n,m,pos,ans;int main(){    int T;    cin>>T;    for(int i=1;i<=T;i++)    {        pos=0;        cin>>n>>m;        for(int j=1;j<=n;j++)        {             int b;             char k;             cin>>k;             if(k=='W')             {                 pos=j;             }             else if(k=='C')             {                 cin>>b;                 num[j]=b;             }             else if(k=='B')             {                 cin>>b;                 num[j]=m+b;             }             else if(k=='D')             {                 cin>>b;                 num[j]=m*2+b;             }        }             if(n==1)//一张牌时，无论这张牌是什么，所有牌都可能是幸运牌             {                 cout<<3*m<
      
       num[2])//乱序了，只有1张幸运牌                        cout<<1<
       
        num[2])                        cout<<1<
        
         num[2])                        cout<<1<
        
       
      
     

---

L

结构体排个序就好了

---

M

签到

---

Summary

Ym：躺好别送，B题疯狂wa，一度坚信自己一开始想法是right，前期czh做的不错，在ym B题wa的时候稳住了局面，没有大崩盘，D题dp转移有点难想，K题没读懂，F题多读读没准还有机会？

Czh：后期有两个小时没有一点思绪。算法题做不动，实力不足啊