ICPC2021南京部分题解

· 2022-04-18 ·

场上过了5题。自己就写了一道签到和树p，罚时过高。第一次icpc遗憾铜牌

A. Oops, It's Yesterday Twice More（签到题）

题意： 先判断离哪个角近走到角上，然后在走到(x, y)。

Solution： 签到水题

C. Klee in Solitary Confinement

题意： 长度为n的序列，选择一段区间加上k。使整个序列众数的数量最大。

Solution： 对每个 $a_i$ 和 $a_i-k$ 一起考虑即可。把这两个丢进一个vector里

$sum[i][0]$ 表示前 i 个中 $a_i$ 的个数， $sum[i][1]$ 表示前 i 个中 $a_i-k$ 的个数。

对一段 $l,r$ 答案即为： $sum[m][0]-(sum[r][0]-sum[l-1][0])+(sum[r][1]-sum[l-1][1])$

移项得： $sum[m][0]+(sum[r][1]-sum[r][0])+(sum[l-1][0]-sum[l-1][1])$

这样就能线性解决了，复杂度 $O(2n)$

特别的对 $k=0$ 的情况进行特判。

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define vpii vector<pi>
#define il inline
#define ri register
#define all(a) a.begin(), a.end()
#define fr(a) freopen(a, "r", stdin)
#define fo(a) freopen(a, "w", stdout);
#define mod 998244353
#define debug puts("------------------------")
#define lowbit(x) (x&-x)
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
void Read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
int  read() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
#define LOCAL
using namespace std;
const int maxn = 4000005;
/**/
int n, k, a[maxn], sum[maxn][2], ans;
vi v[maxn];
/**/
signed main()
{
	#if ONLINE_JUDGE
	#else
	// fr("test.in");
	// fo("test.out");
	#endif
	n = read(); k = read();
	for(int i = 1; i <= n; i++)
	{
		a[i] = read();
		a[i] += 2000000;
		v[a[i]].pb(a[i]);
		v[a[i] + k].pb(a[i]);
		ans = max(ans, max((int)v[a[i]].size(), (int)v[a[i] + k].size()));
	}
	if(!k)
	{
		cout << ans / 2;
		return 0;
	}
	ans = 0;
	for(int i = 0; i <= 4000000; i++)
	{
		int m = v[i].size();
		for(int j = 0; j < m; j++)
		{
			sum[j + 1][0] = sum[j][0] + (v[i][j] == i);
			sum[j + 1][1] = sum[j][1] + (v[i][j] != i);
		}
		int tmp = 0;
		ans = max(ans, sum[m][0]);
		for(int j = 1; j <= m; j++)
		{
			tmp = max(tmp, sum[j - 1][0] - sum[j - 1][1]);
			ans = max(ans, sum[m][0] + sum[j][1] - sum[j][0] + tmp);
		}
	}
	cout << ans << '\n';
	return 0;
}

M. Windblume Festival

题意： 长度为n的序列，每次可以选择一个 i，然后将 $a_i$ 和 $a_{i+1}$ 合并为 $a_i-a{i+1}$ 。求最后的一个数最大是多少

Solution： 对有正有负，只有正，只有负三种情况分类讨论一下即可。

H. Crystalfly

题意： 一个树形dp。自己写的，就不补了）

Solution： 考虑清楚细节就可以了。场上脑子一团浆糊简直）

D. Paimon Sorting

题意：

Solution：

J. Xingqiu's Joke

题意：

Solution：

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define vpii vector<pi>
#define il inline
#define ri register
#define all(a) a.begin(), a.end()
#define fr(a) freopen(a, "r", stdin)
#define fo(a) freopen(a, "w", stdout);
#define mod 998244353
#define debug puts("------------------------")
#define lowbit(x) (x&-x)
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
void Read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
int  read() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
#define LOCAL
using namespace std;
const int maxn = 200005;
/**/
vi v;
unordered_map<ll,int>f;
/**/
il ll get(int x, int y) { return x * 1e9 + y; }
int dfs(int a, int c)
{
	// cout << a << ' ' << c << '\n';
	if(a == 0) return 0x3f3f3f3f;
	if(a == 1) return 0;
	if(c == 1) return a - 1;
	if(f[get(a,c)]) return f[get(a,c)];
	int res = a - 1;
	for(auto p : v)
	{
		if(c % p == 0)
		{
			int tmp = a % p;
			res = min({res, tmp + 1 + dfs(a / p, c / p) , p - tmp + 1 + dfs(a / p + 1, c / p)});
		}
	}
	// cout << a << ' ' << c << ' ' << res << '\n';
	return f[get(a,c)] = res;
}
signed main()
{
	#if ONLINE_JUDGE
	#else
	fr("test.in");
	// fo("test.out");
	#endif
	int T = read();
	while(T--)
	{
		f.clear();
		v.clear();
		int a, b, c;
		a = read(); b = read();
		if(a > b) swap(a, b);
		c = b - a;
		for(int i = 2; i * i <= c; i++)
		{
			if(c % i == 0)
			{
				v.pb(i);
				while(c % i == 0) c /= i;
			}
		}
		if(c != 1) v.pb(c);
		// for(auto i : v) cout << "prime = " << i << '\n';
		// cout << v.size() << '\n';
		cout << dfs(a, b - a) << '\n';
		// return 0;
		// debug;
	}
	return 0;
}

L.Secret of Tianqiu Valley

题意：

Solution：

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define vpii vector<pi>
#define il inline
#define ri register
#define all(a) a.begin(), a.end()
#define fr(a) freopen(a, "r", stdin)
#define fo(a) freopen(a, "w", stdout);
#define mod 998244353
#define debug puts("------------------------")
#define lowbit(x) (x&-x)
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
void Read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
int  read() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
#define LOCAL
using namespace std;
const int maxn = 200005;
/**/
int n, a[maxn], d[maxn];
vi ans;
/**/
il int lst(int x) { return x == 1 ? n : x - 1; }
il int nxt(int x) { return x == n ? 1 : x + 1; }
il void change(int x)
{
	d[x] ^= 1;
	a[x] ^= 1; a[lst(x)] ^= 1; a[nxt(x)] ^= 1;
	ans.pb(x);
}
il void work1(int x)
{
	if(!a[x] && d[x])
	{
		change(x);
		work1(nxt(x));
		work1(lst(x));
	}
}
il void work2(int x) // 1 2 1 3
{
	if(!a[x] && !d[x])
	{
		change(x);
		if(d[nxt(x)])
		{
			change(nxt(x)); change(x); change(nxt(nxt(x)));
			work2(nxt(nxt(nxt(x))));
		}
		else
		{
			change(lst(x));	change(x); change(lst(lst(x)));
			work2(lst(lst(lst(x))));
		}
	}
}
il bool check()
{
	for(int i = 3; i <= n; i++)
	{
		d[i] = d[i - 1] ^ d[i - 2] ^ a[i - 1] ^ 1;
	}
	for(int i = 1; i <= n; i++)
	{
		if((a[i] ^ 1) != (d[lst(i)] ^ d[nxt(i)] ^ d[i])) return 0;
	}
	for(int i = 1; i <= n; i++) work1(i);
	for(int i = 1; i <= n; i++) work2(i);

	return 1;
}
il void solve()
{
	ans.clear();
	n = read();
	for(int i = 1; i <= n; i++) scanf("%1d", &a[i]);
	for(int i = 0; i <= 1; i++)
	for(int j = 0; j <= 1; j++)
	{
		d[1] = i, d[2] = j;
		if(check()) break;
	}
	cout << ans.size() << '\n';
	for(auto i : ans)
	{
		cout << i << ' ';
	}
	puts("");
}
signed main()
{
	#if ONLINE_JUDGE
	#else
	fr("test.in");
	// fo("test.out");
	#endif
	int T = read();
	while(T--)
	{
		solve();
	}
	return 0;
}

ICPC2021南京 部分题解

A. Oops, It's Yesterday Twice More（签到题）

C. Klee in Solitary Confinement

M. Windblume Festival

H. Crystalfly

D. Paimon Sorting

J. Xingqiu's Joke

L.Secret of Tianqiu Valley

ICPC2021南京部分题解