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<node> 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的模式务必要记牢
标签：Educational,rotate,int,s1,Codeforces,len,cin,Round,op From： https://www.cnblogs.com/rickly233/p/17068795.html