2022-10-6
T1
炼心
题目背景
\(Cafeiin\)神情认真，专心的听着老师讲话。
“既然你已拜入算法门下，我便为你讲讲这算法的修炼之道，算法之道，分几重境界，初入编程，便是普及，普及之上更有提高。提高之上，一劫一境界。提高巅峰强者引天雷入体渡劫，便能成就省选，省选再渡劫，便是集训队，集训队再渡劫，便证得IOI大道。天榜之下还有地榜，从校赛市赛省赛一路渡劫，证得ICPC world final总决赛。不过，天榜学历皆不过高中，个个都是万里挑一的奇才。为师便考考你，这天地二榜，谁为首。”
题目描述
算法之路中有\(n\)名同学。第\(i\)个同学有\(a_i\)，表示该名同学的程序设计能力，\(b_i\)表示该名同学的学历（\(1\) 表示幼儿园，\(2-7\) 表示小学，\(8-13\) 表示中学，大于\(13\) 表示更高学历），它的名字是\(s_i\)为字符串。
天榜学历不超过\(13\)，地榜学历不小于\(14\)，满足学历要求的同学会分别在两个榜单中排名。
你需要分别输出，天榜地榜当中，程序设计能力最强的同学中，学历最小的名字，存在多个则输出字典序最小的那一个,如果榜上无人,输出\(-1\)。
输入格式
第一行一个整数\(n\)
接下来\(n\)行，每行有三个数据，分别是名字字符串\(s_i\)，程序设计能力\(a_i\)，学历\(b_i\)。
输出格式
两行,第一行为天榜强者的名字,第二行为地榜强者的名字。
样例
样例输入
5
cafeiin 18 11
George_Plover 20 12
Karshilov 19 12
wzk 23 14
Lenska 18 12
样例输出
George_Plover
wzk
数据范围与提示
对于\(10\%\)的数据，天榜强者为George_Plover
对于\(10\%\)的数据，地榜强者为George_Plover
对于\(30\%\)的数据，\(1\leqslant n\leqslant100\)，\(a_i \leqslant10，b_i \leqslant10\)
对于\(100\%\)的数据，\(1\leqslant n\leqslant10^5\)，\(a_i \leqslant100，b_i \leqslant100，1\leqslant字符串s_i长度\leqslant15\)
保证名字互不相同
思路
简单排序题，按学历分成天榜地榜两类，分别按能力第一关键字、学历第二关键字、名字第三关键字排序输出即可。
代码
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,a,b;
string s;
struct node
{
string nam;
int a,b;
};
bool cm(string a,string b)//a<b
{
int la=a.length(),lb=b.length();
int len=min(la,lb);
for(int i=0;i<len;i++)
{
if(a[i]>b[i])return false;
}
return la<lb?true:false;
}
node tian[MAXN],di[MAXN];
int tott=0,totd=0;
bool cmp(node a,node b)
{
if(a.a!=b.a)return a.a>b.a;
if(a.b!=b.b)return a.b<b.b;
return a.nam<b.nam;
}
string sread()
{
getchar();
char c=getchar();
string ans;
while(c!=' ')
{
ans+=c;
c=getchar();
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
//cin>>s;
s=sread();
scanf("%d%d",&a,&b);
if(b<=13)
{
tian[++tott].nam=s;
tian[tott].a=a;
tian[tott].b=b;
}
else
{
di[++totd].nam=s;
di[totd].a=a;
di[totd].b=b;
}
}
sort(tian+1,tian+tott+1,cmp);
sort(di+1,di+totd+1,cmp);
if(tott)cout<<tian[1].nam<<endl;
else cout<<"-1"<<endl;
if(totd)cout<<di[1].nam;
else cout<<"-1";
return 0;
}
T2
炼气
题目背景
师傅讲完算法大道，便将一本黑色厚书丢给了\(Cafeiin\)，让\(Cafeiin\)好好阅读，随后又开始聊起了当年往事：“想当年，为师也是天榜榜上有名的天骄，年纪轻轻便入半步省选，只可惜为了宗门强行渡劫损了元神......”
虽然\(Cafeiin\)知道师傅是在吹牛，但\(Cafeiin\)还是看起了师傅给自己的书。
题目描述
这本书可以看作一个长度为\(n\)的字符串\(S\)，这个字符串由小写字母组成。
师傅说，这本书有千万种变化，如果对于一个区间\([l,r](1\leqslant l\leqslant r\leqslant n)\),如果字符串\(A=s_l s_{l+1}...s_{r-1}s_r\)满足，有不超过\(1\)种字符出现了奇数次，则这个区间是一个“法门”。
\(Cafeiin\)想知道这本书总共有多少个“法门”。
输入格式
第一行一个整数\(n\)，表示字符串\(S\)的长度。
接下来\(1\)行，一个长度为\(n\)的字符串\(S\)。
输出格式
一行一个整数，表示字符串\(S\)中的法门数量。
样例
样例输入
4
abab
样例输出
7
样例解释:区间(1,1),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)满足条件
数据范围与提示
对于\(30\%\)的数据，\(1\leqslant n\leqslant100\)
对于\(60\%\)的数据，\(1\leqslant n\leqslant10^4\)
对于\(100\%\)的数据，\(1\leqslant n\leqslant10^6\)，字符串\(S\)只由小写字母组成
思路
一个区间是“法门”的条件是有不超过\(1\)种字符出现了奇数次。根据此性质容易想到异或^。只要一个区间的所有元素的异或和是\(0\)或‘\(a\)’~‘\(z\)’之间，那么该区间就是一个法门。由此而来的一个暴力想法是处理一个异或前缀和，每次枚举区间的两个端点，计算区间异或和并判断。
但这样的复杂度是\(O(n^2)\)的，无法胜任此题。
考虑从左到右扫一边，同时记录一个\(26\)位的状态\(sta\)，它表示从最左端到当前点，所有字母出现了奇数次还是偶数次。 那么每次到一个地方，能使\(ans\)增加的只会是 以当前节点为右端点且异或和为\(0\)或‘\(a\)’~‘\(z\)’的区间数，即之前与\(sta\)异或的结果 的二进制码中 只有一个\(1\)或没有\(1\)的状态数。因此我们每次更新\(sta\)的时候，\(ans+=cnt[sta\)^（\(0\)或\(1\)<<\(k\)，\(k\in\)[\(0,25\)]）\(]\)，同时用于计数的\(cnt[sta]++\)。这样就统计出了答案。
代码
#include<bits/stdc++.h>
#define MAXN 67108865
#define int long long
using namespace std;
string s;
int n,st,a[MAXN]={0},ans=0;
bool flag=0;
string sread()
{
char c=getchar();
string ans;
while(c>='a'&&c<='z')
{
ans+=c;
c=getchar();
}
return ans;
}
string to_b(int x)
{
string ans;
while(x)
{
ans+=(x%2)+'0';
x>>=1;
}
while(ans.length()<2){ans+='0';}
return ans;
}
signed main()
{
scanf("%lld",&n);
getchar();
s=sread();
st=0;
a[st]=1;
for(int i=1;i<=n;i++)
{
flag=0;
st^=(1<<(s[i-1]-'a'));
for(int j=1;j<=26;j++)
ans+=a[st^(1<<(j-1))];
ans+=a[st];
a[st]++;
}
printf("%d",ans);
return 0;
}
T3
炼体（原题:将军令）
题目背景
“又说回来了，虽说为师当年损失了元神，但是为师的图论......啊不炼体之术可没有落下，这炼体之
道，打通奇经八脉......”
题目描述
人体的经脉可以简化成一个有\(n\)个穴位的图，他们之间通过\(n-1\)条经络互相连通.每条经络长度
为\(1\)。
根据修行的炼体之术，一旦有一个穴位被打通,那么与它距离不超过\(k\)的穴位会被"活化"(包括自己)
Cafeiin想知道，最少需要打通自己多少个穴位，才能"活化"自己全身所有的穴位。
输入格式
第一行一个整数\(n\)，表示共有\(n\)个穴位。
接下来\(n\)行，每行\(2\)个整数\(x、y\)，表示\(x\)穴位到\(y\)穴位之间存在一条长度为\(1\)的边。
输出格式
一行一个整数，表示所需打通最少穴位数量样例。
样例输入1
4 1
1 2
1 3
1 4
样例输出1
1
样例输入2
6 1
1 2
1 3
1 4
4 5
4 6
样例输出2
2
样例\(1\):打通\(1\)号,所有穴位被激活。
样例\(2\):打通\(1\),\(4\)号,所有穴位被激活。
数据范围与提示
对于\(30\%\)的数据，\(n\leqslant10^2\)
对于\(50\%\)的数据，\(n\leqslant10^4，k\leqslant1\)
对于\(100\%\)的数据，\(1\leqslant n\leqslant10^5，0\leqslant k\leqslant20\)
思路
这道题是一类经典的树形\(DP\)的拓展，详见战略游戏和消防局的设立这两题。
但对于这道题较简单的思路并不需要树形\(DP\)。考虑一个贪心策略：先以一个点为根\(dfs\)一遍，求出每个点的层数，并按层数从大到小排序。然后每次选择排序后数组的第\(i\)项，看该点是否被覆盖，如果没有就覆盖它的\(k\)级祖先。显然，我们要想让打通的穴位尽可能少，那么每个打通的穴位之间的重叠应尽可能小，即每个打通的穴位要独立覆盖尽可能大的面积。而每次选择\(k\)级祖先覆盖之所以最优，因为选择\(k\)级祖先一定可以覆盖完以\(k\)级祖先为根的整棵子树（最深的节点都能覆盖了，其他深度更浅的一定能被覆盖），且向子树以外的地方延伸最远，所以覆盖最广。
至于如何求出一个点是否被覆盖，我们使用一个\(dis\)数组表示每个点距离它最近的打通点的距离。如果一个点的父节点的\(dis>=k\)，则这个点一定没有被覆盖。每次确定打通的点时更新\(dis\)即可。
代码
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,k,t,x,y,now,son,ans=0;
vector<int> tmap[MAXN];
int fa[MAXN],dis[MAXN];
struct node
{
int dep,num;
}no[MAXN];
bool cmp(node a,node b)
{
return a.dep>b.dep;
}
void dfs(int st,int fat,int depp)
{
no[st].dep=depp;
fa[st]=fat;
for(int i=0;i<tmap[st].size();i++)
{
if(tmap[st][i]==fat)continue;
dfs(tmap[st][i],st,depp+1);
}
}
int main()
{
scanf("%d%d%d",&n,&k,&t);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
tmap[x].push_back(y);
tmap[y].push_back(x);
}
for(int i=1;i<=n;i++)
no[i].num=i;
dfs(1,1,0);
memset(dis,0x3f,sizeof(dis));
sort(no+1,no+n+1,cmp);
for(int i=1;i<=n;i++)
{
now=son=no[i].num;
for(int j=1;j<=k;j++)
{
now=fa[now];
dis[son]=min(dis[son],dis[now]+j);
}
if(dis[son]>k)
{
dis[now]=0;
ans++;
for(int j=1;j<=k;j++)
{
now=fa[now];
dis[now]=min(dis[now],j);
}
}
}
printf("%d",ans);
return 0;
}