活動(dòng)地址：?？痛赫兴㈩}訓(xùn)練營(yíng) - 編程打卡活動(dòng)

Easy 小美的排列詢問(wèn)

簡(jiǎn)要題意

詢問(wèn)一個(gè)排列中兩個(gè)數(shù)是否相鄰。

Solution

記錄每個(gè)數(shù)的位置，判斷絕對(duì)差是否為 即可。

Code

void R()
{
	int n,x,y;
	cin>>n;
	vector<int> p(n+1);
	for (int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		p[x]=i;
	}

	cin>>x>>y;
	cout<<(abs(p[x]-p[y])==1?"Yes":"No");
	return;
}

Medium 小紅的字符串構(gòu)造

簡(jiǎn)要題意

給一個(gè)字符串 ，構(gòu)造一個(gè)字符串 ，使得 中每個(gè)字母的出現(xiàn)次數(shù)與 相同，且沒(méi)有一個(gè)位置 使得 ，或報(bào)告無(wú)解。

Solution

記錄每個(gè)字母出現(xiàn)位置，先按對(duì)應(yīng)字母出現(xiàn)次數(shù)對(duì)位置排序，記排序得到的位置數(shù)組為 。

將 中第一個(gè)字母對(duì)應(yīng)的位置段挪到最后，記為 。

令 ，若有交則無(wú)解，否則得到構(gòu)造。

Code

void R()
{
	string s,t;
	cin>>s;

	t=s;
	int n=s.size();
	vector<int> A,B;

	vector<vector<int>> pos(26);
	for (int i=0;i<n;i++)
		pos[s[i]-'a'].push_back(i);
	sort(pos.begin(),pos.end(),[&](auto &x,auto &y)
	{
		return x.size()>y.size();
	});
	pos.push_back(pos[0]);
	for (int i=0;i<26;i++)
		for (int p:pos[i])
			A.push_back(p);
	for (int i=1;i<=26;i++)
		for (int p:pos[i])
			B.push_back(p);
	for (int i=0;i<n;i++)
		t[B[i]]=s[A[i]];
	for (int i=0;i<n;i++)
		if (s[i]==t[i])
		{
			cout<<-1;
			return;
		}
	cout<<t;
	return;
}

Hard [ZJOI2010]COUNT 數(shù)字計(jì)數(shù)

簡(jiǎn)要題意

對(duì)區(qū)間 內(nèi)自然數(shù)的各個(gè)數(shù)位，求 分別出現(xiàn)了多少次。

Solution

只要能求 的答案 ， 即為原題的答案，下面考慮如何求 。

記 在十進(jìn)制下有 位。

記 表示考慮到十進(jìn)制下第 位（從高位到低位考慮，個(gè)位為第零位）為 ，當(dāng)前以確定的數(shù)位是否與 的前 位一致的前提下，前 位有多少種方案，有轉(zhuǎn)移：

其中 是 的第 位。

則數(shù)位 的出現(xiàn)次數(shù)為 。

Code

void R()
{
	auto solve=[&](i64 x)->vector<i64>
	{
		vector<i64> cnt(10),dig,pw;
		if (!x) return cnt;
		int L=0;
		i64 tmp=1;
		while (x>=tmp)
		{
			pw.push_back(tmp);
			dig.push_back(x/tmp%10);
			tmp*=10;
			L++;
		}
		pw.push_back(tmp);

		vector<vector<array<i64,2>>> dp(L,vector<array<i64,2>>(10));
		dp[L-1][dig[L-1]][1]=1;
		for (int i=1;i<dig[L-1];i++)
			dp[L-1][i][0]=1;
		for (int i=L-1;i;i--)
		{
			for (int j=1;j<10;j++)
				dp[i-1][j][0]++;
			for (int j=0;j<10;j++)
			{
				for (int k=0;k<10;k++)
				{
					dp[i-1][k][0]+=dp[i][j][0];
					if (k<dig[i-1])
						dp[i-1][k][0]+=dp[i][j][1];
				}
				dp[i-1][dig[i-1]][1]+=dp[i][j][1];
			}
		}

		for (int i=0;i<L;i++)
			for (int j=0;j<10;j++)
				cnt[j]+=dp[i][j][0]*pw[i]+dp[i][j][1]*(x%pw[i]+1);
		return cnt;
	};


	i64 a,b;
	cin>>a>>b;
	auto A=solve(a-1),B=solve(b);
	for (int i=0;i<10;i++)
		cout<<B[i]-A[i]<<" \n"[i==9];
	return;
}