AtCoder 235 A~D题

【题目链接】A - 旋转 (atcoder.jp)

【代码实现】

#include
#include
#include
#include

using namespace std;

//abc+bca+cab： 
//123 231 312 ：231在123基础上将1移到23后 312在231的基础上将2移到最后面 
//也就说：从第二个数开始，每一个数都是在前一个的基础上将第一个字符移到最右边
//因此我们可以先用字符串构造这3个数，在将它们转为数字即可！ 

int main()
{
	string s1, s2, s3;
	cin >> s1;
	char a = s1[0], b = s1[1];
	 
	 s2 = s1.substr(1,3) + a;
	 s3 = s2.substr(1,3) + b;
	 
//	 cout << s1 << ' ' << s2 << " " << s3 << endl;
	 int num1 = stoi(s1), num2 = stoi(s2), num3 = stoi(s3);
	 cout << num1 + num2 + num3 ;

	 
	return 0;
}

【题目链接】B - 攀登高桥 (atcoder.jp)

【代码实现】

#include
#include
#include
#include

using namespace std;

typedef long long LL; 
const int N = 1e5 + 10;
int a[N];

// 找到 第一个 >= 它右边第一个数的数 

int main()
{
	
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n ; i ++) scanf("%d", &a[i]);
	
	for(int i = 0; i < n; i ++)
	{
		if(a[i] >= a[i + 1])
		{
			printf("%d", a[i]);
			break;
		}
	}
	
	return 0;
}

【题目链接】C - 第 K 次时间查询 (atcoder.jp)

刚刚开始想到的就是二分，然后给搜到的数做个标记，跳过出现过的位置，balabala搞不出来，后面看了题解，可以用一个哈希表将这个数和该数出现的所有位置做一个映射！

【代码实现】

#include
#include
#include
#include

using namespace std;

//关联数组：将输入的数a 与 a出现的所有位置关联起来 ——映射关系（哈希表里边嵌套使用vector）  
//序列 1 1 2 3 2 1
//如 m[1]={1, 2, 6}
//   m[2] = {3,5}
//   m[3] = {4} 

int main()
{
	int n , q;
	scanf("%d%d", &n, &q);
	
	unordered_map> query;
	
	for(int i = 1; i <= n; i ++)
	{
		int a;
		scanf("%d", &a);
		query[a].push_back(i);
		
	}
	while(q --)
	{
		int a, k;
		scanf("%d%d", &a, &k);
		
		if(query.find(a) == query.end()) puts("-1");// 没有这个数
		else if(query[a].size() < k) puts("-1");//查询次数 超过 该数的出现次数
		else printf("%dn", query[a][k - 1]); // 注：vector里边存的数下标从0开始 
		
	}
	return 0;
}

【题目链接】D - 乘法和旋转 (atcoder.jp)

题目意思：

给定初始值为 x = 1， 两种操作方式

第一种是将 x 替换为 a * x,第二种是将 x 视为字符串，当前仅当满足 x 大于等于 10且x 不能被 10 整除， 将 x 的最右端字符放到最左端。

求解 由x = 1变到N 时的最小操作次数。

思路：

初始状态1，目标状态N

BFS最小步数模型，状态为操作1的相乘和操作2的换位（根据题意转为字符串后将换位拼接即可）

注：

a与N的范围都在2~10^6之间，对于操作1，当 当前状态 * a（相乘）可能会导致结果溢出，为此要直接开long long

【代码实现】

#include
#include
#include
#include
#include

using namespace std;

queue q;
const int N = 1e6 + 10;

typedef long long LL;

int d[N];
bool st[N];

LL a, n; // 为了防止 a 与 N 相乘结果溢出 直接开long long！  坑啊！  

int bfs()
{
	q.push(1);
	d[1] = 0;
	
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		
		if(t == n) return d[n];
		
		if(st[t]) continue;
		st[t] = true;
		
		//扩展队头元素
		if( t * a <= N)
		{
			q.push(t * a);
			d[t * a] = d[t] + 1;	
		}
		if(t > 10 && t % 10 != 0)
		{
			string str = to_string(t);
			int len = str.size();
			char a = str[len - 1];
			string newStr = a + str.substr(0, len - 1);	
			int nums = stoi(newStr);
			q.push(nums);
			d[nums] = d[t] + 1;
		} 
	}
	
	return -1;
	
}

int main()
{
	cin >> a >> n;
	
	cout << bfs();
	
	return 0;
}