“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

A 。张老师和菜哭武的游戏

题解：所有1–n以内 gcd（a，b）的倍数均能被选到。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=1000100;
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,a,b;
        scanf("%d%d%d",&n,&a,&b);
        printf((n/gcd(a,b)%2)?"Yes\n":"No\n");
    }
    return 0;
}
 

B 。伤害计算

题解：对于骰子，每个骰子伤害的期望值为（1+x）/2。固定为a，期望伤害值为a。
本来以为5000位需要用大数，后来才发现其实范围很小，不过还是用java写了

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
public class Main 
{
    public static void main(String[] args)
    {
        Scanner cin = new Scanner(System.in);
        Pattern pa = Pattern.compile("^[0-9]+$");
        long ans = 0;
        String[] s = cin.nextLine().split("\\+");
         
        for(int i = 0;i < s.length;i ++)
        {
            Matcher ma = pa.matcher(s[i]);
            if(ma.matches()) ans += Long.parseLong(s[i]) * 2;
            else
            {
                String[] ss = s[i].split("d");
                ans += Long.parseLong(ss[0]) * (1 + Long.parseLong(ss[1]));
            }
        }
        if(ans % 2 == 0) System.out.println(ans / 2);
        else System.out.printf("%.1f\n",ans/2.0);
    }
}

C 。张老师的旅行

题解：
考虑dp：
dpl [ l ] [ r ] 表示第 l 个点到第 r 个点都已经到达且最后在 l 点的最小值
dpr [ l ] [ r ] 表示第 l 个点到第 r 个点都已经到达且最后在 r 点的最小值

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=1100;
int dpl[maxn][maxn],dpr[maxn][maxn];
int p[maxn],t[maxn];
int main(void)
{
    int n,st;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t[i]);
        if(t[i]==0) st=i;
    }
    memset(dpl,0x3f,sizeof(dpl));
    memset(dpr,0x3f,sizeof(dpr));
    dpl[st][st]=dpr[st][st]=0;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            dpl[l][r]=min(dpl[l][r],min(dpl[l+1][r]+p[l+1]-p[l],dpr[l+1][r]+p[r]-p[l]));
            dpr[l][r]=min(dpr[l][r],min(dpl[l][r-1]+p[r]-p[l],dpr[l][r-1]+p[r]-p[r-1]));
            if(dpl[l][r]>t[l]) dpl[l][r]=inf;
            if(dpr[l][r]>t[r]) dpr[l][r]=inf;
        }
    }
    int ans=min(dpl[1][n],dpr[1][n]);
    printf("%d\n",ans==inf?-1:ans);
    return 0;
}

D 。车辆调度

题解：
估算一下时间复杂度，直接爆搜即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=20;
char str[maxn][maxn];
int n,m,k;
int x[]={0,0,-1,1};
int y[]={-1,1,0,0};
 
struct node
{
    int x,y;
    node(){}
    node(int a,int b)
    {
        x=a,y=b;
    }
};
vector<node>vc;
 
bool toCheckOk()
{
    for(auto nn:vc)
    {
        if(str[nn.x][nn.y]=='D') return true;
    }
    return false;
}
 
bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return false;
    if(str[x][y]=='X') return false;
    for(int i=0;i<vc.size();i++)
    {
        if(x==vc[i].x&&y==vc[i].y) return false;
    }
    return true;
}
 
void toDo(int i,int j)
{
    while(check(vc[i].x+x[j],vc[i].y+y[j]))
        vc[i].x+=x[j],vc[i].y+=y[j];
}
 
bool dfs(int k)
{
    if(toCheckOk())
        return true;
    if(k==0) return false;
    for(int i=0;i<vc.size();i++)
    {
        for(int j=0;j<4;j++)
        {
            vector<node>vv=vc;
            toDo(i,j);
            if(dfs(k-1)) return true;
            vc=vv;
        }
    }
    return false;
}
 
int main(void)
{
    scanf("%d%d%d",&m,&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%s",str[i]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(str[i][j]=='R')
                vc.pb(node(i,j));
        }
    }
    printf("%s\n",dfs(k)?"YES":"NO");
    return 0;
}

E 。弦

题解：记得很多年之前，学卡特兰数的时候遇到过这个东西，但是不会证明。
圆上2n个点得到n条线段不交的方案数为catn。
圆上2n个点得到n条线段的方案数为
C ( 2 n , 2 ) / n * C ( 2 n - 2 , 2 ) / ( n - 1 ) * * * * * * * C ( 2 , 2 ) / 1
也可以表示为 ( 2 n - 1 ) * ( 2 n - 3 ) * * * * * * * * * 1

不化简直接算：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
ll ans1,ans2,ans3;
ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main(void)
{
    int n;
    scanf("%d",&n);

    ans1=ans2=ans3=1;
    for(ll i=1;i<=n;i++)
    {
        ans1=ans1*(n+i)%mod;
        ans2=ans2*i%mod;
        ans3=ans3*(i*2-1)%mod;
    }
    ans2=ans2*(n+1)%mod;
    printf("%lld\n",ans1*mypow(ans2,mod-2)%mod*mypow(ans3,mod-2)%mod);
    return 0;
}

可以先化简：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
ll ans;
ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main(void)
{
    int n;
    scanf("%d",&n);
    ans=1;
    for(ll i=1;i<=n+1;i++)
        ans=ans*i%mod;
    printf("%lld\n",mypow(2,n)*mypow(ans,mod-2)%mod);
    return 0;
}

F 。排列计算

题解：使出现次数越多的数的权值越大。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=200100;
ll a[maxn];
int main(void)
{
    int n,m;
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x]++,a[y+1]--;
    }
    for(int i=1;i<=n;i++)
        a[i]+=a[i-1];
    sort(a+1,a+n+1);
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=1ll*i*a[i];
    printf("%lld\n",ans);
    return 0;
}

G 。硬币游戏Ⅲ

题解：一个经典的博弈问题，原博弈问题为：每次至少选连续的 1 个翻面，最多选连续的n个翻面，最右边的硬币一定是从正面到反面。推到过程类似，打表看规律。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=1000100;
bool ha[maxn];
int sg[maxn];
char str[maxn];
int n,k,p2=1;
 
int lowbit(int x)
{
    return x&(-x);
}
 
int get(int n)
{
    return lowbit(n%p2==0?p2:n%p2);
}
 
int main(void)
{
    scanf("%d%d",&n,&k);
    scanf("%s",str+1);
    while(p2*2<=k) p2*=2;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        sg[i]=get(i);
        if(str[i]=='1')
            ans^=sg[i];
    }
    printf(ans?"Yes\n":"No\n");
    return 0;
}

H 。时空栈

题解：考虑
某个区间 rz 为该区间净入栈（该区间进行操作完，栈内还能剩余的元素数）
某个区间 cz 为该区间净出栈（该区间操作完，还需要从前一区间出栈多少元素）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=200100;
struct node
{
    int l,r;
    int rz,cz;
}t[maxn<<2];
int op[maxn],ti[maxn],v[maxn],val[maxn],b[maxn];
 
void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].rz=t[cnt].cz=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    build(l,mid,cnt<<1);
    build(mid+1,r,cnt<<1|1);
}
 
void pushup(int cnt)
{
    if(t[cnt<<1].rz<=t[cnt<<1|1].cz)
    {
        t[cnt].cz=t[cnt<<1].cz+t[cnt<<1|1].cz-t[cnt<<1].rz;
        t[cnt].rz=t[cnt<<1|1].rz;
    }
    else
    {
        t[cnt].cz=t[cnt<<1].cz;
        t[cnt].rz=t[cnt<<1].rz+t[cnt<<1|1].rz-t[cnt<<1|1].cz;
    }
}
 
void change(int pos,int cnt,int val)
{
    if(t[cnt].l==t[cnt].r)
    {
        if(val==1)
            t[cnt].rz=1;
        else t[cnt].cz=1;
        return ;
    }
    if(pos<=t[cnt<<1].r) change(pos,cnt<<1,val);
    else change(pos,cnt<<1|1,val);
    pushup(cnt);
}
 
node ask(int l,int r,int cnt)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
        return t[cnt];
    if(r<=t[cnt<<1].r) return ask(l,r,cnt<<1);
    if(l>=t[cnt<<1|1].l) return ask(l,r,cnt<<1|1);
    node ansl,ansr,ans;
    ansl=ask(l,r,cnt<<1);
    ansr=ask(l,r,cnt<<1|1);
    if(ansl.rz<=ansr.cz)
    {
        ans.cz=ansl.cz+ansr.cz-ansl.rz;
        ans.rz=ansr.rz;
    }
    else
    {
        ans.cz=ansl.cz;
        ans.rz=ansl.rz+ansr.rz-ansr.cz;
    }
    return ans;
}
 
int ask(int l,int r,int cnt,int res)
{
    if(t[cnt].l==t[cnt].r) return val[t[cnt].l];
    if(r<=t[cnt<<1].r) return ask(l,r,cnt<<1,res);
    if(l>=t[cnt<<1|1].l) return ask(l,r,cnt<<1|1,res);
 
    node ansr=ask(t[cnt<<1|1].l,r,cnt);
    if(ansr.rz>=res) return ask(l,r,cnt<<1|1,res);
    else return ask(l,r,cnt<<1,res+ansr.cz-ansr.rz);
}
 
int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&op[i],&ti[i]);
        if(op[i]==0) scanf("%d",&v[i]);
        b[i]=ti[i];
    }
 
    build(1,n,1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        ti[i]=lower_bound(b+1,b+n+1,ti[i])-b;
 
        if(op[i]==0)
        {
            val[ti[i]]=v[i];
            change(ti[i],1,1);
        }
        else if(op[i]==1)
            change(ti[i],1,-1);
        else printf("%d\n",ask(1,ti[i],1,1));
    }
    return 0;
}

I 。纸牌

题解：
考虑
先进行一轮（n - 1）次操作。
可以得到x个闭环（x个划分），总共进行 k/（n-1）***作。
再进行k%（n-1）次操作。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=2000100;
int a[maxn],b[maxn];
bool ha[maxn];

void nextK(int n,int k)
{
    for(int i=1;i<=n;i++)
    {
        b[(i<<1)]=0;
        b[(i<<1)-1]=a[i];
    }
    int now=1;
    //这里，b数组的前 2*i 个元素中一共有 i 个 a数组中的元素
    //那么我们将第一个元素放置到 第 2*（i+1）处，那么他前面有i个元素，他就是第i+1个元素
    for(int i=1;i<=k;i++)
    {
        while(!b[now]) now++;
        swap(b[now],b[(i+1)<<1]);
    }
    now=0;
    for(int i=1;i<=n*2;i++)
    {
        if(b[i]) a[++now]=b[i];
    }
}

void nextC(int n,ll c)
{
    for(int i=1;i<=n;i++)
    {
        if(ha[i]) continue;
        int cnt=0,nt=i;
        while(!ha[nt])
        {
            ha[nt]=true;
            b[++cnt]=nt;
            nt=a[nt];
        }

        int p=c%cnt;
        b[0]=b[cnt];
        for(int i=1;i<=cnt;i++)
            a[b[i]]=b[(i+p)%cnt];
    }
}

int main(void)
{
    int n;
    ll k;
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++)
        a[i]=i;
    nextK(n,n-1);
    nextC(n,k/(n-1));
    nextK(n,k%(n-1));
    for(int i=1;i<=n;i++)
    {
        if(i!=1) putchar(' ');
        printf("%d",a[i]);
    }
    putchar('\n');
    return 0;
}

J 。斐波那契和

题解：推公式+矩阵快速幂。
算了，杜教BM真香！！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=998244353;
const double eps=1e-8;
const int maxn=550;

namespace linear_seq
{
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef pair<int,int> PII;
    const int N=10010;
    ll res[N],base[N],c[N],md[N];
    vector<int> Md;
    const ll mod=998244353;

    ll powmod(ll a,ll b)
    {
        ll res=1;
        a%=mod;
        for(;b;b>>=1)
        {
            if(b&1)
                res=res*a%mod;
            a=a*a%mod;
        }
        return res;
    }

    void mul(ll *a,ll *b,int k)
    {
        for(int i=0;i<k+k;++i) c[i]=0;
        for(int i=0;i<k;++i)
            if(a[i])for(int j=0;j<k ;++j)
                    c[i+j]=(c[i+j]+a[i]*b[j])%mod;

        for (int i=k+k-1;i>=k;i--)
            if(c[i])for(int j=0;j<(int)Md.size();++ j)
                    c[i-k+Md[j]]=(c[i-k+Md[j]]-c[i]*md[Md[j]])%mod;

        for(int i=0;i<k;++i) a[i]=c[i];
    }

    int solve(ll n,VI a,VI b)
    {
        ll ans=0,pnt=0;
        int k=SZ(a);
        for(int i=0;i<k;++i) md[k-1-i]=-a[i];
        md[k]=1;Md.clear();
        for(int i=0;i<k;++i)
            if(md[i]!=0)Md.push_back(i);

        for(int i=0;i<k;++i) res[i]=base[i]=0;
        res[0]=1;

        while ((1ll<<pnt)<=n)
            pnt++;

        for (int p=pnt;p>=0;p--)
        {
            mul(res,res,k);
            if ((n>>p)&1)
            {
                for (int i=k-1;i>=0;i--) res[i+1]=res[i];
                res[0]=0;
                for(int j=0;j<(int)Md.size();++ j)
                    res[Md[j]]=(res[Md[j]]-res[k]*md[Md[j]])%mod;
            }
        }

        for(int i=0;i<k;i++) ans=(ans+res[i]*b[i])%mod;
        if (ans<0) ans+=mod;
        return ans;
    }

    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        int L=0,m=1,b=1;
        for(int n=0;n<(int)s.size();++n)
        {
            ll d=0;
            for(int i=0;i<L+1;++ i)
                d=(d+(ll)C[i]*s[n-i])%mod;
            if(d==0) ++m;
            else if(2*L<=n)
            {
                VI T=C;
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m)C.push_back(0);
                for(int i=0;i<(int)B.size();++i) C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L; B=T; b=d; m=1;
            }
            else
            {
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m)C.push_back(0);
                for(int i=0;i<(int)B.size();++ i) C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        return C;
    }

    ll gao(VI a,ll n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        for(int i=0;i<(int)c.size();++i) c[i]=(mod-c[i])%mod;
        return (ll)solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
    }
};

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int f[maxn];
int main()
{
    ll n,k;
    scanf("%lld%lld",&n,&k);
    f[1]=f[2]=1;
    for(int i=3;i<maxn;i++)
        f[i]=(f[i-1]+f[i-2])%mod;
    ll ans=0;
    vector<int>vc;
    for(int i=1;i<=500;i++)
    {
        ans=(ans+mypow(i,k)*f[i])%mod;
        vc.pb(ans);
    }
    printf("%lld\n",linear_seq::gao(vc,n-1));
    return 0 ;
}