muti多校7 & 2017百度之星复赛 HDU 6129 题目要求 求原数组m次xor前缀和后的数组
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using namespace std;
int a[maxn],b[maxn];
int main
// freopen("input.txt" ,"r" ,stdin);
int t;
scanf("%d" ,&t);
while (t--){
int n,m;
scanf("%d%d" ,&n,&m);
mm(b,0);
for (int i=1;i<=n;i++) scanf("%d" ,&a[i]);
for (int i=1;i<=n;i++){
int x=i+m-2;
int y=i-1;
if ((x&y)==y){
for (int j=i;j<=n;j++) b[j]^=a[j-i+1];
}
}
for (int i=1;i<=n;i++){
if (i==1) printf ("%d" ,b[i]);
else printf (" %d" ,b[i]);
}
printf ("\n" );
}
return 0;
}
思路 转跳链接
HDU 6144 题目要求 Bomb Number中的bomb，也就是#号，会展开一些数字，这会导致最终展开的数字超出了度度熊所能理解的范畴。比如”(1)#(3)”表示”1”出现了3次，将会被展开为”111”，
第一行为T，表示输入数据组数。
1≤T≤100
1≤length(Bomb Number)≤1000
对每组数据输出表达式的结果，结果对 1 000 000 007 取模。
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
const LL mod=1e9+7;
vector<int>e;
int main
// freopen("input.txt" ,"r" ,stdin);
int t;
scanf("%d" ,&t);
while (t--){
e.clear();
string s;
cin>>s;
int len=s.length();
int st=-1,ed=-1;
int flag=-1;
int num=0;
for (int i=0;i<len;i++){
if (s[i]=='(' ){
if (flag==-1) flag=1;
}
if (s[i]>='0' && s[i]<='9' ){
if (flag==-1) e.push_back(s[i]-'0' );
else if (flag==1){
if (st==-1) st=i,ed=i;
else ed++;
}
else {
num=num*10+s[i]-'0' ;
}
}
if (s[i]=='#' ) flag=2;
if (s[i]==')' && flag==2){
for (int k=1;k<=num;k++){
for (int j=st;j<=ed;j++) e.push_back(s[j]-'0' );
}
flag=-1,num=0,st=-1,ed=-1;
}
}
LL ans=0;
for (int i=0;i<e.size();i++){
ans=(((ans*10)%mod+e[i])%mod)%mod;
}
cout<<ans<<endl;
}
return 0;
}
思路 模拟
HDU 6148 题目要求 当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。
第一行为T，表示输入数据组数。
对每组数据输出不大于N的Valley Number个数，结果对 1 000 000 007 取模。
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
const LL mod = 1e9+7;
int dp[105][15][2];
char s[105];
int bit[105];
LL dfs(int pos,int status,int pre,int limit ){
if (pos<1) return 1;
if (!limit && dp[pos][pre][status]!=-1) return dp[pos][pre][status];
int end=limit ? bit[pos]:9;
LL ans=0;
if (status){
for (int i=pre;i<=end;i++){
ans+=dfs(pos-1,1,i,limit &&i==end);
ans%=mod;
}
}
else {
for (int i=0;i<=end;i++){
if (i>pre) ans+=dfs(pos-1,1,i,limit &&i==end);
else {
if (!i && pre==10) ans+=dfs(pos-1,0,10,limit &&i==end);
else ans+=dfs(pos-1,0,i,limit &&i==end);
}
ans%=mod;
}
}
if (!limit ) dp[pos][pre][status]=ans;
return ans;
}
int main
// freopen("input.txt" ,"r" ,stdin);
mm(dp,-1);
int t; scanf("%d" ,&t);
while (t--){
scanf("%s" ,&s);
int len=strlen(s);
mm(bit,0);
for (int i=0;i<len;i++) bit[len-i]=s[i]-'0' ;
LL ans=dfs(len,0,10,1);
cout<<ans-1<<endl;
}
return 0;
}
思路 数位dp裸题 记忆化搜索
