牛客周赛 Round 38

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

A-小红的正整数自增_牛客周赛 Round 38 (nowcoder.com)

取出最后一位判断即可 

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA cout << "SHU_YUAN" << endl;
const int maxn = 1e6 + 10;
int n, m, k, d, T = 1, A, B;void solve()
{string s;cin >> s;char ch = s.back();int x = (ch ^ 48);x = 10 - x;cout << (x == 10 ? 0 : x);
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//cin >> T;while (T--) solve();return 0;
}

 

B-小红的抛弃后缀_牛客周赛 Round 38 (nowcoder.com) 

小红拿到了一个正整数，她准备切掉一个后缀并抛弃，使得剩余部分是9的倍数。小红想知道有多少种不同的操作方案？ 

因为删除的后缀是连续的，即有多少前缀满足是9的倍数，从前往后O(n)判断即可

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA cout << "SHU_YUAN" << endl;
const int maxn = 1e6 + 10;
int n, m, k, d, T = 1, A, B;void solve()
{string s;cin >> s;int sum = 0;int ans = 0;for(auto &x : s){sum = sum * 10 + (x ^ 48);if(sum % 9 == 0)ans += 1;sum %= 9;}cout << ans;
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//cin >> T;while (T--) solve();return 0;
}

C-小红的字符串构造_牛客周赛 Round 38 (nowcoder.com) 
小红希望你构造一个长度为nnn的、仅包含小写字母的字符串，其中恰好有kkk个长度大于1的回文子串。你能帮帮她吗 

 有2种方式:因为k <= n / 2

所以可以通过前k个由2个相同字符(a -> z轮流输出)，后 n - 2k个乱序即可

我的方式是先用前几个字符找到可达到的最大值，挨个靠近，最后的剩下的乱序，这样k可以不局限于k <= n / 2,k可以取n个字符能达到的最多回文数

// Problem: 小红的字符串构造
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/78292/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA cout << "SHU_YUAN" << endl;
const int maxn = 1e6 + 10;
int n, m, k, d, T = 1, A, B;
/*
aa   1
aaa  3 
aaaa 6 
aaaaa 10 
*/
string s = "qwertyuiopasdfghjklzxcvbnm";
void solve()
{cin >> n >> k;int pos = 0;int t = 0;while(k){k--; t+=2;cout << s[pos] << s[pos];int cnt = 2;while(k >= cnt){cout << s[pos];k -= cnt;cnt++;t++;}pos = (pos + 1) % 26;}//cout <<"T = " << t << endl;for(int i = 1; i <= n - t;i++){cout << (s[(pos + i) % 26]);}
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//cin >> T;while (T--) solve();return 0;
}

D-小红的平滑值插值_牛客周赛 Round 38 (nowcoder.com) 

显然该题最终只有3个情况

情况1:最大平滑值 == k，无需操作

情况2:最大平滑值 < k，可证明最多只需一次操作，随便列一组数据即可:如k取7

最大平滑值取 任意x < 7，即任意1 < =i < j <= n abs(a[j] - a[i])< 7

1 7 ==> 在1后面插入一个 8 即可

1 3 == > 依旧插入一个8即可

显而易见若最大平滑值abs(a[x] - a[y] ) < k == > 在a[x] a[y]中间插入a[x] + k即可

情况3:最大平滑值 > k

在每一个平滑值大于k的数中间插入一个大小为x，首项为a[X] + k,d = k的等差数列，其中x = a[y] /a[x]向下取整

特例若可以整除需要减1 ，原因最后一项大小 == a[y]因此无需插入 

 

// Problem: 小红的平滑值插值
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/78292/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA cout << "SHU_YUAN" << endl;
const int maxn = 1e6 + 10;
int n, m, k, d, T = 1, A, B;
int a[maxn];
int pos = 0;
int fun(int a, int b)
{return a % b == 0 ? a / b - 1 :a / b;
}void solve()
{cin >> n >> k;for(int i = 1;i <= n;i++)cin >> a[i];int mk = 0;int ans = 0;for(int i = 2;i <= n;i++){int t = abs(a[i] - a[i - 1]);if(t > k){ans += fun(t, k);}mk = max(mk, t);}if(mk == k)cout << 0;else if(mk > k)cout << ans;	else cout << 1;}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//cin >> T;while (T--) solve();return 0;
}

E-小苯的等比数列_牛客周赛 Round 38 (nowcoder.com) 

暴力枚举即可

// Problem: 小苯的等比数列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/78292/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
//#define for(a -> b) for(int i = a; i <= b;i++)
#define WA cout << "SHU_YUAN" << endl;
const int maxn = 1e6 + 10;
int n, m, k, d, T = 1, A, B;
vector<int>v;
int M[maxn];
int cnt[maxn];void solve()
{cin >> n;int ans = 0;for(int i = 1;i <= n;i++){cin >> m;M[m] += 1;ans = max(ans, M[m]);}for(int i = 1; i <= 2e5; i++){if(M[i])for(int j = 2; i * j <= 2e5; j++){int cnt = 1;if(M[i * j]){for(int k = i * j; k <= 2e5; k *= j){if(M[k])ans = max(ans, ++cnt);else break;}}}}cout << ans << endl;
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//cin >> T;while (T--) solve();return 0;
}

F-小苯的回文询问_牛客周赛 Round 38 (nowcoder.com) 

因为是不连续的，因此每一次对于M[a[i]]的更新即是最后一次出现a[i]的位置 

我们只需要找到最近可满足的坐标

当查找区间l r时，我们通过找到r位置最近可以形成回文的位置，若其大于等于l说明该区间有子区间满足不连续的回文串，其中如果dp[r] = 0说明没有回文串可形成

    // Problem: 小苯的回文询问
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/78292/F
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA cout << "SHU_YUAN" << endl;
const int maxn = 1e6 + 10;
int n, m, k, d, q, T = 1, A, B;
int a[maxn],dp[maxn];//第i位往前最近可构成回文的坐标
map<int,int>M;
void solve()
{cin >> n >> q;for(int i = 1;i <= n;i++)cin >> a[i];for(int i = 1;i <= n;i++){dp[i] = max(dp[i - 1], M[a[i]]);if(i - 1)M[a[i - 1]] = i - 1;}while(q--){int l, r;cin >> l >> r;cout << (dp[r] >= l ? "YES" : "NO") << endl;}
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//cin >> T;while (T--) solve();return 0;
}