2019牛客暑期多校训练营（第二场）(除C外）

@[toc]

A Eddy walk

题意

给定长度为n的环，编号,起始点在0，每一次可以向前向后走一格，问走完所有的格子之后所在的位置为M的概率。

分析

暴力打表找规律

const int maxn = 100 + 10;
double p[maxn];
int n;
bool vis[maxn];
void dfs(int x, int n, double pro) {
    if (pro < 1e-10 ) return ;
    for (int i = 0; i < n; ++i)
        if (!vis[i]) {
            int nxt = (x + 1) % n;
            bool tmp = vis[nxt];
            vis[nxt] = true;
            dfs(nxt, n, pro * 0.5);
            vis[nxt] = tmp;

            nxt = (x - 1 + n) % n;
            tmp = vis[nxt];
            vis[nxt] = true;
            dfs(nxt, n, pro * 0.5);
            vis[nxt] = tmp;
            return ;
        }
    p[x] += pro;
}
int main(void)
{
    int n = 6;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= i; ++j)
            p[j] = 0;
        vis[0] = 1;
        dfs(0, i, 1);
        cout << i << endl;
        for (int j = 0; j < i; ++j) {
            cout << p[j] << " ";
        }
        cout << endl;
    }

    return 0;
}

B Eddy Walker 2

BM 算法套用即可

D Kth Minimum Clique

题意：

求第k小团

分析：

暴力搜索，每次加入一个节点, 使用优先队列每次取最小的团加入节点，使用bitset优化

#include<bits/stdc++.h>

using namespace std;
#define maxn 110
typedef long long ll;
int n, k, a[maxn];

bitset<maxn> bit[maxn];
struct node {
  bitset<maxn> now;
  ll val, last;
  bool operator <(const node &a) const {
    return val > a.val;
  }
};
ll solve() {
  priority_queue<node> q;
  node no;
  no.now.reset();
  no.val = 0;
  no.last = 0;
  q.push(no);
  while (!q.empty()) {
    node t = q.top(); q.pop();
    // cout << t.val << endl;
    if (--k == 0)
      return t.val;
    // cout << q.size() << endl;
    for (int i = t.last; i < n; ++i) {
      if (!t.now[i] && ((t.now & bit[i]) == t.now)) {
        t.now.set(i);
        // cout << t.val + a[i] << endl;
        // node nn = node{t.now, t.val + a[i], i + 1};
        // cout << nn.val << endl;
        q.push(node{t.now, t.val + a[i], i + 1});

        t.now.reset(i);
      }
    }
  }
  return -1;
}



int main(void)
{
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i)
    scanf("%d", &a[i]);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int x; scanf("%1d", &x);
      bit[i].set(j, x);
      // cout << x << endl;
    }
  }
  printf("%lld\n", solve());
}

E MAZE

题意：

给定一个的01矩阵，0代表道路，1代表墙壁，每次可以从 走到 ,但不能走到墙壁也不能往回走，有Q次操作
操作 1：将 位置反转，道路变为墙壁，墙壁变为道路
操作 2：询问从 的合法道路有多少条

分析：

我们注意到N很大，M很小，可以通过矩阵实现行间状态转移，修改操作可以看做是修改转移矩阵 M,用线段树维护转移矩阵 所有转移矩阵的乘积就是从第一行到最后一行的方案个数，就是我们所求。

参考代码：

const int maxn = 100+10;
bitset<maxn> bit[maxn];
int n,k;
int a[maxn];
char ar[maxn][maxn];
// 求第k小团

struct Node{
  int last;
  LL  val;
  bitset<maxn> bit;

  bool operator <(const Node &a)const{
    return val > a.val;
  }
};
LL solve(){
  priority_queue<Node> Q;
  Node node;
  node.val = node.last = 0;
  node.bit.reset();
  Q.push(node);
  while(!Q.empty()){
    Node tmp = Q.top(); Q.pop();
    if(--k == 0)
      return tmp.val;
    for(int i = tmp.last; i < n; ++i){
      if(!tmp.bit[i]&&(bit[i]&tmp.bit)==tmp.bit){
        tmp.bit.set(i);
        Q.push(Node{i+1,tmp.val+a[i],tmp.bit});
        tmp.bit.reset(i);   
      }
    }
  }
  return -1;
}
int main(void)
{
    cin>>n>>k;
    for(int i =0;i < n; ++i)
      cin>>a[i];
    for(int i = 0;i < n; ++i){
        cin>>ar[i];
        for(int j =0;j < n; ++j){
           // /if(ar[i] == '0')
            bit[i].set(j,ar[i][j]-'0');
          // else

        }
    }
    printf("%lld\n",solve());
   return 0;
}

F Partition problem

题意：

将个人分到两个team，每个team右m个人，如果i,j两个人位于不同的team，那么收益增加 ,求分配的最大收益

分析：

暴力枚举+加预处理可过(评测机抖动的厉害)

参考代码:

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40981102

G Polygons

题意：

平面上有n条直线，求着n条直线形成的所有闭多边形的面积

分析：

PSLG（平面直线图）模板题，建议学习《算法竞赛入门经典训练指南》的板子

参考代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40979712

H Second Large Rectangle

题意：

求第二大子矩阵

分析：

利用单调栈求最大值，在最大值的基础上选择将 长度-1，宽度-1，取次大值

参考代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40973800

I Inside A Rectangle

题意：

给定一个的矩阵，矩阵元素, 最多可以选择两个矩形，求两个矩阵不想交部分的元素和的最大值

分析：

考虑所有情况即可，具体情况见代码以及注释

代码参考

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40981082

J Subarray

题意：

存在一个的数列，有n个区间值为1，其它的都为-1，求有多少个区间的值大于0

分析：

1. 所有的1区间的长度的和为,那么区间和大于0的区间数最大是
2. 我们将所有的区间和可能大于0的区间都处理出来，怎么确定这样的区间呢？考虑判断两个1区间能否合并的条件 这段区间值为-1，我们需要从r[i] 向左的最大的区间和和l[i+1]向有的区间和大于 ,所以预处理出来 从r[i]为右端点的区间最大值，以l[i] 为左端点的最大值

1. 可以合并的区间一起处理，考虑移动右端点，要查询有多少左端点的前缀和小于,可以用树状数组来做，但是复杂度过高，考虑到 每次sum[i] 与sum[i-1] 的值差1，所以我们可以利用上一次计算的结果。
2. 假如当前值是1，小于的个数为个，当前的那么我们只需要加上 就可以了
3. 假设当前值是-1，小于的个数为个，当前的那么我们需要减去

参考代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int maxn = 1e6+10;
int inf = 1e9;
int l[maxn],r[maxn];
int suf[maxn],pre[maxn];// pre[i] 代表以 r[i] 为右端点的最大值是多少,suf[i] 代表以l[i] 为左端点的最大值是多少
const int maxm = 2e8+10;
bool vis[maxm];
int cnt[maxm];
int main(void){

  int n;cin>>n;
  for(int i = 1;i <= n; ++i){
    scanf("%d%d",&l[i],&r[i]);
  }
  pre[1] = r[1]-l[1]+1;
  for(int i = 2;i <= n; ++i){
    pre[i] = r[i]-l[i]+1+max(pre[i-1]-(l[i]-r[i-1]-1),0);
  }

  suf[n] = r[n]-l[n]+1;
  for(int i = n-1;i >= 1; --i){
    suf[i] = r[i]-l[i]+1+max(suf[i+1]-(l[i+1]-r[i]-1),0);
  }
  int k = 1;
  LL res = 0;
  while(k <= n){
    int j = k;
    while(j < n && (pre[j]+suf[j+1] >= l[j+1]-r[j]-1))
      ++j;
    int lb = max(0,l[k]-suf[k]),ub = min(inf-1,r[j]+pre[j]);


    for(int i = k;i <= j; ++i)
      for(int m = l[i];m <= r[i]; ++m)
        vis[m-lb] = 1;
    LL ans = 0;
    int t = 1e8;
    cnt[t] = 1;// 这里的t代表0
    for(int i = lb;i <= ub; ++i){
       if(vis[i-lb]) ans += cnt[t],cnt[++t]++;
       else ans -= cnt[t-1],cnt[--t]++;
       res += ans;
    }
    t = 1e8;
    for(int i = lb; i <= ub; ++i){
      if(vis[i-lb])
          cnt[++t]--;
      else
          cnt[--t]--;  
      if(vis[i-lb])
        vis[i-lb] = 0;      

    }
    k = j+1;
  }

  cout<<res<<endl;




  return 0;
}