\[暑假集训CSP提高模拟 \operatorname{EIJ}_{2}(6)-1 \]
\(\operatorname{EIJ}_{k}(A)\) 定义为有 \(A\) 个球，\(k\) 个盒子，盒子相同，球不同，把全部球放入的方案数
Hint
易知 \(\operatorname{EIJ}_k(A)=\dfrac{A^k}{k!}\)，详见 这篇文章
其实我觉得构造的过程更有意思：对一个给定的正整数 \(x\)，找到一组 \((A.k)\)，满足 \(x\times k!=A^{k}\)
我只简单 BrainStorm 了一组 \((6,2)\)，实际上这个问题还是十分有趣的.
A.符号化方法初探
当序列全为正数时，构造方法是显然的：从左到右依次将每一个数加上前一个数，这样总是可以保证每一个数比上一个数大. 操作次数严格 \(n-1\)
当序列全为负数时同理，只不过对负数的加法相当于减法. 因此我们考虑从后向前依次将每一个数加上后一个数，这样总是可以保证每一个数比下一个数小. 操作次数也为严格 \(n-1\)
考虑到先找出一个绝对值最大的数，然后将序列里其他所有的数都加上该数. 假设此数是正的，则操作后数列中全为正数（若存在一个 \(x\lt 0\) 使得 \(x+\max\lt 0\)，则有 \(\operatorname{abs}(x)\gt \operatorname{abs}(\max)\)，与假设不成立）. 同理，假设此数是负的，则操作后序列中全为负数. 按上述情况处理即可. 操作数严格 \(2n-2\)
#include<bits/stdc++.h>
//#include"test.h"
#define int long long
using namespace std;
int n,a[200001];
vector<pair<int,int>>cz;
signed main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%lld",&n);int maxn=0;int maxid=1;
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
if(abs(a[i])>abs(maxn)){
maxn=a[i];
maxid=i;
}
}
for(int i=1;i<=n;++i){
if(i!=maxid){
cz.push_back({maxid,i});
a[i]+=maxn;
}
}
if(maxn>0){
for(int i=1;i<=n-1;++i){
cz.push_back({i,i+1});
}
}
else{
for(int i=n;i>=2;--i){
cz.push_back({i,i-1});
}
}
cout<<cz.size()<<endl;
for(auto i:cz){
cout<<i.first<<" "<<i.second<<endl;
}
// freopen("CON","w",stdout);
// checker("test.in","test.out");
}
放一份 test.h
#include<bits/stdc++.h>
using namespace std;
long long aaa[1000001];
int checker(char*in,char*out){
ifstream f1,f2;
f1.open(out);
f2.open(in);
int n,m;f2>>n;
for(int i=1;i<=n;++i){
f2>>aaa[i];
}
f1>>m;
for(int i=1;i<=m;++i){
int x,y;
f1>>x>>y;
aaa[y]+=aaa[x];
}
bool ac=true;
for(int i=2;i<=n;++i){
if(aaa[i]<aaa[i-1]){
ac=false;
cout<<"Wrong Answer On Place: "<<i-1<<","<<i<<endl;
}
}
if(m>2*n){
ac=false;
cout<<"Too much operations:"<<m<<"(max is"<<2*n<<")"<<endl;
}
if(ac) cout<<"Accepted"<<endl;
return ac;
}
B.无标号 Sequence 构造
考虑到 \(A\times B\) 复杂度为 \(n^{3}\)，在 \(t\le 10^{4}\) 的情况下一定跑不过去，考虑如何优化.
可以想到：矩阵乘法虽然没有 \(A\times B=C\rightarrow T\times A\times B=T\times C\)，这样的规律，但是假如我们真的这样干了，出错概率好像不大. 将矩阵想象成高维向量，会发现只有向量点乘相等的那个球面里的矩阵会出现误判的情况，实在微乎其微. 因此我们考虑这样做.
再想到，假如 \(T\) 是一个 \((1,n)\) 的矩阵，乘起来之后，所有矩阵都变成 \((1,n)\) 的了，那么我们矩阵乘法的复杂度就会降低成 \(n^{2}\)，可以通过此题.
实际上，出错的概率为 \(\frac{1}{p}\)，可以多跑几遍拉正确率.
还有一种做法，即先乘一个 \((1,n)\) 的矩阵，再乘一个 \((n,1)\) 的矩阵，这样它就变成单点了，感觉意义不大.
我这一份洛谷过了，在题库上过不去，懒得调了.
#include<bits/stdc++.h>
using namespace std;
namespace hdk{
namespace fastio{
inline long long read(){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
template<typename T>
inline T read(T &A){A=read();return A;}
#define ws(a) write(a);space()
}
}
using namespace hdk::fastio;
/* _MATRIX_H_ */
const int mod=998244353;
template<typename T,int maxlen>
class matrix{
private:
int n,m;
bool ifmod;
T mat[maxlen+5][maxlen+5];
public:
inline T* operator[](int x){
return mat[x];
}
inline void clear(){
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
mat[i][j]&=0;
}
}
n=0;
m=0;
ifmod=false;
}
inline void setmod(int x){
if(x==0){
ifmod=false;
}
else{
ifmod=true;
}
}
inline void resize(int nsize,int msize){
n=nsize;
m=msize;
}
inline void fill(int x){
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
mat[i][j]=x;
}
}
}
inline void fill(std::vector<std::vector<T>> x){
for(register int i=0;i<=(int)x.size()-1;++i){
for(register int j=0;j<=(int)x[i].size()-1;++j){
mat[i+1][j+1]=x[i][j];
}
}
}
inline void packed_clear(std::vector<std::vector<T>> x,int mod=0){
resize(x.size(),x.front().size());
fill(x);
setmod(mod);
}
inline void packed_clear(int nsize,int msize,int filln=0,int mod=0){
clear();
resize(nsize,msize);
setmod(mod);
fill(filln);
}
inline void input(int nsize,int msize){
n=nsize;
m=msize;
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
read(mat[i][j]);
}
}
}
inline matrix operator *(const matrix &A)const{
matrix p;
p.packed_clear(n,A.m,0,mod);
for(register int i=1;i<=n;++i){
for(register int j=1;j<=A.m;++j){
for(register int k=1;k<=m;++k){
p.mat[i][j]+=(1ll*mat[i][k]*A.mat[k][j])%mod;
p.mat[i][j]%=mod;
}
}
}
return p;
}
inline bool operator ==(matrix<T,maxlen>A){
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
if(mat[i][j]!=A[i][j]) return false;
}
}
return true;
}
};
/*--NAMESPACE HDK::MATRIX MATRIX_H_--*/
matrix<int,3000> a,b,c,h,l;
int main(){
srand(time(0));
int cases;read(cases);while(cases--){
int n;read(n);
h.resize(1,n);
l.resize(n,1);
for(int i=1;i<=n;++i){
h[1][i]=rand();
l[i][1]=rand();
}
a.input(n,n);b.input(n,n);c.input(n,n);
if(h*a*b*l==h*c*l) printf("Yes\n");
else printf("No\n");
// a.clear();b.clear();c.clear();
}
}
D.有限制的构造
能想到这题是个背包，但是直接跑复杂度 \(nV^{2}\)，显然 T
这个时候使用经典套路，互换值与值域，定义 \(f_{i,j,k}\) 表示考虑前 \(i\) 个，选了 \(j\) 个，第一个参数为 \(k\) 的第二参最小值，容易得到：
\[f_{i,j,k}=\min\begin{cases}f_{i-1,j,k}\\f_{i-1,j-1,k-a_{i}}+b_{i}\end{cases} \]初始化 \(f_{i,0,0}=0\)
#include<bits/stdc++.h>
using namespace std;
int n,x,y,td[81],xd[81],f[81][81][10001];
int main(){
scanf("%d %d %d",&n,&x,&y);
for(int i=1;i<=n;++i){
scanf("%d %d",&td[i],&xd[i]);
}
memset(f,0x3f,sizeof f);
for(int i=0;i<=n;++i){
f[i][0][0]=0;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
for(int k=0;k<=x;++k){
f[i][j][k]=f[i-1][j][k];
if(k>=td[i]){
f[i][j][k]=min(f[i][j][k],f[i-1][j-1][k-td[i]]+xd[i]);
}
}
}
}
for(int i=n;i>=0;--i){
// cout<<i<<": ";
for(int j=0;j<=x;++j){
// cout<<f[n][i][j]<<" ";
if(f[n][i][j]<=y){
cout<<min(i+1,n)<<endl;
return 0;
}
}
// cout<<endl;
}
}