hihocoder编程练习赛53
A
描述
H国的国王有很多王子，这些王子各自也都有很多王孙，王孙又各自有很多后代…… 总之，H国王族的族谱形成了一棵以国王为根的树形结构。
根据H国的法律，王族的继承顺位这样规定的：
假设A和B是两位王族
- 如果其中一位是另一位的直系父亲、祖先，则辈份高的王族继承顺位更高
- 否则，假设C是A和B的最近公共祖先。显然A和B一定是C的两位不同子嗣的后代。其中C较年长的子嗣的后代的继承顺位更高
按时间顺序给出所有国王后代的出生和死亡记录，请你计算所有还活着的后代的继承顺位。
输入
第一行包含一个整数N和一个只包含大写字母和数字的字符串，分别代表记录的条数和国王的名字。
以下N行每行包含一条记录：
birth name1 name2 代表name1的儿子name2出生
death name 代表name死亡
1 <= N <= 10000
名字长度不超过20，并且没有重名的王族。
输出
按继承顺位从高到低输出每位王族的名字。(不包括国王)
每个名字一行。
样例输入
4 KING
birth KING ALI
birth KING BOB
birth ALI CARRO
death ALI
样例输出
CARRO
BOB
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| using namespace std; int n; string op,op1,op2,op3; map<string,int>mp1; map<int,string>mp2; int vis[maxn]; vector<int>e[maxn]; void dfs(int x){ for(int i=0;i<e[x].size();i++){ int next=e[x][i]; if(!vis[next]) cout<<mp2[next]<<endl; dfs(next); } } int main(){ // freopen("input.txt","r",stdin); cin>>n>>op; int id=0; mp1[op]=++id; mp2[id]=op; memset(vis,0,sizeof vis); for(int i=0;i<=n;i++) e[i].clear(); for(int i=1;i<=n;i++){ cin>>op1; if(op1[0]=='b'){ cin>>op2>>op3; if(!mp1.count(op2)){ mp1[op2]=++id; mp2[id]=op2; } if(!mp1.count(op3)){ mp1[op3]=++id; mp2[id]=op3; } e[mp1[op2]].push_back(mp1[op3]); } else{ cin>>op2; vis[mp1[op2]]=1; } } dfs(1); return 0; }
|
思路
观察后发现深搜就是优先级
B
描述
我们定义第一代hiho字符串是”h”。
第N代hiho字符串是由第N-1代hiho字符串变化得到，规则是在每一个h后插入i，i后插入o，o后插入h。
例如第二、三、四代hiho字符串分别是： “hi”、”hiio”和”hiioiooh”。
给定K，请你计算第100代hiho字符串中的第K个字符是什么。
输入
第一行包含一个整数T，代表测试数据的组数。 (1 ≤ T ≤ 10)
以下T行每行包含一个整数K。
对于50%的数据，1 ≤ K ≤ 1000000
对于100%的数据， 1 ≤ K ≤ 1000000000000000
输出
对于每组数据，输出一行，包含一个字符代表答案。
样例输入
2
3
7
样例输出
i
o
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| using namespace std; int t; LL k; char op[3]={'h','i','o'}; int main(){ cin>>t; while(t--){ cin>>k; int num=0; while(k>1){ if(k&1) k=(k+1)/2; else k/=2,num++; } cout<<op[num%3]<<endl; } return 0; }
|
思路
观察后发现
第i+1个的第2×k+1项等于第i个的第k项
第i+1个的第2×k项等于第i个的第k项的下一个推导
所以我们从后往前模拟 如果是奇数 k=(k+1)/2 如果是偶数 k/=2 并且记录下num(推导次数)
最后推导次数mod3就是答案
C
描述
给定一个由N个元素组成的序列： A1, A2, … AN，请你找出其中最长的子序列B1, B2, … BM满足其中至多有一次上升，即只有一次Bi+1 - Bi > 0。
输入
第一行包含一个整数N。
第二行包含N个两辆不同的整数，A1, A2, … AN。
对于30%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 100000 , 1 <= Ai <= 100000
输出
最长的满足条件的序列的长度
样例输入
5
3 5 4 1 2
样例输出
4
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| using namespace std; int n,len; int a[maxn]; int l[maxn],r[maxn]; int ans[maxn]; int bin(int l,int r,int x){ int re=0; while(l<=r){ int mid=l+r>>1; if(ans[mid]<=x){ re=mid; r=mid-1; } else l=mid+1; } return re; } int main(){ // freopen("input.txt","r",stdin); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) l[i]=r[i]=1; memset(ans,0,sizeof ans); len=1,ans[1]=a[n]; for(int i=n-1;i>=1;i--){ if(a[i]>=ans[len]){ ans[++len]=a[i]; r[i]=len; } else{ int pos=lower_bound(ans+1,ans+1+len,a[i])-ans; ans[pos]=a[i]; r[i]=len; } } memset(ans,0,sizeof ans); len=1,ans[1]=a[1]; for(int i=2;i<=n;i++){ if(a[i]<=ans[len]){ ans[++len]=a[i]; l[i]=len; } else{ int pos=bin(1,len,a[i]); ans[pos]=a[i]; l[i]=len; } } // for(int i=1;i<=n;i++) cout<<a[i]<< " "; cout<<endl; // for(int i=1;i<=n;i++) cout<<l[i]<<" "; cout<<endl; // for(int i=1;i<=n;i++) cout<<r[i]<<" "; cout<<endl; int Max=0; for(int i=1;i<n;i++){ Max=max(Max,l[i]+r[i+1]); } Max=max(Max,l[n]); Max=max(Max,r[1]); cout<<Max<<endl; return 0; }
|
思路
l[i]:i左侧的(从右往左)的最长下降子序列
r[i]:i右侧的(从左往右)的最长上升子序列
注意不是终点 因为l和r均定义成了len
对于每个i 更新答案l[i]+r[i+1] 因为题目要去可以有一次上升 所以不必关注a[i]右边的末尾元素和a[i+1]左边的开头元素的关系
注意补上l[n]和r[1]即可
注意
与此题的区别
本题要求是可以有一次上升 即对于每个点i i点不一定取 所以l和r维护的是左侧和右侧所有的最值 而非以i为终点的最值
而链接中的题目 对于i点必取 所以l和r维护的是必取i点 左侧和右侧的最值
前者答案为max(l[i]+r[i+1],l[n],r[1]) 这次取的是i的值 + i+1的值 因为i点非必取
后者答案为2×min(l[i],r[i])-1 减1是因为终点必取 算了2次
