前言
- 比赛链接。
T1 写得和正解差不多但少了个细节炸 long long 了；T2 只会 \(n^3\) 的本来只有 \(50pts\)，但考虑出题人大概率会搞一个 \(n\) 越大 \(T\) 越小，所以对于 \(n\) 很大的直接 \(rand\) 正确率还是有的，所以获得了 \(80pts\)；T3 不会；T4 没有和 \(n\) 取 \(\min\) 直接挂成 \(25pts\)，好多人都因为这个挂分。
不过这次部分分给的很足好评。
T1
-
部分分 \(55pts\)：对于 \(a_i\) 全为正数、\(|a_i|\le 1\)、样例三个包分别处理。
-
正解：
考虑只有正数的数据，直接每次另 \(a_i+=a_{i-1}\) 即可，每次最多 \(+1e9\)，最后最大为 \(1e14\)，全是负数同理。
然后启发正解，取一个 \(minn,maxx\)，以 \(|maxx|\ge|minn|\) 为例，现将所有数都加上 \(maxx\) ，就变成了全是正数的情况；\(|maxx|<|minn|\) 同理全变成负数即可。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=2e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);} int n,a[N],pos1,pos2; signed main() { read(n); for(int i=1;i<=n;i++) { read(a[i]); if(a[i]>a[pos1]) pos1=i; if(a[i]<a[pos2]) pos2=i; } if(!pos1||!pos2) { write(n-1),puts(""); if(!pos1) for(int i=n-1;i>=1;i--) write(i+1,i),puts(""); else for(int i=2;i<=n;i++) write(i-1,i),puts(""); } else { write(2*n-2),puts(""); if((-a[pos2])<=a[pos1]) { for(int i=1;i<=n;i++) if(i!=pos1) write(pos1,i),puts(""); for(int i=2;i<=n;i++) write(i-1,i),puts(""); } else { for(int i=1;i<=n;i++) if(i!=pos2) write(pos2,i),puts(""); for(int i=n-1;i>=1;i--) write(i+1,i),puts(""); } } }
T2
-
部分分 \(50+?pts\)：\(n^3+rand\)。
-
正解：
随一个 \(1\times n\) 的矩阵 \(d\)，判断 \(d\times a\times b\) 是否等于 \(d\times c\)，复杂度就变成了 \(O(n^2)\)，正确性我不会证明，但是错误率只有 \(\dfrac{1}{998244353}\)。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=3010,P=998244353; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);} int T,n; ll d[N],ans1[N],ans2[N],ans3[N],a[N][N],b[N][N],c[N][N]; void add(ll &x,ll y) {x+=y; x=x>=P?x-P:x;} bool check(ll x[],ll y[]) { for(int i=1;i<=n;i++) if(x[i]!=y[i]) return 0; return 1; } signed main() { srand(time(0)); for(int i=1;i<=3000;i++) d[i]=rand()%P; read(T); while(T--) { read(n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(b[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(c[i][j]); memset(ans1,0,sizeof(ans1)); memset(ans2,0,sizeof(ans2)); memset(ans3,0,sizeof(ans3)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) add(ans1[i],d[j]*a[j][i]%P); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) add(ans2[i],ans1[j]*b[j][i]%P); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) add(ans3[i],d[j]*c[j][i]%P); puts(check(ans2,ans3)?"Yes":"No"); } }
T3
发现 \(k\) 很小，那么对于每一行只有 \(2^k\) 中可能，将这 \(n\) 行组合起来，发现 \(2^k\) 中每一种状态出现多次并不会影响连通性，那么直接处理每种情况是否出现，那么有 \(2^{2^k}\) 种状态，爆搜判断每种状态是否合法，复杂度是不允许的，考虑打表，因为合法的状态并不多。
之后就是计数，设一个总的状态中共出现了 \(m\) 个 \(2^k\) 中的状态，将其扩展到 \(n\) 列里，等价于 \(n\) 个不同的球放 \(m\) 个不同的盒子里，每个盒子至少放一个。
考虑容斥，发现对于不限制每个盒子至少放一个的情况为 \(m^n\)，那么这里我钦定至少有 \(i\) 个是空的，那么最后方案数就是：
\[\sum_{i=1}^m (-1)^{m - i} C_{m}^{i} i^n \]上面打出来的表，\(num_{i,j}\) 表示 \(k=i\) 时，\(m=j\) 的合法状态有多少，那么最终答案为：
\[\sum_{m=1}^{2^k}num_{k,m}\times \sum_{i=1}^m (-1)^{m - i} C_{m}^{i} i^n \]发现给 \(num_{k,i}\) 加上一个 \(0\) 的状态就能够转移给 \(num_{k,i+1}\)，所以每个 \(num_{k,i}\) 都要加上 \(num_{k,i-1}\) 的贡献，注意不是前缀和，要倒序枚举。
打表代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
ll ans[N];
bitset<N>vis;
vector<int>pos;
void check(int have,int k)
{
if(!have) return ;
int sta=0,tot=0;
sta|=pos[0];
while(k--) for(int i:pos)
if(i&sta) tot+=vis[i],vis[i]=0,sta|=i;
for(int i:pos) vis[i]=1;
if(tot==have) ans[tot]++;
}
void dfs(int x,int have,int k)
{
if(x==(1<<k)) {check(have,k); return ;}
dfs(x+1,have,k);
pos.push_back(x),vis[x]=1;
dfs(x+1,have+1,k);
pos.pop_back(),vis[x]=0;
}
signed main()
{
freopen("a.out","w",stdout);
for(int k=1;k<=5;k++)
{
vis.reset();
vector<int>().swap(pos);
memset(ans,0,sizeof(ans));
write(k),puts("");
dfs(1,0,k);
ans[0]=1;
for(int i=0;i<=31;i++) write(ans[i]),putchar(i!=31?',':' ');
puts(""),puts("");
}
}
表
1
1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
2
1,3,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
3
1,7,15,28,32,21,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
4
1,15,80,373,1222,2857,4918,6407,6431,5005,3003,1365,455,105,15,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
5
1,31,375,3860,28845,162440,720491,2603950,7856260,20127820,44327130,84657300,141113700,206250800,265182000,300540120,300540190,265182525,206253075,141120525,84672315,44352165,20160075,7888725,2629575,736281,169911,31465,4495,465,31,1
正解代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
ll num[6][35]=
{
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,3,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,7,15,28,32,21,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,15,80,373,1222,2857,4918,6407,6431,5005,3003,1365,455,105,15,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,31,375,3860,28845,162440,720491,2603950,7856260,20127820,44327130,84657300,141113700,206250800,265182000,300540120,300540190,265182525,206253075,141120525,84672315,44352165,20160075,7888725,2629575,736281,169911,31465,4495,465,31,1}
};
ll n,m,k,P,ans,sum,jc[N],inv[N];
ll qpow(ll a,ll b)
{
ll ans=1;
for(;b;b>>=1)
{
if(b&1) (ans*=a)%=P;;
(a*=a)%=P;
}
return ans;
}
ll C(ll n,ll m)
{
if(m>n) return 0;
if(m==0||m==n) return 1;
return jc[n]*inv[n-m]%P*inv[m]%P;
}
signed main()
{
read(n,k,P); m=min(n,1ll<<k);
jc[0]=1;
for(int i=1;i<=m;i++) jc[i]=jc[i-1]*i%P;
inv[m]=qpow(jc[m],P-2);
for(int i=m-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%P;
for(int i=m;i>=1;i--) num[k][i]+=num[k][i-1];
for(int i=1;i<=m;i++)
{
sum=0;
for(int j=i,op=1;j>=1;j--,op=-op)
(sum+=op*C(i,j)%P*qpow(j,n)%P+P)%=P;
(ans+=sum*num[k][i]%P)%=P;
}
write(ans);
}
T4
挺简单一道 DP，\(O(nv^2)\) 的肯定都会，考虑 \(n\) 很小，\(f_{i,i,j}\) 表示前 \(i\) 个数中选 \(j\) 个 \(\sum a=k\) 时 \(\sum b\) 最小为多少，最后暴力扫一遍统计答案。
注意最后求出来的 \(ans\) 要 \(+1\) 因为题目要求的是第一个大于的，但其最大为 \(n\)，所以要和 \(n\) 取 \(\min\)！qwq
最后复杂度为 \(O(n^2v)\)，即使这样空间也很难受，可以滚掉一维。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=85,M=1e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,mx_a,mx_b,ans,a[N],b[N],f[N][M];
signed main()
{
read(n,mx_a,mx_b);
for(int i=1;i<=n;i++) read(a[i],b[i]);
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=i;j>=1;j--)
for(int k=mx_a;k>=a[i];k--)
{
f[j][k]=min(f[j][k],f[j-1][k-a[i]]+b[i]);
ans=f[j][k]<=mx_b&&ans<j?j:ans;
}
write(min(n,ans+1));
}
总结
好好理解题意，T1、T4 都因为这个挂分了。
附录
熟悉的：
请注意：题目背景与题目可能没有关系。
所以题名和背景：
标签：write,21,int,void,Tp,2024,read,inline,集训 From： https://www.cnblogs.com/Charlieljk/p/18353850A 符号化方法初探
B 无标号 Sequence 构造
C 无标号 Multiset 构造
D 有限制的构造