首页 > 其他分享 >暑假训练2023.7.16

暑假训练2023.7.16

时间:2023-07-16 18:00:44浏览次数:46  
标签:opt 16 int mid 2023.7 暑假 oplus now poss

Codeforces Round 882 (Div. 2)

A. The Man who became a God

分成若干段后,分割处的差分会丢失,因此要使所求的各段的差分和最小,只需要让丢失的差分尽可能大。

求出序列差分,从大到小排序,去除前\(k - 1\)个即可。

B. Hamon Odyssey

首先一个数不断按位与其他数,结果是不增的,因此整个序列作为一组时按位与的结果一定为最小。

首先求出 \(s = a_1 \& a_2 \& ... \& a_n\), 此时有两种情况:

若\(s > 0\) :无论如何细分按位与的和一定大于s,因此答案为1

若\(s = 0\) :划分成的每一组的按位与一定也为0,因此从第一个位置贪心地往后划分,直到和为0,组数+1,然后从下一位置继续。对于结尾一段,若不为0则将其并入前面的一段,否则单独为一段。

C. Vampiric Powers, anyone?

若先取下标\(i = x\), 记$A = a_x \oplus a_{x + 1} \oplus ... \oplus a_m $

再取下标\(i = y, (y > x)\), 将其记为\(B\), 则\(B = a_y \oplus a_{y + 1} \oplus ... \oplus a_m \oplus a = a_y \oplus a_{y + 1} \oplus ... \oplus a_m \oplus a_x \oplus a_{x + 1} \oplus ... \oplus a_m = a_x \oplus ... \oplus a_y\)

当\(y < x\)时同理,可以发现经过两次操作我们可以取到原序列中任意一段子序列的异或和,则问题转换为求a的子序列异或和的最大值。

使用01-Trie可以解决

代码
const int N = 100005;
struct node {
	int next[2];
	int number;
};
node tr[N * 8];
int cnt = 0;
void insert(int x, int numb) {
	int p = 0;
	for(int i = 7; i >= 0; i--) {
		int now = (((1 << i) & x) == 0 ? 0 : 1);
		if(!tr[p].next[now]) {
			tr[p].next[now] = ++cnt;
		}
		p = tr[p].next[now];
	}
	tr[p].number = numb;
}
int sear(int x) {
	int p = 0;
	for(int i = 7; i >= 0; i--) {
		int now = ((1 << i) & x) == 0 ? 0 : 1;
		if(!tr[p].next[now ^ 1]) p = tr[p].next[now];
		else p = tr[p].next[now ^ 1];
	}
	return tr[p].number;
}
 
int main() {
	// freopen("data.in", "r", stdin);
	int T; cin >> T;
	while(T--) {
		cnt = 0;
		int n, a[N]; cin >> n;
		a[0] = 0;
		for(int i = 1; i <= n; i++) {
			cin >> a[i];
			a[i] = a[i] ^ a[i - 1];
			insert(a[i], i);
		}
		int ans = 0;
		for(int i = 1; i <= n; i++) {
			int numb = sear(a[i]);
			ans = max(ans, a[i] ^ a[numb]);
			ans = max(ans, a[i]);
		}
		cout << ans << endl;
		for(int i = 0; i <= cnt; i++) {
			tr[i].next[0] = tr[i].next[1] = tr[i].number = 0;
		}
	}
	return 0;
}

D. Professor Higashikata

首先可以知道,s字符串中每个位置的字符可能在拼接后的t串中出现若干次,但为了求最大字典序,我们只关心其在t中第一次出现的位置。

首先将t串简化,只保留s中每个字符在t中第一次出现的位置,这个处理可以用set维护,或者用一个链表暴力处理。得到新字符串T

对于T中为0的位置,我们可以将其与后面的1交换,或者与原串s中未参与构成T的1交换。记k等于原串s中未参与构成T的1的数量,则问题转化为在T中找一个位置x,满足1到x中0的数量等于x + 1到n中1的数量加上k,答案即为1到x中0的数量。

可以用树状数组维护某一区间中1和0的数量,然后二分查找位置x,每次询问时可以在\(O(log^2n)\)复杂度内完成

代码
const int N = 200005;
int n, m, q, tot = 0;
char ss[N];
int nextt[N], a[N], cnt = 0;
bool vis[N];
int c[N], pos[N];
inline int lowbit(int x) {
    return x & -x;
}
void add(int x, int k) {
    for(; x < N; x += lowbit(x)) c[x] += k;
}
int sum(int x) {
    int sum = 0;
    for(; x; x -= lowbit(x)) sum += c[x];
    return sum;
}
int getans() {
    int l = 0, r = cnt;
    while(l < r) {
        int mid = (l + r) >> 1;
        int lef0 = mid - sum(mid);
        int righ1 = sum(cnt) - sum(mid);
        if(lef0 >= righ1 + tot) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l - sum(l);
}
 
int main() {
    // freopen("data.in", "r", stdin);
    cin >> n >> m >> q;
    cin >> (ss + 1);
    for(int i = 1; i <= n; i++) {
        nextt[i] = i + 1;
    }
    for(int i = 1, l, r; i <= m; i++) {
        cin >> l >> r;
        int now = l;
        while(now <= r) {
            if(!vis[now]) {
                a[++cnt] = now;
                pos[now] = cnt;
            }
            vis[now] = true;
            int tmp = now; 
            if(now == n) break;
            now = nextt[now];
            if(tmp != r) nextt[tmp] = r;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i] && ss[i] == '1') tot++;
    }
    for(int i = 1; i <= cnt; i++) {
        if(ss[a[i]] == '1') {
            add(i, 1);
        }
    }
    for(int t = 1, opt; t <= q; t++) {
        cin >> opt;
        if(!vis[opt]) {
            if(ss[opt] == '1') {
                tot--; ss[opt] = '0';
            } else {
                tot++; ss[opt] = '1';
            }
        } else {
            int delt = 0;
            if(ss[opt] == '0') {
                delt = 1;
                ss[opt] = '1';
            } else {
                delt = -1;
                ss[opt] = '0';
            }
            add(pos[opt], delt);
        }
        cout << getans() << endl;
    }
    return 0;
}

F. The Boss's Identity

将n以后的项逐一列出来找规律,将a序列看成循环的,可以发现:

第\(kn+i, (i < n)\)项是\(a_i | a_{i + 1}|...|a_{j}\),其中,当\(i + k <= n\)时,\(j = i + k\),当\(i + k >= n + 1\)时,\(j = i + k + 1\)

且第\(n^2\)项之后,所有元素一定为\(a_1|a_2|...|a_n\)

考虑i相同的所有项,相当于不断地按位或上一些数,设所有数的值域为\(V\),每次或上一个数若产生了变化,则必有二进制上的一位从0变为了1,因此最多有\(O(logV)\)个不同的值。对于所有i,有\(O(nlogV)\)个不同的值。因此可以预处理出这些值然后二分查询。

预处理时枚举或区间的右端点,维护二进制每一位距离右端点最近的一个1的位置,然后将这一段的按位或的值记下来并算出对应a序列的坐标。

使用ST表可以\(O(1)\)查询一段区间的按位或。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N = 200005;
typedef long long lld;
int a[N << 1], n, q, maxx = 0;
int f[N << 1][23];
int las[32];
map<int, lld> mp;
vector<pair<int, lld> > poss;
inline int rmq(int l, int r) {
	int k = log2(r - l + 1);
	return f[l][k] | f[r - (1 << k) + 1][k];
}
lld getans(int x) {
	int l = 0, r = poss.size() - 1;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(poss[mid].first > x) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	return poss[l].second;
}

int main() {
	// freopen("data.in", "r", stdin);
	int T; scanf("%d", &T);
	while(T--) {
		maxx = 0;
		mp.clear(); poss.clear(); 
		scanf("%d%d", &n, &q);
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			maxx = maxx | a[i];
			if(!mp[a[i]]) mp[a[i]] = 1ll * i;
			else mp[a[i]] = min(mp[a[i]], 1ll * i);
		}
		for(int i = n + 1; i <= (n << 1); i++) {
			a[i] = a[i - n];
		}
		for(int j = 0; j <= 22; j++) {
			for(int i = 1; i <= (n << 1); i++) {
				if(j == 0) {
					if(i > n) {
						f[i][0] = a[i - n];
					} else {
						f[i][0] = a[i];
					}
				} else {
					if(i + (1 << j) > (n << 1)) continue;
					else f[i][j] = f[i][j - 1] | f[i + (1 << (j - 1))][j - 1];
				}
			}
		}
		memset(las, 0, sizeof(las));
		for(int i = 1; i <= (n << 1); i++) {
			if(i == n + 1) continue;
			for(int j = 0; j <= 30; j++) {
				if((a[i] >> j) & 1) {
					las[j] = i;
				}
			}
			int tmp[32];
			for(int t = 0; t <= 30; t++) {
				tmp[t] = las[t];
			}
			sort(tmp, tmp + 31);
			for(int j = 0; j <= 30; j++) {
				if(tmp[j] != tmp[j + 1] && tmp[j] <= n && tmp[j]) {
					lld k = (i > n) ? (i - tmp[j] - 1) : (i - tmp[j]);
					int now = rmq(tmp[j], i);
					if(mp[now] == 0) mp[now] = 1ll * tmp[j] + n * k; 
					else mp[now]= min(mp[now], 1ll * tmp[j] + n * k);
				}
			}
		}
		for(auto tmp : mp) {
			poss.push_back(tmp);
		}
		sort(poss.begin(), poss.end());
		for(int i = poss.size() - 2; i >= 0; i--) {
			poss[i].second = min(poss[i].second, poss[i + 1].second);
		}
		for(int i = 1, x; i <= q; i++) {
			scanf("%d", &x);
			if(x >= maxx) cout << "-1" << endl;
			else cout << getans(x) << endl;
		}
		for(int j = 0; j <= 22; j++) {
			for(int i = 1; i <= (n << 1); i++) {
				f[i][j] = 0;
			}
		}
	}
	return 0;
}

标签:opt,16,int,mid,2023.7,暑假,oplus,now,poss
From: https://www.cnblogs.com/mcggvc/p/17558274.html

相关文章

  • 【雕爷学编程】Arduino动手做(163)---大尺寸8x8LED方格屏模块2
    37款传感器与模块的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的,这里准备逐一动手试试多做实验,不管成功与否,都会记录下来——小小的进步或是搞不掂的问题......
  • 7.16周报
    文献阅读 (一)利用文本挖掘作为食品科学与营养的大数据分析工具:Utilizationoftextminingasabigdataanalysistoolforfoodscienceandnutrition-Tao-2020-ComprehensiveReviewsinFoodScienceandFoodSafety-WileyOnlineLibrary笔记地址:利用文本挖掘作......
  • 2023.07.16 高质量 NOIP 模拟赛题解
    HDU5719Arrange【模拟】给定数列\(B_n,C_n\),求出满足\[B_i=\min_{j=1}^i\{A_j\},\quadC_i=\max_{j=1}^i\{A_j\}\]的排列\(A\)的数量。维护每个位置可能的数字数量,然后乘法原理即可。代码:http://acm.hdu.edu.cn/viewcode.php?rid=38654445。HDU5807KeepInTouch......
  • 暑假补题记 1
     题目意思就是:有n个任务,每一个任务都有K个小任务每一个小任务都有指定时间,之后做完一个大任务额外加一分,然后给你M分钟,问在M分钟里,你需要得到最多分是多少。题解:首先对K个小任务排个序,对n个大任务进行遍历,就是你做完一个大任务,其他的时间全部搞小任务,然后一个个n进行比较,看看做......
  • 2023/7/16
    今天主要学习了字符串操作1.首先是获取字符串sbustring(int)和substring(int,int)前者是从索引开始一直到字符串的结尾,后者是从前索引位置到后索引位置,不包括后索引位置package字符串操作;publicclass获取子字符串{publicstaticvoidmain(String[]args){......
  • 【雕爷学编程】Arduino动手做(163)---大尺寸8x8LED方格屏模块
    37款传感器与模块的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的,这里准备逐一动手试试多做实验,不管成功与否,都会记录下来——小小的进步或是搞不掂的问题......
  • 暑假生活1
    放假第一周没放太多时间在学习上,稍微了解了一下大数据技术方面的知识,总结了一下这学期在知识层面的缺漏点。说实话有很多地方是不足的,可能是因为对浏览器等信息检索设备的利用率不够,加之我很难在对Javascript、CSS、HTML等语言了解不足的情况下实现简单的web界面的搭建以及对部......
  • 暑假第一周总结
    第一周主要学习了python还有hadoop的前期内容,还有Linux的基本命令,shell的基本命令python里面学习了python的注释方法,python里面的基本的三个函数input(),print(),type(),python的格式化输出。Hadoop里面学习了Hadoop是什么,Hadoop的基本概念,Hadoop里面的三大分类HDFS,YARN,MapReduce。安装了......
  • 7.16 动态规划
    线性DP[USACO20DEC]SleepingCowsP先不考虑极大,将奶牛和牛棚放在一起排序并离散化,设\(F_{i,j}\)为处理到第i个元素(奶牛/牛棚),有j头奶牛还没有进入牛棚的方案数。对于牛棚:\[F_{i,j}\rightarrowF_{i+1,j}\]\[j*F_{i,j}\rightarrowF_{i+1,j-1}\]对于奶牛:\[F_{i,j}......
  • [ARC162D] Smallest Vertices
    [ARC162D]SmallestVerticesAtcoder:[ARC162D]SmallestVertices洛谷:[ARC162D]SmallestVerticesProblem在本问题中,当我们提到有根有向树时,我们指的是所有边都指向从根到叶子的有根树。给定一个使得其总和为\(N-1\)的非负整数序列\(d=(d_1,d_2,\ldots,d_N)\)。对于带编......