省流：\(55+5+0+10=70\)
简称：唐诗
T1
第一眼发现在二进制下加法不能进位，然后码了个 DP 就放那了……
DP 代码：
int S=(1<<14)|1;
fd(i,0,r[1]) f[1][i]=1;
fd(i,2,n)
{fd(j,0,S){f[i][j]=f[i-1][j];for(int s=j;s;s=(s-1)&j){(f[i][j]+=(s<=r[i])*f[i-1][j-s])%=mod;}}
}
ans=0;
fd(i,0,S) (ans+=f[n][i])%=mod;
正解的话，这里给一个记忆化代码：
int DP(int msk,int x)
{if(x<0) return 1;if(f[msk][x]) return f[msk][x];int res=0;fd(i,1,n){if((r[i]>>x&1)||(msk>>i)&1){int mask=msk;fd(j,1,n){if(i==j) continue;if((r[j]>>x)&1) mask|=(1<<j);}(res+=DP(mask,x-1))%=mod;}}int mask=msk;fd(j,1,n) if((r[j]>>x)&1) mask|=(1<<j);(res+=DP(mask,x-1))%=mod;return f[msk][x]=res;
}
T2
就写了个暴力……
正解人类智慧+三分（）
核心代码（一个大佬的）：
struct Tuple {int a, b, t;
} s[N];Tuple Merge(Tuple x, Tuple y) { return {x.b + y.b, x.a + y.a, 1 - x.t - y.t}; }
Tuple Move(Tuple x, int t) { return {x.a + t * 3, x.b - t * 3, x.t - t * 2}; }vector<Tuple> tu;inline int Calc(Tuple i) { return sum[i.a] - (sum[n] - sum[i.a]) + k * i.t; }signed main() {n = read(), q = read();for (int i = 1; i <= n; ++i) a[i] = read();sort(a + 1, a + 1 + n, [&](int x, int y) { return x > y; });for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];for (int i = 1; i <= n; ++i) s[i] = {1, 0, 0};for (int i = 2; i <= n; ++i) s[i] = Merge(s[i], s[i - 1]);Tuple tt = s[n];while (tt.a - 3 >= 0) tt = Move(tt, -1);do {tu.push_back(tt);tt = Move(tt, 1);} while (tt.b >= 0);while (q--) {k = read(), ans = -9E18;int l = 0, r = tu.size();while (l + 3 < r) {int ml = l + (r - l) / 3;int mr = r - (r - l) / 3;if (Calc(tu[ml]) > Calc(tu[mr]))r = mr;elsel = ml;}for (int i = max(0ll, l - 1); i <= min((int)(tu.size() - 1), r + 1); ++i)ans = max(ans, Calc(tu[i]));printf("%lld\n", ans);}return 0;
}
T3
赛时没看到下标从 \(0\) 开始，然后虚空调试半天……
正解还没写……
但是给出一个 \(20\) 分的核心代码：
int check(int x)
{fd(i,0,n-1) in[i]=0;fd(i,1,m){if((x>>(m-i))&1){in[e[i].x]++;in[e[i].y]++;}}int res=0;fd(i,0,n-1) if(in[i]&1) res++;return res;
}//然后这样枚举int S=(1<<(m))-1;
bd(i,S,0)
{int chk=check(i);if(chk>maxx){maxx=chk;ans=i;}
}
fd(i,1,m)
{cout<<((ans>>(m-i))&1);
}
T4
好像是个原，但是只写了 \(20\) 分的 DFS 序……
其实不用树剖的，但是赛时脑残写了个树剖……
然后还把暴力分的 \(DFS1\) 和 \(DFS2\) 搞反了，痛失 \(10\) 分……
