2019牛客国庆训练第一场

A. 全 1 子矩阵

题意:
给出一个01矩阵,问矩阵是否存在全是1的子矩阵

题解:
找出矩形四个角,看是否全是1,模拟即可。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

int n, m;
char a[15][15];


int main()
{
  while(~scanf("%d%d",&n, &m)){
      int cnt = 0;
      int x1 = 20;
      int x2 = 0;
      int y1= 20;
      int y2 = 0;
      for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
          cin >> a[i][j];
          if(a[i][j] == '1'){
            cnt ++;
            x1 = min(x1, i);
            x2 = max(x2, i);
            y1 = min(y1, j);
            y2 = max(y2, j);
          }
        }
      }
      if(cnt == (x2 - x1 + 1) * (y2 - y1 + 1)){
        puts("Yes");
      }
      else
        puts("No");
  }
  return 0;
}

B. 组合数

题意:
给定nk, 求\min \left( \frac{n!}{k!\left( n-k \right) !},10^{18} \right)的值。

题解:
C_{n}^{k}=\frac{n!}{k!\left( n-k \right) !}

=\frac{n\cdot(n-1)\cdot(n-2)\cdot\cdot\cdot(n-k+1)}{k\cdot(k-1)\cdot(k-2)\cdot\cdot\cdot1}

=\frac{n}{1}\cdot \frac{n-1}{k-1}\cdot \frac{n-2}{k-2}\cdot\cdot \frac{n-k+1}{k}

因为

C_{n}^{k}=C_{n}^{n-k}

所以当k>n/2时,使用C_{n}^{n-k}

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

ll C(ll n, ll m){
  if(n == 0 || n == m)  return 1ll;
  if(n == 0 || n == m)  return 1ll;
  if(m > n / 2) m = n - m;
  __int128 ans = (__int128)1;
  for(ll i = 1; i <= m; i ++){
    ans = ans * (n - i + 1) / i;
    if(ans > 1000000000000000000)
      return 1000000000000000000ll;
  }
  return (ll)ans;
}


int main()
{
  ll n, k;
  while(~scanf("%d%d", &n, &k)){
    printf("%lld\n", C(n, k));
  }

  return 0;
}

E. Numbers

题意:
给定一个字符串,让你分割数值范围在0-99的数字,求有多少种不同取值。

题解:
DFS爆搜,当不能往下一层搜索时返回。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e4 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

char s[100];
int ans = 0;
int len;
int vis[100];

void dfs(int u){
  if(u >= len){
    ans ++;
    return ;
  }
  int ne;
  for(int i = 1; i <= 2; i ++){
    if(i == 1){
      ne = s[u] - '0';
      if(vis[ne] == 0){
        vis[ne] ++;
        dfs(u + 1);
        vis[ne] --;
      }
    }
    else if(s[u] != '0' && u + 1 < len){
      ne = 10 * (s[u] - '0') + (s[u + 1] - '0');
      if(vis[ne] == 0){
        vis[ne] ++;
        dfs(u + 2);
        vis[ne] --;
      }
    }
  }
}


int main()
{
  while(~scanf("%s", s)){
    ans = 0;
    len = strlen(s);
    memset(vis, 0, sizeof(vis));
    dfs(0);
    printf("%d\n", ans);
  }
  return 0;
}

F. 4 Buttons

题意:
在一个网格上,初始点(0,0),有上下左右四个方向,每个方向最多走(b,d,c,a)步,求所有能走到不同点的取值。

题解:
找规律可发现时四个象限的点+中间的十字架

\frac{n\cdot(n-1)}{2}\cdot (ab+bc+cd+da)+(a+b+c+d)\cdot n + 1

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e4 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);
const int mod = 1e9 + 7;
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};


ll n, a, b, c, d;

ll ksm(ll a, ll b, ll mod){
  ll ans = 1ll % mod;
  while(b){
    if(b & 1) ans = ans * a % mod;
    b >>= 1;
    a = a * a % mod;
  }
  return ans;
}

int main()
{
  while(~scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d)){
    ll ans = 0;
    ll t = n * (n - 1) % mod * ksm(2, mod - 2, mod) % mod;
    ll k = ((((a * b) % mod + (b * c) % mod) % mod + (c * d) % mod) % mod + (d * a) % mod) % mod;

    ans = (1ll + (a + b + c + d) % mod * n % mod) + ((t * k) % mod) % mod;
    printf("%lld\n", ans % mod);
  }
  return 0;
}

C. Distinct Substrings

题意:
向字符串末尾添加任意字符所增加的不同子串个数

题解:
一个长度为n字符串的字串个数为\frac{n\cdot(n+1)}{2}
重复字串的个数为\sum{height}
当添加一个字符串所增加的不同字串个数为
\frac{(n+1)\cdot(n+2)}{2}-\sum{h1} - \frac{n\cdot(n+1)}{2} + \sum{h0}
化简得:
(n+1)-(\sum{h1 - \sum{h0}})

现在问题简化成求height数组的增量t。
如一个数组[1, 2, 1, 3, 1, 2, 1]如果末尾添加3的
出现4个重复的字串:
3和31213
13和131213
213和2131213
1213和12131213
所以现在需要求的就是这个原字符串以0为起点以i为结尾的子串和原字符串有多少公共后缀
倒过来就可以用扩展kmp来求公共前缀z[i](z[i]表示倒过来的字符串中以i为起点的后缀子串与倒过来的字符串的最长公共前缀)

求的z数组之后就可以计算p数组(p[i]表示在原字符串中添加i之后会得到比原字符串新加的重复子串个数(也就是t))

p[s[i]] = max(p[s[i]], z[i + 1] + 1)
因为在第i+1个数字有z[i+1]个公共前缀,所以添加i的话,就会多出z[i+1]+1个重复的子串。

代码:
扩展KMP:

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const double eps = 1e-8;
const int inf = 1e9;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

int n, m;
vector<int> s;



int Next[maxn];
int extend[maxn];   // extend[i] 表示 子串 T与 母串 S[i, n-1]的最长公共前缀
//预处理next 数组
void getNext(vector<int> str){
    int i = 0, j, po, len = n;
    Next[0] = len;
    while(i + 1 < len && str[i] == str[i + 1])   // 计算 next[1]
        ++i;
    Next[1] = i;
    po = 1; //初始化 po位置
    for(int i = 2; i < len; ++i){
        if(Next[i - po] + i < Next[po] + po){
            Next[i] = Next[i - po];
        }else{  //第二种情况,要继续匹配才能得到next[i]的值
            j = Next[po] + po - i;
            if(j < 0)
                j = 0;  //如果i>po+next[po],则要从头开始匹配
            while(i + j < len && str[j] == str[j + i])
                ++j;
            Next[i] = j;
            po = i;
        }
    }
}
//计算extend 数组,是求s1的extend,
//extend[i]代表的是s1[i]~s[n-1],与s2数组前缀的最大相同是多少。
void exkmp(vector<int> s1, vector<int> s2){// s2 是子串,s1是母串
    int i = 0, j, po, len = n, l2 = n;
    getNext(s2);
    while(i < l2 && i < len && s1[i] == s2[i])
        ++i;
    extend[0] = i;
    po = 0; //初始化po的位置
    for(i = 1; i < len; ++i){
        if(Next[i - po] + i < extend[po] + po){
            extend[i] = Next[i - po];
        }else{
            j = extend[po] + po - i;
            if(j < 0)
                j = 0;
            while(i + j < len && j < l2 && s1[j + i] == s2[j]){
                ++j;
            }
            extend[i] = j;
            po = i;
        }
    }
}





void solve(){
  for(int i = 0; i <= n; i ++){
        Next[i] = 0;
        extend[i] = 0;
    }
    reverse(s.begin(), s.end());
    exkmp(s, s);
    extend[0] = 1;
    vector<int> p(m + 1);
  for(int i = 0; i < n; i ++){
    p[s[i]] = max(p[s[i]], 1 + extend[i + 1]);
  }

  ll ans = 0, k = 3;
  for(int i = 1; i <= m; i ++){
    ans ^= k * (n + 1 - p[i]) % mod;
    (k *= 3) %= mod;
  }
  printf("%lld\n", ans);
}

int main()
{
  while(~scanf("%d%d", &n,&m)){
    s.resize(n);
    for(int i = 0; i < n; i ++){
      scanf("%d", &s[i]);
    }
    solve();
  }
  return 0;
}

Z算法:

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const double eps = 1e-8;
const int inf = 1e9;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

int n, m;
vector<int> s;
int z[maxn];


void get_z()
{
    int l=0,r=0;
    for (int i=1;i<n;i++)
    {
        if (i>r)
        {
            l=i,r=i;
            while (r<n && s[r-l]==s[r]) r++;
            z[i]=r-l,r--;
        }
        else
        {
            int k=i-l;
            if (z[k]<r-i+1) z[i]=z[k];
            else
            {
                l=i;
                while (r<n && s[r-l]==s[r]) r++;
                z[i]=r-l,r--;
            }
        }
    }
}





void solve(){
  for(int i = 0; i <= n; i ++){
        z[i] = 0;
    }
    reverse(s.begin(), s.end());
    get_z();
    vector<int> p(m + 1);
  for(int i = 0; i < n; i ++){
    p[s[i]] = max(p[s[i]], 1 + z[i + 1]);
  }

  ll ans = 0, k = 3;
  for(int i = 1; i <= m; i ++){
    ans ^= k * (n + 1 - p[i]) % mod;
    k = (k * 3) % mod;
  }
  printf("%lld\n", ans);
}

int main()
{
  while(~scanf("%d%d", &n,&m)){
        s.resize(n);
    for(int i = 0; i < n; i ++){
      scanf("%d", &s[i]);
    }
    solve();
  }
  return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注