当前位置: 首页 > article >正文

2023年 ZZU ACM 招新赛暨选拔赛题解

比赛题目链接

感谢wb学长贡献的 B、L题解

A. NANA与字符串—找规律

题目链接

注意题目中 字符串中只有a,b两个字符
因此只要找到左右两端点字符相同的子串,这个子串一定回文,这里不在证明
求长为偶数回文串数量,就等于求相同的两个字符,而下标奇偶性不同的数对数量,比如0, 1 两个下标都是‘a’,这是偶数回文
同理 求长度为奇数回文,等于求下标奇偶性相同的数对数量
求奇数时需要注意,因为奇偶性相同是同类,求数对数量即求组合数n*(n - 1)/ 2 最后加上每个单个的字符
偶数不需要除以2是因为奇偶性不同,不会重复

#include <iostream>
#include <cstring>
using namespace std;
#define int long long
signed main()
{
	string s; cin >> s;
	int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
	for(int i = 0; i < s.size(); i ++)
	{
		a1 += (s[i] == 'a' && (i & 1));
		a2 += (s[i] == 'a' && !(i & 1));
		b1 += (s[i] == 'b' && (i & 1));
		b2 += (s[i] == 'b' && !(i & 1));
	}
	
	int res = a1 * a2 + b1 * b2;
	cout << res << ' ';	

	res = (a1 - 1) * a1 / 2 + (a2 - 1) * a2 / 2 + (b1 - 1) * b1 / 2 + (b2 - 1) * b2 / 2;
	cout << res + s.size() << '\n';
}

B. NANA学跳舞 — 字典树

题目链接

对于给定的下界 k k k,可以发现如下性质.

性质1

k = 8 k=8 k=8为例,一个二进制数的二进制位可以分为k的最高位(1000)前的k的最高位后的.例如,16是最高位前的二进制位、4和8是最高位后的二进制位。

对于两组二进制数,可以证明,如果当前的二进制位数 u u uk的最高位靠前,那么这两个二进制数在 u u u上的取值对答案不构成影响. 证明如下:

设其一组 A A A u u u的下一位上取0,另一组 B B B u u u的下一位上取1. 那么任意 a ∈ A , b ∈ B , a   x o r   b > = k . a \in A, b\in B, a \space xor \space b >= k. aA,bB,a xor b>=k. 同时,由于任两个元素的异或也要 > = k >=k >=k,这就要求 A A A组内两两异或也要符合要求. 实际上,答案的个数就是 A A A组内合法的个数+ B B B组内合法的个数.

小结1

实际上,上面的性质可以转化成如下做法.

维护一棵字典树,对于比k的最高位高的位数,它的答案等于:

左子树的答案+右子树的答案. [ 1 ] ^{[1]} [1]

这样问题就转化为,对于一棵任意位都比k的最高位低的字典树,如何维护它的答案,使得结果 > = k >=k >=k?

[ 1 ] [1] [1]如果某一棵子树没有答案,由于左右子树异或之后的答案也合法,此时如果这棵子树有儿子,就可以强行使这棵树的答案取1.

性质2

对于上述的一棵低位字典树,其对答案的贡献只能是0或2.

证明如下.

对于任意二元组,要使它们的答案大于 k k k,就一定要有k的最高位上的结果是1,也就是说,这两个数在二进制的那一位上一个是0、一个是1.

这样答案就不可能>=3. 因为这样就一定会有两个元素在k的最高位上取得相同的结果,异或值也就不可能 > = k >=k >=k.

如果找不到这样的元组,答案为0.

问题就转化为,对于给定树根的字典树,是否存在二元组的异或值 > = k >=k >=k?

小结2

这是一个比较熟悉的问题. 我们可以转化问题为,求异或的最大值是否比 k k k大. 利用字典树即可解决.

总之,对于字典树内的每个节点我们都访问了一次,最终的复杂度为 O ( n ∗ l o g ( 2 30 ) ) O(n*log(2^{30})) O(nlog(230))

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e5 + 5;

int n, m, tr[N * 30][2], idx;

void add(ll c) {
    int root = 0;
    for (int i = 29; i >= 0; i --) {
        ll cur = ((c >> i) & 1);
        if (!tr[root][cur])
            tr[root][cur] = ++ idx;
        root = tr[root][cur];
    }
    a[root] = c;
}

ll tot;

vector<int> res;

void dfs2(int u, int cur) {
    if (!tr[cur][0] && !tr[cur][1]) {
        int root = u; ll ans = 0;
        for (auto c: res) {
            ans = ans * 2;
            if (tr[root][!c])
                ans += 1, root = tr[root][!c];
            else
                root = tr[root][c];
        }
        tot = max(tot, ans);
        return;
    }
    if (tr[cur][0]) {
        res.push_back(0);
        dfs2(u, tr[cur][0]);
        res.pop_back();
    }
    if (tr[cur][1]) {
        res.push_back(1);
        dfs2(u, tr[cur][1]);
        res.pop_back();
    }
}

ll dfs(int u, int k) {
     ll next = (1LL << (k - 1));
     if (next > m) {
        ll p1 = 0, p2 = 0;
        if (tr[u][0])
            p1 = dfs(tr[u][0], k - 1);
        if (tr[u][1])
            p2 = dfs(tr[u][1], k - 1);
        if (tr[u][0] && tr[u][1])
            return max(1LL, p1) + max(1LL, p2);
        else
            return p1 + p2;
     } else {
        tot = 0;
        dfs2(u, u);
        return (tot >= m)? 2: 0;
     }
}

int main() {
    cin >> n >> m;
    while (n --) {
        ll x; cin >> x;
        add(x);
    }
    ll p = dfs(0, 30);
    cout << (p == 0? -1: p);
}

C. NANA去上课 — 简单数学

需要记录上一步处在哪个位置
然后判断如果是同一侧移动距离就是abs(x1 - x2)
如果不同就是x1 + x2

#include <iostream>
#include <cmath>
using namespace std;
#define int long long
signed main()
{
	int n; cin >> n;
	char s, pres; 
	int x, prex; 
	cin >> pres >> prex;
	int res = prex;
	for(int i = 2; i <= n; i ++)
	{
		cin >> s >> x;
		if(pres != s) res += x + prex;
		else res += abs(prex - x);
		pres = s, prex = x;
	}
	res += prex;
	cout << res << '\n';
}

D. NANA在夜市 — bfs

倒着思考,从终点往周围扩展,判断能否到达,把能到达的点放入队列,接着扩展
这里判断时需要注意从能到达的点往外扩展时 方向是反着的,判断能否到达需要反着判断

#include <iostream>
#include <queue>
using namespace std;
const int N = 1010;
char g[N][N];
bool st[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};

signed main()
{
	int n, m; cin >> n >> m;
	for(int i = 0; i < n; i ++) cin >> g[i];
	int sx, sy;
	// 找到终点位置 
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m; j ++)
			if(g[i][j] == 'O')
				sx = i, sy = j;
	
	queue<pair<int,int>> q;
	q.push({sx, sy});
	st[sx][sy] = true;
	int res = 1;
	while(q.size())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i ++)
		{
			int ax = x + dx[i];
			int ay = y + dy[i];
			if(ax < 0 || ax >= n || ay < 0 || ay >= m || st[ax][ay]) continue;
			if((i == 0 && g[ax][ay] == 'D') || (i == 1 && g[ax][ay] == 'U') || (i == 2 && g[ax][ay] == 'L') || (i == 3 && g[ax][ay] == 'R')) 
			{
				q.push({ax, ay});
				st[ax][ay] = true;
				res ++;
			}
		}
	}
	cout << res << '\n';
	
}

E.


F. NANA 的排名 — 二分+排序

先按照每个人的最低分加入到总成绩,用两个数组记录,一个原始数组,一个按总成绩从大到小排序的数组
遍历每一个人,用二分在在已经排序的数组里找到比它的数的数量就是排名
这里不需要考虑原来加入的自己,因为按最高分加入一定比最低分加入高

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node
{
	int l, r;
	int sum;
};
bool cmp(Node a, Node b)
{
	return a.sum > b.sum;
}
signed main()
{
	int n; scanf("%d", &n);
	vector<Node> vec, pre;	
	for(int i = 0, l, r, x, sum; i < n; i ++)
	{
		scanf("%d %d", &l, &r);
		sum = 0;
		for(int j = 0; j < 5; j ++)
		{
			scanf("%d", &x);
			sum += x;
		}
		sum += l;
		vec.push_back({l, r, sum});
		pre.push_back({l, r, sum});
	}
	sort(vec.begin(), vec.end(), cmp);
	vector<int> res;
	for(int i = 0; i < n; i ++)
	{
		int sum = pre[i].sum + pre[i].r - pre[i].l;
		int l = 0, r = n;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(vec[mid].sum <= sum) r = mid;
			else l = mid + 1;
		}
		cout << l + 1 << '\n';
	}
}

G. NANA看天鹅舞会 — 贪心

最小的天鹅数黑白配对
剩下的相同2只配对
如果剩下的是奇数 减去c

#include <iostream>
using namespace std;
#define int long long
signed main()
{
	int n, m, a, b, c;
	cin >> n >> m >> a >> b >> c;
	if(n > m) swap(n, m);
	int res = n * a;
	m -= n;
	res += (m / 2) * b;
	if(m & 1) res -= c;
	cout << res << '\n';
}

H. NANA去集训 — 虚拟源点 + 堆优化的dijkstra

题目链接

这是一个很经典虚拟源点的模板题
需要将问题转化为单源最短路问题
因为最后还需要返回,因此路程距离直接乘2
对于每个答案,相当于求虚拟源点0 到点 i 的最短距离

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define int long long
const int N = 200010;
vector<pair<int, int>> g[N];
int d[N];
bool vis[N];
signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1, a, b, w; i <= m; i ++)
    {
    	cin >> a >> b >> w;
    	g[a].push_back({b, w * 2});
    	g[b].push_back({a, w * 2});
	}
	for(int i = 1, x; i <= n; i ++)
	{
		cin >> x;
		g[0].push_back({i, x});
	}
	
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
	for(int i = 1; i <= n; i ++) d[i] = 1e18;
	d[0] = 0;
	q.push({0, 0});
	while(q.size())
	{
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(auto [v, w] : g[u])
		{
			if(d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				q.push({d[v], v});
			}
		}
	}
	for(int i = 1; i <= n; i ++)
		cout << d[i] << " ";
}

I. NANA做胡辣汤 — 滑动窗口

先把处理好的全加起来
用hh记录长度为k窗口的左端点,遍历右端点每次求出长度为k的区间中的没处理好的调料数量
每次更新res

#include <iostream>
using namespace std;
const int N = 100010;
#define int long long
int a[N], b[N];
signed main()
{
	int n, k; cin >> n >> k;
	for(int i = 0; i < n; i ++) cin >> a[i];
	for(int i = 0; i < n; i ++) cin >> b[i];
	
	int hh = 0, sum = 0;
	for(int i = 0; i < n; i ++)
		if(b[i]) sum += a[i];
	
	// 先处理第一个窗口 
	for(int i = 0; i < k; i ++)
		if(!b[i]) sum += a[i];
	int res = sum;
	
	for(int i = k; i < n; i ++)
	{
		if(!b[i - k]) sum -= a[i - k];
		if(!b[i]) sum += a[i];
		res = max(sum, res);
	}
	cout << res << '\n';
}

J. NANA与她的朋友们 — 双指针

题目链接

k和ai很大,但是数只有1e5个,很容易想到离散化
因为每次影响的只有最大值和最小值,就可以直接看 最大值 和 最小值分别对应的数量哪个小
每次用k减去 那个小的,维护一个双指针,直到k小于0,或者双指针相遇

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define int long long
map<int,int> mp;
signed main()
{
	int n, k, x; scanf("%lld %lld",&n, &k);
	vector<int> vec;
	for(int i = 0; i < n; i ++)
	{
		scanf("%lld", &x);
		if(!mp.count(x)) vec.push_back(x);
		mp[x] ++;
	}
	sort(vec.begin(), vec.end());
	int hh = 0, tt = vec.size() - 1;

	while(hh < tt)
	{
		int l = mp[vec[hh]];
		int r = mp[vec[tt]];
		if(l < r)
		{
			int num = vec[hh + 1] - vec[hh];
			int cnt = l;
			if(k >= cnt * num)
			{
				k -= cnt * num;
				mp[vec[hh + 1]] += mp[vec[hh]];
				hh ++;	
			} 
			else
			{
				int t = k / cnt;
				k -= t * cnt;
				int res = vec[tt] - vec[hh] - t;
				cout << res << '\n';
				return 0;
			}
		}
		else
		{
			int num = vec[tt] - vec[tt - 1];
			int cnt = r;
			
			if(k >= cnt * num)
			{
				k -= cnt * num;
				mp[vec[tt - 1]] += mp[vec[tt]];
				tt --;
			}
			else
			{
				int t = k / cnt;
				k -= t * cnt;
				int res = vec[tt] - t - vec[hh];
				cout << res << '\n';
				return 0;
			}
		}
	}
	cout << 0 << '\n';
}

K. NANA在郑州 — 小模拟

#include <iostream>
using namespace std;
#define int long long
int val[] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};
signed main()
{
	int n;cin >> n;
	// kong ge
	int res = n - 1;
	while(n --)
	{
		string s; cin >> s;
		for(int i = 0; i < s.size(); i ++) res += val[s[i] - 'a'];
	}
	cout << res << '\n';
}

L. NANA与梦中的洛阳 — dp

如果问题缩减到1e6,由于y是单调不减的,dp跑一遍就好

但是现在问题是1e9的,可以考虑离散化,对于每个机关(x, y),维护y, y+1, y+2,即把这三项加入要离散化的序列中,随后跑一遍dp即可.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e6 + 5;
const int mod = 998244353;

int n, m, k;

int dp[N][4], f[N][4];

map<int, int> rev;

int main() {
    //freopen("parkour3.in", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> k;
    vector<pair<int, int>> res;
    rev[m] = 1, rev[1] = 1;
    for (int i = 0; i < k; i ++) {
        int u, v; cin >> u >> v;
        res.push_back({u, v});
        for (int j = v; j <= v + 2; j ++)
            rev[j] = 1;
    }
    int cnt = 0;
    for (auto [a, b]: rev) {
        rev[a] = ++ cnt;
    }
    for (auto c: res) {
        int a = c.first, b = c.second;
        f[rev[b]][a] = true;
    }
    dp[1][1] = true;
    int du = rev[m];
    for (int i = 1; i <= du; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (!f[i][j])
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
            else {
                dp[i + 1][max(1, j - 1)] = (dp[i + 1][max(1, j - 1)] + dp[i][j]) % mod;
                dp[min(du, i + 2)][j] = (dp[min(du, i + 2)][j] + dp[i][j]) % mod;
                dp[i + 1][min(n, j + 1)] = (dp[i + 1][min(n, j + 1)] + dp[i][j]) % mod;
            }
        }
    }
    for (int i = 1; i <= n; i ++)
        cout << dp[du][i] << '\n';
    return 0;
}
/*
all right,
but m8 tle?
*/

http://www.kler.cn/a/1900.html

相关文章:

  • 搭建Elastic search群集
  • 本科阶段最后一次竞赛Vlog——2024年智能车大赛智慧医疗组准备全过程——13使用Resnet-Bin
  • React 前端框架简介
  • opencv中的各种滤波器简介
  • MyBatis通过注解配置执行SQL语句原理源码分析
  • Python 写的 智慧记 进销存 辅助 程序 导入导出 excel 可打印
  • yolov8训练筷子点数数据集
  • 浏览器的组成部分
  • 2023美赛C题【分析思路+代码】
  • (只需五步)注册谷歌账号详细步骤,解决“此电话号码无法验证”问题
  • Android---动态权限申请
  • 算法学习之三步翻转法
  • 51单片机入门 -驱动 8x8 LED 点阵屏
  • 高速PCB设计指南(十五)
  • 【js】多分支语句练习(2)
  • Docker入门到放弃笔记之容器
  • Android绘制——自定义view之onLayout
  • 前缀和 及其优化技巧Ⅱ
  • SAP 发出商品业务配置
  • 蓝桥杯备赛 [day01]|python|迷宫问题|乘积尾零|平方和|切面条|付账问题
  • 数据可视化
  • 数据库:mysql的主从复制实战
  • 版本管理工具git 与 svn 的区别具体有哪些?
  • UE实现地面动态交互效果
  • 大数据框架保姆级安装教程——Kafka(3.0.0)
  • 小白学Pytorch系列--Torch API (7)