2019牛客暑期多校训练营（第二场）

Solutions

A：Eddy Walker

题意：

给出$n$个点，编号为$0\sim n-1$，问走完所有点恰巧到达$m$点的概率。

思路：

如果，只要$m$不为$0$，到其他点概率都是一样的，为$\frac1{n-1}$，然后判$m=0$的情况。

 1 //#define DEBUG
 2 #include
 3 using namespace std;
 4 const int N=100010;
 5 const int inf=0X3f3f3f3f;
 6 const long long INF = 0x3f3f3f3f3f3f3f3f;
 7 const double eps = 1e-6;
 8 const double pi = acos(-1.0);
 9 const int mod = 1000000007;
10 typedef long long ll;
11 
12 ll q_pow(ll a,ll b) {
13     ll ans=1;
14     ll tmp=a%mod;
15     while(b) {
16         if(b&1) ans=ans*tmp%mod;
17         tmp=tmp*tmp%mod;
18         b=b>>1;
19     }
20     return ans;
21 }
22 
23 int main() {
24     #ifdef DEBUG
25     freopen("in.txt","r",stdin);
26     #endif
27     int _;
28     ll ans=1;
29     for(scanf("%d",&_);_;_--) {
30         ll n,m;
31         scanf("%lld%lld",&n,&m);
32         if(n==1&&m==0) ans*=1;
33         else if(m==0&&n>1) ans=0;
34         else ans=ans*q_pow(n-1,mod-2)%mod;
35         printf("%lld\n",ans);
36     }
37 }

B：Eddy Walker 2

题意：

某人开始在$0$点，给出目标点$k$，和每步能走的最大距离$k$，且走距离$1\sim k$概率都为$\frac1k$，求最后到达$n$点的概率，$n=-1$表示无穷远。

思路：

$dp[i]$表示到达$i$点的概率，那么

$dp[i]=\frac1k\sum_{j=i-k}^{i-1}dp[j]$，线性递推式，丢进BM里搞一搞

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include <string>
  7 #include 

D：Kth Minimum Clique

题意：

给出$n$个点以及点权，求第$k$小团。空团是第一小。

思路：

可以拿着空的，往里面放。每次取出最小的，往里放点，放的时候判断一下是否和团里面的都有边，判断可以用$bitset$优化

放的时候，编号递增的放，防止放入重复点。

 1 //#define DEBUG
 2 #include
 3 using namespace std;
 4 const int N=100010;
 5 const int inf=0X3f3f3f3f;
 6 const long long INF = 0x3f3f3f3f3f3f3f3f;
 7 const double eps = 1e-6;
 8 const double pi = acos(-1.0);
 9 const int mod = 1000000007;
10 typedef long long ll;
11 
12 struct Node{
13     ll w;
14     bitset<110> S;
15     bool operator < (const Node& b) const {
16         return w>b.w;
17     }
18 };
19 
20 char buf[110];
21 bitset<110> bs[110];
22 ll a[110];
23 
24 int main() {
25     #ifdef DEBUG
26     freopen("in.txt","r",stdin);
27     #endif
28     int n,k;
29     scanf("%d%d",&n,&k);
30     for(int i=0;i"%lld",&a[i]);
31     for(int i=0;i) {
32         scanf("%s",buf);
33         for(int j=0;buf[j];j++) {
34             if(buf[j]=='1') bs[i][j]=1;
35         }
36     }
37     priority_queue pq;
38     bitset<110> t;
39     pq.push((Node){0,t});
40     while(!pq.empty()) {
41         Node f=pq.top();pq.pop();
42         bitset<110> r=f.S;
43         k--;
44         if(k==0) {
45             printf("%lld\n",f.w);
46             return 0;
47         }
48         int pos=0;
49         for(int i=0;i) {
50             if(r[i]) {
51                 pos=i+1;
52             }
53         }
54         for(int i=pos;i) {
55             if(!r[i]&&(bs[i]&r)==r) {
56                 r[i]=1;
57                 pq.push((Node){f.w+a[i],r});
58                 r[i]=0;
59             }
60         }
61     }
62     puts("-1");
63 }

E：MAZE

题意：

有一个$n\times\ m$的$01$矩阵，$1$表示不可行，$0$表示可行

每次可以从$\left(i,j\right)$走到$\left(i,j-1\right),\left(i,j+1\right),\left(i+1,j\right)$，且不能回到走过的格子

有$q$个以下两种欧冠操作：

1. 将某个格子的状态反转
2. 询问从$\left(1,x\right)走到\left(n,y\right)$的方案数

• $1\leq\ n$，$q\leq\ 5e4$，$1\leq\ m\leq10$

思路：

参考1、、3Bolgs

先不考虑修改，设$a[i][j]$表示第$i$行第$j$个元素

$dp[i][j]$表示能从第$i-1$行经过$\left(i-1,j\right)$走到$\left(i,j\right)$的方案数，状态转移方程如下：

$dp[i][j]=\sum_{k=1}^{j-1}{dp[i-1][k]}_{for\ a[i-1][k]=0} +\sum_{k=j}^m\ {dp[i-1][k]}_{for\ a[i-1][k]=0}$

比如，$n=2,m=6$时，

$dp[2][2]=dp[1][1]+dp[1][2]+dp[1][3]$

$dp[2][6]=dp[1][5]+dp[1][6]$

我们可以用“列可达”矩阵表示转移关系，然后乘起来就是最后的结果。

“列可达”比如第一行的列可达，第一列为$0$，所以$\left(0,0\right)$位置为$1$，它能到达$2,3$列所以$\left(2,1\right),\left(3,1\right)$为$1$，遇到$1$结束。（见下图）

依次类推。

也就是这样：

发现两个矩阵相乘就可以查询答案了。可以用线段树维护矩阵相乘，每个节点维护一个矩阵（一行）。

修改的话，就修改维护那一行的节点。

 1 //#define DEBUG
 2 #include
 3 using namespace std;
 4 const int N=50010;
 5 const int inf=0X3f3f3f3f;
 6 const long long INF = 0x3f3f3f3f3f3f3f3f;
 7 const double eps = 1e-6;
 8 const double pi = acos(-1.0);
 9 const int mod = 1000000007;
10 typedef long long ll;
11 
12 int n,m,a[N][15];
13 
14 struct Mat{
15     ll a[15][15];
16     void init() {memset(a,0,sizeof(a));}
17     Mat operator * (const Mat &b)const {
18         Mat ans;
19         ans.init();
20         for(int i=1;i<=m;i++) {
21             for(int j=1;j<=m;j++) {
22                 for(int k=1;k<=m;k++) {
23                     ans.a[i][j]=(ans.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
24                 }
25             }
26         }
27         return ans;
28     }
29 }mat[N<<2];
30 
31 void mul(int rt,int x) {
32     mat[rt].init();
33     for(int i=1;i<=m;i++) {
34         if(a[x][i]) continue;
35         mat[rt].a[i][i]=1;
36         for(int k=i+1;k<=m&&(!a[x][k]);k++)
37             mat[rt].a[k][i]=1;
38         for(int k=i-1;k>=1&&(!a[x][k]);k--)
39             mat[rt].a[k][i]=1;
40     }
41 }
42 
43 void build(int l,int r,int rt) {
44     if(l==r) {
45         mul(rt,l);
46         return ;
47     }
48     int mid=(l+r)>>1;
49     build(l,mid,rt<<1);
50     build(mid+1,r,rt<<1|1);
51     mat[rt]=mat[rt<<1]*mat[rt<<1|1];
52 }
53 
54 void updata(int v,int l,int r,int rt) {
55     if(l==r) {
56         mul(rt,l);
57         return ;
58     }
59     int mid=(l+r)>>1;
60     if(v<=mid) updata(v,l,mid,rt<<1);
61     else updata(v,mid+1,r,rt<<1|1);
62     mat[rt]=mat[rt<<1]*mat[rt<<1|1];
63 }
64 
65 int main() {
66     #ifdef DEBUG
67     freopen("in.txt","r",stdin);
68     #endif
69     int q;
70     scanf("%d%d%d",&n,&m,&q);
71     for(int i=1;i<=n;i++) {
72         for(int j=1;j<=m;j++)
73             scanf("%1d",&a[i][j]);
74     }
75     build(1,n,1);
76     while(q--) {
77         int op,x,y;
78         scanf("%d%d%d",&op,&x,&y);
79         if(op==1) {
80             a[x][y]^=1;
81             updata(x,1,n,1);
82         } else printf("%lld\n",mat[1].a[x][y]);
83     }
84     return 0;
85 }

F：Partition problem

题意：

$2n$个人，每个人都与其他人有对抗值，分成两个集合且集合大小相等，求分配后的最大对抗值

思路：

啥都不说，就是不会$DFS$，感觉还做过。给出链接

 1 //#define DEBUG
 2 #include
 3 using namespace std;
 4 const int N=100010;
 5 const int inf=0X3f3f3f3f;
 6 const long long INF = 0x3f3f3f3f3f3f3f3f;
 7 const double eps = 1e-6;
 8 const double pi = acos(-1.0);
 9 const int mod = 1000000007;
10 typedef long long ll;
11 
12 ll a[30][30],ans;
13 int sa[30],sb[30];
14 int n;
15 
16 void dfs(int id,int num1,int num2,ll sum) {
17     if(num1==n&&num2==n) {
18         for(int i=0;i"%d ",sa[num1]);
19         puts("");
20         for(int i=0;i"%d ",sb[num2]);
21         puts("");
22         ans=max(ans,sum);
23         return;
24     }
25     if(num1<n) {
26         ll tmp=0;
27         for(int i=0;ia[id][sb[i]];
28         sa[num1]=id;
29         dfs(id+1,num1+1,num2,sum+tmp);
30     }
31     if(num2<n) {
32         ll tmp=0;
33         for(int i=0;ia[id][sa[i]];
34         sb[num2]=id;
35         dfs(id+1,num1,num2+1,sum+tmp);
36     }
37 }
38 int main() {
39     #ifdef DEBUG
40     freopen("in.txt","r",stdin);
41     #endif
42     scanf("%d",&n);
43     for(int i=1;i<=2*n;i++) {
44         for(int j=1;j<=2*n;j++)
45             scanf("%lld",&a[i][j]);
46     }
47     dfs(1,0,0,0);
48     printf("%lld\n",ans);
49 }

H：Second Large Rectangle

题意：

求次大全$1$矩阵的面积。

思路：

首先最大全$1$矩阵可以通过单调栈求出，用同样的方法，把二维的压下来，每一行存当前高度，然后每一行都用单调栈维护，求得的矩阵去更新答案，注意！！！$x\ast(y-1),y\ast(x-1)$也要更新答案。。。当时没理解，加入就AC了。。

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=100010;
 5 const int inf=0x3f3f3f3f;
 6 
 7 int a[1010][1010];
 8 int n,m;
 9 stackint,int> > s;
10 vector<int> ansans;
11 int main() {
12     while(~scanf("%d%d",&n,&m)) {
13         for(int i=1;i<=n;i++) {
14             for(int j=1;j<=m;j++) {
15                 scanf("%1d",&a[i][j]);
16                 if(a[i][j]) a[i][j]+=a[i-1][j];
17             }
18             a[i][m+1]=0;
19         }
20         pair<int,int> v;
21         for(int i=1;i<=n;i++) {
22             for(int j=1;j<=m+1;j++) {
23                 if(s.empty()||s.top().second<=a[i][j]) {
24                     s.push({1,a[i][j]});
25                 }
26                 else {
27                     int sum=0;
28                     while(!s.empty()&&s.top().second>a[i][j]) {
29                         v=s.top();
30                         sum+=v.first;
31                         int area1=sum*v.second;
32                         int area2=(sum-1)*v.second;
33                         int area3=sum*(v.second-1);
34                         ansans.push_back(area1);
35                         ansans.push_back(area2);
36                         ansans.push_back(area3);
37                         s.pop();
38                     }
39                     s.push({sum+1,a[i][j]});
40                 }
41             }
42             while(!s.empty()) s.pop();
43         }
44         sort(ansans.begin(),ansans.end());
45         int len=ansans.size();
46         if(len<2) printf("0\n");
47         else {
48             printf("%d\n",ansans[len-2]);
49         }
50         while(!s.empty()) s.pop();
51         ansans.clear();
52     }
53 }