【题解】牛客练习赛76

A.校园活动

因为如果能够进行分组，那么每个组的总熟悉度是相同的

所以枚举最左边的组的总熟悉度的所有可能进行验证，特判所有都为0的情况。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
int sum[1005];
string s;
int solve()
{
    if(sum[n]==0)
        return n;
    for(int i=1;i<n&&sum[n]-sum[i];i++)
    {
        int tmp=sum[i];
        int tmpsum=0;
        for(int i=1;i<=n;i++)
        {
            tmpsum+=s[i-1]-48;
            if(tmpsum==tmp)
                tmpsum=0;
            if(tmpsum>tmp)
                break;
        }
        if(tmpsum==0)
            return sum[n]/tmp;
    }
    return -1;
}
int main()
{
    cin >> n;
    cin >> s;
    for(int i=0;i<n;i++)
        sum[i+1]=sum[i]+s[i]-48;
    cout << solve() << endl ;
    return 0;
}

B.zzugzx (vs) Kurisu

记忆化搜索+简单的算期望(另外看到有人是直接递推的,没细看,大家可以去康康)

注意到这个范围给的很奇葩

因为要根据对手和自己当前的状况来决策,所以维护两个进制数几乎是必须的

然后如果在一个位置填上,仍然不能判断是否被填充,所以把映射到变成进制数

表示当前先手数字为,后手数字为的获胜概率,然后去记忆化暴搜

每次枚举当前摇到的点数,然后对可能放置的每一个位置取最大(先手),取最小(后手)

个人认为不恐怖但很有意思的一题!!!

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double f[5009][5009];
int n,m,ok[5009][5009];
double dfs(int tim,int a,int b)
{
    if( tim==0 )    return 1.0*(a>b);
    if( ok[a][b] )    return f[a][b];
    ok[a][b] = 1;
    if( tim%2==0 )
    {
        for(int i=1;i<=m;i++)
        {
            double maxx = 0; int now = a, base = i;            
            for(int j=1;j<=n;j++)//每一位
            {
                if( now%(m+1)==0 )    maxx = max( maxx,dfs(tim-1,a+base,b) );
                now /= (m+1), base *= (m+1);    
            }
            f[a][b] += maxx/m; 
        }
    }
    else
    {
        for(int i=1;i<=m;i++)
        {
            double minn = 1; int now = b, base = i;            
            for(int j=1;j<=n;j++)//每一位
            {
                if( now%(m+1)==0 )    minn = min( minn,dfs(tim-1,a,b+base) );
                now /= (m+1), base *= (m+1);    
            }
            f[a][b] += minn/m; 
        }
    }
    return f[a][b];
}
int main()
{
    cin >> n >> m;
    printf( "%.7lf",dfs(n*2,0,0) );
}

C.CG的通关秘籍

总共的数字方式有,计算每个方案累加显然不可取

经典的贡献法,我们定义每个数字只在作为前面那个数时有贡献

数字只有放在有后继,可能产生贡献,放在这个位置的贡献相等

有个数比小,放在后继形成逆序,个数放后继形成顺序

这样的话,数字放在特定位置的贡献就是

所有数字放在这个位置的贡献就是

其实这样相当于固定了数字和它的后继,那么剩下个位置怎么放都有这样的贡献

所以答案为

D.魔物消灭计划

由于拥有同种宝石的城市之间可以直接传送而不消耗任何资源

所以实际上我们可以将拥有同种宝石的城市缩成一个个特殊点

再加上首都和祭坛我们也将它们看成两个特殊点

这样题目实际上就变成了求包含若干特殊点的最小生成树

这实际上是一个最小斯坦纳树的基本模型，套用即可得到解

#include <bits/stdc++.h>
using namespace std;

int cnt = 0, head[110],dp[110][1 << 10];;
struct Edge {
    int next, to, w;
} edge[510 << 1];
void init() {
  cnt = 0;
  memset(head, -1, sizeof(head));
  memset(dp, 0x3f, sizeof(dp));
}
void add_edge(int u, int v, int w) {
  edge[++cnt] = {head[u], v, w};
  head[u] = cnt;
}
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int>>> que;
bool vis[110];
void dijkstra(int s) {
  memset(vis, false,sizeof(vis));
  while (!que.empty()) {
    int u = que.top().second;
    que.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int to = edge[i].to;
      if (dp[to][s] > dp[u][s] + edge[i].w) {
        dp[to][s] = dp[u][s] + edge[i].w;
        que.push(make_pair(dp[to][s], to));
      }
    }
  }
}
int n,m,k,x,y,a[110],id[110];
signed main() {
  std::ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m >> k >> x >> y;
  id[x] = k + 1,id[y] = k + 2; k += 2;
  int num = k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (i == x || i == y) continue;
    if (a[i] == 0) id[i] = ++num;
    else id[i] = a[i];
  }
  n = num; init();
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    if (id[u] == id[v]) continue;
    add_edge(id[u], id[v], w);
    add_edge(id[v], id[u], w);
  }
  for (int i = 1; i <= k; i++) dp[i][1 << (i - 1)] = 0;
  for (int s = 1; s < (1 << k); s++) {
    for (int i = 1; i <= n; i++) {
      for (int subs = s & (s - 1); subs; subs = s & (subs - 1)) {
        dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]);
      }
      if (dp[i][s] != 0x3f3f3f3f) { que.push(make_pair(dp[i][s], i)); }
    }
    dijkstra(s);
  }
  int ans = 1e9;
  for (int i = 1; i <= n; i++) ans = min(ans, dp[i][(1 << k) - 1]);
  cout << ans << '\n';
  return 0;
}

E.牛牛数数

线性基+(dp|二分)都可

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct linearbasis {
    ll base[64], flag, cnt;

    void add(ll x) {
        for(int i = 62; ~i; i--) {
            if(x >> i & 1) {
                if(!base[i]) {
                    base[i] = x;
                    return ;
                }
                x ^= base[i];
            }
        }
        flag = 1;
    }

    void rebuild() {
        cnt = 0;
        for(int i = 62; i >= 0; i--) {
            for(int j = i - 1; j >= 0; j--) {
                if(base[i] >> j & 1) {
                    base[i] ^= base[j];
                }
            }
        }
        for(int i = 0; i <= 62; i++) {
            if(base[i]) {
                ll temp = base[i];
                base[i] = 0;
                base[cnt++] = temp;
            }
        }
    }

    ll query_k(ll k) {
        k -= flag;
        if(k == 0) return 0;
        if(k >= 1ll << cnt) return -1;
        ll ans = 0;
        for(int i = 62; ~i; i--) {
            if(k >> i & 1) {
                ans ^= base[i];
            }
        }
        return ans;
    }
    void init() {
        memset(base, 0, sizeof base), flag = cnt = 0;
    }
}a;

int main() {
//     freopen("9.in", "r", stdin);
//     freopen("9.out", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll k, x;
    int n;
    scanf("%d %lld", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &x);
        a.add(x);
    }
    a.rebuild();
    ll l = 1, r = (1ll << a.cnt) - 1 + a.flag;
    while(l < r) {
        ll mid = l + r >> 1;
        if(a.query_k(mid) <= k) l = mid + 1;
        else r = mid;
    }
    if((l == (1ll << a.cnt) - 1 + a.flag) && a.query_k(l) <= k) l++;
    ll total = (1ll << a.cnt) - 1 + a.flag, now = l;
    printf("%lld\n", total - now + 1);
    return 0;
}

F.phi and phi

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 1e9 + 7;

int prime[N], phi[N], cnt, n;

ll ans[N];

bool st[N];

void init() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for(int i = 1; i < N; i++) {
        int sum = 0;
        for(int l = i, r; l < N; l += i) {
            sum = (sum + phi[l]) % mod;
            r = l + i; // l + i - 1
            ans[l] = (ans[l] + 1ll * sum * sum % mod * phi[i] % mod) % mod;
            if(r < N) ans[r] = (ans[r] - 1ll * sum * sum % mod * phi[i] % mod + mod) % mod;
        } 
    }
    for(int i = 1; i < N; i++) {
        ans[i] = (ans[i] + ans[i - 1] + mod) % mod;
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}