牛客周赛 Round 61 （C++实现）
比赛链接：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
文章目录
- 1.致十年后的我们
- 1.1 题目描述
- 1.2 思路
- 1.3 代码
- 2.简单图形问题
- 2.1 题目描述
- 2.2 思路
- 2.3 代码
- 3. 小红的机器人构造
- 3.1 题目描述
- 3.2 思路
- 3.2.1 问题1
- 3.2.2 问题2
- 3.2.3 问题3
- 3.3 代码
1.致十年后的我们
1.1 题目描述
这个月，牛客科技创立十周年啦！
2014~2024，回望这十年时光，每个人一定都有无数想要感慨，想要抱怨，想要倾诉，想要怀念的事情。
十年前的你有对自己说过什么吗？
你想对十年后的自己说点什么吗？
1.2 思路
因为题目的数据量极少，不需要考虑进位的问题，直接加就可以了。
1.3 代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
string s;
cin >> s;
s[2] = (s[2] + 1);
cout << s;
return 0;
}
2.简单图形问题
2.1 题目描述
对于给定的未知多边形的面积，请你判断这是一个以整数为边长的正方形、或是以整数为边长的等边三角形、或是两者均是、或是两者均不是。
2.2 思路
首先我们肯定要知道正方形和等边三角形的面积计算公式吧，正方形就不说了，等边三角形面积为：（根号3*边长的平方）/4通过公式也就说明了，在边长为整数的情况下，三角形的面积是不可能为整数的。，这样的话，只需要判断是不是正方形就可以了。
2.3 代码
#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
int main() {
int t;
cin>>t;
while (t--) {//面积为整数，边也为整数
int x;
cin >> x;
if ((int)sqrt(x) * (int)sqrt(x) == x) {
//正方形
cout << 0 << endl;
}
else {
cout << 3 << endl;
}
}
return 0;
}
3. 小红的机器人构造
3.1 题目描述
3.2 思路
可以把这个问题分成3小块来做。
- 判断是否可以到达。
- 输出一种可以到达的情况。
- 输出可以删除的不同方案数。
3.2.1 问题1
为了解决这个问题，我们肯定就必须朝着目标方向走能达到的最大步数，不能回头。那么我们可以用4个变量来记录四个方向的的各个步数，然后再判断。
ll cu = 0, cd = 0, cl = 0, cr = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'U') {
cu++;
}
else if (s[i] == 'D') {
cd++;
}
else if (s[i] == 'L') {
cl++;
}
else if (s[i] == 'R') {
cr++;
}
ll op = max(cu, cd);
ll po = max(cl, cr);
if (op >= abs(x) && po >= abs(y)) {
cout << "YES ";
}
else {
cout << "NO";
}
}
其实这里我是有些疑问的，如果我走与目标方向完全相反的路，只要数量大按这个判断也是会输出YES的，但是如果精准到方向题目会判错。就很困惑。
3.2.2 问题2
问题2的解决方法就是贪心，我们已经知道目标位置。能走则走，别回头。
ll c[6] = {0};
c[1] = abs(x);c[2] = abs(x);c[3] = abs(y); c[4] = abs(y);
for(int i = 0;i<n;++i){
if(c[1]&&x>0&&s[i] == 'U'){
cout<<'U';
c[1]--;
}
else if(c[2]&&x<0&&s[i] =='D'){
cout<<'D';
c[2]--;
}
else if(c[3]&&y>0&&s[i] == 'R'){
cout<<'R';
c[3]--;
}
else if(c[4]&&y<0&&s[i] == 'L'){
cout<<'L';
c[4]--;
}
}
3.2.3 问题3
也是本题的重点，需要了解组合数，且能够转化为代码。
以下为组合数的模板代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
const ll N=1e5+5;
const ll p=1e9+7;
ll a[N];
ll jc[N+5],inv[N+5],pw[N+5];
ll ksm(ll a,ll b)
{
ll ans=1;
a%=p;
while(b)
{
if(b&1)
{
ans=ans*a%p;//错过一次
}
a=a*a%p;
b>>=1;
}
return ans;
}
void init()
{
jc[0]=inv[0]=pw[0]=1;
for(int i=1;i<=N;i++)
{
jc[i]=jc[i-1]*i%p;
}
inv[N]=ksm(jc[N],p-2);
for(int i=N-1;i>=1;i--)
{
inv[i]=inv[i+1]*(i+1)%p;
}
}
ll C(ll n,ll m)//cnm
{
if(n<m||n<0||m<0)
{
return 0;
}
return jc[n]*inv[m]%p*inv[n-m]%p;//inv[m]是m!取模p的逆元
}
然后我们需要组合数计数。在一个方向，如果该方向上的步数可以到达目标且有多的话，以x的正方向为例子就是：C(cu,x)，如果存在负方向的操作，就可以再加上C(cu,x+1)*C(cd,1)。以此类推就可以得到所有的组合数了。
3.3 代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define ll long long
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
const ll N = 1e5 + 5;
const ll p = 1e9 + 7;
ll a[N];
ll jc[N + 5], inv[N + 5], pw[N + 5];
ll ksm(ll a, ll b)
{
ll ans = 1;
a %= p;
while (b)
{
if (b & 1)
{
ans = ans * a % p;//错过一次
}
a = a * a % p;
b >>= 1;
}
return ans;
}
void init()
{
jc[0] = inv[0] = pw[0] = 1;
for (int i = 1; i <= N; i++)
{
jc[i] = jc[i - 1] * i % p;
}
inv[N] = ksm(jc[N], p - 2);
for (int i = N - 1; i >= 1; i--)
{
inv[i] = inv[i + 1] * (i + 1) % p;
}
}
ll C(ll n, ll m)//cnm
{
if (n < m || n < 0 || m < 0)
{
return 0;
}
return jc[n] * inv[m] % p * inv[n - m] % p;//inv[m]是m!取模p的逆元
}
int main()
{
int t;
cin >> t;
while (t--) {
int n, x, y;
cin >> n >> x >> y;
string s;
cin >> s;
ll cu = 0, cd = 0, cl = 0, cr = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'U') {
cu++;
}
else if (s[i] == 'D') {
cd++;
}
else if (s[i] == 'L') {
cl++;
}
else if (s[i] == 'R') {
cr++;
}
}
ll op = max(cu, cd);
ll po = max(cl, cr);
if (op >= abs(x) && po >= abs(y)) {
cout << "YES ";
ll c[6] = { 0 };
c[1] = abs(x); c[2] = abs(x); c[3] = abs(y); c[4] = abs(y);
ll f = 0;
for (int i = 0; i < n; ++i) {
if (c[1] && x > 0 && s[i] == 'U') {
cout << 'U';
c[1]--;
}
else if (c[2] && x < 0 && s[i] == 'D') {
cout << 'D';
c[2]--;
}
else if (c[3] && y > 0 && s[i] == 'R') {
cout << 'R';
c[3]--;
}
else if (c[4] && y < 0 && s[i] == 'L') {
cout << 'L';
c[4]--;
}
}
init();
ll res = 0, ret = 0;
if (x >= 0) {
for (int i = x; i <= cu; ++i) {
if (i - x > cd) break;
res += (C(cu, i) * C(cd, i-x));
res %= p;
}
}
else {
x = -x;//为了方便计算
for (int i = x; i <= cd; ++i) {
if (i - x > cu) break;
res += (C(cu, i-x) * C(cd, i));
res %= p;
}
}
if (y >= 0) {
for (int i = y; i <= cr; ++i) {
if (i - y > cl) break;
ret += (C(cr, i) * C(cl, i-y));
ret %= p;
}
}
else {
y = -y;
for (int i = y; i <= cl; ++i) {
if (i - y > cr) break;
ret += (C(cr, i - y) * C(cl, i));
ret %= p;
}
}
ll num = res % p * ret % p;
cout <<' '<< num;
}
else {
cout << "NO";
}
cout << endl;
}
return 0;
}