【题解】牛客练习赛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;
} 
