A 膜法记录

Solution

$观察数据范围 n很小，用状压dp的思想考虑二进制枚举选择的行，二进制位为1的表示选择该行$
$对于剩下的列部分直接暴力找有多少列仍然有敌人, 详情看代码及注释$
$时间复杂度O（2^n*n*m）$

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int vis[50];
char maze[22][100005];
int main(){
  int t;
  cin >> t;
  while(t--){
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        cin >> maze[i][j];
      }
    }
    int flag = 0;
    for(int i = 0; i < (1LL << n); i++){
      int num = 0;
      memset(vis, 0, sizeof(vis));
      for(int j = 0; j < n; j++){
        if((i >> (n - j - 1)) & 1){
          num++; // 二进制有多少个1  第几个为1 说明选择第几行
          vis[n - j] = 1;
        }
      }
      if(num != a){ 
        continue;
      }
      vector<int> v(m + 1);
      for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        for(int j = 1; j <= m; j++){
          if(maze[i][j] == '*')
            v[j]++; // j列有敌人
        }
      }
      int cnt = 0;
      for(int i = 1; i <= m; i++){
        if(v[i] > 0) cnt++;
      }
      if(cnt <= b){ // 剩下有敌人的列大于b
        cout << "yes\n";
        flag = 1;
        break;
      }
    }
    if(!flag){
      cout << "no\n";
    }
  }
  return 0;
}

B 阶乘

Solution

$看起来没啥思路, 我们考虑打个表上OEIS$

图片说明

$(非OEIS做法)其实我们先质因数分解，然后暴力枚举质因子的倍数即可$

Code1(OEIS给的思路模拟)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
ll qpow(ll a, ll b){
  ll res = 1;;
  while(b){
    if(b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
ll pre[30];
map<ll, ll> mp;
ll solve(ll p){
  ll ans = 0;
  ll pre = p;
  int flag = 0;
  for(ll i = 2; i * i <= p; i++){
    if(p % i == 0){
      flag = 1;
      break;
    }
  }
  if(!flag){
    return p; // prime 素数直接输出
  }
  vector<pair<ll, ll> > v;
  for(ll i = 2; i * i <= p; i++){
    if(p % i == 0){
      ll cnt = 0;
      while(p % i == 0){
        p /= i;
        cnt++;
      }
      v.push_back({i, cnt}); // 质因数分解
    }
  }
  if(p > 1){
    v.push_back({p, 1});
  }
  flag = 0;
  for(int i = 0; i < v.size(); i++){
    if(v[i].second > 1){
      flag = 1;
      break;
    }
  }
  if(!flag){
    return v[v.size() - 1].first;
  }
  else if(v.size() == 1 && v[0].second <= v[0].first){
    return v[0].first * v[0].second;
  }
  else if(v.size() == 1){
    ll prime = v[0].first;
    for(ll i = prime; ; i += prime){
      int cnt = 0;
      pre = i;
      while(pre % prime == 0){
        pre /= prime;
        cnt++;
      }
      v[0].second -= cnt;
      if(v[0].second <= 0){
        return i;
      }
    }
  }
  else {
    ll ans = 0;
    for(int i = 0; i < v.size(); i++){
      ans = max(ans, solve(qpow(v[i].first, v[i].second)));
    }
    return ans;
  }
}
int main(){
  int n;
  cin >> n;
  pre[1] = 1;
  for(ll i = 2; i <= 20; i++){
    pre[i] = pre[i - 1] * i; 
    mp[pre[i]] = i;
  }
  while(n--){
    ll p;
    cin >> p;
    if(mp[p]){
      cout << mp[p] << "\n";
      continue;
    }
    else cout << solve(p) << "\n";
  }
  return 0;
}

Code2(待补QAQ)

C 完全图

Solution

$一开始以为是个图论，看了下数据范围n, m <= 1e18, 显然是个结论题$
$我们考虑完全图的特点, 每一个点都与其他(n - 1)个点有(n - 1)条边相连$
$那么我们要使得连通分量尽可能多需要尽可能地让每一个点孤立$
$即对于第一个点，我们删去与相连的 (n - 1) 条边，此时有2个连通分量$
$对于第二个点，我们删去与相连的 (n - 2) 条边，此时有3个连通分量$
$.....$
$于是删去的过程是 (n - 1) + (n - 2) + .... + 1的过程$
$我们可以二分模拟这个过程因为数据很大需要高精度我用了python$

Code

while True:
  try:
    t = int(input())
    while t > 0:
      t = t - 1
      n, m = map(int, input().split())
      left = 0
      right = n - 1
      ans = 0
      while left <= right:
        mid = (left + right) // 2
        if ((n - 1 + n - mid) * mid //  2) <= m:
          ans = mid
          left = mid + 1
        else:
          right = mid - 1
      print(ans + 1)
  except EOFError:
    break

D 病毒传染

Solution(待补QAQ)

E A+B问题

Solution

$签到,因为A 和 B 都在32位有符号整数能存储的范围内, 所以在考虑自然溢出的特性下所有情况均为4294967296$

Code(python)

print('4294967296');

F 美丽的序列I

Solution(待补QAQ)

G 树上求和

Solution

$比赛时想了个假的算法, 卡了两个小时....$
$一开始想的是先从叶子染色(类似拓扑排序的思想) 然后贴个树上任意两点距离和的板子(只能过60%样例)$
$正确做法:树形dp处理出每条路径要走的次数, 排序后赋值即可$
$那么如何处理出要走的次数呢？$
$考虑sum[i] 是以i为根的子树拥有的节点数$
$那么假设把这个点作为树上的划分点，左边有sum[i]个点，右边有n - sum[i]个点$
$显然经过这个点的次数是左边的点去往右边的点的路径数量,即sum[i] * (n - sum[i])$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
struct Edge{
    int v, nextz;
    ll w;
}E[N << 1];
int head[N], tot;
void init(){
    memset(head, -1, sizeof(head));
    tot = 0;
}
int n;
ll sum[N];
void add(int u, int v, ll w){
    E[tot].v = v;
    E[tot].w = w;
    E[tot].nextz = head[u];
    head[u] = tot++;
}
ll dp[N], sz[N], val[N];
ll ans = 0;
void dfs(int u, int fa) {
    sum[u] = 1;
    for (int i = head[u]; ~i; i = E[i].nextz) {
        int v = E[i].v;
        if (v == fa)
            continue;
        dfs(v, u);
        sum[u] += sum[v];
    }
}
ll cal[N];
void solve(int u, int fa) {
    for (int i = head[u]; ~i; i = E[i].nextz) {
        int v = E[i].v;
        ll w = E[i].w;
        if (v == fa)
            continue;
        cal[w] += sum[v] * (n - sum[v]);
        solve(v, u);
    }
}
bool vis[N];
int se[N];
int main(){
  init();
  cin >> n;
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    add(u, v, i);
    add(v, u, i);
  }
  dfs(1, -1);
  solve(1, -1);
  ll ans = 0;
  for(int i = 1; i <= n - 1; i++){
    se[i] = i;
  }
  sort(se + 1, se + n, [](int x, int y){return cal[x] < cal[y];});
  ll color = n - 1;
  for(int i = 1; i <= n - 1; i++){
    ans += color * cal[se[i]];
    color--;
  } 
  cout << ans << "\n";
  return 0;
}

H 奇怪的背包问题增加了

Solution

$首先考虑如何判断是否有方案成立$
$把2的30次方看成二进制位的第31位为1，然后寻找方案$
$我们知道高位的数字可以由低位配凑, 所以我们从低位开始满2进位$
$最终检验能否配凑出2的30次方$
$然后再考虑可行方案, 我们用num[i] 表示原来拥有的2^i的数量$
$从高位开始构造可行方案即可$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
int a[N], vis[50], num[50];
int main(){
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    memset(vis, 0, sizeof(vis));
    memset(num, 0, sizeof(num));
    for(int i = 1; i <= n; i++) cin >> a[i], vis[a[i]]++, num[a[i]]++;
    for(int i = 0; i <= 29; i++){
      vis[i + 1] += vis[i] / 2;
      vis[i] %= 2;
    }
    if(!vis[30]){
      cout << "impossible\n";
      continue;
    }
    ll need = 1;
    vector<int> v(50);
    for(int i = 30; i >= 0; i--){
      if(num[i]){
        v[i] += min(need, 1LL *num[i]);
        need -= v[i];
        if(!need) break;
      }
      need *= 2;
    }
    for(int i = 1; i <= n; i++){
      if(v[a[i]]){
        cout << 1;
        v[a[i]]--;
      }
      else cout << 0;
    }
    cout << '\n';
  }
  return 0;
}

I 寻找子串

Solution

$签到,花里胡哨地写了个O(n^2)，好像可以O(nlogn)和O(n)(待补)$
$因为前缀相同的情况下肯定越长的字典序越大(比如aaab大于aaa)$
$于是考虑取所有后缀，找其中字典序最大的子串即可$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e3 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
string pre[N];
int main(){
  int n;
  string s;
  cin >> s;
  int pos = 0;
  string ans;
  string t = "";
  for(int i = s.size() - 1; i >= 0; i--){
    t = s[i] + t;
    pre[i] = t;
  }
  for(int i = 0; i < s.size(); i++){
    ans = max(ans, pre[i]);
  }
  cout << ans << "\n";
  return 0;
}

J 最大的差

Solution

$签到,sort后最大减最小即可$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
ll a[N];
int main(){
  int t;
  t = 1;
  while(t--){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
      cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    cout << a[n] - a[1] << "\n";
  }
  return 0;
}

牛客小白月赛23题解

A 膜法记录

Solution

Code

B 阶乘

Solution

Code1(OEIS给的思路模拟)

Code2(待补QAQ)

C 完全图

Solution

Code

D 病毒传染

Solution(待补QAQ)

E A+B问题

Solution

Code(python)

F 美丽的序列I

Solution(待补QAQ)

G 树上求和

Solution

Code

H 奇怪的背包问题增加了

Solution

I 寻找子串

Solution

J 最大的差

Solution

Code