P7193 [COCI 2007/2008 #6] PRINCEZA题目背景对于 C 语言和 C 语言请使用cinscanf进行读入否则可能会出现R E \color{purple}\mathsf{RE}REW A \color{red}\mathsf{WA}WA。题目描述Luka 把卡车停在湖边。Barica 在湖中居住Barica 跳过漂浮在湖面上的n nn种植物。Luka 知道许多民间故事知道如果他亲吻 Barica她会变成一个可爱的女孩子。但是他需要先抓住她可以用一对坐标定义植物在湖面上的位置。 Barica 可以从( x , y ) (x, y)(x,y)植物中跳跃p pp为任意正整数。方向 A( x p , y p ) (x p, y p)(xp,yp)。方向 B( x p , y − p ) (x p, y - p)(xp,y−p)。方向 C( x − p , y p ) (x - p, y p)(x−p,yp)。方向 D( x − p , y − p ) (x - p, y - p)(x−p,y−p)。Barica 选择四个方向之一然后沿所选方向跳到第一个植物上。如果在选定的方向上没有植物Barica 将留在原处。Barica 跳下后她从水槽上跳下的植物消失了。知道植物的位置和 Barica 选择的方向顺序后Luka 希望确定 Barica 最终将位于植物的坐标。 Luka 将在她的位置等她亲吻她。编写一个解决 Luka 问题的程序并帮助他将 Barica 变成美丽的公主。输入格式第一行两个正整数n , k n, kn,k分别表示植物数和跳跃次数。第二行k kk个字母ABC或D表示她跳的方向。接下来n nn行的每行都包含两个整数x , y x, yx,y表示一棵植物的坐标。 Barica 最初位于第一颗植物。输出格式第一行Barica 的最终坐标。输入输出样例 #1输入 #17 5 ACDBB 5 6 8 9 4 13 1 10 7 4 10 9 3 7输出 #17 4输入输出样例 #2输入 #26 12 AAAAAABCCCDD 1 1 2 2 3 3 4 4 5 3 6 2输出 #25 3说明/提示数据规模与约定对于100 % 100\%100%的数据1 ≤ n , k ≤ 10 5 1 \le n, k \le 10 ^ 51≤n,k≤1050 ≤ x , y ≤ 10 9 0 \le x, y \le 10 ^ 90≤x,y≤109。说明本题满分60 6060分。本题默认开启 O2 优化开关。题目译自 COCI2007-2008 CONTEST #6 T5 PRINCEZA译者 tearing。C实现#includebits/stdc.husingnamespacestd;intn,k,p1;charch[100005];intid[100005];structNode{intsum1,sum2,x,y;intl[4];}a[100005];boolCmp1(intx,inty){if(a[x].sum1!a[y].sum1)returna[x].sum1a[y].sum1;returna[x].xa[y].x;}boolCmp2(intx,inty){if(a[x].sum2!a[y].sum2)returna[x].sum2a[y].sum2;returna[x].xa[y].x;}signedmain(){cinnk;for(inti1;ik;i)cinch[i];for(inti1;in;i){cina[i].xa[i].y;id[i]i;a[i].sum1a[i].xa[i].y;a[i].sum2a[i].x-a[i].y;}sort(id1,idn1,Cmp1);for(inti2;in;i)if(a[id[i]].sum1a[id[i-1]].sum1){a[id[i-1]].l[1]id[i];a[id[i]].l[2]id[i-1];}sort(id1,idn1,Cmp2);for(inti2;in;i)if(a[id[i]].sum2a[id[i-1]].sum2){a[id[i-1]].l[0]id[i];a[id[i]].l[3]id[i-1];}for(inti1;ik;i){intnxta[p].l[ch[i]-A];if(!nxt)continue;for(intj0;j4;j)if(a[p].l[j])a[a[p].l[j]].l[3-j]a[p].l[3-j];pnxt;}couta[p].x a[p].y;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容