Educational Codeforces Round 89

比赛链接 / 官方题解链接

A. Shovels and Swords

Solution

答案是 $\min\left\{\left\lfloor\frac{a+b}{3}\right\rfloor,a,b\right\}$.

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 T, a, b;

int main(){
	for(read(T); T; T--){
		read(a, b);
		printf("%d\n", min((a + b) / 3, min(a, b)));
	}
	return 0;
}

---

B. Shuffle

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 = 105;

int T, n, x, m, l[N], r[N];

int main(){
	for(read(T); T; T--){
		read(n, x, m);
		int L = x, R = x;
		for(int i = 1; i <= m; i++){
			read(l[i], r[i]);
			if(l[i] <= R && L <= r[i]){
				L = min(L, l[i]);
				R = max(R, r[i]);
			}
		}
		printf("%d\n", R - L + 1);
	}
	return 0;
}

---

C. Palindromic Paths

Solution

可以证明：所有路径均为回文的充要条件是：对于 $2\leq k\leq n+m$，所有满足 $i+j=k\ 或\ n+m+2-k$ 的 $a[i][j]$ 均相等。

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 = 35;

int T, n, m, g[N][N];

int main(){
	for(read(T); T; T--){
		int ans = 0;
		read(n, m);
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				read(g[i][j]);
		for(int p = 2; p <= n + m; p++){
			int q = n + m + 2 - p;
			if(p >= q)	break;
			int cnt[2] = {0};
			for(int i = 1; i <= n; i++)
				for(int j = 1; j <= m; j++)
					if(i + j == p || i + j == q)
						cnt[g[i][j]]++;
			ans += min(cnt[0], cnt[1]);
		}
		printf("%d\n", ans);
	}
	return 0;
}

---

D. Two Divisors

Solution

分解质因数 $x={p_1}^{r_1}\cdot {p_2}^{r_2}\cdots{p_k}^{r_k}$，则取 $d_1={p_1}^{r_1},\ d_2={p_2}^{r_2}\cdots{p_k}^{r_k}$ 即可。

因为这样，对于 $x$ 的任一质因数 $a$，要么 $a\mid d_1$，要么 $a\mid d_2$，因此 $a\nmid (d_1+d_2)$，于是 $(d_1+d_2)\nmid x$.

那无解的情况就是 $x$ 只有一个质因数。

完成上述操作可以用线性筛，筛出质数的同时得到每个合数的最小质因数。

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 MAX = 10000005;

bool notP[MAX];
int pList[MAX], pID, minDiv[MAX];
void Euler(int n){
    notP[0] = notP[1] = 1;
    for(int i = 1; i <= n; i++){
        if(!notP[i])	pList[++pID] = i;
        for(int j = 1; j <= pID; j++){
            if(1ll * i * pList[j] > n)	break;
            notP[i * pList[j]] = 1;
            minDiv[i * pList[j]] = pList[j];
            if(i % pList[j] == 0)	break;
        }
    }
}

const int N = 500005;

int n;
vector<pii> ans;

int main(){
	Euler(10000000);
	read(n);
	for(int i = 1; i <= n; i++){
		int a; read(a);
		if(!notP[a])	ans.pb(mp(-1, -1));
		else{
			int d = minDiv[a];
			while(a % d == 0)  a /= d;
			if(a == 1)	ans.pb(mp(-1, -1));
			else	ans.pb(mp(d, a));
		}
	}
	for(auto &k: ans)	printf("%d ", k.first);
	puts("");
	for(auto &k: ans)	printf("%d ", k.second);
	return 0;
}

---

E. Two Arrays

Solution

由于 $b[]$ 单调递增的特点，针对 $a[]$ 开一个单调栈，对这个单调栈进行划分即可。第一划必须在第一个元素之前，对于第二划，找到单调栈中等于 $b[2]$ 的那个区间，设为 $(l,r]$（注意左开右闭），则第二划必须落在这个区间上，总共有 $r$ 对应的位置减去 $l$ 对应的位置那么多划法；后面类似。答案即所有划法之积。

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 = 200005;
const LL MOD = 998244353;

int n, m;
LL a[N], b[N];

int main(){
	read(n, m);
	for(int i = 1; i <= n; i++)	read(a[i]);
	for(int i = 1; i <= m; i++)	read(b[i]);
	vector<pii> sta(n+5); int sn = 0;
	for(int i = 1; i <= n; i++){
		while(sn > 0 && sta[sn].first > a[i])	sn--;
		sta[++sn] = mp(a[i], i);
	}
	if(sta[1].first != b[1])	return puts("0"), 0;
	LL ans = 1;
	int lst = 0;
	for(int i = 2; i <= m; i++){
		int l = lst, r = lst;
		while(l < sn && sta[l+1].first < b[i])	l++;
		if(l == sn)	return puts("0"), 0;
		while(r < sn && sta[r+1].first <= b[i])	r++;
		(ans *= sta[r].second - sta[l].second) %= MOD;
		lst = r;
	}
	printf("%lld\n", ans);
	return 0;
}