牛客周赛 Round 61 （C++实现）

比赛链接：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

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小块来做。

1. 判断是否可以到达。
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 longint 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;
}