牛客周赛 Round 92-题解

牛客周赛 Round 92-题解

A-小红的签到题

code

#include<iostream>
#include<string>
using namespace std;
string s;
int main()
{int n;cin >> n;cout << "a_";for (int i = 0; i < n - 2; i ++)cout << 'b';return 0;
}

B-小红的模拟题

算法思路

dfs模板题

code

const int N = 1e3 + 10;
char g[N][N];
bool st[N][N];
char op[] = "DS";
bool flag;
string ans;
int n, m;
void dfs(int x, int y, string path)
{if (flag)return;if (x == n - 1 && y == m - 1){ans = path;flag = 1;return;}if (x >= n || y >= m)return;for (int i = 0; i < 2; i++){int a, b;char ch;if (i == 0){a = x;b = y + 1;ch = 'D';}else{a = x + 1;b = y;ch = 'S';}if (st[a][b])continue;if (g[a][b] == '#')continue;st[a][b] = 1;dfs(a, b, path + ch);st[a][b] = 0;}
}
void solve()
{cin >> n >> m;for (int i = 0; i < n; i++)cin >> g[i];dfs(0, 0, "");cout << ans;
}

C-小红的方神题

题目描述

小红希望构造一个长度为 $n$ 的排列，使得对该排列连续进行 $n-1$ 次“退化”操作后，最终只剩下一个数，且该数恰好等于 $n-2$。

• 退化操作：对于数组 $a$，其退化状态定义为取每对相邻元素之差的绝对值构成的新数组。
  例如，若 $a=[a_1,a_2,\dots ,a_k]$，则退化后得到数组

  $$b=[|a_1-a_2|,|a_2-a_3|,\dots ,|a_{k-1}-a_k|],\text{长度为 }k-1.$$

• 排列定义：长度为 $n$ 的排列是由 { 1 , 2 , … , n } \{1,2,\dots,n\} {1,2,…,n} 按任意顺序组成的数组，每个数恰好出现一次。

如果存在满足条件的排列，输出任意一个；否则输出 $-1$。

---

输入格式

n

• 一行，一个整数 $n$（$1\le n\le 10^3$），表示排列的长度。

---

输出格式

• 如果不存在这样的排列，输出一行：

  -1
  

• 否则输出一行 $n$ 个用空格分隔的整数，表示所构造的排列。

---

算法思路

好家伙，又拿next_permutation 去暴力了，喜提超时

那么回过头思考一下，看看样例为什么是1 3 2呢

那么我假设一下 $1,n,n-1,n-2,n-\mathrm{3...}$ 那么做减法

第一次： $n-1,1,1,...$

第二次： $n-2,0,0,0,...$

好家伙这不就直接出来了吗，

code

#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin >> n;if (n < 3) {cout << -1 << "\n";return 0;}cout << 1;for (int x = n; x >= 2; --x) {cout << " " << x;}cout << "\n";return 0;
}

D-小红的数学题

题目描述

小红拿到了一个正整数 $k$，她希望你找到两个正整数 $p,q$ 满足

$$p+q=k$$

且二次方程

$$x^2-px+q=0$$

存在两个正整数根。如果不存在这样的 $p,q$，请输出 $-1$。

---

输入描述

一个正整数

$$k(1\le k\le 10^{12})$$

---

输出描述

• 如果不存在满足条件的正整数 $p,q$，输出一行：

  -1
  

• 否则，输出一行两个正整数 $p$ 和 $q$，以空格分隔，代表你找到的任意一组解：

  p q
  

---

算法思路

首先要想到韦达定理

那么只需要枚举 k+1的两个大于1的整数因数就可以了

code

void solve()
{i64 k, p, q;cin >> k;k = k + 1;for (i64 i = 1; i * i <= k + 1; i++){if (k % i == 0){i64 a, b;a = i;b = k / i;if (a >= 2 && b >= 2){i64 p = a - 1 + b - 1, q = (a - 1) * (b - 1);cout << p << " " << q;return;}}}cout << -1;
}k / i;if (a >= 2 && b >= 2){i64 p = a - 1 + b - 1, q = (a - 1) * (b - 1);cout << p << " " << q;return;}}}cout << -1;
}