【Codeforces 1281C】Cut and Paste | 思维
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【Codeforces 1281C】Cut and Paste | 思维，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2149字，纯文字阅读大概需要4分钟。
内容图文
题目大意：
给一个串
s
s
s(下标从
1
1
1到
n
n
n),和一个变量
i
t
it
it,初始为
0
0
0.要你执行
x
x
x次操作,求最后的串长度对
1
0
9
+
7
10^9+7
109+7取模的结果.
操作如下:
- 将 i t + 1 it+1 it+1
- 将剪贴板的内容替换为 [ i t , n ] [it,n] [it,n]( n n n是当前的串的长度),并在原串中删除 [ i t , n ] [it,n] [it,n]
- 在串的末尾把剪贴板内容粘贴 s i t s_{it} sit? 次
题目思路：
靠。。。写的不能再傻逼了。
靠。。。我做法也太傻逼了。
看下正解：
考虑只会执行 x x x次，所以先把前x长度的串维护起来就好了。
每次操作都会增加一部分长度，因为前 x x x串长度都知道了，第 i i i个位置也就知道了，增加的长度就是：
( n n ? i ) ? ( s [ i ] ) (nn-i)*(s[i]) (nn?i)?(s[i])
操…
我的思路：
首先找下规律：
用 l a s t [ k ] last[k] last[k]代表第当前 k k k个数字的对长度贡献， c [ k ] c[k] c[k]代表 k k k已经出现了多少次，这样能推出上述公式的规律。
然后 n × 3 n \times 3 n×3模拟就好了…
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const int maxn = 1e6+700;
const int M = 1e6+8;
const int mod= 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll last[15],vis[15];
char s[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
memset(vis,0,sizeof(vis));
memset(last,0,sizeof(last));
scanf("%s",s+1);
int cnt = strlen(s+1);
for(int i=1;i<=cnt;i++) last[s[i]-'0']++;
for(int i=1;i;i++){
if(cnt>=n) break;
int len = cnt-i;
for(int j=2;j<=(s[i]-'0');j++){
for(int x=1;x<=len;x++){
s[cnt+1] = s[cnt+1-len];
++cnt;
if(cnt>=n) break;
}
if(cnt>=n) break;
}
}
s[cnt+1] = '\0';
//printf("%s\n",s+1);
int len = strlen(s+1);
for(int i=1;i<=min(n,len*1ll);i++){
vis[s[i]-'0']++;
ll tmp = s[i]-'0';
for(int k=1;k<=3;k++){
last[k] = ((vis[k]*(1ll-tmp)%mod+mod)%mod + tmp*last[k])%mod;
}
}
ll ans = 0;
for(int k=1;k<=3;k++) ans = (ans + last[k])%mod;
dl(ans);
}
return 0;
}
/***
1
24
133321333
***/
内容总结
以上是互联网集市为您收集整理的【Codeforces 1281C】Cut and Paste | 思维全部内容，希望文章能够帮你解决【Codeforces 1281C】Cut and Paste | 思维所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。