Educational Codeforces Round 80 (Rated for Div. 2) 题解

Deadline

[Time Limit: 2 squad Memory Limit: 256 MB ]

这是个对勾函数,所以最小的话是在 (sqrt) 位置,所以只要找这附近的数字就可以了。

view
/*************************************************************** 
    > File Name        : a.cpp
    > Author           : Jiaaaaaaaqi
    > Created Time     : 2020/1/14 22:35:48
 ***************************************************************/

#include <bits/stdc++.h>
#define  fi         first
#define  se         second
#define  pb         push_back
#define  pii        pair<int, int>
#define  dbg(x)     cout << #x << " = " << (x) << endl
#define  mes(a, b)  memset(a, b, sizeof a)

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int    maxn = 1e5 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;

ll n, m;
int T, cas, tol = 0;

int main() {
	// freopen("in", "r", stdin);
	scanf("%d", &T);
	while(T--) {
		scanf("%lld%lld", &n, &m);
		ll x = sqrt(m), ans = INF;
		for(ll i=max(x-1000, 0ll); i<=min(n, x+1000); i++) {
			ans = min(ans, i + (int)ceil(1.0*m/(i+1)));
		}
		puts(ans<=n ? "YES" : "NO");
	}
	return 0;
}

Yet Another Meme Problem

[Time Limit: 1 squad Memory Limit: 256 MB ]

以下式子肯定成立

[ conc(a, b) = a*10^x+b = ab+a+b \ a*10^x = ab+a \ 10^x = b+1 ]

所以只要满足上述式子的 (b) 都是合法的,对 (a) 并没有限制,那么就可以算一下有多少个 (b) 就可以了。

view
/*************************************************************** 
    > File Name        : b.cpp
    > Author           : Jiaaaaaaaqi
    > Created Time     : 2020/1/14 22:57:36
 ***************************************************************/

#include <bits/stdc++.h>
#define  fi         first
#define  se         second
#define  pb         push_back
#define  pii        pair<int, int>
#define  dbg(x)     cout << #x << " = " << (x) << endl
#define  mes(a, b)  memset(a, b, sizeof a)

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int    maxn = 1e5 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;

ll n, m;
int cas, tol, T;

int main() {
	// freopen("in", "r", stdin);
	scanf("%d", &T);
	while(T--) {
		scanf("%lld%lld", &n, &m);
		ll ans = 0, x = 1;
		for(int i=1; ; i++) {
			x = x*10;
			if(x-1 <= m)	ans++;
			else	break;
		}
		printf("%lld
", ans*n);
	}
	return 0;
}

Two Arrays

[Time Limit: 1 squad Memory Limit: 256 MB ]

(dp[i][j]) 表示 (a、b) 数组都放到第 (i) 位,并且 (b[i]-a[i]=j) 的方案数,只要保证 (j>=0) 就一定是合法的。

view
/*************************************************************** 
    > File Name        : c.cpp
    > Author           : Jiaaaaaaaqi
    > Created Time     : 2020/1/14 23:04:21
 ***************************************************************/

#include <bits/stdc++.h>
#define  fi         first
#define  se         second
#define  pb         push_back
#define  pii        pair<int, int>
#define  dbg(x)     cout << #x << " = " << (x) << endl
#define  mes(a, b)  memset(a, b, sizeof a)

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int    maxn = 1e3 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;

int n, m;
int cas, tol, T;

ll dp[11][maxn];

int main() {
	// freopen("in", "r", stdin);
	scanf("%d%d", &n, &m);
	mes(dp, 0);
	dp[0][n-1] = 1;
	for(int i=0; i<m; i++) {
		for(int j=0; j<=n; j++) {
			if(dp[i][j] == 0)	continue;
			ll ans = 1;
			for(int k=j; k>=0; k--) {
				dp[i+1][k] = (dp[i+1][k] + dp[i][j]*ans%mod)%mod;
				ans = (ans+1)%mod;
			}
		}
	}
	ll ans = 0;
	for(int i=0; i<=n-1; i++)	ans = (ans+dp[m][i])%mod;
	printf("%lld
", ans);
	return 0;
}

Minimax Problem

[Time Limit: 5 squad Memory Limit: 256 MB ]

二分答案,然后就变成了判断某个值是否可行的可行性问题。

判断 (mid) 是否合法时,令 (b[i][j] = a[i][j]>=mid ? 1 : 0),那么问题就变成了找到一对 (pair<i, j>) 使得 (b[i] & b[j]) 的二进制全为 (1)。那么可以算出每一个行的状态,然后把这个状态的所有子状态都设成 (i),然后如果在之前存在某一个状态和这一行的状态互补,则说明找到了一对 (pair)

由于 (m) 只有 (8),则可以用数组暴力存储。

view
/*************************************************************** 
    > File Name        : d.cpp
    > Author           : Jiaaaaaaaqi
    > Created Time     : 2020/1/14 23:21:52
 ***************************************************************/

#include <bits/stdc++.h>
#define  fi         first
#define  se         second
#define  pb         push_back
#define  pii        pair<int, int>
#define  dbg(x)     cout << #x << " = " << (x) << endl
#define  mes(a, b)  memset(a, b, sizeof a)

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int    maxn = 3e5 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;

int n, m;
int cas, tol, T;

int mx;
int a[maxn][10];
int sta[maxn];

pii check(int mid) {
	for(int i=0; i<=mx; i++)	sta[i] = 0;
	for(int i=1; i<=n; i++) {
		int st = 0;
		for(int j=1; j<=m; j++) {
			if(a[i][j] >= mid)	st |= (1<<(j-1));
		}
		for(int j=st; ; j=(j-1)&st) {
			if(sta[j])	break;
			sta[j] = i;
			if(j==0)	break;
		}
		int nst = mx-st;
		if(sta[nst])	return {i, sta[nst]};
	}
	return {-1, -1};
}

int main() {
	// freopen("in", "r", stdin);
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++)	for(int j=1; j<=m; j++)
		scanf("%d", &a[i][j]);
	mx = (1<<m)-1;
	int l = 0, r = 1e9;
	pii ans;
	while(l<=r) {
		int mid = l+r>>1;
		pii pa = check(mid);
		if(pa.fi == -1 || pa.se == -1) {
			r = mid-1;
		} else {
			l = mid+1;
			ans = pa;
		}
	}
	printf("%d %d
", ans.fi, ans.se);
	return 0;
}

Messenger Simulator

[Time Limit: 3 squad Memory Limit: 256 MB ]

所有数的最小值和最大值一开始都是 (i),然后如果存在某个数字被提取到前面去,则这个数字的最小值就是 (1)

如果某个数字 (i) 从来没有被提取到前面去,则其最大值一定是 (i+) 出现的大于 (i) 的数字种类,这一部分可以使用一个后缀和实现。

对于某个数字 (i) 第一次提取到头部时,需要计算这个位置之前的数字中出现了大于 (i) 的数字种类,这一部分可以使用树状数组来实现。

对于某个数字 (i) 在两次提取到最前之间,也就是位置从 (1-x-1) 的过程,那么只要就算这个 (x) 即可,这个 (x) 其实就是这两次提取到头部之间的数字种类数 (+1),这一部分可以使用莫队来实现。为了方便做,对于每个数字的最后一次出现位置可以设置成 (m+1)

view
/*************************************************************** 
    > File Name        : e.cpp
    > Author           : Jiaaaaaaaqi
    > Created Time     : 2020/1/15 21:07:22
 ***************************************************************/

#include <bits/stdc++.h>
#define  fi         first
#define  se         second
#define  pb         push_back
#define  pii        pair<int, int>
#define  dbg(x)     cout << #x << " = " << (x) << endl
#define  mes(a, b)  memset(a, b, sizeof a)
#define	 lowbit(i)	(i&(-i))

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int    maxn = 1e6 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;

int n, m;
int T, cas, tol = 0;

int block;
struct Node {
	int l, r, id;
	bool operator < (Node a) const {
		return l/block==a.l/block ? r<a.r : l/block<a.l/block;
	}
} node[maxn];
int ans = 0;
int last[maxn], a[maxn];
int Min[maxn], Max[maxn], sum[maxn], cnt[maxn];
bool vis[maxn];

void add(int i) {
	if(cnt[a[i]] == 0)	ans++;
	cnt[a[i]]++;
}

void del(int i) {
	cnt[a[i]]--;
	if(cnt[a[i]] == 0)	ans--;
}

int main() {
	// freopen("in", "r", stdin);
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)	scanf("%d", &a[i]), cnt[a[i]] = 1;
	for(int i=n; i>=1; i--)	Min[i] = Max[i] = i, last[i] = m+1, cnt[i] += cnt[i+1];
	block = sqrt(m);
	for(int i=m; i>=1; i--) {
		if(i+1 <= last[a[i]]-1)	node[++tol] = {i+1, last[a[i]]-1, a[i]};
		last[a[i]] = i;
	}
	for(int i=1; i<=n; i++) {
		if(last[i] != m+1)	Min[i] = 1;
		else	Max[i] = max(Max[i], i+cnt[i]);
	}
	for(int i=1; i<=m; i++) {
		if(vis[a[i]])	continue;
		for(int j=a[i]; j; sum[j]++, j-=lowbit(j));
		int ans = 0;
		for(int j=a[i]+1; j<=n; ans+=sum[j], j+=lowbit(j));
		Max[a[i]] = max(Max[a[i]], a[i]+ans);
		vis[a[i]] = 1;
	}
	sort(node+1, node+1+tol);
	int L=1, R=0;
	for(int i=1; i<=n; i++)	cnt[i] = 0;
	for(int i=1; i<=tol; i++) {
		while(node[i].l < L)	add(--L);
		while(node[i].r > R)	add(++R);
		while(node[i].l > L)	del(L++);
		while(node[i].r < R)	del(R--);
		Max[node[i].id] = max(Max[node[i].id], ans+1);
	}
	for(int i=1; i<=n; i++)	printf("%d %d
", Min[i], Max[i]);
	return 0;
}
原文地址:https://www.cnblogs.com/Jiaaaaaaaqi/p/12199172.html