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的模式务必要记牢