最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Educational Codeforces Round 1

来源：博客园

A. Tricky Sum

题意:

给一个n,求1到n的运算,如果不是2的次方就加,否则减


(相关资料图)

思路:

由于n有1e9,直接暴力扫过去肯定要寄

所以先$n * (n + 1) / 2$来算出1到n的和

再减去2倍的2的次方之和

代码:

void solve(){cin >> n;int res = n * (n + 1) / 2;int op = 0;for(int i = 1;i <= n;i *= 2) op += i;cout << res - 2 * op << endl;}

总结:

水题不用总结(

B. Queries on a String

题意:

给一个字符串,再给n个操作

每次取l到r然后操作k次

每次将一个字符从尾部放到头部

思路:

我看这个操作非常地像rotate这个函数

而且每操作字符串长度次就相当于没有操作

所以先%个字符串长度

然后再用rotate函数模拟即可

rotate函数是头部到尾部,跟这题相反

但是我又发现一个性质

只要将这个字符串用rotate函数操作字符串长度 - k的长度就行了

但是写的过程呢.....

额,一言难尽

写了差不多半个小时才调好

具体实现看代码

这里代码有两种写法,我用的第一种

第一种:

void solve(){string s1;cin >> s1;s1 = " " + s1;cin >> n;int l,r,k;while(n--){cin >> l >> r >> k;int len = r - l + 1;k %= len;rotate(s1.begin() + l,s1.begin() + r - k + 1,s1.begin() + r + 1);// cout << l << " " << r - k << " " << r << endl;// cout << s1 << endl;}s1.erase(s1.begin());cout << s1 << endl;}

第二种:

void solve(){string s1;cin >> s1;s1 = " " + s1;cin >> n;int l,r,k;while(n--){cin >> l >> r >> k;int len = r - l + 1;k %= len;string s2 = s1.substr(l,len - k);s1.erase(l,len - k);s1.insert(l + k,s2);}s1.erase(s1.begin());cout << s1 << endl;}

总结:

字符串的函数感觉都有两种用法,第一种是两个迭代器,表示开始和结束的位置

还有一种用法输入两个数字,第一个输入开始的位置,第二个输入长度

迭代器的用法又要特别注意,尾迭代器要特别注意,如果用begin来表示的话,长度要+1才能刚好吻合尾迭代器

而rotate函数则更特殊,第一个是头迭代器,后面两个都是尾迭代器

在进行一些稍微复杂的操作时最好用个例子这样速度快一些

C. Nearest vectors

题意:

给很多个点,求哪两个点跟原点形成的向量夹角最小

思路:

这题难的原因就是没有一个东西去衡量角的大小关系

所以引入极角的概念

极角的求法:$atan2(y,x)$

再进行一波极角排序

排完序了就算极角的差和极角差的补角取个最小值即可

每次都更新一下下标

最后记得要比较一下最小和最大的极角差

代码:

struct node{int id;double op;}a[100010];bool cmp(node &x,node &y){return x.op < y.op;}void solve(){int l,r;cin >> n;for(int i = 1;i <= n;i++){cin >> l >> r;double uu = atan2(r,l);a[i] = {i,uu};}sort(a + 1,a + n + 1,cmp);double res = min(abs(a[n].op - a[1].op),2 * PI - (abs(a[n].op - a[1].op)));int x = a[1].id,y = a[n].id;for(int i = 1;i < n;i++){double uu = min(abs(a[i].op - a[i + 1].op),2 * PI - (a[i].op - a[i + 1].op));if(uu < res){res = uu;x = a[i].id;y = a[i + 1].id;}}cout << x << " " << y << endl;}

总结:

计算几何最好用long double

求两个向量夹角最小的话记得考虑补角

以及最小极角和最大极角

D. Igor In the Museum

题意:

给一个字符串地图

要输出所有.周围的*数量

思路:

每次bfs一下,找连通块周围的*的数量并且打上标记

然后用个二维数组来记录每次bfs的序号

等bfs完了以后用个一维数组记录*的数量

最后输出的时候看点的坐标在二维数组哪个序号里面

然后输出对应序号的数量即可

代码:

struct node{int x,y;}; int bfs(int x1,int y1){int sum = 0;queue q;q.push({x1,y1});st[x1][y1] = idx;while(!q.empty()){auto now = q.front();q.pop();for(int i = 0;i < 4;i++){int x = now.x + dx[i];int y = now.y + dy[i];if(mp[x][y] == "*") sum++;if((!st[x][y])&&x >= 1&&x <= n&&y >= 1&&y <= m&&mp[x][y] == "."){q.push({x,y});st[x][y] = idx;}}}return sum;} void solve(){int k;cin >> n >> m >> k;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin >> mp[i][j];}}for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){if(mp[i][j] == "."){if(!st[i][j]){op[idx] = bfs(i,j);idx++;}}}}// for(int i = 1;i <= n;i++)// {// for(int j = 1;j <= m;j++)// {// cout << st[i][j] << " ";// }// cout << endl;// }int x,y;while(k--){cin >> x >> y;cout << op[st[x][y]] << endl;}}

总结:

主要是代码实现

bfs的模式务必要记牢

关键词： 字符串长度 一维数组 还有一种