首页 > 其他分享 >[赛记] 暑假集训CSP提高模拟15

[赛记] 暑假集训CSP提高模拟15

时间:2024-08-07 17:06:42浏览次数:19  
标签:赛记 15 int mid id vis 端点 ask CSP

原题还是没找

串串 49pts

用的 $ manacher $,板子差点没打对,但好歹还是打对了。。。

赛时写的时候没有考虑到不用管偶回文,导致递归的时候有点问题。。。

其实根本用不到递归,将循环顺序改为倒序即可;

有三种情况:

  1. 回文半径 + 位置能够到达右端点;

显然,这种情况是合法的;

  1. 既到不了左端点,又到不了右端点;

显然,这种情况是不合法的;

  1. 能到左端点,到不了右端点;

倒序循环,看看当前的右端点是否合法即可;

其实挺简单,但还是没切,赛时切两道题就这么难吗。。。

点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t;
char c[5000005];
char s[5000005];
int n;
int a;
int mid, r;
int p[5000005];
int vis[5000005];
int main() {
	cin >> t;
	while(t--) {
		mid = 0;
		r = 0;
		scanf("%s", s + 1);
		a = strlen(s + 1);
		if (a == 1) {
			cout << 1 << endl;
			continue;
		}
		n = 1;
		c[1] = '~';
		for (int i = 1; i <= a; i++) {
			c[++n] = s[i];
		}
		c[++n] = '#';
		for (int i = 1; i <= n; i++) {
			p[i] = 0;
			vis[i] = 0;
		}
		for (int i = 2; i <= n - 1; i++) {
			if (i <= r) p[i] = min(r - i + 1, p[2 * mid - i]);
			while(c[i - p[i]] == c[i + p[i]]) p[i]++;
			if (i + p[i] - 1 >= r) {
				r = i + p[i] - 1;
				mid = i;
			}
			if (i + p[i] - 1 >= n - 1) vis[i] = true;
		}
		for (int i = n - 1; i >= 2; i--) {
			if (vis[i]) continue;
			if (i - p[i] + 1 > 2) continue;
			if (vis[i + p[i] - 1]) vis[i] = true;
		}
		for (int i = 2; i <= n - 1; i++) {
			if (vis[i]) {
				cout << i - 1 << ' ';
			}
		}
		cout << endl;
	}
	return 0;
}

排排 100pts

结论题,所以没给大样例。。。

  1. 给出的就是顺序,需要0次操作;

  2. 1或n在自己的位置上,1次;

  3. 有在自己位置上的,且左边没有比它大的,右边没有比它小的,1次;

  4. 1在n上,n在1上,3次;

  5. 剩下情况2次;

对于3,我用了线段树维护,当然也可以用ST表等等;

点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n;
int a[500005];
int num[500005];
inline int ls(int x) {
	return x << 1;
}
inline int rs(int x) {
	return x << 1 | 1;
}
struct sss{
	int l, r, ma, mi;
}tr[3000005];
inline void push_up(int id) {
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
	tr[id].mi = min(tr[ls(id)].mi, tr[rs(id)].mi);
}
void bt(int id, int l, int r) {
	tr[id].l = l;
	tr[id].r = r;
	if (l == r) {
		tr[id].ma = a[l];
		tr[id].mi = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	bt(ls(id), l, mid);
	bt(rs(id), mid + 1, r);
	push_up(id);
}
int ask_ma(int id, int l, int r) {
	if (tr[id].l >= l && tr[id].r <= r) {
		return tr[id].ma;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return ask_ma(ls(id), l, r);
	else if (l > mid) return ask_ma(rs(id), l, r);
	else return max(ask_ma(ls(id), l, mid), ask_ma(rs(id), mid + 1, r));
}
int ask_mi(int id, int l, int r) {
	if (tr[id].l >= l && tr[id].r <= r) {
		return tr[id].mi;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return ask_mi(ls(id), l, r);
	else if (l > mid) return ask_mi(rs(id), l, r);
	else return min(ask_mi(ls(id), l, mid), ask_mi(rs(id), mid + 1, r));
}
int main() {
	cin >> t;
	while(t--) {
		cin >> n;
		num[0] = 0;
		bool vis = true;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			if (a[i] != i) vis = false;
		}
		bt(1, 1, n);
		if (vis) {
			cout << 0 << endl;
			continue;
		}
		if (a[1] == 1 || a[n] == n) {
			cout << 1 << endl;
			continue;
		}
		for (int i = 1; i <= n; i++) {
			if (a[i] == i) num[++num[0]] = i;
		}
		bool vi = false;
		for (int i = 1; i <= num[0]; i++) {
			if (a[num[i]] > ask_ma(1, 1, num[i] - 1) && a[num[i]] < ask_mi(1, num[i] + 1, n)) {
				cout << 1 << endl;
				vi = true;
				break;
			}
		}
		if (!vi) {
			if (a[1] == n && a[n] == 1) {
				cout << 3 << endl;
			} else {
				cout << 2 << endl;
			}
		}
	}
	return 0;
}

桥桥 13pts

标签:赛记,15,int,mid,id,vis,端点,ask,CSP
From: https://www.cnblogs.com/PeppaEvenPig/p/18347429

相关文章

  • LeetCode150 逆波兰表达式求值
    前言题目:150.逆波兰表达式求值文档:代码随想录——逆波兰表达式求值编程语言:C++解题状态:成功解答!思路还是利用栈的思想,遍历到数字时,加入栈,遍历到运算符时,取出两个数进行运算,并将结果加入到栈中。代码classSolution{public:intevalRPN(vector<string>......
  • 洛谷P1596 [USACO10OCT] Lake Counting S
    这种普通走迷宫的题,还是最好用bfs,毕竟复杂度是比dfs低的。但我这用dfs讲解。具体思路就不做详解,看代码注释。Code#include<bits/stdc++.h>usingnamespacestd;intn,m;chara[105][105];intdx[8]={0,1,-1,0,-1,1,-1,1};//搜索的八个方向常量,xintdy[8]={1,0......
  • 暑假集训CSP提高模拟15
    \[\color{red}{\huge囍挂111pts}\]叠词词恶心心T1串串一眼马拉车。我们来看看只翻转一次后就能得到答案的情况,就是如果某个位置的回文长度能到达这个字符串的末尾,那这个位置肯定能做翻转位置的,但是这种情况出现的位置只能在后半部分。如果是翻转多次的话,那么位置只能出现在......
  • 【JVM基础15】——实践-JVM调优的参数有哪些?
    目录1-引言:2-⭐核心:2-1设置堆空间大小2-2虚拟机栈的设置2-3年轻代Eden区和两个Survivor区的大小比例2-4年轻代晋升老年代阈值2-5设置垃圾回收器3-小结:3-1JVM调优的参数有哪些?1-引言:对于JVM调优,主要就是调整年轻代、老年代、元空间的内存空间大小......
  • 第15天:信息打点—主机架构&蜜罐识别&WAF识别&&端口扫描&协议识别&服务安全
    时间轴主要内容1、端口扫描-应用&协议2、WAF识别-分类&识别3、蜜罐识别-分类&识别解决:1、Web服务器&应用服务器差异性2、WAF防火墙&安全防护&识别技术3、蜜罐平台&安全防护&识别技术端口服务及渗透......
  • 代码随想录算法训练营第七天|454.四数相加II,383. 赎金信,15. 三数之和,18. 四数之和,总结
    力扣题部分:454.四数相加II题目链接:.-力扣(LeetCode) ​​​​​思路(map哈希表):    将数组分为两组分别用双重for循环遍历。第一组将来自不同数组的两个数之和(记为sum1)作为map的key,两个数之和出现的次数作为map的value,第二组通过在map查询来自不同数组的两......
  • [Tkey] CF1526B I Hate 1111
    给定一个数,将它表示成若干个形如\(11,111,1111\cdots\)之类的数之和,判断有没有可行解考虑到一种贪心,即从高位开始依次向下减去每位数字,判断还能不能减动,减不动或者没减完就报告无解.显然这样的贪心仅在\(11,111,1111\cdots\)的出现次数之和不超过\(9\)时是稳定正确的,一......
  • 【题解】暑假集训CSP提高模拟14
    目录Rank&挂分A.BA题目内容部分分10pts10+20pts正解思路代码B.BB题目内容部分分5pts正解思路代码C.BCD.BDRank&挂分T4暴搜后来改了记搜,不知道哪里锅了,挂5pts。A.BA题目内容现在有\(m\)块烙板,\(n\)张饼,第\(i\)张饼需要烙\(a_i\)个单位时间,一张饼一个单位时刻只能......
  • CSP14
    暴力最高\(50\)吧,本地测试不太准跑得快的只得了\(10\)分,慢的却得了\(50\)分暴力#include<bits/stdc++.h>#definepbpush_back#definelllonglong#definebsbitset<70>#definespeed()ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);usingnamespacestd;con......
  • 暑假集训CSP提高模拟14
    刚放假回来,好困……赛时rank38,T1100,T20,T30,T40打了T1后迷迷糊糊,半睡不睡的。这还能抢一个T1首切?T1BA烙饼问题。答案是\(\max(\max(a_i),\left\lceil\frac{\sum_{i=1}^na_i}{\min(n,m)}\right\rceil)\)还有一个二分答案的做法。但我们好像没有人写……点此查看......