牛客竞赛_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;
}