新生赛题解
签到
https://ac.nowcoder.com/acm/contest/71508/A
A题:
定义一个空数组a[]表示每个数出现过几次
每输入一个数据k，就让a[k] ++，表示k在场中已经出现了至少一次
如果a[k]==1说明 k 在场出现了第一次，这时直接输出即可，反之不输出
ac代码：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int main()
{
cin >> n;
while(n --)
{
int x;
cin >> x;
a[x] ++;
if(a[x] == 1) cout << x << " ";
}
return 0;
}
B题：
ac代码：
#include <iostream>
using namespace std;
int main(){
double a;
cin >> a ;
cout << (int)(a * 100) << '%' ;
}
C题：
打表题，其中一个公式是把 1 到 n*n 的数累加起来 sum ，幻和 sum/边 ，中间数 sum/n/n 记得开 long long
ac代码：
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long long n ;cin >> n;
long long a = ceil(n * n / 2.0);
cout << a * n << ' ' << a << endl;
}
D题：
i：行， j：列
按列排序，与行无关，说明在排完 j 这一列之前 j 不会改变，那么列循环就应该在最外侧，
然后按照冒泡(sort)排序排就行
ac代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int p[N][N];
int main (){
int n ; cin >> n ;
for(int i = 0 ; i < n ; i ++ ){
for(int j = 0 ; j < n ; j ++ ){
cin >> p[j][i];
}
}
for(int i = 0 ; i < n ; i ++ ){
sort(p[i], p[i] + n);
}
for(int i = 0 ; i < n ; i ++ ){
for(int j = 0 ; j < n ; j ++ ){
cout << p[j][i] << ' ' ;
}
cout << endl;
}
}
E题：
创建两个数组分别将数值输入，根据公式分别求出分子和分母，数值可能过大，需要开 long long ，分母可以利用pow()函数，根据求最大公约数进行约分，可以利用gcd()函数求出最大公约数，分子和分母同时除以最大公约数并按格式输出（分子/分母），分子分母可能相等，结果为1，需要进行特殊判断。
ac代码：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
long long d[1000], p[1000];
long long gcd(long long a,long long b) {
return b > 0 ? gcd(b, a % b) : a ;
}
int main() {
long long n , a ,b;cin >> n >> a >> b;
for(int i = 0 ; i < n ; i ++ ) cin >> d[i];
for(int i = 0 ; i < n ; i ++ ) cin >> p[i];
long long w = 0 ,s = 0 , sum1= 0 ,sum2 = 0;
for(int i = 0 ;i < n ; i ++) w += d[i] * p[i];
for(int i = 0 ;i < n ; i ++) {
sum1 += d[i];
sum2 += p[i];
}
s += pow(sum1, a) + pow(sum2, b);
long long t = __gcd(w, s);
if(w == s) {
cout << 1 << endl;
return 0;
}
cout << w / t << '/' << s / t << endl;
}
F题：
找连续字符串"Huade"，并在该字符串后面加上"yyds"，可以利用string的find查找函数与insert插入函数直接进行操作，也可以暴力操作，最后特判 0 即可。
ac代码：
#include <iostream>
using namespace std;
int main(){
string s;
cin >> s ;
string H = "Huade";
int t = 0;
int cnt = 0 ;
while(true){
t = s.find(H, t);
if(t == -1){
break;
}
cnt ++ ;
s.insert(t + H.size(), "yyds");
t++;
}
if(cnt == 0){
cout << 0 ;
return 0;
}
cout << cnt << endl << s << endl;
}
G题：
出现了排版错误，正确题目链接：https://ac.nowcoder.com/acm/contest/71505/G
密码：hdacm2023
(我就说我怎么检查了5遍测试点都没有问题。。。)
思路：
线性 dp ，状态表示为 f (i , j) ，i 表示当前原始字符串位置(可以压缩掉)，j 表示当前目标字符串的下标。
f (i , j) 的值表示为在原始字符串下标 0 ~ i 的字符串中，有目标字符串下标 0 ~ j 的字符串 的子序列个数。
ac代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010 , mod = 1000000007;
typedef long long LL;
LL dp[N][30];
string str , go;
int n , m;
int main()
{
cin >> n >> m;
cin >> str >> go;
for(int i = 0 ; i <= n ; i ++)
dp[i][0] = 1;
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= m ; j ++)
dp[i][j] = dp[i - 1][j];
int idx = go.find(str[i - 1]) + 1;
if(idx > 0){
dp[i][idx] += dp[i - 1][idx - 1] %= mod;
}
}
cout << dp[n][m] % mod;
}
H题：
循环匹配字符串，遇到？默认为满足。
ac代码：
#include <iostream>
using namespace std;
int main(){
string a , b ; cin >> a >> b;
int cnt = 0;
for(int i = 0 ; i < a.size() ; i ++ ){
int j = i;
int t = 0;
while(j < a.size()){
if(a[j] == b[t] || a[j] == '?'){
j ++ ;
t ++ ;
}else {
break;
}
if(t == b.size()) {
cnt ++ ;
break;
}
}
}
cout << cnt << endl;
}
I题：
标准BFS，每一步的步长改为 2 就行，注意边界问题。
ac代码：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1000;
int p[N][N];
int dx[]= {2,2,-2,-2}, dy[] = {2,-2,-2,2};
int n , m;
void dfs(int x , int y){
p[x][y] = 0;
queue<pair<int,int>> q;
q.push({x, y});
while(!q.empty()){
auto t = q.front();
q.pop();
for(int i = 0 ; i < 4 ; i ++ ){
int xi = t.first + dx[i] , yj = t.second + dy[i];
if(xi >= 0 && xi < n && yj >= 0 && yj < m && p[xi][yj] == -1){
q.push({xi, yj});
p[xi][yj] = p[t.first][t.second] + 1;
}
}
}
}
int main() {
int x, y;
cin >> n >> m >> x >> y;
x--;
y--;
memset(p, -1, sizeof(p));
dfs(x, y);
for(int i = 0 ; i < n ; i ++ ){
for(int j = 0 ; j < m ; j ++ ){
cout << p[i][j] << ' ' ;
}
cout << endl;
}
}
J题：
约瑟夫环，创建一个链表，让这个链表的尾部指向头部，打印出每次删掉的元素，循环直到链表中只剩一个元素为止。
注意开始编号与轮数的定义。
ac代码：
#include <iostream>
#include <vector>
using namespace std;
vector<int> V;
int main() {
int n , k;cin >> n >> k;
for(int i = 0 ; i < n ; i ++ ){
int a; cin >> a ;
V.push_back(a);
}
int t = 0 ;
while(V.size() > 1){
vector<int>::iterator it = V.begin();
t = (t + k + 1)% V.size();
cout << V[t] << ' ' ;
V.erase(it + t);
t -- ;
}
}
K题：
签到题，先输入大圆的半径为R，小圆的半径为r，被切前圆锥的高为H，切去的圆锥高度为h,利用题目公式分别求出半球和圆台的体积相加，利用printf的小数输出格式进行输出，保留两位小数。
注意精度问题。
ac代码：
#include <iostream>
using namespace std;
const double PI = 3.14;
int main() {
double R , r , H ,h;
cin >> R >> r >> H >> h ;
double s = 4.0 / 3.0 * PI * R * R * R / 2;
double f = (1.0 / 3.0 * PI * R * R * H) - (1.0 / 3.0 * PI * r * r * h);
double res = s + f;
printf("%.2f", res);
}
L题：
线段树，先创建一个足够大的线段树，维护该线段树，初始给出的单词视为加入元素，后续每次查询按照模板编写，每个线段中所推算的值为字典序最大的字符串，直接用max函数比较即可。
ac代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n , q;
struct tree{
int l , r;
string v;
}tr[4 * N];
void pushup(int u)
{
tr[u].v = max(tr[2 * u].v , tr[2 * u + 1].v);
}
void build(int u , int l , int r)
{
tr[u].l = l , tr[u].r = r;
if(l == r) return;
int mid = (l + r) >> 1;
build(2 * u , l , mid);
build(2 * u + 1 , mid + 1 , r);
}
void re(int u , int old , string neu)
{
if(tr[u].l == old && tr[u].r == old) tr[u].v = neu;
else{
int mid = (tr[u].l + tr[u].r) >> 1;
if(old <= mid) re(u * 2 , old , neu);
else re(u * 2 + 1 , old , neu);
pushup(u);
}
}
string query(int u , int l , int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点，已经被完全包含在[l, r]中了
int mid = (tr[u].l + tr[u].r) >> 1;
string v = "";
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> q;
build(1 , 1 , N);
for(int i = 1 ; i <= n ; i ++){
string str;
cin >> str;
re(1 , i , str);
}
//U:更改 Q:查询
while(q --)
{
char ch; cin >> ch;
if(ch == 'U'){
int idx; string x;
cin >> idx >> x;
re(1 , idx , x);
}
else{
int l , r;
cin >> l >> r;
string t = query(1 , l , r);
if(t.size() <= 0)
t += "null";
cout << t << endl;
}
}
}
投递菜鸟集团等公司6个岗位 >
查看29道真题和解析