搜索

10.6 QWJ专场 - llwwll - 博客园


发布时间: 2022-11-24 18:21:01    浏览次数:32 次

T1 炼心

题面

算法之路中有 \(n\) 名同学,第 \(i\) 个同学有 \(a\) , 表示该名同学的程序设计能力 , \(b\) 表示该名同学的学历,它的名字是 \(s\) 为字符串。

天榜学历不超过 13 ,地榜学历不小于 14,满足学历要求的同学会分别在两个榜单中排名。

你需要分别输出,天榜地榜当中,程序设计能力最强的同学中,学历最小的名字,存在多个则输出字典序最小的那一个,如果榜上无人,输出 −1。

分析

排序
结构体存几个变量,\(string\) 存不了用个 \(id\) 打标记,用自带的字符串排序就行

点击查看代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 100010
#define int long long
using namespace std;
int a,b;
string name[maxn];
int power,n,age,tott,totd,d,N;
struct node{string s;int power,age,id;};
node ti[maxn],di[maxn];
bool cmp(node a,node b)
{
	if(a.power==b.power)
	{
		if(a.age==b.age)
		{
			return name[a.id]<name[b.id];
		}
		else return a.age<b.age;
	}
	else return a.power>b.power;
}
signed main()
{
	freopen("reheart.in","r",stdin);
	freopen("reheart.out","w",stdout);
	cin>>N;
	for(int i=1;i<=N;i++)
	{

		cin>>name[i]>>power>>age;

		if(age>=14)
		{
			di[++totd].id=i;
			di[totd].power=power;
			di[totd].age=age;
		}
		if(age<=13)
		{
			ti[++tott].id=i;
			ti[tott].power=power;
			ti[tott].age=age;
		}
	}
	sort(ti+1,ti+tott+1,cmp);

	sort(di+1,di+totd+1,cmp);

	if(!tott) cout<<-1<<'\n';
	else cout<<name[ti[1].id]<<'\n';
	if(!totd) cout<<-1<<'\n';
	cout<<name[di[1].id]<<'\n';
	return 0;
}
/*
5
cafeiin 18 11 
George_Plover 20 12 
Karshilov 19 12 
wzk 23 14 
Lenska 18 12
*/

T2 炼气

题面

有一长度为 \(n\) 的字符串 \(S\) ,这个字符串由小写字母组成 。

师傅说,这本书有千万种变化,如果对于一个区间 \([l,r] (1⩽l⩽r⩽n)\) ,如果字符串
\(A=S_lS_{l+1}...S_{r-1}S_r\) 满足,有不超过 1 种字符出现了奇数次,则这个区间是一个“法门”。

\(Cafeiin\) 想知道这本书总共有多少个“法门。

分析

状压,前缀
容易想到用前缀统计 \(26\) 个字母在每一位出现的次数,然后用 \(26n^2\) 进行枚举

事实上每一个状态可以用一个 \(26\)\(2\) 进制表示 (1为奇,0为偶),以\(O(n)\) 递推
考虑每次枚举之前出现的次数,用一个前缀表示出现次数
考虑查询,因为是一个奇数,就考虑枚举这个奇数 (1)
对当前状态 \(A\) 每一位都 \(xor\) 1,得到之前状态 \(B\) ,就说明 \(A-B\) 之间是满足条件的
特殊情况,如果之前出现状态一模一样的,也要统计答案

点击查看代码
#include<iostream>
#include<cstdio>
#define int long long
#define maxn 1000010
using namespace std;
int n,ans,vis[(1<<27)],wow;
char s[maxn];
signed main()
{
	freopen("rebreth.in","r",stdin);
	freopen("rebreth.out","w",stdout);
	scanf("%lld",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		vis[wow]++;
		int tmp=s[i]-'a';
		wow^=(1<<tmp);
//		cout<<wow<<" "<<endl;;
//		if(!wow) ans++;
		ans+=vis[wow];
		for(int j=0;j<26;j++)
		{
			ans+=vis[wow^(1<<j)];
			
		}
//		cout<<endl;
	}
	printf("%lld\n",ans);
	return 0;
}
/*
4 
abab
a
1 0 
ab
1 1
aba
0 1
abab
0 0
*/

T3 炼体

题面

人体的经脉可以简化成一个有 \(n\) 个穴位的图,他们之间通过 \(n-1\) 条经络互相连通.每条经络长度
\(1\)
根据修行的炼体之术,一旦有一个穴位被打通,那么与它距离不超过 \(k\) 的穴位会被"活化"(包括自己)
\(Cafeiin\)想知道,最少需要打通自己多少个穴位,才能"活化"自己全身所有的穴位

分析

贪心,树形结构
容易想到从根节点开始打通,如果在该节点下未打通的距离为 \(k\) 则该节点必须打通
并且覆盖周围 \(k\) 个节点
具体看码

点击查看代码
#include<bits/stdc++.h>
#define N 200010
using namespace std;

int n,k,t,st,son,Ans;

int head[N],nex[N],ver[N],tot;
void add(int u,int v) {ver[++tot]=v; nex[tot]=head[u]; head[u]=tot; }

struct node {int id,dep;}re[N];
int fat[N],dis[N],bui[N];
bool cmp(node a,node b){return a.dep>b.dep;}

void DFS(int x,int fa,int dep)
{
	re[x].dep=dep;//记录深度 
	fat[x]=fa;//记录父亲节点 
	for(int i=head[x];i;i=nex[i])
	{
		int v=ver[i];
		if(v==fa) continue;
		DFS(v,x,dep+1);
	}
}

signed main()
{
//	freopen("rebody.in","r",stdin);
//	freopen("rebody.out","w",stdout);
	
	scanf("%d%d%d",&n,&k);
	for(int i=1,u,v;i<n;i++) 
	{
		scanf("%d%d",&u,&v);
		add(u,v); add(v,u);
	}
	DFS(1,1,0);
	for(int i=1;i<=n;i++) re[i].id=i;
	memset(dis,0x3f,sizeof (dis));//没有穴位时,所有距离为极大值 
	sort(re+1,re+n+1,cmp);//根据策略, 按照深度排序 
	// 由于树形结构 ,每个点的相互距离是唯一的,且必然经过公共祖先,因此只需要覆盖 穴位 的 k 个父亲
	// 在剩余点进行统计即可 
	for(int i=1;i<=n;i++)
	{
		st=son=re[i].id;
		for(int j=1;j<=k;j++) 
		{
			st=fat[st];
			dis[son]=min(dis[son],dis[st]+j);//跳 k 个父亲,并维护 son 到最近穴位的距离 
		}
		if(dis[son]>k) //距离超过 k 
		{
			Ans++;
			dis[st]=0;// 打通该点 
//			dis[son]=k;
			for(int j=1;j<=k;j++)// 覆盖这条链 
			{
				st=fat[st];
				dis[st]=min(dis[st],j);
			}
		}
	}
/*	for(int i=1;i<=n;i++) cout<<i%10<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<bui[i]<<" ";*/
	printf("%d\n",Ans);
	return 0;
}
/*

26 2 1
1 2
2 3
3 4
3 5
2 6
6 7
7 8
8 9
9 10
10 11
1 12
12 13
13 14
13 15
14 16
14 17
12 18
18 19
19 20
20 21
21 22
19 23
23 24
19 25
25 26

4 1 3
1 2
1 3 
1 4

6 1 3
1 2 
2 3
3 4
4 5 
5 6
*/
免责声明 10.6 QWJ专场 - llwwll - 博客园,资源类别:文本, 浏览次数:32 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:21:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/llwwll/p/16770869.html