EOJ 2020.7 月赛

比赛链接 / 官方题解链接

A. 打字机

Solution

显然，题设操作使得每一个 $b$ 前面必然有一个与之匹配的 $a$，所以如果某一前缀中 $a$ 的数量小于 $b$ 的数量，那么不合法。

于是我们找到最后一个 $a$ 和 $b$ 的数量相等的前缀，这之前的所有 $a$ 必然都是第二种（都是操作 $2$ 得到的）。如果之后没有 $b$ 出现，那么后面的 $a$ 必然都是第一种，输出 Happy；否则，可以有多种方案，输出 Sad。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 1000005;

int T, cnta[N], cntb[N];
char s[N];

int main(){
	for(read(T); T; T--){
		scanf("%s", s+1);
		int n = strlen(s+1);
		cnta[0] = cntb[0] = 0;
		for(int i = 1; i <= n; i++){
			cnta[i] = cnta[i-1] + (s[i] == 'a');
			cntb[i] = cntb[i-1] + (s[i] == 'b');
		}
		bool happy = true, dead = false;
		int mxpos = 0;
		for(int i = 1; i <= n; i++){
			if(cnta[i] < cntb[i]){ dead = true; break; }
			if(s[i] == 'b' && cnta[i] == cntb[i])	mxpos = i;
		}
		for(int i = mxpos + 1; i <= n; i++){
			if(s[i] == 'b'){
				happy = false;
				break;
			}
		}
		if(dead)	puts("Dead Fang");
		else if(!happy)	puts("Sad Fang");
		else	puts("Happy Fang");
	}
	return 0;
}

---

B. 线上考试

Solution

单选题共 $x$ 种可能，多选题共 $2^x-1$ 种可能，取最大即可。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int n, x, ans;
char c[2];

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		scanf("%s%d", c, &x);
		if(c[0] == 'S')	ans = max(ans, x);
		else	ans = max(ans, (1 << x) - 1);
	}
	printf("%d\n", ans);
	return 0;
}

---

C. OLED

Solution

对于屏幕的每个像素找到它在图像上可能出现的所有位置（是一个矩形），二维前缀和即可。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 4005;

int n, m, a, b;
int g[N][N];
int res[N][N];

inline int getSub(int u, int d, int l, int r){
	return g[d][r] - g[u-1][r] - g[d][l-1] + g[u-1][l-1];
}

int main(){
	read(n, m, a, b);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			read(g[i][j]);
			g[i][j] += g[i][j-1] + g[i-1][j] - g[i-1][j-1];
		}
	}
	int mx = 0;
	for(int x = 1; x <= a; x++){
		for(int y = 1; y <= b; y++){
			int u, d, l, r;
			if(x >= n)	d = n; else	d = x;
			if(x + n - 1 <= a)	u = 1; else	u = x - a + n;
			if(y >= m)	r = m; else	r = y;
			if(y + m - 1 <= b)	l = 1; else	l = y - b + m;
			res[x][y] = getSub(u, d, l, r);
			mx = max(mx, res[x][y]);
		}
	}
	for(int i = 1; i <= a; i++){
		for(int j = 1; j <= b; j++)
			// printf("%d ", res[i][j]);
			printf("%d ", (int)(res[i][j] * 100.0 / mx));
		puts("");
	}
	return 0;
}

---

D. 前缀排序

Solution

字符串连接比较问题的经典解法：按照 $A+B$ 和 $B+A$ 的比较顺序进行排序。

这道题关键是 cmp 函数的实现，我们希望在 $O(\lg n)$ 的时间内比较 $A+B$ 和 $B+A$。这里可以二分+哈希：二分找第一个前缀字符串不相等的位置，该过程使用哈希来比较前缀字符串是否相等。

时间复杂度：$O(n\lg^2n)$

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef unsigned long long ULL;

const int N = 200005;
const int MOD = 998244353;

int n, t[N], _10[N], p[N];
char s[N];

ULL h[N], base = 233, power[N]; // hash value of string s[1...i] is stored in h[i]
void Hash(char s[]){
	int len = strlen(s+1);
    h[1] = s[1];
    for(int i = 2; i <= len; i++)
        h[i] = h[i-1] * base + s[i];
}
ULL getSubstring(int l, int r){ // get hash value of s[l...r]
    return h[r] - h[l-1] * power[r-l+1];
}

bool check(int mid, int a, int b){
	ULL h1 = -1, h2 = -1;
	if(mid <= a)	h1 = h[mid];
	else	h1 = h[a] * power[mid-a] + h[mid-a];
	if(mid <= b)	h2 = h[mid];
	else	h2 = h[b] * power[mid-b] + h[mid-b];
	return h1 == h2;
}

bool cmp(int a, int b){
	int l = 1, r = a + b;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid, a, b))	l = mid + 1;
		else	r = mid;
	}
	char A, B;
	if(l <= a)	A = s[l];
	else	A = s[l-a];
	if(l <= b)	B = s[l];
	else	B = s[l-b];
	return A > B;
}

int main(){
	power[0] = 1, _10[0] = 1;
	for(int i = 1; i <= 200000; i++)	power[i] = power[i-1] * base;
	for(int i = 1; i <= 100000; i++)	_10[i] = _10[i-1] * 10ll % MOD;
	scanf("%s", s+1);
	n = strlen(s+1);
	Hash(s);
	for(int i = 1; i <= n; i++){
		t[i] = i;
		p[i] = (p[i-1] * 10ll % MOD + (s[i] - '0')) % MOD;
	}
	sort(t+1, t+n+1, cmp);
	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans = (1ll * ans * _10[t[i]] % MOD + p[t[i]]) % MOD;
	printf("%d\n", ans);
	return 0;
}

---

E. 因数串

Solution

$n$ 个质因数可以看成一个 $n$ 维向量，第 $i$ 维可以取值 $[0,k_i]$，每一次选择一维 $\pm1$，要求构造出一种方案使得所有 $\prod\limits_{i=1}^n(k_i+1)$ 种向量不重复地全部出现一次。

先考虑 $2$ 维的情况：我们可以递增第二维，每增加 $1$，第一维就正序或者逆序遍历一遍（上一次是正序则这一次是逆序，反之同理）。以 $(3,2)$ 为例：第二维为 $0$ 时，正序遍历第一维：$(0,0),(1,0),(2,0),(3,0)$，现在第二维 $+1$，逆序遍历第一维：$(3,1),(2,1),(1,1),(0,1)$，然后第二维再 $+1$，正序遍历第一维：$(0,2),(1,2),(2,2),(3,2)$，拼起来就是答案。

$n$ 维的情况就是递归进行 $2$ 维的构造。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int n;
LL p[20], k[20];
vector<LL> power[20];

vector<LL> v;
int sz;

void solve(int b){
	if(b == 1){
		for(int i = 0; i <= k[1]; i++)	v.pb(power[1][i]);
		sz = v.size();
		return;
	}
	solve(b-1);
	vector<LL> u(v);
	for(int i = 1; i <= k[b]; i++){
		if(i & 1){
			for(int j = sz - 1; j >= 0; j--)
				u.pb(v[j] * power[b][i]);
		}
		else{
			for(int j = 0; j < sz; j++)
				u.pb(v[j] * power[b][i]);
		}
	}
	v = u;
	sz = v.size();
}

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		read(p[i], k[i]);
		power[i].pb(1);
		for(int j = 1; j <= k[i]; j++)
			power[i].pb(power[i].back() * p[i]);
	}
	solve(n);
	for(auto &k : v)	printf("%lld\n", k);
	return 0;
}