Algorithms Weekly 9

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;
}