牛客寒假基础训练1

官方题解地址：https://ac.nowcoder.com/acm/contest/9981
####A
题意：输出所有含有子序列"us"并且长度为n的字符串
计数dp：

$dp[i][0]代表当前长度为i，并且不存在u的字符串的个数$

$dp[i][1]代表当前长度为i，并且存在u但是不存在s的字符串的个数$

$dp[i][2]代表当前长度为i，并且存在u和s的字符串的个数$

由于当dp[i][2]不为0时，dp到当前位置刚好存在us两个字符，因此不存在冲突现象

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000010, mod = 1e9 + 7;

typedef long long ll;

int n;
ll dp[N][3];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

    cin >> n;
    dp[0][0] = 1;


    for(int i = 1; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] * 25) % mod;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 25) % mod;
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 26) % mod;
    }

    ll res = 0;
    for(int i = 1; i <= n; i++) res = (res + dp[i][2]) % mod;
    cout << res << '\n';

  return 0;
}

B

构造刚好为k的括号匹配，并使最终字符串的长度在100000以内。
假如字符串的构造形式像这样：()()()()
令n为完整括号形式，上面这个的n = 4
那么所能构造的括号匹配数量为 $n * (n + 1) / 2$
自然还会剩下一些，那么在剩下的内些数量的括号位置加上一个）即可
比如要构造13个匹配，而()()()()只能构造12给匹配，那么在第一对括号后面加上一个）即可
即:())()()()

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  long long k, n = 1;
  cin >> k;

  if(!k) {
      cout << "(" ;
      return 0;
    }

  while(n * n + n <= 2 * k) {
      n++;
    }
  n--;
  long long tmp = k - (n * n + n) / 2;
  string res;
  for(int i = 1; i <= n; i++)
      if(i == tmp) {
          res += "())";
          cout << "())";
        }
      else {
          res += "()";
          cout << "()";
        }
  return 0;
}

F

最大的即为相同的个数 * 2 + 不同个数，最下为0

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;
int n;

char a[N], b[N];


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;

  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];

  int cnt = 0;
  for(int i = 0; i < n; i++) 
      if(a[i] == b[i]) cnt++;
  cout << n + cnt << ' ' << 0 << '\n';
  return 0;
}

I

由于k <= n / 2，并且偶数为n / 2个，那么能构成k-1个gcd为2的序列，最后再在末尾添加一个能整除该末尾偶数的数即可

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 100010; 

bool vis[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  vector<int> res;

  if(n <= 3) {
      if(k) cout << -1;
      else for(int i = 1; i <= n; i++) cout << i << ' ';
      return 0;
    }

  if(n == 4) {
      if(k == 1) cout << "1 2 4 3";
        else if(k == 0) cout << "1 2 3 4";
        else cout << -1;
        return 0; 
    }

  if(n == 5) {
      if(k == 1) cout << "1 2 4 3 5";
      else if(k == 0) cout << "1 2 3 4 5";
      else cout << -1;
        return 0;
    } 

    if(k == n / 2) {
        for(int i = 2, j = 0; j < k; j++, i += 2) {
            res.push_back(i);
            vis[i] = true;
        }
        for(int i = 3; i <= n; i += 2) {
            if(res.back() % i == 0) {
                res.push_back(i);
                vis[i] = true;
                break ;
            } 
        }
        for(auto x : res) cout << x << ' ';
      for(int i = 1; i <= n; i++) if(!vis[i]) cout << i << ' ';
    } else {
        for(int i = 2, j = 0; j <= k; j++, i += 2) {
            res.push_back(i);
            vis[i] = true;
        }
        for(auto x : res) cout << x << ' ';
      for(int i = 1; i <= n; i++) if(!vis[i]) cout << i << ' ';
    }

  return 0;
}

C

转载他人做法https://blog.nowcoder.net/n/32e7a9e7caa3422286109ab0b3fabf37

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = N << 1;

int n;
int h[N], e[M], ne[M], idx;
int f[N], col[N], cnt;
bool ok = true;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
} 

void dfs1(int u, int fa) {
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == fa) continue ;
        dfs1(j, u);
    }
    if(!f[u]) {
        if(fa == -1 || f[fa]) ok = false;
        f[fa] = f[u] = ++cnt;
    }
}

void dfs2(int u, int fa) {
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == fa) continue ;
        if(f[j] == f[u]) col[j] = col[u];
        else col[j] = col[u] ^ 1;
        dfs2(j, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(h, -1, sizeof h);

    cin >> n;
    for(int i = 0, a, b; i < n - 1; i++) {
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    dfs1(1, -1);
    if(!ok) {
        cout << -1 << '\n';
        return 0;
    } 

    col[1] = 1;
    dfs2(1, -1);

    for(int i = 1; i <= n; i++) 
        if(col[i])  cout << 'B';
        else cout << 'R';
    return 0;
}

J

LCM的组合一定是质数的最高次幂，因此考虑求质数的最高次幂
对于2来说，其能贡献的最高次幂为k，那么最终应该是 $图片说明$ 其中k为最大的次幂，贡献为2的k次幂
对于大于2的质数应满足k， $图片说明$ 贡献为p的k次幂

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 80010000, mod = 1e9 + 7;

typedef long long ll;

int n;
bool vis[N];
int prime[5000010], cnt;

void init() {
    for(int i = 2; i < N; i++) {
        if(!vis[i]) prime[cnt++] = i;
        for(int j = 0; 1ll * i * prime[j] < N ; j++) {
            vis[prime[j] * i] = true;
            if(i % prime[j] == 0) break ;
        }
    }
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

    init(); 

    cin >> n;

    if(n < 6) {
        cout << "empty" << '\n';
        return 0;
    }

    ll res = 1;

    for(int i = 0; i < cnt && prime[i]  <= n / 2; i++) {
        int p = prime[i];
        if(p == 2) {
            ll tmp = 1;
            while(tmp * p  <= n / 3) tmp *= p;
            res = res * tmp % mod;
        } else {
            ll tmp = 1;
            while(tmp * p  <= n / 2) tmp *= p;
            res = res * tmp % mod; 
        }
    }

    cout << res << '\n';
  return 0;
}