Link:

C:

暴力$dfs$就好了

#include 
      
       using namespace std;typedef long long ll;ll n,res=0;int dgt[15],cnt;void dfs(int dep,ll sum){    if(dep==cnt){res+=sum;return;}    for(int i=dep+1;i<=cnt;i++)    {        ll t=0;        for(int j=dep+1;j<=i;j++)             t=t*10+dgt[j];        dfs(i,sum+t);    }}int main(){    scanf("%lld",&n);    for(;n;n/=10) dgt[++cnt]=n%10;    reverse(dgt+1,dgt+cnt+1);dfs(0,0);    printf("%lld",res);    return 0;}
      

 

D:

没有办法直接上暴力，但可以采取计算贡献的方式：

每个有色点都对周围的9个正方形恰好有1点贡献

将$9*k$个正方形用其左上角的坐标表示，排序后将相同的合并就是该正方形的个数了

最后用总的减去个数为$[1,9]$的就是个数为0的个数了

#include 
      
       using namespace std;#define X first#define Y secondtypedef long long ll;typedef pair
       
         P;const int MAXN=1e5+10;P sqr[MAXN*10];ll sum=0,cnt[15];int n,m,k,x,y,tot;int dx[]={-2,-2,-2,-1,-1,-1,0,0,0};int dy[]={-2,-1,0,-2,-1,0,-2,-1,0};int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=k;i++)    {        scanf("%d%d",&x,&y);        for(int j=0;j<9;j++)        {            int fx=x+dx[j],fy=y+dy[j];            if(fx>0&&fy>0&&fx<=n-2&&fy<=m-2)                sqr[++tot]=P(fx,fy);        }    }        sort(sqr+1,sqr+tot+1);    int cur=1;    for(int i=2;i<=tot;i++)        if(sqr[i]==sqr[i-1]) cur++;        else cnt[cur]++,cur=1;    if(k) cnt[cur]++;//不要忘记对末尾的处理         for(int i=1;i<=9;i++) sum+=cnt[i];    cnt[0]=1ll*(m-2)*(n-2)-sum;    for(int i=0;i<10;i++) printf("%lld\n",cnt[i]);    return 0;}
       
      

 

E:

先来说说正解：拆点最短路

在每个站点中，对于每一个其能转换到的公司都新设立一个站点，并建立一个总站

也就是说，对于边$(u,v,c)$，建边$(u,u[c],1),(v,v[c],1),(u[c],v[c],0)$

这样体现了是否转换公司的抉择，直接在新图上求最短路就好了

但注意最后答案要除以2，毕竟这样建图每转换一次其实计算了2次1

 

我的做法又是极为感性的

在每个点都用一个$set$维护当前能达到最短距离时的末尾公司名，转移时贪心

感觉没什么问题，但不知道为什么在距离相同时一定要先处理编号较大的节点？请各位神犇们指点啊……

#include 
      
       using namespace std;#define X first#define Y secondtypedef pair
       
         P;const int MAXN=1e5+10,INF=1<<27;int n,m,x,y,z,dist[MAXN];set
        
          s[MAXN];vector
         
 G[MAXN];//必须要用set，因为可能dist最小时有多种公司供选择 struct cmp{
     //一定要编号大的先处理（原因未知）     bool operator() (const P& a,const P& b)    {
     return a.X!=b.X?a.X>b.X:a.Y
          
           ,cmp > q;    for(int i=2;i
           
            dist[u]) continue; for(int i=0;i
           
          
        
       
      

 

F:

设游戏结束前使用了$x$张$b$，$y$张$c$

可以发现最终一共使用了$n+x+y$张卡片，且由于最后一张一定是$a$可以不用考虑

因此可以比较容易的写出一下的式子：

$res=\sum_{p=0}^{m+k} C_{n−1+x+y}^{n-1}*3^{m+k−x−y}*\sum_{0\le x\le m,0\le y\le k}[x+y=p]C_{p}^{x}$

 

为了将计算的时间降到$O(n)$，我们可以用递推的方式优化$\sum C_{p}^{x}$

设$f(i)$表示$p=i$时该式的值，发现递推有三个阶段（假设$m<k$）：

1、$i<m$时$f(i)=\sum_{j=0}^{i} C_i^j$

2、$m\le i<k$时$f(i)=\sum_{j=0}^{m} C_i^j$

3、$k\le i$时$f(i)=\sum_{j=i-k}^m C_i^j$

将这些式子放到杨辉三角形上可以发现：

1阶段时$f(i)=f(i-1)*2$（二项式系数和的基本结论）

2阶段时$f(i)=f(i-1)*2-C_{i-1}^m$（减掉右边界的值）

3阶段时$f(i)=f(i-1)*2-C_{i-1}^m-C_{i-1}^{i-1-k}$（减掉左右边界的值）

#include 
      
       using namespace std;typedef long long ll;const int MAXN=(3e5+10)*3,MOD=1e9+7;ll res=0,cur=1;int n,m,k,fac[MAXN],inv[MAXN];ll quick_pow(ll a,ll b){    ll ret=1;    for(;b;b>>=1,a=a*a%MOD)        if(b&1) ret=ret*a%MOD;    return ret;}int C(int a,int b){
     if(a
       
        <0) return 0;return 1ll*fac[a]*inv[b]%MOD*inv[a-b]%MOD;}int main(){    scanf("%d%d%d",&n,&m,&k);    fac[0]=1;    for(int i=1;i
        
         =0;i--)        inv[i]=1ll*inv[i+1]*(i+1)%MOD;        for(int i=n;i<=n+m+k;i++)        (res+=C(i-1,n-1)*cur%MOD*quick_pow(3,n+m+k-i)%MOD)%=MOD,        cur=(2*cur-C(i-n,m)+MOD-C(i-n,i-n-k)+MOD)%MOD;    printf("%lld",res);    return 0;}
        
       
      

优化方式涨姿势了