周末作业（20170402）

题解
A - Country Roads
题目链接
题目大意：

一个图，求一个点到分别到各个点的最大消耗，最短路中最长的边即为最大消耗

解题思路：

dij的变形，稍作改变即可

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int w[1005][1005],d[1005],vis[505];
int main(){
    int T,n,m,ncase=0;
    cin>>T;
    while(T--){
        cin>>n>>m;
        memset(d,0x3f,sizeof(d));
        memset(w,0x3f,sizeof(w));
        int u,v,t,s;
        for(int i=0;i<m;i++){
            cin>>u>>v>>t;
            if(w[u][v]>t){
                w[u][v]=t;
                w[v][u]=t;
            }
        }
        cin>>s;
        d[s]=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++){
            int x,m=INF;
            for(int j=0;j<n;j++){
                if(!vis[j]&&d[j]<m)
                    m=d[x=j];
            }
            vis[x]=1;
            for(int j=0;j<n;j++){
                    d[j]=min(d[j],max(d[x],w[x][j])); //本来应为d[j]=min(d[j],max(d[x]+w[x][j]))求最短路
            }
        }
        cout<<"Case "<<++ncase<<":"<<endl;
        for(int i=0;i<n;i++){
            if(d[i]==INF)
                cout<<"Impossible"<<endl;
            else cout<<d[i]<<endl;
        }
    }
    return 0;
}

B - How Many Zeroes?
题目链接
题目大意：

给出一些区间，求这些区间中共有多少个0（100有2个0，10有1个，11没有）注意前导0不算（‘十’ 010只是一个0）

解题思路：

（a，b）用solve（b）-solve（a-1）即为答案。求0~n一共有多少个0，先将这个数拆分放进数组里，一位一位的遍历，注意234，当第一位为2时，第二位只能为0,1,2,3.当第一位为0,1,2时第二位可以为0~9没有限制，还有前导0不算，搞懂这一点以为以为dfs就行了

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
int dp[50][50],d[50];//dp[i][j]表示处理到第i位是，前面有j个0（前导0不算）（例如：dp[2][j]（除前面都是0的情况）共有20个0，，00,01,02,03,04,05,06,07，08，09,10,20，30,40,50,60,70,80.。。dp【1】【j】就只有1个0）
LL dfs(int len,bool first,int sta,bool limit){//len为数的长度，first判断是不是前导0，sta表示已有多少0，limit表示上一位是否让这一位数字受到限制（如上述）
    if(!len){//处理到最后一位
        if(first) return 1;  //前面都没非0数，说明这个数为0
        else return sta;
    }
    if(!first&&!limit&&dp[len][sta]!=-1) //无上一位限制，且并非前导0，且dp值不等于-1，则可以记忆化搜索
        return dp[len][sta]; 
    int n=(limit?d[len]:9);  // 上一位限制
    LL ans=0;
    for(int i=0;i<=n;i++){
        if(first)
            > ans+=dfs(len-1,first&&i==0,0,limit&&i==n)//前导0情况
        else {
            if(i==0)
                ans+=dfs(len-1,0,sta+1,limit&&i==n);
            else ans+=dfs(len-1,0,sta,limit&&i==n);
        }
    }
    if(!limit&&!first)
        dp[len][sta]=ans;  //无限制非前导可保存
    return ans;
}
LL solve(LL x){
    int cnt=0;
    if(x<0) return 0;
    if(x==0) return 1;
    while(x){
        d[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,1,0,1);
}
int main(){
    LL T,a ,b,ncase=0;
    cin>>T;
    while(T--){
        cin>>a>>b;
        memset(dp,-1,sizeof(dp));
        printf("Case %d: ",++ncase);
        cout<<solve(b)-solve(a-1)<<endl;
    }
}

**D - Summing up Powers **
题目链接
题目大意：

给出一个数n,k，求1^k+2^k+3^k+.....n^k 对2^32求膜

解题思路：

这道题不会，是看了题解才明白的题解，但是一个细节２＾３２就是unsigned int。注意要快速幂

ＡＣ代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef unsigned int  uint;
LL mod;
struct matrix{
    uint m[55][55];
    int r;
    matrix(int _r){
        r=_r;
        memset(m,0,sizeof(m));
    }
    matrix operator* (matrix t){
        matrix res=matrix(r);
        for(int i=1;i<=r;i++)
            for(int j=1;j<=r;j++)
                for(int k=1;k<=r;k++)
                   res.m[i][j]+=m[i][k]*t.m[k][j];
        return res;
    }
};
matrix getA(int k){
    matrix res=matrix(k+2);
    for(int i=1;i<=res.r;i++)
        res.m[i][1]=1;
    return res;
}
uint c[55][55];
void init(){
    memset(c,0,sizeof(c));
     c[1][1] = 1;
    for(int i = 1; i <= 50; ++i) c[i][0] = 1;
    for(int i = 2; i <= 50; ++i)
        for(int j = 1; j <= i; ++j)

          c[i][j]=c[i-1][j]+c[i-1][j-1];
}
matrix getD(int k){
    matrix res=matrix(k+2);
    res.m[1][1]=1;
    for(int i=2;i<=k+2;i++)
        res.m[1][i]=c[k][i-2];
    for(int i=2;i<=k+1;i++){
        for(int j=i;j<=k+2;j++)
            res.m[i][j]=c[k+2-i][j-i];
    }
    res.m[k+2][k+2]=1;
    return res;
}
matrix powmatrix(matrix a,LL n){
    matrix res=matrix(a.r);
    for(int i=1;i<=res.r;i++)
        res.m[i][i]=1;
    while(n){
        if(n&1) res=res*a;
        a=a*a;
        n>>=1;
    }
    return res;
}
int main(){
    init();
    int T,ncase=0;
    cin>>T;
    while(T--){
        LL n;int k;
        cin>>n>>k;
        if(k==0) {
             printf("Case %d: %u\n",++ncase,(uint)n);
             continue;
        }
        matrix D = getD(k);
        matrix A=getA(k);
        matrix ans = powmatrix(D, n-1) * A;
        printf("Case %d: %lld\n",++ncase,ans.m[1][1]);
    }
    return 0;
}