杭电多校训练第八场

题意：给一个序列，每次贪心选取比前一个数大的数。每次询问修改一个数，求修改后的序列的能选出多少个数。询问不叠加。

题解：

方法一：参考http://www.cnblogs.com/xingkongyihao/p/9489494.html

　　RMQ+二分查找。dp1为前缀，dp2为后缀，cnt记录1~i的最大值。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAX=1e5+10;
 4 int dp[MAX][25],a[MAX],cnt[MAX],dp1[MAX],dp2[MAX],q[MAX],t,n,m;
 5 void ST()
 6 {
 7     for(int i=1;i<=n;i++)
 8         dp[i][0]=a[i];
 9     for(int j=1;(1<<j)<=n;j++)
10         for(int i=1;i+(1<<j)-1<=n;i++)
11             dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
12 }
13 int rmq(int l,int r)
14 {
15     int k=0;
16     while((1<<(k+1))<=r-l+1)    k++;
17     return max(dp[l][k],dp[r-(1<<k)+1][k]);
18 }                                                             //RMQ模板
19 int find_pos(int l,int r,int x)                                 //二分查找
20 {
21     int pos=-1;
22     while(l<=r)
23     {
24         int mid=(l+r)>>1;
25         if(rmq(l,mid)>x)
26         {
27             pos=mid;
28             r=mid-1;
29         }
30         else
31             l=mid+1;
32     }
33     return pos;
34 }
35 int main()
36 {
37     scanf("%d",&t);
38     while(t--)
39     {
40         scanf("%d%d",&n,&m);
41         int tmp=0;
42         for(int i=1;i<=n;i++){
43             scanf("%d",&a[i]);
44             if(tmp<a[i])
45             {
46                 tmp=a[i];
47                 dp1[i]=dp1[i-1]+1;  //求前缀
48             }
49             else    dp1[i]=dp1[i-1];
50             cnt[i]=max(a[i],cnt[i-1]); //求最大值
51         }
52         ST();
53         int tail=0,head=1;
54         for(int i=n;i>=1;i--)       //求后缀
55         {
56             while(head<=tail&&q[tail]<=a[i])    tail--;
57             q[++tail]=a[i];
58             dp2[i]=tail-head+1;
59         }
60         int x,y;
61         while(m--)
62         {
63             scanf("%d%d",&x,&y);
64             int ans=dp1[x-1];
65             if(y>cnt[x-1])  ans++;
66             y=max(y,cnt[x-1]);
67             int pos=find_pos(x+1,n,y);
68             if(pos!=-1) ans+=dp2[pos];
69             printf("%d
",ans);
70         }
71     }
72     return 0;
73 }

View Code

方法二：参考https://blog.csdn.net/GYH0730/article/details/81783283

　　利用线段树来查找dp1和dp2，最后加和就是答案

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int MAX=1e5+10;
  4 struct node
  5 {
  6     int l,r;
  7     int maxn,pos;    
  8     #define lson rt << 1
  9     #define rson rt << 1 | 1
 10 }tree[4*MAX];
 11 int a[MAX],dp1[MAX],dp2[MAX],cur; //cur代表下标
 12 void pushUp(int rt)
 13 {
 14     tree[rt].maxn=max(tree[lson].maxn,tree[rson].maxn);
 15     if(tree[lson].maxn>=tree[rson].maxn)    tree[rt].pos=tree[lson].pos;
 16     else        tree[rt].pos=tree[rson].pos;
 17 }
 18 void build(int rt,int l,int r)
 19 {
 20     tree[rt].l=l;
 21     tree[rt].r=r;
 22     if(l==r)
 23     {
 24         tree[rt].maxn=a[l];
 25         tree[rt].pos=l;
 26         return ;
 27     }
 28     int mid=(l+r)>>1;
 29     build(lson,l,mid);
 30     build(rson,mid+1,r);
 31     pushUp(rt);
 32 }
 33 void query1(int rt,int l,int r,int val)      //寻找后面第一个比val大的下标，即后缀
 34 {
 35     if(tree[rt].l==tree[rt].r)
 36     {
 37         if(tree[rt].maxn>val)   cur=min(cur,tree[rt].l);
 38         return ;
 39     }
 40     int mid=(tree[rt].l+tree[rt].r)>>1;
 41     if(tree[rt].l>=l&&tree[rt].r<=r)
 42     {
 43         if(tree[lson].maxn>val) query1(lson,l,mid,val);
 44         else if(tree[rson].maxn>val)    query1(rson,mid+1,r,val);
 45         return;
 46     }
 47     if(l<=mid)  query1(lson,l,r,val);
 48     if(r>mid)   query1(rson,l,r,val);
 49 }
 50 void query2(int rt,int l,int r)     //寻找前缀
 51 {
 52     if(tree[rt].l>=l&&tree[rt].r<=r)
 53     {
 54         if(tree[rt].maxn>a[cur])    cur=tree[rt].pos;
 55         return ;
 56     }
 57     int mid=(tree[rt].l+tree[rt].r)>>1;
 58     if(l<=mid)  query2(lson,l,r);
 59     if(r>mid)   query2(rson,l,r);
 60 }
 61 int n,m,t;
 62 int main()
 63 {
 64     scanf("%d",&t);
 65     while(t--)
 66     {
 67         memset(dp1,0,sizeof(dp1));
 68         memset(dp2,0,sizeof(dp2));//将dp1和dp2初始化为0
 69         scanf("%d%d",&n,&m);
 70         int tmp=0;
 71         for(int i=1;i<=n;i++)
 72         {
 73             scanf("%d",&a[i]);
 74             if(tmp<a[i])    //寻找前缀
 75             {
 76                 tmp=a[i];
 77                 dp1[i]=dp1[i-1]+1;
 78             }
 79             else
 80                 dp1[i]=dp1[i-1];
 81         }
 82         build(1,1,n);
 83         dp2[n]=1;
 84         for(int i=n-1;i>=1;i--) //寻找后缀
 85         {
 86             cur=n+1;
 87             query1(1,i+1,n,a[i]);
 88             dp2[i]=dp2[cur]+1;
 89         }
 90         int x,y;
 91         while(m--)
 92         {
 93             scanf("%d%d",&x,&y);
 94             int ans=0;
 95             cur=0;      //寻找前缀，初始化cur=0
 96             if(x!=1)    query2(1,1,x-1); 
 97             ans+=dp1[cur];
 98             if(y>a[cur])    ans++;  //如果y>a[cur]，ans++
 99             else    y=a[cur];       //否则让y等于a[cur]
100             cur=n+1;       //寻找后缀，初始化cur=n+1
101             if(x!=n)    query1(1,x+1,n,y);
102             ans+=dp2[cur];
103             printf("%d
",ans);
104 
105         }
106     }
107     return 0;
108 }

View Code

Character Encoding

参考https://blog.csdn.net/luyehao1/article/details/81738825

题意：x1+x2+x3+...+xm=k，其中0<=xi<=n-1，已知n,m,k，求所有可能的情况数。

方程整数解经典问题，用容斥定理进行求解

如果xi无上限，那么用隔板法即可求解，总的方案数是：C(m+k-1,m-1)

本题中的0<=xi<=n-1，所以就会有不合法的xi（xi>=n），我们需要将其变成xi-n。

又根据容斥的性质，奇数个交集乘以-1，偶数个交集乘以1，可以得到式子：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int MAX=1e6;
 6 const int mod=998244353;
 7 ll fac[MAX+10],inv[MAX+10];   //fac阶乘，inv是逆元的阶乘
 8 ll qpow(ll x,ll y)                      
 9 {
10     ll ans=1;
11     while(y)
12     {
13         if(y&1) ans=(ans%mod*x%mod)%mod;
14         x=(x%mod*x%mod)%mod;
15         y>>=1;
16     }
17     return ans;
18 }
19 void init()             //初始化fac和inv
20 {
21     fac[0]=1;
22     for(ll i=1;i<=MAX+1;i++)
23         fac[i]=(fac[i-1]%mod*i%mod)%mod;
24     inv[MAX+1]=qpow(fac[MAX+1],mod-2);
25     for(ll i=MAX;i>=0;i--)
26         inv[i]=(inv[i+1]%mod*(i+1)%mod)%mod;
27     return ;
28 }
29 ll C(ll x,ll y)             //求组合数模板
30 {
31     if(!x&&!y)  return 1;
32     if(x<y) return 0;
33     return (fac[x]%mod*inv[y]%mod*inv[x-y]%mod)%mod;
34 }
35 ll t,n,m,k;
36 int main()
37 {
38     init();     //不要忘记在在主函数中调用初始化函数
39     for(scanf("%lld",&t);t;t--)
40     {
41         scanf("%lld%lld%lld",&n,&m,&k);
42         ll ans=0;
43         for(ll i=0;i<=min(k/n,m);i++)
44         {
45             if(i%2==0)
46                 ans=(ans%mod+C(m+k-1-i*n,m-1)%mod*C(m,i)%mod+mod)%mod;
47             else
48                 ans=(ans%mod-C(m+k-1-i*n,m-1)%mod*C(m,i)%mod+mod)%mod;      //在有加减的操作中不要忘记再加上mod，否则对答案会产生影响
49         }
50         printf("%lld
",ans);
51     }
52 //    cout << "Hello world!" << endl;
53     return 0;
54 }

View Code

Parentheses Matrix

当h 和w 中有一个是奇数时，构造的方法是显然的。下面仅讨论h 和w 都是偶数的情况。不妨设h ≤ w。

首先，第一行、最后一列中最多只有一个能够匹配，第一列、最后一行也只有一个能够匹配（考虑右上角和左下角的括号选取方法），故答案不会超过w+h−2。

当h = 2 时，每一列可以构造一对匹配，这样答案已经到达上界。

当h = 4 时，可以如下构造：

((((((
)))(((
((()))
)))))) 　　
这样答案是w+h−3（即牺牲第一行、第二行和最后一行）。若存在更优的答案，则必有一个边界能够匹配，不妨设是第一列。这样，就已经有除第一行以外的两行（右括号开头的行）不匹配了，而第一行和最后一列中至少有一个不匹配因此最优解不会超过w+h−3。

当h ≥ 6 时，可以如下构造：
((((((((
()()()()
(()()())
()()()()
(()()())
))))))))
答案是w+h−4（即牺牲第一行、最后一行、第一列、最后一列）。同理可证明不存在更优的方法。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 int t,h,w;
 5 char mp[300][300];
 6 int main()
 7 {
 8     for(scanf("%d",&t);t;t--)
 9     {
10         memset(mp,0,sizeof(mp));
11         scanf("%d%d",&h,&w);
12         if(h%2&&w%2)
13         {
14             for(int i=0;i<h;i++)
15                 for(int j=0;j<w;j++)
16                     mp[i][j]='(';
17         }
18         else if(h%2&&w%2==0)
19         {
20             for(int i=0;i<h;i++)
21                 for(int j=0;j<w;j++)
22                     mp[i][j]=j%2 ? ')' : '(';
23         }
24         else if(h%2==0&&w%2)
25         {
26             for(int j=0;j<w;j++)
27                 for(int i=0;i<h;i++)
28                     mp[i][j]=i%2 ? ')' : '(';
29         }
30         else
31         {
32             if(min(h,w)==2)
33             {
34                 if(h<=w)
35                     for(int i=0;i<w;i++)
36                         mp[0][i]='(',mp[1][i]=')';
37                 else
38                     for(int i=0;i<h;i++)
39                         mp[i][0]='(',mp[i][1]=')';
40             }
41             else if(min(h,w)==4)
42             {
43                 if(h<=w)
44                     for(int i=0;i<w;i++)
45                         mp[0][i]='(',mp[h-1][i]=')',mp[1][i]=i<w/2 ? ')' : '(',mp[2][i]=i<w/2 ? '(' : ')';
46                 else
47                     for(int i=0;i<h;i++)
48                         mp[i][0]='(',mp[i][w-1]=')',mp[i][1]=i<h/2 ? ')' : '(',mp[i][2]=i<h/2 ? '(' : ')';
49             }
50             else
51             {
52                 if(h<=w)
53                 {
54                     for(int j=0;j<w;j++)
55                         mp[0][j]='(',mp[h-1][j]=')';
56                     for(int i=1;i<h-1;i++)
57                         for(int j=0;j<w;j++)
58                             if(i%2) mp[i][j]=j%2 ? ')' : '(';
59                             else
60                             {
61                                 if(j==0)    mp[i][j]='(';
62                                 else if(j==w-1) mp[i][j]=')';
63                                 else  mp[i][j]=j%2 ? '(' : ')';
64                             }
65                 }
66                 else
67                 {
68                     for(int i=0;i<h;i++)
69                         mp[i][0]='(',mp[i][w-1]=')';
70                     for(int j=1;j<w-1;j++)
71                         for(int i=0;i<h;i++)
72                             if(j%2) mp[i][j]=i%2 ? ')' : '(';
73                             else
74                             {
75                                 if(i==0)    mp[i][j]='(';
76                                 else if(i==h-1) mp[i][j]=')';
77                                 else    mp[i][j]=i%2 ? '(' : ')';
78                             }
79                 }
80             }
81         }
82         for(int i=0;i<h;i++)
83         {
84             for(int j=0;j<w;j++)
85                 printf("%c",mp[i][j]);
86             printf("
");
87         }
88     }
89 //    cout << "Hello world!" << endl;
90     return 0;
91 }

View Code

如有错误，请指正，感谢！