T1- 开着老爷车去 CSP

你有一辆车，每开 $k$ 公里要修理 $t$ 秒 你离目的地 $d$ 公里，你开车的速度和步行的速度分别是 $a$ 和 $b$ 你可以随时弃车步行，求到目的地的最少时间

解法

数学推导，第一段肯定是开车去 后面将开车一段和修理的时间与步行相同路程的时间做一下比较 如果步行优，行完第一段就弃车 如果开车优，还要判断最后一段是开车还是步行

ac 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll d,k,a,b,t,ans;
int main()
{
    scanf("%lld%lld%lld%lld%lld",&d,&k,&a,&b,&t);
    if(d<=k)printf("%lldn",a*d),exit(0);
    ll opt=ak-bk+t;
    if(opt>=0)ans=ak+b(d-k);
    else
    {
        ll x=d/k,y=d%k;
        if(y)ans=min(optx+db-t,da+xt);
        else ans=optx+db-t;
    }
    printf("%lldn",ans);
    return 0;
}

T2-CSP- S 图

一幅带权有向图，每个点有且只有一个出边 求每个点走了 k 步之后经过的所有权值和最小权值

解法

因为每个点只有一个出边，所以每一步走法是唯一的 所以可以搞出一个 dp $f_{i,k}=f_{to_i,k-1}+w[i]$ $g_{i,k}=min(g_{to_i,k-1},w[i])$ 然后这玩意可以倍增优化转移

ac 代码

#include<bits/stdc++.h>
#define N 100010
#define K 35
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
int n,k,tN,sumN,minnN;
signed main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&ti),ti++;
    for(int i=1;i<=n;i++)
        scanf("%lld",&sumi),minni=sumi;
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++)
            ti=tt[i][j-1],
            sumi=sumi+sumt[i][j-1],
            minni=min(minni,minnt[i][j-1]);
    for(int i=1;i<=n;i++)
    {
        int ans1=0,ans2=inf,nw=i;
        for(int j=0;j<K;j++)if(k&(1ll<<j))
            ans1+=sumnw,ans2=min(ans2,minnnw),nw=tnw;
        printf("%lld %lldn",ans1,ans2);
    }
    return 0;
}

T3- 好运

一个数如果是 7 的倍数，会带来好运气 但如果 $x\mod p_i=a_i$ 反而会带来坏运气 求区间 $[l,r]$ 内会带来好运气的数的个数

解法

用 CRT 和容斥乱搞一下 具体见代码

ac 代码

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
void ex_gcd(int a,int b,int &x,int &y)
{
    if(!b)x=1,y=0;
    else ex_gcd(b,a%b,y,x),y-=(a/b)*x;
}
int T,q,l,r,ans,p[20],o[20],m[20],a[20];
pii tmp;
pii china(int n)
{
    int ans=0,lcm=1,x,y;
    for(int i=1;i<=n;i++)lcm*=m[i];
    for(int i=1;i<=n;i++)
    {
        int M=lcm/m[i];
        ex_gcd(M,m[i],x,y);
        x=(x%m[i]+m[i])%m[i];
        ans=(ans+Mxa[i])%lcm;
    }
    return mp((ans+lcm)%lcm,lcm);
}
//CRT模板
int solve()
{
    int st,ed;
    if(l<=tmp.fir)st=0;
    else st=(l-tmp.fir-1)/tmp.sec+1;
    if(r<tmp.fir)ed=-1;
    else ed=(r-tmp.fir)/tmp.sec;
    return ed-st+1;
}
//solve用来求一个区间内满足要求的数的个数
void dfs(int nw,int cnt)
{
    if(nw>q)
    {
        tmp=china(cnt);
        //用CRT求出最小整数解
        if(cnt&1)ans+=solve();
        else ans-=solve();
        //如果限制条件是奇数，就加
        //如果限制条件是偶数，就减
    }
    else
    {
        dfs(nw+1,cnt);
        cnt++;
        m[cnt]=p[nw];
        a[cnt]=o[nw];
        dfs(nw+1,cnt);
    }
}
signed main()
{
    scanf("%lld",&T);
    for(int _i=1;_i<=T;_i++)
    {
        memset(m,0,sizeof(m));
        memset(a,0,sizeof(a));
        scanf("%lld%lld%lld",&q,&l,&r);
        for(int i=1;i<=q;i++)
            scanf("%lld%lld",&p[i],&o[i]);
        m[1]=7,a[1]=0,ans=0,dfs(1,1);
        printf("Case #%lld: %lldn",_i,ans);
    }
    return 0;
}