首页 > 其他分享 >230715校内赛

230715校内赛

时间：2023-07-17 22:12:29浏览次数：41  
标签：校内 int ne st lst 区间 230715 it1

T1 串

背景

形貌昳丽的西克是風子国王嫡系军队的 general, 同时也兼任風子王国驻绿鸟国的外交官。

西克喜欢在蕉含流群里与其它王国的使者蕉含流, 但前段时间由于说怪话被来自绿鸟国意识形态 不完全的国王驱含逐出境。

西克非常愤怒, 想要说出一句最怪的话, 但他却忙于敢览求社的训练。

于是, 他找到了你, 无上尼特, 想让你帮助解决他的问题。

题目描述

在風子王国, 一句话由 \(n\) 个词组成, 其中恰好有 \(k\) 个词是怪的, 其它的词都不是怪的。

众所周知, 负负得正, 我们定义一句话的一个区间是怪的, 当且仅当其中含有奇数个怪词。

请构造一句符合条件的话, 使得其中怪的区间数量最多。

输入格式

从文件 string.in 中读入数据。

一行两个整数 \(n,k\) 。

输出格式

输出到文件 string.out 中。

第一行一个整数 \(ans\), 表示至多可以有的怪的区间个数。

第二行一个长度为 \(n\) 的 01 串, 表示构造方案, 若一个单词是怪的, 输出 1 , 否则输出 0 , 字符 间用空格隔开。

本题使用自定义校验器检验你的答案是否正确, 因此若有多种满足条件的方案, 你只需要输出任 意一种。

样例

输入数据 1

7 2

输出数据 1

16 
0 1 0 0 0 1 0

怪的区间有 [1, 2], [1, 3], [1, 4], [1, 5], [2, 2], [2, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 6], [4, 7], [5, 6], [5, 7], [6, 6], [6, 7] 共 16 个。

数据规模与约定

对于所有测试点：\(1≤n≤10^5，0≤k≤n\)。

每个测试点的具体限制见下表：

测试点 \(n\) \(k\)
1∼2 \(≤10\) ≤n
3∼5 \(≤10^3\) 同上
6∼7 \(≤10^5\) 1
8 同上 2
9∼10 \(≤n\) $ \le n$

题解

打表题，正常看挺难看出它的规律，打表则很容易计算出来

是我不会推导

有人忘了开longlong，还没特判

大概看了一下正常思路代码我就不写了

先特判 \(k=0\) 的情况。

将数组做前缀和, 令前缀和数组中 1 的个数为 \(X,0\) 的个数为 \(Y\), 则答案为 \(X \times Y\), 由于\(X+Y=n+1\), 所以我们只需要让 \(X,Y\) 尽量接近, 一种简单的做法是先在最前方放 \(k−1\) 个 1 , 再在后面的位置中选择最优 的位置放一个 1 , 可以发现, 这样构造一定能够做到 \(X \times Y\) 取到最大, 时间复杂度 \(\mathcal O(n)\),

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100010];
long long ans;
int main(){
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	scanf("%d%d",&n,&k);
	if(k==0){
		puts("0");
		for(int i = 1;i<=n;i++)	
			printf("0 ");
		return 0;
	}
	ans = (long long)((n/2)+1)*(long long)(n/2);
	if(n%2==1) ans+=(long long)(n/2)+1;
	printf("%lld\n",ans);
	for(int i = n;i>=n-k+2;i--) a[i] = 1;
	a[(n-k)/2+1] = 1;
	for(int i = 1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}

背景

吉娜是一名艺术家, 一名表演艺术家 (performance artist)。

此时正值風子王国建国 114514 周年, 風子国王抵德请来艺术家吉娜设计游行的道路。

吉娜非常重占视这份工作, 但却在喝水的时候被巡逻的抵德训占斥工作不认真, 于是剥占夺了吉 娜的设计权利, 将吉娜贬含为了负责计算道路的信息的计算机。

吉娜心想: “为什么设计的时候不能喝水? ?? 我听歌都可以设计好。”

但终是敢怒占不敢言, 不幸的是, 计算量实在太大, 吉娜怕黑, 必须赶在天黑占之前做完工作。 于是他请来了你, 伟大尼特, 帮助它解决这个问题。

题目描述

给定一个长度为 n 的颜色序列 c 。

再给出 m 个区间, 第 i 个区间为 \([l_i,r_i]\) 保证任何两个区间都是不相交或包含的关系。

在接下来的 q 个单位时间内, 第 \(i\) 个时间会给定 \(x,y\), 表示将 \(c_x\) 变为 \(y\) 。

请对于每一个区间求出, 最早的其中所有颜色都互不相同的时间。

输入格式

从文件 artist.in 中读入数据。

第一行三个正整数 \(n,m,q\) 。

接下来一行 \(n\) 个整数, 第 \(i\) 个数表示第 \(i\) 个点的初始颜色 \(c_i\)。

接下来 \(m\) 行, 每行两个整数 $l_i,r_i $。

接下来 \(q\) 行, 每行两个整数 \(x,y\), 表示一次修改。

输出格式

输出到文件 artist.out 中。

令 \(L_i\) 表示第 \(i\) 个区间之中最早的所有颜色互不相同的时间, 若在修改前就已经满足条件, 则 \(L_i=0\), 若不存在这样的时间, 则令 \(L_i = m+i\) 。

请输出 \(⨁_{i=1}^mL_i\), 其中 \(⨁\) 表示二进制下的按位异或。

样例

输入数据 1

6 6 5 
1 2 1 2 1 2 
1 6 
5 5 
4 5 
3 5
2 5 
1 5 
5 2 
4 3 
2 1 
3 4 
1 5

输出数据 1

4

【样例解释 1】

\(L_i\) 依次为 7,0,0,2,4,5 。

数据规模与约定

对于所有数据, 满足 \(1≤n,m,q≤5×10^5,1≤l_i≤r_i≤n,1≤c_i,y≤n\), 保证任何两个区间都是 不相交或包含的关系，保证不存在两个完全相同的区间。

题解

发现所有区间不相交也不包含, 可以看作一个树形的关系, 一个区间的父亲必须在这个区间之后满足要求, 同时, 所有的叶子节点的区间互不相交, 相当于每个点只会在当前的一个区间中, 每次修改之后查询这个区 间是否合法即可。

查询一个区间是否合法有两种方式:

  1. 建出树, 相当于一个单点修改, 子树数颜色, 使用 dfsdfs 序, set, 树状数组可以做到 \(\mathcal O(logn)\) 。

  2. 在原数轴上维护 \(lst_i\) 表示 \(i\) 之前第一个颜色与 \(i\) 相同的点, 则一个区间内部颜色互不相同等价于 \(\min \{ lst_i,l≤i≤r \}\), 使用 set 和线段树维护可以做到 \(\mathcal O(logn)\)。

    时间复杂度 \(\mathcal O(n+(m+q)logn)\) 。

#include<bits/stdc++.h>
#define N 500010
#define mid ((l+r)>>1)
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
struct node{
	int x,y,id;
	bool operator<(const node &a)const{
		return x==a.x?y>a.y:x<a.x;
	}
}stk[N],p[N];
set<node>s;
set<node>::iterator it1;
set<int>st[N];
set<int>::iterator it;
int n,m,q,cnt,tim,X,Y,tp,lf[N],rg[N],rd[N],ans[N],c[N],h[N],ne[N],t[N<<2],lst[N],fa[N],pos[N],pre[N];
void add(int p,int l,int r){
	if(l==r){
		t[p] = Y;
		return ;
	}
	if(X<=mid) add(lc,l,mid);
	else add(rc,mid+1,r);
	t[p] = max(t[lc],t[rc]);
}
int ask(int p,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r) return t[p];
	int res = 0;
	if(ql<=mid) res = max(res,ask(lc,l,mid,ql,qr));
	if(qr>mid) res = max(res,ask(rc,mid+1,r,ql,qr));
	return res;
}
void build(int p,int l,int r){
	if(l==r){
		t[p] = lst[l];
		return ;
	}
	build(lc,l,mid);
	build(rc,mid+1,r);
	t[p] = max(t[lc],t[rc]);
}
void change(int x,int y){
	if(ne[x]){
		X = ne[x];
		Y = lst[x];
		add(1,1,n);
	}
	ne[lst[x]] = ne[x];
	lst[ne[x]] = lst[x];
	st[c[x]].erase(x);
	c[x] = y;
	int p = lst[x];
	it = st[y].upper_bound(x);
	lst[x] = ne[x] = 0;
	if(it!=st[y].end()){
		X = *it;
		ne[x] = X;
		Y = x;
		add(1,1,n);
	}
	if(it!=st[y].begin()){
		it--;
		lst[x] = *it;
	}
	st[y].insert(x);
	lst[ne[x]] = ne[lst[x]] = x;
	X = x;
	Y = lst[x];
	if(p^Y) add(1,1,n);
}
void check(int x){
	if(ask(1,1,n,lf[x],rg[x])<lf[x]){
		s.erase((node){lf[x],rg[x],x});
		ans[x] = tim;
		if(fa[x]&&(!(--rd[fa[x]]))){
			rd[fa[x]] = -1;
			s.insert(p[pos[fa[x]]]);
			check(fa[x]);
		}
	}
}
int main(){
	freopen("artist.in","r",stdin);
	freopen("artist.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i = 1;i<=n;i++)	
		scanf("%d",&c[i]);
	for(int i = 1;i<=m;i++){
		lst[i] = pre[c[i]];
		ne[pre[c[i]]] = i;
		pre[c[i]] = i;
		st[c[i]].insert(i);
	}
	build(1,1,n);
	for(int i = 1;i<=m;i++){
		scanf("%d%d",&p[i].x,&p[i].y) ;
		lf[i] = p[i].x;rg[i] = p[i].y;
		ans[i] = m+i;
		p[i].id = i;
	}
	sort(p+1,p+m+1);
	for(int i = 1;i<=m;i++){
		if(p[i].x==p[i].y||ask(1,1,n,p[i].x,p[i].y)<p[i].x){
			ans[p[i].id] = 0;
			rd[p[i].id] = -1;
			continue;
		}
		pos[p[i].id] = i;
		while(tp&&stk[tp].y<p[i].x) tp--;
		fa[p[i].id] = stk[tp].id;
		stk[++tp] = p[i];
		rd[fa[p[i].id]]++;
	}
	for(int i = 1;i<=m;i++){
		if(!rd[p[i].id])
			s.insert(p[i]);
	}
	for(int i = 1;i<=q;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		tim = i;
		change(x,y);
		it1 = s.upper_bound((node){x,0,0});
		if(it1!=s.begin()){
			it1--;
			check((*it1).id);
		}
	}
	int res = 0;
	for(int i = 1;i<=m;i++)
		res^=ans[i];
	printf("%d",res);
	return 0;
}

T3 黑白树(tree)

背景

一天, 風子国王抵德带着助手尼特以及西可和西克来到一片 dark 含森林探险, 在这里, 它们发 现了 \(n\) 个阿玮。

与此同时, 杰哥带着彬概也正好发现了这些阿玮。

与此同时, 抵德也发现了杰哥带着彬彬也正好发现了这些阿玮。

抵德说: “如果这些阿玮给你的话, 那么它们就不是我的了”。

杰哥说: “如果这些阿玮给你的话, 那么它们就不是我的了”。

两边吵得不可开蕉♂，这时，尼特发现，这些阿玮有些非常逊，有一些非常勇♂，于是经过调解, 抵德带走了所有逊的阿玮, 杰哥带走了所有勇含的阿玮。

同时, 尼特发现这 \(n\) 个阿玮之间仿佛产生了 \(n−1\) 条联系, 构成了一棵树的关系。

题目描述

给定一棵 \(n\) 个点的树, 每一个结点都可以是黑色或白色, 每一条边的长度都为 1 。

定义两个点的距离为两个点最短路径上边的条数, 定义一棵树的价值, 为同色点距离的最大值。 请求出在所有情况下, 树的价值之和, 对 \(10^9+7\) 取模。

输入格式

从文件 tree.in 中读入数据。

第一行一个正整数 \(n\) 。

接下来 \(n−1\) 行, 每行两个数 \(x,y\), 表示树中的一条边。

输出格式

输出到文件 tree.out 中。

输出一行一个数, 表示你的答案, 对 \(10^9+7\) 取模。

样例

输入数据 1

2
1 2

输出数据 1

2

【样例解释 1】

若两个点颜色相同，同色点距离最大值为 1。

若两个点颜色不同，同色点距离最大值为 0。

输入数据 2

6 
1 2 
2 3 
3 4 
4 5 
3 6

输出数据 2

224

题解

#include<bits/stdc++.h>
#define N 1000010
#define mod 1000000007
using namespace std;
struct edge{
	int v,ne;
}e[N<<1];
int n,s,cnt,ans,pos,sum,h[N],dis[N],c[N],dis1[N],c1[N];
bool vis[N];
void add(int u,int v){
	e[++cnt].v = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
int ksm(int x,int y){
	int ans = 1;
	while(y){
		if(y&1) ans = 1ll*ans*x%mod;
		x = 1ll*x*x%mod;
		y>>=1;
	}
	return ans;
}
void dfs(int u,int fa,int x){
	dis[u] = x;
	if(dis[u]>dis[pos]) pos = u;
	for(int i = h[u];i;i = e[i].ne){
		int v = e[i].v;
		if(v!=fa) dfs(v,u,x+1);
	}
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%lld",&n);
	for(int i = 1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1,1,0);
	int x = pos;
	pos = 0;
	dfs(x,x,0);
	for(int i = 1;i<=n;i++){
		if(dis[i]==dis[pos])
			sum++;
		c[dis[i]]++;
	}
	for(int i = 1;i<=n;i++){
		dis1[i] = dis[i];
		c1[i] = c[i];
	}
	x = pos;
	dfs(x,x,0);
	memset(c,0,sizeof(c));
	for(int i = 1;i<=n;i++){
		if(dis[i]==dis[pos])
			sum++;
		c[dis[i]]++;
	}
	for(int i = 1;i<=n;i++)
		vis[min(dis[i],dis1[i])] = true;
	int mx = dis[pos];
	sum = ksm(2,n);
	s = n+1;
	for(int i = mx;~i;i--){
		if(vis[i]){
			ans = (ans+1ll*sum*i%mod)%mod;
			printf("%d",ans);
			return 0;
		}
		s-=c[i];
		s-=c1[i];
		int tmp = ksm(2,s);
		ans = (ans+1ll*i*(sum-tmp+mod)%mod)%mod;
		sum = tmp;
	}
	return 0;
}

T4敢览求(rugby)

题目

题解

写不动了容我偷个懒

这道题根本不是给人写的吧

#include<bits/stdc++.h>
#define N 200010
using namespace std;
struct node{
	int x,y;
	bool operator <(const node A)const{
		return x==A.x?y<A.y:x<A.x;
	}
};
int n,K,ls[N],rs[N],a[N],b[N],f[N],cc,tot;
multiset<node>st[N];
multiset<node>::iterator it,it1,it2,it3,it4;
void find(multiset<node>&A,int x){
	it1 = A.upper_bound((node){x+1,-1});
}
bool ck(multiset<node>&A,multiset<node>&B){
	cc = 0;
	for(it = B.begin();it!=B.end();it++){
		find(A,(*it).x);
		if(it1!=A.begin()){
			it1--;
			if((*it1).y>=(*it).x) return 1;
			it1++;
		}
		if(it1!=A.end()&&(*it1).x<=(*it).y)return 1;
		tot++;
	}
	return 0;
}
void cg1(multiset<node>&A,multiset<node>&B){
	it2 = A.begin();
	cc = 0;
	for(it = B.begin();it!=B.end();it++){
		find(A,(*it).x);
		while(it2!=A.end()&&(*it2).y<(*it).x)it3=it2,++it2,A.erase(it3);
		if(it1!=A.begin()){
			it1--;
			int xx = -1;
			if((*it1).y>=(*it).x){
				xx = min((*it).y,(*it1).y); 
				A.insert((node){(*it).x,xx});
				A.erase(it1);
			}
			if(~xx&&(*it1).y!=xx) A.insert((node){xx+1,(*it1).y});
		}
		find(A,(*it).y);
		if(it1!=A.begin()){
			it1--;
			int xx = -1;
			if((*it1).x<=(*it).y){
				xx = min((*it).y,(*it1).y); 
				A.insert((node){(*it).x,xx});
			}
			if(~xx&&(*it1).y!=xx) A.insert((node){xx+1,(*it1).y});
			A.erase(it1);
		}
		it2 = A.upper_bound((node){(*it).y+1,-1});
		tot++;
	}
	while(it2!=A.end()){
		it3 = it2;
		it2++;
		A.erase(it3);
	}
}
void cg2(multiset<node>&A,multiset<node>&B){
	for(it = B.begin();it!=B.end();it++){
		int l = (*it).x,r = (*it).y;
		find(A,l);
		if(it1!=A.begin()){
			it1--;
			l = max(l,(*it1).y+1);
			it1++;
		}
		while(it1!=A.end()&&(*it1).y<=r){
			it2 = it1;
			it1++;
			A.erase(it2);
		}
		if(it1!=A.end()) r = min(r,(*it1).x-1);
		if(l<=r) A.insert((node){l,r});
		tot++;
	}
}
void dfs(int x){
	if(!ls[x]) swap(ls[x],rs[x]);
	if(ls[x]) dfs(ls[x]);
	if(rs[x]) dfs(rs[x]);
	if(a[x]>=b[x]){
		st[x].insert((node){0,K-a[x]-1});
		if(b[x]) st[x].insert((node){K-b[x],K-1});
	}else st[x].insert((node){K-b[x],K-a[x]-1});
	if(!ls[x]) return;
	if(!rs[x]){
		if(ck(st[ls[x]],st[x])){
			cg1(st[ls[x]],st[x]);
			f[x] = f[ls[x]];
		}else{
			cg2(st[ls[x]],st[x]);
			f[x] = f[ls[x]]+1;
		}
		st[x].swap(st[ls[x]]);
		return ;
	}
	multiset<node>tmp1,tmp2;
	if(st[ls[x]].size()<st[rs[x]].size()) swap(ls[x],rs[x]);
	if(ck(st[x],st[rs[x]])){
		tmp1 = st[rs[x]];
		cg1(tmp1,st[x]);
		if(ck(tmp1,st[ls[x]])){
			cg1(st[ls[x]],tmp1);
			st[x].swap(st[ls[x]]);
			f[x] = f[ls[x]]+f[rs[x]];
		}else{
			tmp2 = st[rs[x]];
			cg2(tmp2,st[x]);
			cg1(st[ls[x]],tmp2);
			cg2(st[ls[x]],tmp1);
			st[x].swap(st[ls[x]]);
			f[x] = f[ls[x]]+f[rs[x]]+1;
		}
	}else if(ck(st[ls[x]],st[x])||ck(st[ls[x]],st[rs[x]])){
		cg2(st[x],st[rs[x]]);
		cg1(st[ls[x]],st[x]);
		swap(st[x],st[ls[x]]);
		f[x] = f[ls[x]]+f[rs[x]]+1;
	}else{
		cg2(st[ls[x]],st[x]);
		cg2(st[ls[x]],st[rs[x]]);
		st[x].swap(st[ls[x]]);
		f[x] = f[ls[x]]+f[rs[x]]+2;
	}
}
int main(){
	freopen("rugby.in","r",stdin);
	freopen("rugby.out","w",stdout);
	scanf("%d%d",&n,&K);
	for(int i = 1;i<=n;i++)
		scanf("%d%d%d%d",&a[i],&b[i],&ls[i],&rs[i]);
	dfs(1);
	if((*st[1].begin()).x>0) f[1]++;
	printf("%d",f[1]);
	return 0;
}

最后一道绝对有点问题，烦请各位指正

标签：校内,int,ne,st,lst,区间,230715,it1
From： https://www.cnblogs.com/cztq/p/17561394.html

相关文章

  • HHHOJ #1247. 「NOIP 2023 模拟赛 20230715 A」1 题解--zhengjun
    法老找来的题，说是找了三道其他模拟赛的T4拼成T1~T3，另外搞了道T4。思维好题，但是放在T1有点搞心态，但是还好大样例够强，400没挂。然而T3大样例输出错了，浪费了我0.5h，差评。首先发现向左走之后向右走是一定不优的，所以最短路的情况只能先向右再向左。考虑枚举起点\(s......
  • 剑指offer_20230715
    剑指Offer67.把字符串转换成整数题目说明写一个函数StrToInt，实现把字符串转换成整数这个功能。不能使用atoi或者其他类似的库函数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符......
  • 230713校内赛
    MC党狂喜系列比赛T1命令方块题目描述实际上这道题与命令方块没有什么关系。给定\(n\)个字符串\(s_i\),将它们按给出的顺序排开。你每次可以交换任意两个字符串的位置。通过交换,这些字符串最终需要满足如下的性质:对于任意的\(i<j<k\),必须有:\(lcp(s_i,s_j)\gel......
  • 230712校内赛
    T1前缀和题目描述给你一个字符串，求所有长度为偶数的前缀在整个字符串中出现的次数和。输入格式共一行，一个字符串S输出格式共一行，输出一个整数，代表长度为偶数的前缀在整个字符串中出现的次数和样例输入数据1abababc输出数据16输入数据2isdashagayisdashagaydas......
  • 大学生毕业设计（论文）管理系统 校内互检 只能点左边高亮右边重复
    document.querySelectorAll("span.right_txt_blue").forEach(element=>{  letstr=element.getAttribute("name")  //letno=str[str.length-1]  letno=str.replace("rightblock","");  element.setAttribu......
  • 基于餐厅消费数据的隐形资助研究|校内数模竞赛分享
    前言幸亏校赛当做期末考试，才第一次这么认真点去审视一道建模同题目，前期的莽撞，对数据无奈是很崩溃的。另寻它解或是坚持耕耘都可以作为这次建模收官的关键词，因为它们真的都同时存在，并且不相上下。由于这是一道有关我们"本家"————大数据的题目，我们把数据处理当做了一个比较重要......
  • 校内天梯赛总结
    1107:ZN的随机数#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intans;intmain(){lln,m;while(cin>>n)//在while中赋值{ans=0;boola[1001]={0};for(inti=0;i<n;i++){intx;cin&g......
  • 2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛 L 捡贝壳
    题目链接还没补一道类似的题线段树上维护四个信息，从左端点向右连续的最大值lmx，从右端点向左连续的做大值rmx，区间最大值mx，区间和sum，每次pushup的时候如何维护四个信息？对......
  • 2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛 H 摘苹果
    题目链接算是比较入门的线段树题了考虑线段树上维护三个值，sum维护总和，used维护当前结点是否还能进行操作，cnt100维护当前结点里面树上苹果数量少于100的树的数量。我们可......
  • 2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛 J 前缀复制
    题目链接https://ac.nowcoder.com/acm/contest/52244/J对于给定的字符串s我们算出它每个位置能到达的前缀最大合法位置，然后进行dp即可先对于s串求一遍kmp，然后建立boder......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99