比赛链接

A.ZYB的测验计划

problem

有\(m\)道题，\(n\)个人，每个人对于每道题都有一个答案且每个人都可能来或不来，求出对于所有可能的\({2^m-1}\)个题目子集，每个子集有多少是有区分度的。一个题目子集有区分度当且仅当子集中的每个题都有人回答NO也也有人回答YES。

\(n\le 10^5,m\le15\)

solution

暴力出奇迹

用\(f(S)\)表示S这个集合中的题目全都没有区分度的方案数，其他的题目随意。求出f之后容斥一下就能得到答案。

考虑如何求\(f(S)\)。我们先枚举集合\(S\)，既然没有区分度，那么集合S中的元素必须全是YES或全是NO。枚举S的子集，然后求出与这些子集在S这个集合中的位置都恰好相等的数量。计算一下即可。

code

/*
* @Author: wxyww
* @Date: 2020-06-05 10:45:24
* @Last Modified time: 2020-06-05 18:46:44
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 1 <<16,mod = 998244353;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c <'0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
int n,m;
namespace BF1 {
int f[N],sum[N],cnt[N],tsum[N],mi[100010];//f(S)表示集合S中的题目全都没有区分度的方案数
char s[21];
void getf(int x) {
memset(tsum,0,sizeof(tsum));
for(int i = 0;i <(1 < tsum[i & x] += sum[i];
}
for(int i = x;;i = (i - 1) & x) {
if(tsum[i])
f[x] += (mi[tsum[i]] - 1);
// if(x == 3) printf("%d %d\n",i,mi[tsum[i]]);
f[x] >= mod ? f[x] -= mod : 0;
if(!i) break;
}
f[x]++;
f[x] %= mod;
}
void main() {
mi[0] = 1;
for(int i = 1;i <= n;++i) {
mi[i] = (mi[i - 1] <<1) % mod;
scanf("%s",s + 1);
int t = 0;
for(int j = 1;j <= m;++j)
t = t <<1 | (s[j] - '0');
sum[t]++;
}
for(int i = 0;i <(1 < cnt[i] = cnt[i >> 1] + (i & 1);
for(int i = 0;i <(1 < getf(i);
// cout< ll anss = 0;
for(int i = 1;i <(1 < ll ans = 0;
for(int j = i;;j = (j - 1) & i) {
int k = 1;
if(cnt[j] & 1) k = -1;
ans += k * f[j];
ans %= mod;
if(!j) break;
}
ans = (ans + mod) % mod;
anss ^= ans;
}
cout< }
}
int main() {
n = read(),m = read();
// if(m <= 10) {
BF1::main();return 0;
// }
return 0;
}


B.function

咕咕咕

C.光滑序列

problem

对于一个长度为\(n\)的序列，说他是光滑的当且仅当任意\(K\)个相邻元素的和都是\(S\)。给出一个长度为\(n\)的非负整数序列，问至少需要修改多少个元素才能使序列A变成光滑的序列。

\(k\le n\le 5000,0\le A_i\le S\le 5000\)

solution

显然模\(k\)意义下相等的位置要放的数字必须是相等的。所以把模\(k\)意义下相等的位置放到一起进行\(dp\)。

用\(f[i][j]\)表示前i个位置和为j最多不需要修改的元素数量。然后我们枚举一下所有对k取模为i的位置中的数字进行转移，即加入一种数字x在模k为i的位置出现过y次，那么就有\(f[i][j] = max(f[i][j],f[i-1][j-x]+y)\)。

那么如果第i个位置我们不修改成已有的位置，应该怎么转移呢。

因为不修改成已有位置造成的贡献是固定的。如果我们修改成\(x\)，那么就有\(f[i][j] = max(f[i][j],f[i-1][j-x])\)。前缀和优化一下即可。

最后答案就是\(n-f[k-1][S]\)

code

/*
* @Author: wxyww
* @Date: 2020-06-05 07:56:07
* @Last Modified time: 2020-06-05 08:50:29
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 5004;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c <'0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
int w[N][N],f[N][N],sum[N][N];
vectora[N];
vector::iterator it;
int main() {

// freopen("1.in","r",stdin);
int n = read(),K = read(),S = read();
for(int i = 0;i int x = read();
if(!w[i % K + 1][x])
a[i % K + 1].push_back(x);
w[i % K + 1][x]++;
}
memset(f,-0x3f,sizeof(f));
f[0][0] = 0;
for(int i = 1;i <= K;++i) {
for(int j = 0;j <= S;++j) {
for(it = a[i].begin();it != a[i].end();++it) {
if(j <(*it)) continue;
f[i][j] = max(f[i][j],f[i - 1][j - (*it)] + w[i][*it]);
}
sum[i][j] = f[i][j] = max(f[i][j],sum[i - 1][j]);
if(j) sum[i][j] = max(sum[i][j],sum[i][j - 1]);

}
}
cout< return 0;
}


===================================================================================