第十届河南理工大学程序设计大赛题解

很高兴能和小伙伴们办一场成功的河南理工大学程序设计大赛。

Dong Zhi

直接输出即可。

1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;
int main()
{
printf("Let's eat dumplings");
return 0;
}
The flower

利用$map$储存长为$k$的字符串,暴力计算即可。

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
#include<bits/stdc++.h>

using namespace std;
int main(){
string s;
int k;
cin>>s>>k;
unordered_map<string,int> mmp;
set<string> st;
int n=(int)s.length();
for(int i=k-1;i<n;i++){
string now=s.substr(i-(k-1),k);
mmp[now]++;
st.insert(now);
}
set<string> ans;
for(auto v:st){
if(mmp[v]>2){
ans.insert(v);
}
}
cout<<(int)ans.size()<<endl;
for(auto v:ans) cout<<v<<endl;
return 0;
}
Xor Path

$DFS$计算从根节点到每个节点的异或和,同时计算倍增。然后利用倍增可以实现$O(log_n)$的查询。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
vector<int> G[N];
int pre[N],a[N],par[N];
long long bit[30];
int f[N][30];
int depth[N];
void init(){
bit[0]=1;
for(int i=1;i<=29;i++) bit[i]=(bit[i-1]<<1);
}
void dfs(int u,int par){
depth[u]=depth[par]+1;
f[u][0]=par;
for(int i=1;bit[i]<=depth[u];i++) f[u][i]=f[f[u][i-1]][i-1];
for(int v:G[u]){
if(v!=par) dfs(v,u);
}
}
int lca(int x,int y){
if(depth[x]<depth[y]) swap(x,y);
for(int i=29;i>=0;i--){
if(depth[x]-depth[y]>=bit[i]){
x=f[x][i];
}
}
if(x==y) return x;
for(int i=29;i>=0;i--){
if(depth[x]>=(1<<i)&&f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void DFS1(int u,int fa){
par[u]=fa;
pre[u]=pre[fa]^a[u];
for(int v:G[u]){
if(v==fa) continue;
DFS1(v,u);
}
}
int main(){
int n,u,v,q;
cin>>n;
init();
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<=n;i++) G[i].clear();
for(int i=1;i<=n-1;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
DFS1(1,0);
int x,y;
cin>>q;
while(q--){
cin>>x>>y;
int c=lca(x,y);
int f=par[c];
cout<<(pre[x]^pre[f]^pre[c]^pre[y])<<endl;
}
return 0;
}
LaunchPad

开两个数组分别记录当前行或列是否有操作,再开一个二维数组计算每个灯在操作后的亮灭情况(用来调整行和列所带来的一次操作而不是两次操作)。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000+10;
int a[maxn],b[maxn];
int c[maxn][maxn];
int main()
{
int n,m,q;
scanf("%d %d",&n,&m);
scanf("%d",&q);
while(q--){
int u,v;
scanf("%d %d",&u,&v);
c[u][v]^=1;
a[u]^=1;
b[v]^=1;
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans+=a[i]^b[j]^c[i][j];
}
}
printf("%d\n",ans);
return 0;
}
Morse code

长度为$2$的$4$种情况已经全部出现过,长度为$3$的$8$种情况也已经出现过,因此我们一定能够利用长度为$2$或$3$的字母去填充,因此答案就是$len/2$。

此处给出$dp$做法,以供学习。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
map<int,int>mp;
string code[100];
char s[maxn];
int dp[maxn];
void init(){
code[1]=".-"; code[2]="-..."; code[3]="-.-."; code[4]="-..";
code[5]="..-."; code[6]="--."; code[7]="....";
code[8]=".."; code[9]=".---"; code[10]="-.-"; code[11]=".-..";
code[12]="--"; code[13]="-."; code[14]="---"; code[15]=".--.";
code[16]="--.-";code[17]=".-."; code[18]="...";
code[19]="..-"; code[20]="...-"; code[21]=".--";code[22]="-..-";
code[23]="-.--"; code[24]="--..";
for(int i=1;i<=24;i++){
int num=0;
for(int j=0;j<code[i].length();j++) num=num*100+code[i][j];
mp[num]++;
}
}
int cal(int a,int b){
int num=0;
for(int i=a;i<=b;i++) num=num*100+s[i];
return mp[num]?1:0;
}
void solve(){
scanf("%s",s);
int n=strlen(s);
for(int i=0;i<n;i++){
dp[i]=0;
for(int j=1;j<=4;j++){
int y=i-j;
dp[i]=max(dp[i],dp[i-j]+cal(i-j+1,i));
}
}
printf("%d\n",dp[n-1]);
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
For language

直接模拟计算即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
const ll maxn=1000000+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
map<string,int>mp;
char s[maxn];
int main()
{
int n;
scanf("%d",&n);
ll ans=0,sum=1;
for(int i=0;i<n;i++){
scanf("%s",s);
if(s[0]=='f'){
ll x,y;
scanf("%s %lld %lld",s,&x,&y);
sum*=(y-x+1);
sum%=mod;
}
else if(s[0]=='e'){
ans=(ans+sum)%mod;
sum=1;
}
}
printf("%lld\n",ans);
return 0;
}
Puzzle

原签到题。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
const ll maxn=1000000+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
int a[100];
void init(){
a[0]=1;
a[1]=0;
a[2]=0;
a[3]=0;
a[4]=1;
a[5]=0;
a[6]=1;
a[7]=0;
a[8]=2;
a[9]=1;
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--){
ll x;
scanf("%lld",&x);
if(x==0) printf("1\n");
else{
int num=0;
while(x){
num+=a[x%10];
x/=10;
}
printf("%d\n",num);
}
}
return 0;
}
Triangle tower

尖向上的小三角形能够组成一个杨辉三角,向下的又能够组成一个杨辉三角,因此分情况计算即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int maxn=100000+10;
ll fac[maxn];
void init(){
fac[0]=1;
for(int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
}
ll qp(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll c(int n,int m){
return fac[n]*qp(fac[m],mod-2)%mod*qp(fac[n-m],mod-2)%mod;
}
ll solve(int n,int m){
n--;
if(m%2==0) n--;
m=(m-1)/2;
printf("%lld\n",c(n,m));
}
int main()
{
int t,n,m;
scanf("%d",&t);
init();
while(t--){
scanf("%d %d",&n,&m);
solve(n,m);
}
return 0;
}
Kingdom of Mathematics

应该是整个比赛里面最难的一个题?

Part1
$$
2f(n)+f(n+1)=f(n+2)-2n+1 \\
f(n+2)-f(n+1)=2f(n)+2n-1 \\
f(n+1)-f(n)=2f(n-1)+2(n-1)-1 \\
f(n)-f(n-1)=2f(n-2)+2(n-2)-1 \\
… \\
f(3)-f(2)=2f(1)+2-1 \\
f(2)-f(1)=2f(0)+0-1 \\
$$
左边相加与右边相加即可得:
$$
f(n+2)-f(1)=2\sum_{i=0}^{n}(f(i)+i)-n-1 \\
f(n+2)=2\sum_{i=0}^{n}(f(i)+i)-n \\
f(n+2)+(n+2)=2\sum_{i=0}^{i=n}(f(i)+i)+2
$$
设$g(x)=f(x)+x$ ,则:
$$
g(n+2)=2\sum_{i=0}^{i=n}(g(i))+2 \\
g(n+1)=2\sum_{i=0}^{i=n-1}(g(i))+2 \\
g(n+2)-g(n+1)=2g(n) \\
g(n+2)=g(n+1)+2g(n) \\
g(n+1)=g(n)+2g(n-1) \\
… \\
g(3)=g(1)+2g(0) \\
\because g(0)=f(0)+0=1,g(1)=f(1)+1=2 \\
\therefore g(2)=4 \\
\therefore g(n)=2^n
$$
所以可计算出:
$$
f(x)=g(x)-x \\
=2^x-x
$$
Part2

可以发现,$f(x)$的二进制表示位数为$x$位,而且在$x$足够大时,可以发现高位数几乎全为$1$。我们将$f(x)$每两项进行异或$(f(1)\bigoplus f(2),f(3)\bigoplus f(4) …)$,可以发现$f(2n-1)\bigoplus f(2n)=2^{2n-1}+1$ ,因此前偶数项我们就可以用类似的方法计算出结果$((11)_2\bigoplus(1001)_2\bigoplus (100001)\bigoplus…)$ ,结果为各项$2^k$部分相加,最后一位判断总共有多少对即可。

对于奇数$n$,我们已知前$n-1$位的值$101010101010…$,我们将其分为两部分,低位部分位$n$影响到的部分(即与高位全一部分的分界线),高位部分为全一部分。然后分开计算即可。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000+10;
const ll mod=1e9+7;
ll T,n;
ll qp(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
//等比数列前x项之和 第一项为1
ll judge(ll x){
ll sum=(qp(4,x)-1+mod)%mod;
return 2*sum*qp(3,mod-2)%mod;
}
//二进制位数
ll bits(ll x){
ll sum=0;
while(x){
sum++;
x>>=1;
}
return sum;
}
ll revise(ll x,ll step){
ll pos=1;
stack<ll>st;
for(int i=1;i<=step;i++){
if(i%2==0) st.push(1-(x&1));
else st.push(x&1);
x>>=1;
}
ll sum=0;
while(!st.empty()){
sum=sum*2+st.top();
st.pop();
}
return sum;
}
int main()
{
scanf("%lld",&T);
while(T--){
ll res;
scanf("%lld",&n);
if(n&1){
ll vis=bits(n);
//高位没被影响到的的值
res=judge((n-vis)/2);
if((n-vis)&1) res=(res*2+1)%mod;
res=res*qp(2,vis)%mod;
//低位被异或的值
res=(res+revise((1ll<<vis)-n,vis))%mod;

//最后一位加or减
if((n/2)&1){
if(n&1) res=(res-1+mod)%mod;
else res=(res+1)%mod;
}
}
else{
res=judge(n/2);
if((n/2)&1) res=(res+1)%mod;
}
printf("%lld\n",res);
}
return 0;
}
HPU’s birthday

暴力计算每个$0$的贡献即可,假如某个$0$前面有$n$个$1$,那么它的贡献即为$a*(a-1)/2$。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
int q[100];
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int num=0;
ll ans=0;
ll x=n;
while(x){
q[num++]=x&1;
x>>=1;
}
x=0;
for(int i=0;i<n;i++){
for(int j=num-1;j>=0;j--){
if(q[j]) x++;
else ans=(ans+x*(x-1)/2)%mod;
}
}
printf("%lld\n",ans);
}
return 0;
}

以下为$n=10^{18}$的解法:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
int q[100];
ll qp(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll cal(ll x,ll n,ll a){
ll ans=0;
ans=n*x*x%mod;
ans=(ans+(n-1)%mod*n%mod*x%mod*a%mod);
ans=(ans+(n-1)%mod*n%mod*(2*n-1)%mod*qp(2,mod-2)%mod*a%mod*a%mod);
ans=(ans-n%mod*x%mod+mod)%mod;
ans=(ans-(n-1)%mod*n%mod*qp(2,mod-2)%mod*a%mod+mod)%mod;
return ans;
}
int main()
{
ll inv2=qp(2,mod-2);
ll t;
scanf("%lld",&t);
while(t--){
ll n;
scanf("%lld",&n);
ll num=0,ans=0,x=n;
ll one=0;
while(x){
if(x&1) one++;
q[num++]=x&1;
x>>=1;
}
x=0;
for(int i=num-1;i>=0;i--){
if(q[i]) x++;
else ans=(ans+cal(x,n,one));
}
printf("%lld\n",ans*inv2%mod);
}
return 0;
}
Max Sum

我们首先记录前缀和数组$pre[]$和后缀和数组$nxt[]$,然后对其建两棵线段树。

对于第$i$个位置,我们计算区间$[i-k-1,i-1]$的最小前缀和和$[i+1,i+k+1]$的最小后缀和,数组总和减去这两部分的值即为第$i$个位置的最大值。由于数据范围的原因,还要特别处理一下边界条件。

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
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
int a[maxn];
ll pre[maxn],nxt[maxn];
int k[maxn];
int N;
struct Tree{
ll x[maxn];
void init(int x){
N=1;
while(N<=x*2) N*=2;
}
void update(int k,int q){
k+=N-1;
x[k]=q;
while(k){
k=(k-1)/2;
x[k]=min(x[k*2+1],x[k*2+2]);
}
}
ll query(int a,int b,int l,int r,int k){
if(r<a || b<l) return INF;
if(a<=l && r<=b) return x[k];
else{
ll vl=query(a,b,l,(l+r)/2,k*2+1);
ll vr=query(a,b,(l+r)/2+1,r,k*2+2);
return min(vl,vr);
}
}
}tp,tn;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&k[i]);
tp.init(n);
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
tp.update(i,sum);
}
sum=0;
for(int i=n;i>=1;i--){
sum+=a[i];
tn.update(i,sum);
}
ll ans=0;
for(int i=1;i<=n;i++){
ans+=sum;
ans-=tp.query(max(i-k[i]-1,0),max(i-1,0),0,N-1,0);
ans-=tn.query(min(i+1,n+1),min(i+k[i]+1,n+1),0,N-1,0);
}
printf("%lld\n",ans);
return 0;
}
Restore Expressions

要使中的贡献最小,首先把除了第一项以外的值全部置为$1$,仅考虑第一项的值即可,假设表达式的值为$0$,计算出两个式子第一项值为$a,b$,那么我们就进行如下操作:若其中一项不为正数,则两个数均加上一个值使得两个数均为正数。这样可以使得两个式子值相同且贡献尽可能的小。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000+10;
char s[maxn],t[maxn];
void solve(){
int n;
scanf("%d",&n);
scanf("%s %s",s,t);
int a=0,b=0;
for(int i=0;i<n;i++){
if(s[i]=='-') a++;
else a--;
if(t[i]=='-') b++;
else b--;
}
int prea,preb;
prea=a+max(1-min(a,b),0);
preb=b+max(1-min(a,b),0);

printf("%d %d\n",0,prea+preb+n*2);

printf("%d",prea);
for(int i=1;i<=n;i++) printf(" %d",1);
printf("\n");

printf("%d",preb);
for(int i=1;i<=n;i++) printf(" %d",1);
printf("\n");
}
int main()
{
solve();
return 0;
}

总的来说这套题目难度一般,并没有特别的偏难怪题,也没有卡题意卡空间卡时间的题,感觉质量还是可以的。

感谢您的支持
-------------本文结束感谢您的阅读-------------