水博客太快乐了
烤场
顺序开题。
啥也不会。。。
写了 \(t1, t3, t4\) 的暴力，t2懒就没有写，发现了 \(t4\) 的一些结论，但是不全，最终也没有什么用处。。。
最后十分钟想出 \(t3\) 正解，没来的及写，考完写了就过了。。。
总之貌似烤的挺炸的。。全是暴力。。。
分数
预估 ：\(t1 \ 30pts \ + \ t2 \ 0pts \ + \ t3 \ 50pts \ + \ t4 \ 50pts \ = \ 130pts\)
实际 ：\(t1 \ 30pts \ + \ t2 \ 0pts \ + \ t3 \ 50pts \ + \ t4 \ 30pts \ = \ 110pts\)
题解
A. 如何优雅的送分
本蒟蒻对这种数论的理解也并不是很深刻，建议移步巨佬 y_cx 的博客
B. 阴阳
巨佬cyh ：暴力踩标算，直接暴力踩过去。
记录巨佬的方法:用主席树记录点的颜色暴力 bfs 找答案。
C. 你猜是不是找规律
提供一个不同于题解的方法。。。
考试最后 \(10min\) 想到，没来得及写。
最开始想的 \(dp\) 状态是 ：\(f_{i,j}\) 表示长度为 \(i\) ，交换 \(j\) 次后变为顺序的排列数量，转移类似错排数的递推式，但是这样转移显然是 \(O(nk)\) 的，直接 \(T\) 飞。考虑优化。
发现 \(k\) 小的可怜，而 \(n\) 大的可怕，因此在最终的到的序列中，大部分的数都是有序的，只有少部分数无序，因此考虑只对无序的数进行 \(dp\) ，设计状态为 ：\(f_{i,j}\) 表示长度为 \(i\) ，交换 \(j\) 次会变有序的错排列数量 （指 \(\forall i, a_i \ne i\)）。
转移也类似与错排数，此处只给出转移，不加以赘述。。。
不难发现只要求出 \(i \le 2k ,j \le k\) 的所有情况即可（因为总共就这么几种情况。。。），复杂度 \(O(k^2)\) 。
最终的答案就是将求出的所有无序序列插入一个有序序列即可。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e3+10, mod=1e9+7;
inline int read(){
int f=1, x=0; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
return f*x;
}
int n, k, ans, f[4][N], sum[N<<1];
inline int qp(int n, int m){
int ans=1;
while(m){
if(m&1) (ans*=n)%=mod;
m>>=1; (n*=n)%=mod;
}
return ans;
}
inline int C(int n, int m){
int mul=1, inv=1;
for(int i=n-m+1; i<=n; ++i) (mul*=i)%=mod;
for(int i=1; i<=m; ++i) (inv*=i)%=mod;
return mul*qp(inv, mod-2)%mod;
}
signed main(void){
n=read(); k=read(); f[0][0]=1; sum[0]=1;
for(int i=2; i<=k<<1; ++i){
memset(f[i%3], 0, sizeof(int)*(k+1));
for(int j=1; j<=k; ++j)
f[i%3][j]=(i-1)*(f[(i-1)%3][j-1]+f[(i-2)%3][j-1])%mod;
for(int j=0; j<=k; ++j) (sum[i]+=f[i%3][j])%=mod;
}
for(int i=0; i<=k<<1; ++i)
(ans+=sum[i]*C(n, i)%mod)%=mod;
printf("%lld\n", ans);
}
D. 小说
首先 \(a\) 很好求，依次删去每个数跑一次背包，得到能容量种类数最多的即是 \(a\) 。这一定是正确的，设当前最大容量为 \(maxn\) ，种类数量为 \(num\) ，则一定可以使 \(b=maxn+1\) ，种类数会便为 \(2num+1\)。
可以用退背包的技巧，也可以用 \(bitset\) 优化。
接下来求 \(b\) ，考虑 \(b\) 需要满足什么条件，对于任意两个合法容量 \(x, y, x \le y\) ，都有 \(x+b \ne y\)，即 \(b \ne x-y\) 。
\(x, y\) 是由 \(v\) 构成的，那么 \(b\) 就不可以由 \(v\) 之间相互加减得到，也就是将所有 \(v_i, -v_i\) 放在一起跑一个背包，最小无法被构成的数即为最小的 \(b\) 。
code
#include<bits/stdc++.h>
using namespace std;
const int N=110, V=7e5+10;
inline int read(){
int f=1, x=0; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
return f*x;
}
int n, a[N], maxn, a1, b1, sum;
bitset<V> ul;
signed main(void){
n=read();
for(int i=1; i<=n; ++i) sum+=a[i]=read();
sort(a+1, a+1+n);
for(int i=1; i<=n; ++i){
ul.reset(); ul[0]=1;
for(int j=1; j<=n; ++j){
if(i==j) continue;
ul|=(ul<<a[j]);
}
int num=ul.count();
if(num>maxn) maxn=num, a1=i;
}
ul.reset(); ul[0]=1;
for(int i=1; i<=n; ++i){
if(i==a1) continue;
ul|=(ul<<a[i]);
}
for(int i=1; i<=n; ++i){
if(i==a1) continue;
ul|=(ul>>a[i]);
}
for(int i=1; i<=sum-a[a1]+1; ++i)
if(!ul[i]) { b1=i; break; }
printf("%d %d\n", a[a1], b1);
return 0;
}
summary
成为了史上最水博客。。。