The 2021 ICPC Asia Nanjing Regional Contest

E. Paimon Segment Tree

tyy很快意识到额外维护一个前缀和即可求解，则现在只需要处理一个平方和即可。

但是看到需要维护平方和，naive的我以为线段树无法解决，再加上看到5e4的数据量，所以训练的时候想了个分块的做法。

可惜需要维护的变量太多，导致一直没有调出来，下来补题却最后一直在第23个点TLE

无奈查看题解，居然真的是线段树…其实使用矩阵乘法来维护，继而就可利用懒标记来优化了…

注意矩阵乘法的常数极大，又观察得知，矩阵中仅有6个参数是变量，所以可以极大的优化乘法运算的复杂度。

最后在cf上面使用64位测评机，刚好卡过去…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7; 
const int maxn=5e4+5;
int n,m,q;
int a[maxn];
ll ans[maxn];
struct Mat{
	array<array<ll,4>,4>mat;
	void init(int k){
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)mat[i][j]=0;
		for(int i=0;i<4;i++)mat[i][i]=1;
		mat[1][0]=k;
		mat[2][0]=1ll*k*k,mat[2][1]=2*k;
		mat[3][0]=1ll*k*k,mat[3][1]=2*k,mat[3][2]=1;
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)mat[i][j]%=mod;
	}


};

Mat mul(Mat a,Mat b){
	Mat c;
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)c.mat[i][j]=0;
	for(int i=1;i<4;i++){
		for(int j=0;j<i;j++){
			for(int k=j;k<=i;k++){
				c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
				c.mat[i][j]%=mod;
			}
		}
	}
	for(int i=0;i<4;i++)c.mat[i][i]=1;
	return c;
}
array<ll,4> get_ans(Mat m,array<ll,4> a){
	array<ll,4>b;
	for(int i=0;i<4;i++)b[i]=0;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			b[i]+=a[j]*m.mat[i][j];
			b[i]%=mod;
		}
	}
	return b;
}

struct Opt{
	int l,r,x;
}opt[maxn];
struct ques{
	int l,r,idx,sgn;
};
vector<ques>vec[maxn];

struct Tree{
	Mat tag;
	array<ll,4>val;
}t[maxn<<2];

void push_up(int rt){
	for(int i=0;i<4;i++){
		t[rt].val[i]=t[rt<<1].val[i]+t[rt<<1|1].val[i];
		t[rt].val[i]%=mod;
	}
}

void push_dn(int rt){
	t[rt<<1].tag=mul(t[rt].tag,t[rt<<1].tag);
	t[rt<<1|1].tag=mul(t[rt].tag,t[rt<<1|1].tag);
	t[rt<<1].val=get_ans(t[rt].tag,t[rt<<1].val);
	t[rt<<1|1].val=get_ans(t[rt].tag,t[rt<<1|1].val);
	t[rt].tag.init(0);
	t[rt].tag.mat[3][2]=0;
}

void update(int rt,int l,int r,int xl,int xr,Mat x){
	int mid=l+r>>1;
	if(xl==l&&xr==r){
		t[rt].val=get_ans(x,t[rt].val);
		t[rt].tag=mul(x,t[rt].tag);
		return;
	}
	push_dn(rt);
	if(xl<=mid)update(rt<<1,l,mid,xl,min(xr,mid),x);
	if(xr>mid)update(rt<<1|1,mid+1,r,max(xl,mid+1),xr,x);
	push_up(rt);
}

ll query(int rt,int l,int r,int xl,int xr){
	ll res=0;
	int mid=l+r>>1;
	if(xl==l&&xr==r){
		return t[rt].val[3];
	}
	push_dn(rt);
	if(xl<=mid)res+=query(rt<<1,l,mid,xl,min(xr,mid));
	if(xr>mid)res+=query(rt<<1|1,mid+1,r,max(xl,mid+1),xr);
	res%=mod;
	return res;
}

void build(int rt,int l,int r){
	int mid=l+r>>1;
	t[rt].tag.init(0);
	t[rt].tag.mat[3][2]=0;
	if(l==r){
		t[rt].val={1,a[l],1ll*a[l]*a[l]%mod,1ll*a[l]*a[l]%mod};
		return;
	}
	if(l<=mid)build(rt<<1,l,mid);
	if(r>mid)build(rt<<1|1,mid+1,r);
	push_up(rt);
}

int main(){
	
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		opt[i]={l,r,x};
	}
	for(int i=1;i<=q;i++){
		int l,r,x,y;
		scanf("%d%d%d%d",&l,&r,&x,&y);
		if(x)vec[x-1].push_back({l,r,i,0});
		vec[y].push_back({l,r,i,1});
	}
	build(1,1,n);
	for(int i=0;i<=m;i++){
		if(i){
			Mat cur;
			cur.init(0);
			if(opt[i].l>1)update(1,1,n,1,opt[i].l-1,cur);
			if(opt[i].r<n)update(1,1,n,opt[i].r+1,n,cur);
			cur.init(opt[i].x);
			update(1,1,n,opt[i].l,opt[i].r,cur);
		}
		for(auto it:vec[i]){
			int l=it.l,r=it.r,sgn=it.sgn,idx=it.idx;
			ll res=query(1,1,n,l,r);
			if(!sgn)ans[idx]-=res;
			else ans[idx]+=res;
			ans[idx]=(ans[idx]%mod+mod)%mod;
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}

I. Cloud Retainer’s Game

算是个比较好想的DP，但是难点在于找到相邻两个DP的状态。

这里我把所有的点都看成状态，然后对于每个点，根据两个不同的入射方向，将每个点都进行回溯，然后映射到x=0时的y轴上。

  • 如果当前点是硬币，则DP的去向和来向必须一样，且DP值+1
  • 如果当前点是障碍物，则DP的值可以由两个不同的来向更新
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=2e5+5;
const int inf=1e9;
const ll mod=998244353;
const double eps=1e-10;
int h,n,m,ans;
struct loc{
	int x,y,tp;
};
vector<loc>a;
map<pii,int>mp;
bool cmp(loc x,loc y){
	return x.x==y.x?x.y<y.y:x.x<y.x;
}
void solve(int r,int c,int sgn){
	int x=r,y=c,tp=0,ad=(sgn==0);
	pii cur[2];
	if(x<=y)y-=x,tp=0;
	else {
		x-=y,y=0;
		int t=x/h;
		if(t%2==0){
			y+=x%h;
			tp=1;
		}
		else {
			y=h-x%h;
			tp=0;
		}
	}
	if(y==0||y==h)tp=0;
	cur[0]={y,tp};

	x=r,y=c,tp=1;
	if(x<=h-y)y+=x,tp=1;
	else {
		x-=h-y;y=h;
		int t=x/h;
		if(t%2==0){
			y-=x%h;
			tp=0;
		}
		else {
			y=x%h;
			tp=1;
		}
	}
	if(y==0||y==h)tp=0;
	cur[1]={y,tp};
	
	int res[2]={-inf,-inf};
	
	for(int i=0;i<2;i++){
		if(mp.count(cur[i])){
			auto pre=mp[cur[i]];
			res[i]=pre+ad;
		}
		else if(!cur[i].first)res[i]=ad;
	}
	int mx=max(res[0],res[1]);
	if(sgn)res[0]=res[1]=mx;
	mp[cur[0]]=res[0];
	mp[cur[1]]=res[1];
	ans=max(ans,mx);
	// printf("##%d %d %d %d\n",r,c,mp[cur[0]],mp[cur[1]]);
	// printf("$$%d %d %d %d\n",cur[0].first,cur[0].second,cur[1].first,cur[1].second);
}
void init(){
	a.clear();
	mp.clear();
	ans=0;
}
int main(){
	int T=1;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&h,&n);
		init();
		for(int i=1;i<=n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			a.push_back({x,y,1});
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			a.push_back({x,y,0});
		}
		sort(a.begin(),a.end(),cmp);
		for(auto it:a){
			int x=it.x,y=it.y,tp=it.tp;
			solve(x,y,tp);
		}
		printf("%d\n",ans);
	}


	return 0;
}
/*
1
3
1
4 2
3
1 1
6 2
9 1
*/

The 2019 ICPC Asia Nanjing Regional Contest

J. Spy

很容易想到这是个二分图最大权匹配，但是naive的我写了个MCMF，直接T飞

下来抄了个KM的板子过了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>pli;
typedef double db;
const int maxn=4e2+5;
const ll mod=998244353;
const double eps=1e-10;
const ll inf=2e9;
int n;
ll b[maxn],c[maxn];
ll pre[maxn];
pli a[maxn];



template <typename T>
struct hungarian {  // km
  int n;
  vector<int> matchx;  // 左集合对应的匹配点
  vector<int> matchy;  // 右集合对应的匹配点
  vector<int> pre;     // 连接右集合的左点
  vector<bool> visx;   // 拜访数组 左
  vector<bool> visy;   // 拜访数组 右
  vector<T> lx;
  vector<T> ly;
  vector<vector<T> > g;
  vector<T> slack;
  T inf;
  T res;
  queue<int> q;
  int org_n;
  int org_m;

  hungarian(int _n, int _m) {
    org_n = _n;
    org_m = _m;
    n = max(_n, _m);
    inf = numeric_limits<T>::max();
    res = 0;
    g = vector<vector<T> >(n, vector<T>(n));
    matchx = vector<int>(n, -1);
    matchy = vector<int>(n, -1);
    pre = vector<int>(n);
    visx = vector<bool>(n);
    visy = vector<bool>(n);
    lx = vector<T>(n, -inf);
    ly = vector<T>(n);
    slack = vector<T>(n);
  }

  void addEdge(int u, int v, int w) {
    g[u][v] = max(w, 0);  // 负值还不如不匹配 因此设为0不影响
  }

  bool check(int v) {
    visy[v] = true;
    if (matchy[v] != -1) {
      q.push(matchy[v]);
      visx[matchy[v]] = true;  // in S
      return false;
    }
    // 找到新的未匹配点 更新匹配点 pre 数组记录着"非匹配边"上与之相连的点
    while (v != -1) {
      matchy[v] = pre[v];
      swap(v, matchx[pre[v]]);
    }
    return true;
  }

  void bfs(int i) {
    while (!q.empty()) {
      q.pop();
    }
    q.push(i);
    visx[i] = true;
    while (true) {
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
          if (!visy[v]) {
            T delta = lx[u] + ly[v] - g[u][v];
            if (slack[v] >= delta) {
              pre[v] = u;
              if (delta) {
                slack[v] = delta;
              } else if (check(v)) {  // delta=0 代表有机会加入相等子图 找增广路
                                      // 找到就return 重建交错树
                return;
              }
            }
          }
        }
      }
      // 没有增广路 修改顶标
      T a = inf;
      for (int j = 0; j < n; j++) {
        if (!visy[j]) {
          a = min(a, slack[j]);
        }
      }
      for (int j = 0; j < n; j++) {
        if (visx[j]) {  // S
          lx[j] -= a;
        }
        if (visy[j]) {  // T
          ly[j] += a;
        } else {  // T'
          slack[j] -= a;
        }
      }
      for (int j = 0; j < n; j++) {
        if (!visy[j] && slack[j] == 0 && check(j)) {
          return;
        }
      }
    }
  }

  void solve() {
    // 初始顶标
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        lx[i] = max(lx[i], g[i][j]);
      }
    }

    for (int i = 0; i < n; i++) {
      fill(slack.begin(), slack.end(), inf);
      fill(visx.begin(), visx.end(), false);
      fill(visy.begin(), visy.end(), false);
      bfs(i);
    }

    // custom
    for (int i = 0; i < n; i++) {
      if (g[i][matchx[i]] > 0) {
        res += g[i][matchx[i]];
      } else {
        matchx[i] = -1;
      }
    }
    cout << res << "\n";
  }
};



int main(){
	scanf("%d",&n);
	hungarian<int>G(n,n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i].first);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].second);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+a[i].second;
	}
	for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
	sort(b+1,b+n+1);
	sort(c+1,c+n+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ll cur=b[i]+c[j];
			int pos=lower_bound(a+1,a+n+1,make_pair(cur,0))-a;
			pos--;
			int cst=0;
			if(pos){
				cst=pre[pos];
				G.addEdge(i-1,j-1,cst);
				// G.addEdge(j-1,i-1,cst);
			}
		}
	}
	G.solve();
	return 0;
}

I. Space Station

还算挺有启发性的DP。

首先应当明确两点：

  • 当选取的数字之和大于等于50之后，就可以想去哪就去哪，意味着直接乘以剩下数字的数量的阶乘即可。
  • 如果已经确定选取了一些数，则这些数之间不论访问顺序如何，后续继续选数时，后续选择的方案总数都是一样的

假设这里使用dfs的方式选数的话，无疑是需要记忆化搜索的，那么状态数有多少种呢？显而易见应当不超过对于50的整数划分的总方案数

所以记忆化搜索的空间及时间复杂度是可以接受的。

这里可以直接使用array<int,50>当作键值存在map里，亦可以先hash后再存进map

前者跑了1900ms，后者800ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
const ll mod=1e9+7;
int n;
int a[maxn];
ll qpow(ll x,ll y){ 
	ll res=1;
	while(y){
		if(y&1)res*=x,res%=mod;
		x*=x,x%=mod;
		y/=2;
	}
	return res;
}
ll fac[maxn],inv[maxn];
int cnt[55];
// map<array<int,51>,ll>mp;
unordered_map<ull,ll>mp;
void init(){
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i,fac[i]%=mod;
	inv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
}
ll dfs(int sum,int rem){
	if(sum>=50||!rem)return fac[rem];
	ll res=0;
	ull temp=0;
	for(int i=1;i<=50;i++){
		temp*=131;
		temp+=cnt[i];
	}
	if(mp.count(temp))return mp[temp];
	for(int i=1;i<=min(50,sum);i++){
		if(!cnt[i])continue;
		cnt[i]--;
		res+=(cnt[i]+1)*dfs(sum+i,rem-1);
		res%=mod;
		cnt[i]++;
	}
	return mp[temp]=res;
}
int main(){
	scanf("%d",&n);
	init();
	scanf("%d",&a[0]);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	printf("%lld\n",dfs(a[0],n-cnt[0])*fac[n]%mod*inv[n-cnt[0]]%mod);
	

	return 0;
}

The 2021 ICPC Asia Shanghai Regional Programming Contest

J. Two Binary Strings Problem

一般来说这种01串相关的区间维护往bitset上面靠准没错

这道题目大方向是，对于b中的每个位置，我们计算它对答案的贡献。

首先把a数组中的’0’看成-1，'1’看成1，然后做一个前缀和。

再将所有的0-n的下标以前缀和的值为关键字从大到小排序

按顺序遍历所有下标，令当前下表为cur

  • 如果b[cur]==1b[cur]==1，那么如果cur-k处的前缀和大于等于cur处的前缀和，则k不是lucky的
  • 如果b[cur]==0b[cur]==0，那么如果cur-k处的前缀和小于cur处的前缀和，则k不是lucky的

这里为了方便处理从而直接得到答案，把cur映射到了n-cur上，相当于做了对称处理。

注意要特判下标较小时的情况，使用一个lst标记即可。

这道题对于没有怎么写过bitset的蒟蒻来说，有些抽象比如我，具体可以康康代码。搞懂后发现其实逻辑还是挺简洁且清晰的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
int n;
bitset<maxn>A,B,C;
char a[maxn],b[maxn];
int pre[maxn],rk[maxn];
bool cmp(int x,int y){
	return pre[x]==pre[y]?x<y:pre[x]>pre[y];
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		scanf("%s%s",a+1,b+1);
		int lst=n+1;
		pre[0]=0;
		for(int i=1;i<=n;i++){
			int ad;
			if(a[i]=='0')ad=-1;
			else ad=1;
			pre[i]=pre[i-1]+ad;
			int sgn;
			if(pre[i]<=0)sgn=0;
			else sgn=1;
			if(sgn!=b[i]-'0')lst=min(lst,i);
		}
		for(int i=0;i<=n;i++)rk[i]=i,C[i]=1;
		sort(rk,rk+n+1,cmp);
		A.reset(),B.reset();
		for(int i=0;i<=n;i++){
			int cur=rk[i];
			if(b[cur]=='1'){
				B|=A>>(n-cur);
			}
			else {
				B|=(A^C)>>(n-cur);
			}
			A[n-cur]=1;
		}
		for(int i=1;i<=n;i++){
			if(B[i]||i>=lst)printf("0");
			else printf("1");
		}
		puts("");
	}

	return 0;
}