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
*/
