2023 OI 集训营提高组第五场题解
T1 矩阵交换
-
题目提到行排序后看每列内部的关系。因此自然的分析列内的性质。
-
如果
则直接输出YES容易解决，考虑
。
-
考虑以第
列元素为关键字对行进行排序，形成了
的序列。认为是三个区间
，其中
，
。此时考虑第列元素，
，即第
列形成的
个区间在第
列内要满足非递减关系。
-
总结下是：前一列形成了若干个区间在当前列满足非递减关系。
-
采用上述方法从第
列推到第
列，该问题解决。
T2 砖块摆放
把三种颜色分别当作 0、1、2 三种数字、
假设相邻两个砖块的颜色为 ，那么通过大眼观察法可以发现上面的一个它们上面的砖块等于
意义下
根据公式可以发现砖块中每个数字和二项式定理（杨辉三角系数）的形式一致，即可用组合数学获得答案。
T3 学习 lis
10分：枚举然后check即可，check的过程稍微加速一下，一旦不满足就返回，否则会TLE。
20分：我们显然可以一边dfs一边check前面生成的序列是否合法，这样的数据就卡不掉了，复杂度接近答案的大小。
30分：其实我们并不关心是多少，只关心我们生成的序列，一共出现了多少种不同的数字，以及这些数字必须得是从
开始连续的，比如，我们可以用
来代表所有类似于
类的序列，最后乘上组合数即可，所以在
的过程中，记录一共用了多少种数字，以及哪些数字被用到了，稍微剪枝一下就可以了。
另外40分：考虑一个状压，我们每次填入相同数字到一个子集去，比如
这个方案，我们可以先给位置
填入
，变成
，然后再给第
个位置填入数字
变成
，这个过程中，凡是填入的数字的
LIS都是可以算出来的。
状态是：表示我考虑完了数字
，填入了
这个集合的方案数。
转移不表，复杂度，但是由于给定
LIS数组的限制，严重卡不满。
#include <bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define mod 998244353
using namespace std;
ll C[3005][3005];
void init()
{
C[0][0]=1;
for (int i=1;i<=3000;i++)
for (int j=0;j<=i;j++)
{
if (i==1 || j==0) C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
int n,m;
int a[21];
ll dp[1<<20][21]; //填了i种数字，填了哪些位置的方案数
void add(ll &x,ll y) {x=(x+y)%mod; return;}
int can(int sta,int nxt)
{
int mx=0;
for (int i=0;i<n;i++)
{
if ((sta>>i)&1) mx=max(mx,a[i]);
if ((nxt>>i)&1) if (a[i]!=mx+1) return 0;
}
return 1;
}
int main()
{
init();
cin>>n>>m;
for (int i=0;i<n;i++) cin>>a[i];
dp[0][0]=1;
for (int sta=0;sta<(1<<n);sta++)
for (int i=0;i<n;i++)
if (dp[sta][i])
{
int bu=(1<<n)-1-sta;
for (int S=bu;S!=0;S=(S-1)&bu)
if (can(sta,S))
{
add(dp[sta|S][i+1],dp[sta][i]);
}
}
ll ans=0;
for (int i=1;i<=n;i++) add(ans,dp[(1<<n)-1][i]*C[m][i]);
cout<<ans<<endl;
}
100分：考虑把状压转移子集的过程拎出来：
表示的是，我正在考虑数字
的填写，当前在从后向前考虑第
个位置填不填数字
，当前状态是
的方案数。
转移不表，有一个小细节是，我们并不知道有没有用到，这样你可以选择加一个
状态来表示是否用过了
，也可以选择就这么
下来，这样你得到的答案
表示的是，最多用了
个不同数字，构造出的序列满足
LIS数组的方案数。
容斥一下：
即是恰好使用了个数字的方案数了。
时间复杂度，需要滚动一下数组。
#include <bits/stdc++.h>
#define ll long long
#define maxn 3000005
#define mod 998244353
using namespace std;
ll C[3005][3005];
void init()
{
C[0][0]=1;
for (int i=1;i<=3000;i++)
for (int j=0;j<=i;j++)
{
if (i==1 || j==0) C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
int n,m;
int a[21];
int premax[1<<20];
void init2()
{
for (int sta=0;sta<(1<<n);sta++)
{
for (int i=0;i<n;i++)
if ((sta>>i)&1)
premax[sta]=max(premax[sta],a[i]);
}
}
int dp[2][22][1<<20];
ll ans[25];
void add(int &x,int y) {x=(x+y)%mod; return;}
void DP()
{
int now=0,nxt=1;
dp[now][n-1][0]=1;
for (int turn=1;turn<=n;turn++)
{
for (int i=n-1;i>=0;i--)
for (int sta=0;sta<(1<<n);sta++)
if (dp[now][i][sta])
{
int tmp=dp[now][i][sta];
//case1：不选
if (i) add(dp[now][i-1][sta],tmp);
else add(dp[nxt][n-1][sta],tmp);
//case2：选
if (((sta>>i)&1)==0 && premax[sta&((1<<i)-1)]+1==a[i])
{
if (i) add(dp[now][i-1][sta|(1<<i)],tmp);
else add(dp[nxt][n-1][sta|(1<<i)],tmp);
}
dp[now][i][sta]=0;
}
//此时dp[nxt][n-1][sta]就是选了最多turn个数的时候的方案数
ans[turn]=dp[nxt][n-1][(1<<n)-1];
swap(now,nxt);
}
ll tot=0;
for (int i=1;i<=n;i++)
{
for (int j=i-1;j>=1;j--)
{
ans[i]=(ans[i]+(-1*C[i][j]*ans[j]%mod)+mod)%mod;
}
tot=(tot+ans[i]*C[m][i]%mod)%mod;
}
cout<<tot<<endl;
}
int main()
{
cin>>n>>m;
for (int i=0;i<n;i++) cin>>a[i];
init(); init2();
DP();
}
T4 战略轰炸
首先断环为链。
下文中 表示联通之后的军事基地的战斗力的最大值。
考虑给定 和
的轰炸机是否可以完美轰炸
次的本质是判断
。
原因是因为一共轰炸
次，一个军事基地最多被轰炸
次，而若
，则代表每次都可以选择轰炸它。否则对剩余的
的军事基地轮流轰炸，即求和之后除以
下取整，最后加起来判断是否能否有大于等于
个军事基地被一同选中。
- 特殊性质
即每次询问一个 ，求
。
考虑对
数组排序，设定一个阈值
，当
时，预处理计算。当
时，枚举
用树状数组统计。再特判一下
的数的个数即可。取
，则复杂度为
。
- 特殊性质
即给定一个长度为 的数组
，
次操作。
-
表示将
。
-
表示求
。
。
考虑对于 的每个
建立一个树状数组直接维护，预处理复杂度
，单次询问复杂度
，单次修改复杂度
。
当 时与特殊性质
的方法一样做即可，预处理复杂度
，单次询问复杂度
，单次修改复杂度
。
取 ，则复杂度为
。
对于 ，暴力判断目前这个区间是否被其他区间覆盖。
对于 ，用特殊性质
的方法暴力做即可。
- 正解
重点是要维护军事基地间的连通性，然后并查集记录连通块大小即可用特殊性质 的方法直接做了。
考虑维护一个连通块中每个元素连接到下一个同连通块内的点。
设 为
号点上方的边数。设我们要合并
和
(
)。
若 ，不妨设
，则我们向右找到第一个位置
满足
，因为
，且此时
所在的连通块必定被
所在的连通块包含，故直接合并
与
。反之同理。
若 ，依旧找到
，若
则如上操作，否则代表
与
之间没有其他连通块阻碍了，直接连接即可。
寻找 可以直接线段树上二分。
而合并连通块时分类讨论：
首先定义 表示
所在连通块最左边的位置，
同理。这个直接用并查集维护。
若 与
所在连通块无包含关系，则直接给区间
的
值加一。
否则需要断掉 这条边，加上
和
这两条边，同样线段树上区间加法维护。
这部分总复杂度 。
然后维护一下连通块的 之和直接继续做即可。
总复杂度 。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = ' ';
int p, p3 = -1;
void read() {}
void print() {}
inline int getc() {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline void flush() {
fwrite(buf2, 1, p3 + 1, stdout), p3 = -1;
}
template <typename T, typename... T2>
inline void read(T &x, T2 &...oth) {
int f = 0;
x = 0;
char ch = getc();
while (!isdigit(ch)) {
if (ch == '-')
f = 1;
ch = getc();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getc();
}
x = f ? -x : x;
read(oth...);
}
template <typename T, typename... T2>
inline void print(T x, T2... oth) {
if (p3 > 1 << 20)
flush();
if (x < 0)
buf2[++p3] = 45, x = -x;
do {
a[++p] = x % 10 + 48;
} while (x /= 10);
do {
buf2[++p3] = a[p];
} while (--p);
buf2[++p3] = hh;
print(oth...);
}
} // namespace FastIO
#define read FastIO::read
#define print FastIO::print
#define flush FastIO::flush
const int B = 100,A = 100000;
int n,q,c,sid,timer = 0,cnt[100010],a[100010],s[100010];
int LSB(int i){
return i & (-i);
}
struct Bit{
int bit[100010];
void upd(int i,int k){
if(!i) return;
while(i <= A){
bit[i] += k;
i += LSB(i);
}
}
int psq(int i){
int s = 0;
while(i){
s += bit[i];
i -= LSB(i);
}
return s;
}
}bt[B + 5];
void modify(int pre,int v){
for(int i = 1; i <= B; i++){
if(!cnt[i]) continue;
bt[i].upd(pre,-pre / i);
bt[i].upd(v,v / i);
}
bt[B + 1].upd(pre,-1);
bt[B + 1].upd(v,1);
}
namespace DSU{
int fa[100010],l[100010],r[100010],sz[100010],val[100010];
void init(){
for(int i = 1; i <= n; i++) fa[i] = l[i] = r[i] = i,sz[i] = 1,val[i] = a[i];
}
int Find(int i){
return fa[i] == i ? i : fa[i] = Find(fa[i]);
}
void unite(int u,int v){
int fu = Find(u),fv = Find(v);
if(fu == fv) return;
if(sz[fu] > sz[fv]) swap(fu,fv);
fa[fu] = fv;
l[fv] = min(l[fu],l[fv]);
r[fv] = max(r[fu],r[fv]);
modify(val[fv],val[fu] + val[fv]);
modify(val[fu],0);
val[fv] += val[fu];
val[fu] = 0;
}
};
using DSU::init;
using DSU::Find;
using DSU::unite;
int mn[400010],tag[400010];
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
void pushup(int i){
mn[i] = min(mn[ls(i)],mn[rs(i)]);
}
void Tag(int i,int v){
mn[i] += v,tag[i] += v;
}
void pushdown(int i){
if(tag[i]){
Tag(ls(i),tag[i]);
Tag(rs(i),tag[i]);
tag[i] = 0;
}
}
void upd(int i,int l,int r,int ql,int qr,int v){
if(ql <= l && r <= qr){
Tag(i,v);
return;
}
pushdown(i);
int mid = (l + r) >> 1;
if(ql <= mid) upd(ls(i),l,mid,ql,qr,v);
if(qr > mid) upd(rs(i),mid + 1,r,ql,qr,v);
pushup(i);
}
int query(int i,int l,int r,int pos){
if(l == r) return mn[i];
pushdown(i);
int mid = (l + r) >> 1;
if(pos <= mid) return query(ls(i),l,mid,pos);
else return query(rs(i),mid + 1,r,pos);
}
int queryl(int i,int l,int r,int pos,int v){
if(r <= pos){
if(mn[i] >= v) return 0;
if(l == r) return l;
pushdown(i);
int mid = (l + r) >> 1;
if(mn[rs(i)] < v) return queryl(rs(i),mid + 1,r,pos,v);
return queryl(ls(i),l,mid,pos,v);
}
pushdown(i);
int mid = (l + r) >> 1,res = 0;
if(mid + 1 <= pos) res = queryl(rs(i),mid + 1,r,pos,v);
if(!res) res = queryl(ls(i),l,mid,pos,v);
return res;
}
int queryr(int i,int l,int r,int pos,int v){
if(pos <= l){
if(mn[i] >= v) return n + 1;
if(l == r) return l;
pushdown(i);
int mid = (l + r) >> 1;
if(mn[ls(i)] < v) return queryr(ls(i),l,mid,pos,v);
return queryr(rs(i),mid + 1,r,pos,v);
}
pushdown(i);
int mid = (l + r) >> 1,res = n + 1;
if(pos <= mid) res = queryr(ls(i),l,mid,pos,v);
if(res == n + 1) res = queryr(rs(i),mid + 1,r,pos,v);
return res;
}
void merge(int x,int y){
x = Find(x),y = Find(y);
if(DSU::r[x] < DSU::l[y]) upd(1,1,n,DSU::r[x] + 1,DSU::l[y] - 1,1);
else upd(1,1,n,max(DSU::l[x],DSU::l[y]),min(DSU::r[x],DSU::r[y]),-1);
unite(x,y);
}
int OP[100010],U[100010],V[100010],C[100010];
signed main(){
read(n),read(q),read(sid);
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 1; i <= B; i++){
for(int j = 1; j <= n; j++) bt[i].bit[a[j]] += (a[j] / i);
for(int j = 1; j <= A; j++) s[j] = s[j - 1] + bt[i].bit[j];
for(int j = 1; j <= A; j++) bt[i].bit[j] = s[j] - s[j - LSB(j)];
}
for(int i = 1; i <= n; i++) bt[B + 1].bit[a[i]]++;
for(int i = 1; i <= A; i++) s[i] = s[i - 1] + bt[B + 1].bit[i];
for(int i = 1; i <= A; i++) bt[B + 1].bit[i] = s[i] - s[i - LSB(i)];
init();
for(int i = 1; i <= q; i++){
read(OP[i]),read(U[i]),read(V[i]);
if(OP[i] == 2){
read(C[i]);
if(U[i] <= B) cnt[U[i]]++;
}
}
int op,u,v;
for(int t = 1; t <= q; t++){
op = OP[t],u = U[t],v = V[t];
if(op == 1){
if(u > v) swap(u,v);
int vu = query(1,1,n,u),vv = query(1,1,n,v);
while(Find(u) != Find(v)){
if(vu > vv) merge(u,queryr(1,1,n,u,vu)),vu--;
else if(vu < vv) merge(queryl(1,1,n,v,vv),v),vv--;
else{
int pos = queryr(1,1,n,u,vu);
if(pos < v) merge(u,pos),vu--;
else merge(u,v);
}
}
}
else{
c = C[t];
swap(c,v);
int sum = (bt[B + 1].psq(A) - bt[B + 1].psq(u * v - 1)) * v;
if(u <= B) sum += bt[u].psq(u * v - 1),cnt[u]--;
else{
for(int cc = u; cc <= min(A,u * v - 1); cc += u){ //cc ~ min(u * v - 1,cc + u - 1)
timer++;
sum += (bt[B + 1].psq(min(u * v - 1,cc + u - 1)) - bt[B + 1].psq(cc - 1)) * (cc / u);
}
}
if(sum >= c * v) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
投递阿里国际数字商业集团等公司10个岗位 >