|
题目链接
?
智乃酱有N{N}N块积木，每一块积木都有自己的颜色以及数字，这N{N}N块积木颜色的范围从1{1}1到M{M}M，数字的范围从0{0}0到9{9}9。
现在智乃酱把这些积木从左到右排成一排，这样积木看上去就形成了一个大整数，智乃觉得这个数字不够大，所以他决定交换一些积木使得这个大整数尽可能的大。
具体来讲，智乃可以在任意时刻无限次的交换相邻且同色的数字积木。
但是即使这样，智乃觉得这个数字还是不够大。
所以智乃酱拿出了她的油漆桶，她决定进行K{K}K次操作，每次操作都选中两种颜色P{P}P,Q{Q}Q，然后将所有颜色为P{P}P的积木染成颜色Q{Q}Q。
当然，在染色结束后智乃酱也是可以交换相邻同色积木进行调整。
现在智乃想要知道，她进行K{K}K次染色操作之前，以及每次染色后能够通过交换得到最大的正整数是多少，当然啦，这个大整数被允许包含前导零。
因为这个大整数很大，所以只要求你输出答案对109+7{10^9+7}109+7取余数的结果即可。
输入描述:
第一行输入三个整数N,M,K(1≤N,M≤105,0≤K≤10){N,M,K(1\leq N,M\leq 10^5,0\leq K\leq 10)}N,M,K(1≤N,M≤105,0≤K≤10)分别表示积木的数目，初始颜色的种类，以及智乃酱染色的次数。
接下来输入一个长度为N{N}N的字符串，字符串仅由数字0?9{0-9}0?9组成。
接下来一行N{N}N个正整数coli(1≤coli≤M){col_i(1\leq col_i \leq M)}coli?(1≤coli?≤M)表示积木的颜色。
接下来K{K}K行，每行输入两个正整数P,Q(1≤P,Q≤M){P,Q(1\leq P,Q \leq M)}P,Q(1≤P,Q≤M)表示选中两种颜色P{P}P,Q{Q}Q，然后将所有颜色为P{P}P的积木染成颜色Q{Q}Q。
输出描述:
输出K+1{K+1}K+1行，即她进行K{K}K次染色操作之前，以及每次染色后能够通过交换得到最大的正整数对109+7{10^9+7}109+7取余数的结果。
示例1
输入
10 2 0
9586547120
1 2 1 2 1 1 1 1 1 1
输出
586754147
示例2
输入
10 2 1
9586547120
1 2 1 2 1 1 1 1 1 1
1 2
输出
586754147
876554147
示例3
输入
5 5 4
12345
1 2 3 4 5
3 2
2 5
4 5
5 1
输出
12345
13245
13245
15432
54321
思路：这个题就是搜同级相同数个数，排序，字符转化为int，查询更改。我们知道相连相同数个数，只需要将这个区间排序即可，然后将排好序的字符转化为int，最后查询更改颜色即可。
同级相同数的搜索：我们需要定义双指针，将l与r的位置至于相差1的位置，让r往后扩展，找到不同数停止即可。
不同级相同数搜索：我们需要初始化p[N]都为1，p[i]=p[i-1]+1。
for(int l=1,r=l+1;l<=n;l=r,r++)
{
if(a[l]!=a[r])continue;
else
{
while(1)
{
r++;
if(a[l]!=a[r])break;
}
}
}
?
排序：如果数组是从1开始的，sort(s+l,s+r+1,cmp);//第一个加的参数不需要加1就能让它从l开始，而第二个参数只能搜到r-1，这时我们就需要加1了。
字符串转化为int：
int res=0;
for(int i=1;i<=n;i++)
{
res=(res*10+(s[i]-'0'))%mod;
}
return res;
完整代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
int col[N];
int n,m,k;
char s[N];
bool cmp(char a,char b)
{
return a>b;
}
int val()
{
int l=1,r=1;
for(int l=1,r=1;l<=n;l=r+1,r=l)
{
if(col[l]!=col[r])continue;
else
{
while(1)
{
r++;
if(col[l]!=col[r])
{
r--;
break;
}
}
}
sort(s+l,s+r+1,cmp);
}
//for(int i=1;i<=n;i++)cout<<s[i];cout<<endl;
int res=0;
for(int i=1;i<=n;i++)
{
res=(res*10+(s[i]-'0'))%mod;
}
return res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m>>k;
cin>>s+1;
for(int i=1;i<=n;i++)
{
cin>>col[i];
}
cout<<val()<<endl;
while(k--)
{
int old,now;
cin>>old>>now;
for(int i=1;i<=n;i++)
{
if(col[i]==old)
{
col[i]=now;
}
}
cout<<val()<<endl;
}
return 0;
}
|