CQUPT 训练题 2017/4/3

未分类

A - Country Roads LightOJ - 1002
题意：

T组测试样例，每组测试样例包含N,M表示有n个点，m条路径，每条路径从u到v权值为w，求出所有点到目的地点t的路径权值最小（此权值表示这条路径上最大的两点之间的权值）。

解题思路：

dijsktra算法的变形，将d[i]保存目的地到第i点路径的最小权值，map[u][j]表示u到j的权值，每次比较最短路径时，
tmp=max(d[u],map[u][j])，    d[j]=min(d[j],tmp);需要注意的是，输入的时候可能有重复的边去最小的输入。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long 
#define inf 0x3f3f3f3f
using namespace std;
int d[600],vis[600],map[600][600];
int n,m;
void dijkstra(int s)
{
    for(int i=0;i<n;i++)
      d[i]=inf;
    d[s]=0;
    vis[s]=1;
    for(int i=0;i<n-1;i++)
    {
        int u=s,mm=inf;
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&d[j]<mm)
            {
                u=j;
                mm=d[j];
            }
        }
        vis[u]=1;
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&map[u][j]!=inf)
            {
                int tmp=max(d[u],map[u][j]);
                d[j]=min(d[j],tmp);
            }
        }
    }
}
int main()
{
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j)
                map[i][j]=0;
                else
                map[i][j]=inf;
            }
        }
        int u,v,w;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
             if(map[u][v] > w)  
            {  
                map[u][v] = w;  
                map[v][u] = w;  
            }
        }
        int s;
        scanf("%d",&s);
        memset(vis,0,sizeof(vis));
        dijkstra(s);
        printf("Case %d:\n",cas++);
        for(int i=0;i<n;i++)
        {
            if(d[i]!=inf)
            printf("%d\n",d[i]);
            else
            printf("Impossible\n");
        }
    }
    return 0;
}

C - Greatest Parent LightOJ - 1128
题意：

给出一棵树有N个节点，每个节点都有一个权值，给出q个查询，每个查询包含一个k和v,k表示第k个节点，求出树根和k节点的路径上，权值大于等于v的离树根最近的节点

解题思路：

dp[v][i] 表示节点y ～ 它的2^i号祖先的路径上点权的最大值
fa[v][i] 表示节点y 的第2^i 号祖先
状态转移方程：dp[y][i] = max(dp[y][i - 1], dp[fa[y][i-1]][i-1])

代码：

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=100005;
vector <int> g[maxn];
int fa[maxn][18];
int dp[maxn][18],val[maxn];
void dfs(int x)
{
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        fa[y][0]=x;
        dp[y][0]=val[y];
        for(int j=1;j<18;j++) fa[y][j] = fa[fa[y][j-1]][j-1]; 
        for(int j=1;j<18;j++) dp[y][j] =max(dp[y][j-1],dp[fa[y][j-1]][j-1]);
        dfs(y);
    }
}
int solve(int x,int y)
{
    for(int i=17;i>=0;i--)
    {
        if(dp[fa[x][i]][i]>=y) x=fa[x][i];
    }
    return x;
}
int main()
{
    int t,cas=1,n,q,x;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        for(int i=0;i<=n;i++)
         g[i].clear();
        val[0]=1;
        for(int i=0;i<18;i++)
        {
            dp[0][i]=val[0];
            fa[0][i]=0;
        }
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&val[i]);
            g[x].push_back(i);
        }
        dfs(0);
        printf("Case %d:\n",cas++);
        int a,b;
        for(int i=0;i<q;i++)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",solve(a,b));
        }
    }
    return 0;
}

D - Summing up Powers LightOJ - 1132
题意：

(1^K + 2^K + 3^K + ... + N^K) % 2^32,给出N和K求出结果

解题思路：

快速矩阵幂：
f(x + 1) = f(x) + (x + 1) ^k，(x + 1)^k是一个二项展开式，这个展开式构造一个包含C(n, m)的矩阵，
当前矩阵:| f(x) x^k x^(k-1) x^(k-2) ... 1 |,目标矩阵：|f（x+1} (x+1)^k (x+2)^k..... 1|  根据当前矩阵和目标矩阵求出状态转移矩阵。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long 
const long long mod=(1LL<<32);
struct Node
{
    LL g[55][55];
}res,ori;
LL n,k,c[55][55];
void init()
{
    c[0][0]=1;
    for(int i=1;i<=50;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
        {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}
Node mul(Node x,Node y)
{
    Node temp;
    for(int i=0;i<k+2;i++)
    {
        for(int j=0;j<k+2;j++)
        {
            temp.g[i][j]=0;
            for(int l=0;l<k+2;l++)
            temp.g[i][j]=(temp.g[i][j]+(x.g[i][l]*y.g[l][j])%mod)%mod;
        }
    }   
    return temp;
}
void sol(LL n)
{
    while(n)
    {
        if(n&1)
         ori=mul(ori,res);
        n>>=1;
        res=mul(res,res);
    }
}
int main()
{
    init();
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&k);
        memset(res.g,0,sizeof(res.g));
        memset(ori.g,0,sizeof(ori.g));
        res.g[0][0]=1;
        for(int i=0;i<k+1;i++)
         res.g[i+1][0]=c[k][i];
        for (int i = 1; i < k + 2; i++)
            for (int j = i, l = 0; j < k + 2; j++, l++)
                res.g[j][i] = c[k - i + 1][l];
        for(int i=0;i<k+2;i++)
         ori.g[0][i]=1;
        sol(n-1);
         printf("Case %d: %lld\n", cas++, ori.g[0][0]);
    }
    return 0;
}

E - Dice (I) LightOJ - 1145
题意：

有N个骰子，每个骰子有K个面，分别从1-k进行标记，求N个骰子正面朝上之和为S的情况有多少种？

解题思路：

定义dp[i][j]为前i个骰子正面朝上和为j；
状态转移方程：dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]....+dp[i-1][j-k];
这种写法的时间复杂度为：O（N*S);
因此用滚动数组进行优化得到：
dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]....+dp[i-1][j-k]
dp[i][j-1]=dp[i-1][j-2]+....dp[i-1][j-k-1];
dp[i][j]=dp[i][j-1]+dp[i-1][j-1]-dp[i-1][j-k-1];

代码：

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int mod=100000007;
long long dp[2][15010];
int main()
{
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,s;
        scanf("%d%d%d",&n,&k,&s);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=k;i++)
        dp[1][i]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=s;j++)
            {
                if(j>k)
                dp[i%2][j]=((dp[i%2][j-1]+dp[(i+1)%2][j-1]-dp[(i+1)%2][j-k-1])+mod)%mod;
                else
                dp[i%2][j]=(dp[i%2][j-1]+dp[(i+1)%2][j-1])%mod;
            }
        //  cout<<dp[i%2][0]<<endl;
        }
        printf("Case %d: %lld\n",cas++,dp[n%2][s]);
    }
    return 0;
}

F - Diablo LightOJ - 1087
题意：

有一列数，有两种操作，第一种操作是‘a p’，向末尾添加一个数p,另一个操作是向‘c k’，找出第k个数，并将其从队列中删除，并输出第k个数

解题思路：

由于此题是在区间内进行查找和删除操作，id记录的是叶子节点数的值，如果第i个叶子节点不存在，id[i]=-1,num数组记录区间内有多少个id的值不为-1.if是‘c’操作，则将查询第k个数所在的位置，根据num数组来判定。

代码：

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=200015;
int ans;
int num[maxn<<2],id[maxn<<2];
char s[10];
void build(int rt,int l,int r)
{
    id[rt]=-1,num[rt]=0;
    if(l==r)
    return ;
    int m=(l+r)>>1;
    build(2*rt,l,m);
    build(2*rt+1,m+1,r);
//  num[rt]=num[rt<<1]+num[rt<<1|1];
}
void update(int k,int x,int l,int r,int rt)
{  
    if(l==r)
    {
        id[rt]=x;
        num[rt]=1;
        return ;
    }
    int m=(l+r)>>1;
    if(k<=m)  update(k,x,l,m,rt<<1);
    else   update(k,x,m+1,r,rt<<1|1);
    num[rt]=num[rt<<1]+num[rt<<1|1];
}
void query(int k,int l,int r,int rt)
{
//  int ans;
    if(l==r)
    {
        ans=id[rt];
        id[rt]=-1;
        num[rt] = 0;
        return ;
    }
    int m=(l+r)>>1;
    if(k<=num[rt<<1]) query(k,l,m,rt<<1);
    else
    {
        k-=num[rt<<1];
        query(k,m+1,r,rt<<1|1);
    }
    num[rt]=num[rt<<1]+num[rt<<1|1];
}
int main()
{
    int t,a,b,x,n,q;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d%d",&n,&q);
        int nn=n+q;
        build(1,1,nn);
    //  cout<<nn<<endl;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            update(i,x,1,nn,1);
        }
        printf("Case %d:\n",cas);
        for(int i=0;i<q;i++)
        {
            scanf("%s%d",s,&b);
            if(s[0]=='a')
            {
                n+=1;
                update(n,b,1,nn,1);
            }
            else
            {
                query(b,1,nn,1);
                if(ans==-1) printf("none\n");
                else
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}