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

230712校内赛

时间：2023-07-12 22:01:09浏览次数：44  
标签：输出 校内 int 数据 石子 整数 230712 SG

T1 前缀和

题目描述

给你一个字符串，求所有长度为偶数的前缀在整个字符串中出现的次数和。

输入格式

共一行，一个字符串 S

输出格式

共一行，输出一个整数，代表长度为偶数的前缀在整个字符串中出现的次数和

样例

输入数据 1

abababc

输出数据 1

6

输入数据 2

isdashagayisdashagaydashisnotagaydashisnotagay

输出数据 2

30

数据规模与约定

对于30%的数据,|S|<=100,保证数据随机

对于100%的数据,|S|<=200000 。

题解

容易想到的是KMP算法中曾有一个p数组记录 \(1 \cdots p_i\) 和子串 \(i-p_i+1 \cdots i\) 相同，

所以长度为 \(i\) 的前缀出现的次数就可以计入长度为 \(p_i\) 的前缀出现次数中。

此时我们想到建树，节点的值代表长度为 \(i\) 的前缀出现的次数，所有偶数节点的值之和就是答案

所以正解代码如下

#include<bits/stdc++.h>
#define N 200010
using namespace std;
char s[N];
int ne[N],len,p[N],ans;
int main(){
	scanf("%s",s+1);
	len = strlen(s+1);
	ne[1] = 0;
	for(int i = 2,j = 0;i<=len;i++){
		while(j&&s[j+1]!=s[i]) j = ne[j];
		if(s[j+1]==s[i]) j++;
		ne[i] = j;
	}
	for(int i = 1;i<=len;i++) p[i] = 1;
	for(int i = len;i>=1;i--)
		p[ne[i]]+=p[i];
	for(int i = 1;i<=len;i++)
		if(i%2==0) ans+=p[i];
	printf("%d\n",ans);
	return 0;
}

而由于数据的随机性,有了以下的离谱代码

别问怎么来的，问就是考试时骗分骗满了

#include<bits/stdc++.h>
using namespace std;
long long ans;
char s[200010],s1[200010];
int n,m,cnt,a[200010];
bool vis[200010];
int main(){
	freopen("pre.in","r",stdin);
	freopen("pre.out","w",stdout);
	scanf("%s",s+1);
	n = strlen(s+1);
	s1[1] = s[1],s1[2] = s[2];
	m = 2;
	for(int i = 1;i<n;i++)
		if(s1[1]==s[i]&&s1[2]==s[i+1])
			a[++cnt] = i;
	while(m<n){
		for(int i = 1;i<=cnt;i++){
			if(vis[i]) continue;
			if(s1[m-1]==s[a[i]+m-2]&&s1[m]==s[a[i]+m-1])
				ans++;
			else vis[i] = true;
		}
		s1[m+1] = s[m+1],s1[m+2] = s[m+2];
		m+=2;
	}
	if(n%2==0) ans++;
	printf("%lld",ans);
	return 0;
}

T2 构造完全图

题目描述

对于完全图 \(G\),若有且仅有一棵最小生成树T,则称完全图G是由T拓展出的。给你一颗树 \(T\),找出 \(T\) 能拓展出的边权和最小的完全图 \(G\)。

输入格式

第一行 \(N\) 表示树 \(T\) 的点数。

接下来 \(N−1\) 行, \(S_i,T_i,D_i\) ;描述一条边 \((S_i,T_i)\) 权值为 \(D_i\) 。

保证输入数据构成一棵树。

输出格式

一个数，表示最小的图 \(G\) 的边权和

样例

输入数据 1

4 
1 2 1 
1 3 1 
1 4 2

输出数据 1

12

【样例说明】

添加 \(D(2,3)=2,D(3,4)=3,D(2,4)=3\) 即可。

样例2，见附加文件。

数据规模与约定

对于20%的数据，\(N \le 10\)

对于50%的数据，\(N \le 1000\)

对于100%的数据，\(N \le 10^5,1 \le D_i \le 10^5\)

题解

先正向思考如何生成一颗正向的最小生成树，毫无疑问会先将边排序一边

其次便是用 kruskal 进行贪心选择，

对于一条边我们考虑什么情况下不会被选择：

当边权更大且两个点都在同一个并查集时不会被选择

那么只要每次往树上加边时对并查集进行合并并统计答案即可

#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v;
	long long w;
	bool operator<(const edge &x)const{
		return w<x.w;
	}
}e[100010];
int n,h[100010],cnt,fa[100010];
long long num[100010],ans;
int find_(int x){
	return fa[x]==x?x:fa[x] = find_(fa[x]);
}
int main(){
	freopen("gouzao.in","r",stdin);
	freopen("gouzao.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i<=n;i++) fa[i] = i,num[i] = 1;
	for(int i = 1;i<n;i++){
		scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
		ans+=e[i].w;
	}
	sort(e+1,e+n);
	for(int i = 1;i<n;i++){
		int fx = find_(e[i].u),fy = find_(e[i].v);
		if(num[fy]>num[fx]) swap(fx,fy);
		ans+=(num[fx]*num[fy]-1)*(e[i].w+1);
		num[fx]+=num[fy];
		fa[fy] = fx;
	}
	printf("%lld",ans);
	return 0;
}

T3 独木桥

Alice和Bob是好朋友，有一天他们带了 \(n\) 个孩子过独木桥。

为了方便，我们将问题抽象如下：

将独木桥看成一个长度无限长的实数轴，将每个孩子看作数轴上的一个实数点。数轴从左到右坐标不断 增大。

孩子的位置用相对于数轴原点的点的坐标来表示。初始时 \(n\) 个点在 \(n\) 个互不相同的整点上。

每个点有一个初始朝向（从左向右或从右向左）。任何时刻所有的点都会以每秒11单位长度的速度匀速向 所朝的方向移动。当某一时刻两个点同时移动到了同一个位置上，它们会立即改变自己的朝向（从左向 右变成从右向左，反之亦然），然后继续移动。

有 \(q\) 次询问，每次询问给定 \(k_i\) 与 \(t_i\) ，询问在 \(t_i\)秒后，孩子 \(k_i\)目前的位置。

Bob 无法同时关注这么多的孩子，请你帮帮他。

输入格式

第一行一个整数 \(n\) 表示孩子数，孩子从0开始编号。

第二行 \(n\) 个整数 \(p_i\)，表示孩子们的初始位置。第三行 \(n\) 个整数 \(d_i\)，表示孩子们的初始朝向。\(d_i = 0\) 则初始向左，\(d_i = 1\) 则初始向右。

第四行一个整数 \(q\) 表示询问数。 接下来 \(q\) 行每行两个正整数 \(k_i,t_i\) 表示一个询问，询问在\(t_i\) 秒后，孩子 \(k_i\)（按输入顺序，从0开始编号 ）目前的位置。

输出格式

\(q\) 行每行一个整数表示答案。

样例

输入数据 1

5 
1 3 5 8 9 
1 1 1 0 0 
3 
3 2 
0 7  
1 5

输出数据 1

7
1
4

样例2：

见附加文件。

数据规模与约定

对于100%的数据，\(1≤n,q≤2×10^5，0≤k_i<n,0≤p_i,t_i≤10^9,d_i∈{0,1}\)

题解

直接求解则需要对孩子的朝向进行大规模的讨论，显然行不通。

但是我们可以发现两点性质

  • 孩子不断移动的过程中，他们的相对位置顺序永远不变

  • 假设相遇的孩子不会掉转方向（即擦肩而过），位置集合与相遇时调转方向的情况相同

    然后对于每个 \(i\) ，求出第 \(i\) 个孩子的位置排名 (从小到大) \(rk_i\)

    一组询问转化成求 S (\(t_i\) 秒后位置集合) 中第 \(rk_i\) 小的数把向左和向右的孩子分开处理，二分答案即可。

复杂度 \(\mathcal O(nlog^2n)\)

当然写二分可以做到upper_bound万岁

#include<bits/stdc++.h>
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;
struct node{
	int p,d,id;
}t[N];
int n,Q,cnt,tot,pos[N],q1[N],q2[N];
bool cmp(node t1,node t2){
	return t1.p<t2.p;
}
int pd(long long x,int t){
	int res1 = upper_bound(q1+1,q1+cnt+1,x-t)-q1-1;
	int res2 = upper_bound(q2+1,q2+tot+1,x+t)-q2-1;
	return res1+res2;
}
int main(){
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i<=n;i++){
		scanf("%d",&t[i].p);
		t[i].id = i;
	}
	for(int i = 1;i<=n;i++)
		scanf("%d",&t[i].d);
	sort(t+1,t+n+1,cmp);
	for(int i = 1;i<=n;i++)
		pos[t[i].id] = i;
	for(int i = 1;i<=n;i++){
		if(t[i].d==0) q2[++tot] = t[i].p;
		else q1[++cnt] = t[i].p;
	}
	scanf("%d",&Q);
	while(Q--){
		int k,ki,tt;
		scanf("%d%d",&ki,&tt);
		k = pos[ki+1];
		int l = t[1].p-tt,r = t[n].p+tt,res;
		res = r;
		while(l<=r){
			long long mid = ((long long)l+(long long)r)>>1ll;
			if(pd(mid,tt)>=k){
				res = mid;
				r = mid-1;
			}else l = mid+1;
		}
		printf("%d\n",res);
	}
	return 0;
}

T4 放石子

题目描述

Alice与Bob在玩游戏 定义游戏规则如下：给一张 n 个点，m 条边的有向无环图，每条边有颜色c，在图上放了 q 颗石子，每 颗石子在一个点上。每次操作时选择一个有出边且点上有石子的点 x，从点上取走一颗石子，然后选 择一个颜色集合 S，对于每条满足颜色 \(e \in S\) 的出边 i，在边i的终点上放上一颗石子。双方轮流操作， 不能操作者负。问Alice是先手获胜还是后手获胜。

输入格式

第1行包含两个整数 n 和 m，表示图的点数和边数。 第 2 到 m+1行每行包含三个整数 s,t和c，表示一条边的起点、终点和颜色。 接下来一行包含一个整数 q，表示石子数量。 接下来一行包含 q 个整数，表示每颗石子所在的点。

输出格式

输出一个整数，如果先手必胜则输出1，否则输出0。

样例

输入数据 1

2 1 
2 1 1 
1 
2

输出数据 1

1

数据规模与约定

实际测试时使用捆绑测试，一个测试点包含多个分测试点。

对于100%的数据，\(n≤200,m≤5000,q≤10000,c≤5000\)

题解

推荐阅读：SG函数和SG定理

显然这是公平博恋，我们要用到 SG 函数

我们将每个节点看成一个状态，将出度为 0 的点看成必败态

首先我们知道每个石子是独立的，我们只需要考虑求一个节点 u 上有一个石子时的 SG(u) 然后将所有石子的对应的 SG 函数求异或和即可得到答案。 我们先拓补排序，然后倒拓补序递推。 我们把结点u的所有出边按颜色分类，如果 c∈*S ，那么每种颜色 c 的边我们必须同时选择,所以我们可以将这一类的权值记为:

\[\oplus (u,v) \in E,(u,v) 的颜色 = c SG(v) \]

其中 \(\oplus\) 表示异或运算

我们将这个权值构成的集合称作A

那么我们所有决策对应的 SG 函数构成的集合就是 \({\oplus x\in B∣B \subset A}\) 。我们要求的就是从这个集合中任意选取一个子集，然后异或起来最小的得不到的数，\(mex{\oplus_{x∈B}x \subset A}\)。只有将A内的元素插入线性基，然后找不在线性基中的最低位，即最小的线性相关的位，设为第 \(i\) 位，就有\(SG(u) = mex{\oplus_{x \in B}x∣B\subset A}=2^i\)

并且求SG函数值的位数最坏情况下是\(\mathcal O(n)\) 的，我们需要用 bitset 来储存答案

总时间复杂度 \(\mathcal O( \frac{∣A∣×n^2}{64})\)

#include<bits/stdc++.h>
#define N 210
#define M 5010
using namespace std;
struct node{
	int ne,v,w;
}e[M];
int n,m,Q,a,cnt = 0,mx = 0,h[N],din[N];
bool vis[N],stp[N];
queue<int>q;
bitset<N>sum,k[N],sg[N],ex[N][M];
void add(int u,int v,int w){
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
void inst(bitset<N>now){
	for(int j = n;j>=0;j--){
		if(now[j]){
			if(!stp[j]){
				k[j] = now;
				stp[j] = 1;
				return ;
			}else now^=k[j];
		}
	}
}
int main(){
	freopen("stone.in","r",stdin);
	freopen("stone.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(v,u,w);
		din[u]++;
		mx = max(mx,w);
	}
	for(int i = 1;i<=n;i++) {
		if(!din[i]){
			vis[i] = 1;
			q.push(i);
		}
	}
	while(q.size()){
		int x = q.front();q.pop();
		if(!vis[x]){
			memset(stp,0,sizeof(stp));
			for(int i = 0;i<=mx;i++){
				if(ex[x][i].any())
					inst(ex[x][i]);
			}
			for(int i = 0;i<=n;i++){
				if(!stp[i]){
					sg[x][i] = 1;
					break;
				}
			}
		}
		for(int i = h[x];i;i = e[i].ne){
			int v = e[i].v,w = e[i].w;
			ex[v][w]^=sg[x];
			if(!(--din[v])) q.push(v);
		}
	}
	scanf("%d",&Q);
	for(int i = 1;i<=Q;i++){
		scanf("%d",&a);
		sum^=sg[a];
	}
	printf("%d",sum.any()?1:0);
	return 0;
}

标签：输出,校内,int,数据,石子,整数,230712,SG
From： https://www.cnblogs.com/cztq/p/17548979.html

相关文章

  • 20230712练习总结
    AGC009DUninity如果构造一棵点分树，答案是\(\logn\)，这是答案上界。将问题转化为每次将若干棵Uninity为\(k\)的树连接到一个点上时将点打上\(k+1\)的\(tag\)。看题面有一个很显然的结论就是两个\(tag=k\)的点间的路径上一定有一个\(tag>k\)。考虑记录\(f_u\)表示......
  • NOIP 2023 模拟赛 20230712 C 论剑
    首先是伟大的题面然后是数据范围先解决1-4号数据点1.枚举每个gcd的值p,统计一次答案，得到最小值（期望得分20）\[ans=\min_{p=2}^{\maxa}\sum^n_{i=1}\min(a_i\bmodp,p-(a_i\bmodp)(a>p))\]2.我们可以发现p仅在为质数时不会重复，也可以将p换为质数（期望得分40）两种的时间复......
  • HHHOJ #1238. 「NOIP 2023 模拟赛 20230712 D」但战斗还未结束 思考--zhengjun
    赛时想写60pts，结果cxr似乎少算了一点空间，导致我一直没把空间卡过去QWQ。当时不会dfs求拓扑序，这里讲一下。枚举所有非访问过的点依次dfs，每次进行下列操作：找出\(v\)的一个未访问过的入点\(u\)，调用dfs(u)；找不到\(u\)的时候，把\(v\)加入拓扑序列中。代码#inc......
  • 成语积累 20230712
    惨淡经营：惨淡：苦费心思；经营：筹划。原指煞费苦心地从事绘画或诗文创作，今泛指在困难的境况中艰苦的从事某种事业。作谓语，定语。不吐不茹：不吐刚，不茹柔：不吐坚硬的东西，不吞柔软的东西，即吞坚硬的东西。形容人正直不阿，不欺软怕硬。作谓语，定语。近义：刚正不阿。反义：柔茹刚吐。例句：我们就是......
  • 20230712 讲题
    CF1364DEhab'sLastCorollary简单题。特判掉\(m=n-1\)的情况，此时一定能找到一个大小为\(\left\lceil\frac{k}{2}\right\rceil\)的独立集，二分图染色即可。否则，我们建出dfstree，找到一条连接的两个端点深度之差最小的返祖边，设它为\((u,v)\)，且\(dep_u>dep_v\)。......
  • 大学生毕业设计（论文）管理系统 校内互检 只能点左边高亮右边重复
    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的树的数量。我们可......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99