2020-01-19 18:15 C++

关注

【题解】河南理工大学新生挑战赛

A、Dong Zhi

直接输出即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    printf("Let's eat dumplings");
    return 0;
}

B、The flower

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

#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;
}

C、Xor Path

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

#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;
}

D、LaunchPad

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

#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;
}

E、Morse code

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

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

#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;
}

F、Puzzle

原签到题。

#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;
}

G、Triangle tower

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

#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;
}

H、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$ 影响到的部分（即与高位全一部分的分界线），高位部分为全一部分。然后分开计算即可。

#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;
}

I、HPU's birthday

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

#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}$ 的解法：

#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;
}

J、Max Sum

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

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

#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;
}

K、Restore Expressions

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

#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;
}