A.
题意:给一个仅由‘V’ ,‘K’构成的串,允许修改一个字母,问最多出现几个VK.
思路:先把相邻的"VK"添加入答案,并立下flag,表示不能被修改,然后尝试着修改"VV","KK"。
hack: KV(这个栗子答案为0)
#include <iostream> #include <cstring> using namespace std; char s[1002]; int vis[1002]; int main() { scanf("%s", s+1); int n = strlen(s+1), ans = 0; for(int i=1;i<n;i++) { if(s[i] == 'V' && s[i+1] == 'K') { ans ++; vis[i] = 1, vis[i+1] = 1; } } for(int i=1;i<n;i++) { if(vis[i] == 0 && vis[i+1] == 0) { if((s[i]=='V'&&s[i+1]=='V') || (s[i]=='K'&&s[i+1]=='K')) { ans ++; break; } } } cout << ans << endl; }
B.
一道休闲的构造题~
#include <iostream> #include <vector> #include <cstring> using namespace std; char s1[1002], s2[1002]; vector<char> v; int main() { scanf("%s", s1+1); scanf("%s", s2+1); int n = strlen(s1+1); for(int i=1;i<=n;i++) { if(s1[i] == s2[i]) { v.push_back('z'); } else if(s1[i] > s2[i]) { v.push_back(s2[i]); } else { printf("-1 "); return 0; } } for(int i=0;i<v.size();i++) { printf("%c", v[i]); } }
C.
题意:
一堆神秘设备在耗电,每分钟每个设备消耗a[i]单位的电,初始电量为a[i],现在你有一个充电器,
每分钟可以给一个设备充p个单位的电。如果有一个设备没电了,就gg了,问最长可以苟多久。
思路:二分答案~
判断能不能苟住t分钟的姿势:
如果一个设备t分钟后电量为正,那恭喜!如果为负,说明需要充电器的拯救,需要充电的时间为:
(t*b[i] - a[i]) / p。对这些设备需要的时间求和,然后和t比较大小即可。
#include <iostream> #include <vector> #include <cstring> using namespace std; const int NICO = 100000 + 10; int n, p, a[NICO], b[NICO]; bool ok(double t) { double need = 0; double ans = 0; for(int i=1;i<=n;i++) { need = (double)a[i] * t - (double)b[i]; if(need > 0) { ans += need / (double)p; } } return (ans + 1e-10) < t; } int main() { scanf("%d %d", &n, &p); for(int i=1;i<=n;i++) { scanf("%d %d", &a[i], &b[i]); } double l = 0, r = 1e14; for(int i=1;i<=300;i++) { double mid = (l+r)/2; if(ok(mid)) l = mid; else r = mid; } if(ok(1e14)) { printf("-1 "); return 0; } printf("%.8f ", l); }
D.
题意:给一个凸多边形,现在每个点都可以在半径为D的范围内乱动,如果要保证,无论怎么
动,凸多边形都不会凹掉,求D的最大值。
题解:动三个点就可以啦!求出一个点,到它的邻居之间的连线的距离。然后有缘千里来相会~
所以距离为 min{dis} / 2
#include <iostream> #include <vector> #include <cmath> #include <cstring> using namespace std; const int NICO = 1002; struct point { double x,y; }; struct line { point a,b; }; double xmult(point p1,point p2,point p0) { return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } double distance(point p1,point p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } double disptoline(point p,line l) { return fabs(xmult(p,l.a,l.b))/distance(l.a,l.b); } point p[NICO]; int n; int main() { scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%lf %lf", &p[i].x, &p[i].y); } double ans = 1e18; for(int i=1;i<=n;i++) { point now = p[i], pre1, pre2, nxt1, nxt2; if(i>1) pre1 = p[i-1]; else pre1 = p[i-1+n]; if(i>2) pre2 = p[i-2]; else pre2 = p[i-2+n]; if(i+1<=n) nxt1 = p[i+1]; else nxt1 = p[i+1-n]; if(i+2<=n) nxt2 = p[i+2]; else nxt2 = p[i+2-n]; line l1, l2, l3; l1.a = pre1, l1.b = nxt1; l2.a = pre1, l2.b = pre2; l3.a = nxt1, l3.b = nxt2; ans = min(ans, disptoline(now, l1)); ans = min(ans, disptoline(now, l2)); ans = min(ans, disptoline(now, l3)); } printf("%.10f ", ans/2); }
E.
题意:
构造一个满足如下条件的串:
1.所有数字小于m
2.前缀积%m的值互不相同。
3.前缀积%m的值不等于{a[1], a[2], ...., a[n]}中的任意一个。
4.尽可能长
思路:
每个数字看成一个节点。
若 kx % m = y 那么x,y之间可连一条边。然后这个问题就转换成了求在有向图中,每个点只能经过一次
最远能走多远。 又发现,如果kx % m = y那么 gcd(m, x) | gcd(m, y)
然后就不知道怎么搞了。比赛完后题解里大致有个强连通分量分解什么的。。抽个时间把这道题的题解,还有
强连通分量blabla补一补。也许....大概....明天吧~。
用小号走了一发。。。心旷神怡!
然后,这个号的主人是上面那货。。。
嗯,采访一下,排骨龙先生,请问对这次比赛自己的表现有什么看法?
排骨龙:比赛之前睡了个好觉,嗑了很多瓜子,所以心情比较愉悦。比赛一上来,A题直接
弹出一个WA,吓得我钻到了木屑里,不过幸运的是,之后调整了状态,打出一波流。比赛
下半场啥也没搞出来。感觉E题自己的姿势还远不够,图论思想方面还是太智障了。下一段
时间得学习一个强连通分量~
听外界消息说,下一场CF,你要上紫名,这是真的吗?
排骨龙:当然啦!不过啊,其实Rating啥的也不必太在意啦!切题的感觉就像跑轮子一样,
细细品味过程,自己才会有在星汉灿烂中奔跑的愉悦感,所以下一场,希望自己能更洒脱
更放肆地coding,多challange一下E,F,哪怕是打出GG也得是荡气回肠!