牛客周賽 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;
}