Algorithms Weekly 9

Posted on | Post modified:

A GuGuGu week

好久没更算法周了,由于考研，写代码的时间基本已经没有了，所以现在的状态基本上是有空补补之前比赛的题目,题意和题解写的会比较潦草。

2020KickStart RoundB T2 Bus Routes (10pts, 13pts)

题意：

有$n$个bus，第$i$个$bus$的发车周期为$x_{i}$,你需要在第$D$天之前按顺序把所有的bus乘坐，求最晚坐第一班的时间。

题解：倒着贪心即可

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
/*
* @author:  codancer
* @createTime:  2020-05-30, 20:55:05
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
void solve(){
	ll n,d;
	scanf("%lld %lld",&n,&d);
	vector<ll> x(n+1);
	rep(i,1,n) scanf("%lld",&x[i]);
	ll now=d;
	fep(i,n,1){
		ll nxt=(now/x[i])*x[i];
		// cout<<i<<' '<<nxt<<endl;
		now=nxt;
	}
	printf("%lld\n",now);
}
int main(){
	int T;
	scanf("%d",&T);
	rep(tt,1,T){
		printf("Case #%d: ",tt);
		solve();
	}
	return 0;
}

2020KickStart RoundB T3 Robot Path Decoding (11pts, 16pts)

题意：

一个机器人在一个$10^9 \cdot 10^9$的方阵上移动（循环方阵），初始是在$(1,1)$，然后只能往$N,W,S,E$四个方向移动，给一个移动序列，计算最终机器人所在的位置。除了正常的字符串序列外，还包含$X(Y)$类似的序列，表示把$Y$重复$X$次。

题解：

首先可以知道横竖互不相干，接下来就是计算横和竖分别的情况。对字符串进行拆解可以用balance，即当前操作的次数是最近出现的balance个数字的累乘。但由于方阵是循环的，每次还需将当前数值对$10^9$取模。

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
/*
* @author:  codancer
* @createTime:  2020-05-30, 21:10:54
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int  N = 3000;
char s[N];
void solve(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	ll N,W,S,E;
	N=W=S=E=0;
	ll balance=0;
	vector<int> nums;
	rep(i,1,n){
		if(s[i]>='1'&&s[i]<='9'){
			nums.pb(s[i]-'0');
		}
		else if(s[i]=='('){
			++balance;
		}
		else if(s[i]==')'){
			--balance;
			if(nums.size()) nums.pop_back();
		}else{
			int siz=(int)nums.size();
			ll cnt=1;
			fep(j,siz-1,siz-balance){
				cnt*=nums[j];
				cnt%=mod;
			}
			if(s[i]=='N'){
				 N+=cnt;
				 N%=mod;
			}
			if(s[i]=='W'){
				 W+=cnt;
				 W%=mod;
			}
			if(s[i]=='E'){
				 E+=cnt;
				 E%=mod;
			}
			if(s[i]=='S'){
				 S+=cnt;
				 S%=mod;
			}
		}
	}
	S-=N;
	S%=mod;
	E-=W;
	E%=mod;
	printf("%lld %lld\n",(E+mod)%mod+1,(S+mod)%mod+1);
}
int main(){
	int T;
	scanf("%d",&T);
	rep(tt,1,T){
		printf("Case #%d: ",tt );
		solve();
	}
	return 0;
}

2020KickStart RoundC Stable Wall (8pts, 13pts)

题意：

判断一个polyomino 是否坚固，关于polyomino就是只有在色块有支撑的情况下，才能放当前色块，最终能构成的就是坚固的，如果坚固，给出一种顺序来。

题解：

拓扑排序，如果$u$色块下面有$v$色块，那么一定是$v$早于$u$,连边，跑拓扑排序即可。

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
/*
* @author:  codancer
* @createTime:  2020-05-19, 21:15:11
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 200;
vector<int> G[N];
bool adj[N][N];
char s[N][N];
int ind[N];
void solve(){
	rep(i,1,100) G[i].clear();
	memset(ind,0,sizeof(ind));
	memset(adj,0,sizeof(adj));
	int n,m;
	cin>>n>>m;
	set<char> sts;
	rep(i,1,n){
		rep(j,1,m){
			cin>>s[i][j];
			sts.insert(s[i][j]);
		}
	}
	rep(i,1,n-1){
		rep(j,1,m){
			adj[s[i+1][j]-'A'+1][s[i][j]-'A'+1]=1;
		}
	}
	rep(i,1,26){
		rep(j,1,26){
			if(i!=j&&adj[i][j]==1){
				G[i].pb(j);
				ind[j]++;
			}
		}
	}
	string ans="";
	queue<int> q;
	rep(i,1,26){
		if(ind[i]==0&&sts.find(char('A'+i-1))!=sts.end()){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		ans+=char('A'+u-1);
		for(int v:G[u]){
			ind[v]--;
			if(ind[v]==0) q.push(v);
		}
	}
	if((int)sts.size()!=(int)ans.length()){
		cout<<"-1"<<'\n';
		return ;
	}
	cout<<ans<<endl;
}
int main(){
	int T;
	cin>>T;
	rep(tt,1,T){
		printf("Case #%d: ",tt);
		solve();
	}
	return 0;
}

2020KickStart RoundD Candies (14pts, 24pts)

题意：

一个长度为$n$序列$A$，两种操作

  • Q L R查询$[l,r]$使得$\sum_{l}^rA_{i}(i-l+1)(-1)^{i-l}$最大。
  • U i j把$A_{i}$变成$j$

题解：

两棵树状数组。

第一棵维护$(-1)^{i-1}iA_{i}$

第二棵维护$(-1)^{i-1}*A_{i}$

查询的时候按奇偶讨论

$u$奇数为: $T1.get(u,v)-(u-1)*T2.get(u,v)$

$u$偶数为:$-T1.get(u,v)+(u-1)*T2.get(u,v)$

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
/*
* @author:  codancer
* @createTime:  2020-05-20, 08:21:40
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 2e6+100;
struct BIT{
	ll c[N];
	int lowbit(int x){
		return x&(-x);
	}
	void update(int pos,ll x){
		for(int i=pos;i<=N-100;i+=lowbit(i)){
			c[i]+=x;
		}
	}
	ll query(int pos){
		ll ans=0;
		for(int i=pos;i;i-=lowbit(i)){
			ans+=c[i];
		}
		return ans;
	}
	ll get(int l,int r){
		return query(r)-query(l-1);
	}
}T1,T2;
void solve(){
	int n,m;
	scanf("%d%d",&n,&m);
	rep(i,1,N-100) T1.c[i]=T2.c[i]=0;
	vector<int> a(n+1);
	rep(i,1,n){
		 scanf("%d",&a[i]);
		 if(i&1) T1.update(i,i*a[i]);
		 else T1.update(i,-i*a[i]);
		 if(i&1) T2.update(i,a[i]);
		 else T2.update(i,-a[i]);
	}
	char op[2];
	int u,v;
	ll ans=0;
	rep(i,1,m){
		scanf("%s %d %d",op,&u,&v);
		if(op[0]=='U'){
			if(u&1) T1.update(u,u*v-u*a[u]);
			else T1.update(u,-u*v+u*a[u]);
			if(u&1) T2.update(u,v-a[u]);
			else T2.update(u,-v+a[u]);
			a[u]=v;
		}else{
			if(u&1){
				ans+=T1.get(u,v)-(u-1)*T2.get(u,v);
				//cout<<u<<' '<<v<<' '<<T1.get(u,v)-(u-1)*T2.get(u,v)<<endl;
			}else{
				ans+=-T1.get(u,v)+(u-1)*T2.get(u,v);
			}
		}
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	rep(tt,1,T){
		printf("Case #%d: ",tt);
		solve();
	}
	return 0;
}

Codeforces Round #644 (Div. 3) F. Spy-string

题意：

给定$n$个长度为$m$的字符串，求一个等长字符串$s$使得$s$与每个字符串最多有一个位置不同。

题解：

我乱搜了一下就过了，时间复杂度???,不过貌似有更好的写法。

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
/*
* @author:  codancer
*/
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
int dif(string a,string b){
	int ans=0;
	for(int i=0;i<(int)a.length();i++){
		if(a[i]!=b[i]) ++ans;
	}
	return ans;
}
set<char> g[20];
string s[20];
int n,m;
string final;
void dfs(int depth,string ans,set<int> ow){
	if(depth==m-1){
		final=ans;
		return ;
	}
	set<int> nxt;
	for(char c:g[depth+1]){
		bool ok=1;
		rep(i,1,n){
			if(s[i][depth+1]!=c&&ow.find(i)!=ow.end()){
				ok=0;
				break;
			}
		}
		if(ok){
			nxt=ow;
			rep(i,1,n){
				if(s[i][depth+1]!=c) nxt.insert(i);
			}
			dfs(depth+1,ans+c,nxt);
		}
	}
}
int main(){
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		rep(i,1,n){
			cin>>s[i];
		}
		rep(j,0,19) g[j].clear();
		rep(j,0,m-1){
			rep(i,1,n){
				g[j].insert(s[i][j]);
			}
		}
		set<int> ow;
		final="";
		dfs(-1,"",ow);
		if(final.length()==0){
			cout<<-1<<endl;
		}else{
			cout<<final<<endl;
		}
	}
	return 0;
}

Codeforces Round #644 (Div. 3) G - A/B Matrix

题意：

构造一个$n\cdot m$的$01$矩阵使得每行$a$个$1$，每列$b$个$1$。

题解：

写了个贪心，没有证明就过了，首先可以排除叼不能构成的情况即$an!=bm$，然后直接按行填，但是要友嫌填列里面$1$最少的。

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
/*
* @author:  codancer
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
int ans[100][100];
int main(){
	int T;
	cin>>T;
	while(T--){
		memset(ans,0,sizeof(ans));
		int n,m,a,b;
		cin>>n>>m>>a>>b;
		if((n*a)%m){
			cout<<"NO"<<endl;
			continue;
		}
		if((n*a)/m!=b){
			cout<<"NO"<<endl;
			continue;
		}
		vector<int> cnt(60,0);
		int minn=0;
		rep(i,1,n){
			int add=0;
			rep(j,1,m){//先填最小的
				if(add>=a) break;
				if(cnt[j]==minn&&cnt[j]<b&&ans[i][j]==0){
					cnt[j]++;
					ans[i][j]=1;
					add++;
				}
			}
			rep(j,1,m){//把a用完
				if(add>=a) break;
				if(cnt[j]<b&&!ans[i][j]){
					cnt[j]++;
					ans[i][j]=1;
					add++;
				}
			}
			minn=1e8;
			rep(j,1,m){
				minn=min(minn,cnt[j]);
			}
		}
		cout<<"YES"<<endl;
		rep(i,1,n){
			rep(j,1,m) cout<<ans[i][j];
			cout<<endl;
		}
	}
	return 0;
}