学步园

链接：http://acm.hdu.edu.cn/diy/contest_show.php?cid=18788

1001:

题意：算时间的问题，没什么算法。

1002：

题意：把一组数依次向后移动，并且乘以一个系数，求最后的状态。

思路：这题稍微找下规律，主要是用到__int64来存数据(我用long long居然wa了)，还有得用到快速幂，否则10^9可不好惹，这个很久没用了都忘了，这次顺便记下快速幂的模版。

代码：

#include<cstdio>
#include<iostream>
#define maxn 10005
#define ll __int64
#define modnum 1000000007
ll a[maxn];
using namespace std;
ll pow(ll k,ll t,ll b)
{
    ll ans=1;
    while(t)
    {
        if(t&1)
        {
            ans=(ans*k)%modnum;
        }
        t=t>>1;
        k=(k*k)%modnum;
    }
    return (ans*b)%modnum;
}
int main()
{
    ll n,T;
    ll t,k;
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d",&n,&t,&k);
        for(int i=0; i<n; i++)
        {
            scanf("%I64d",&a[i]);
            a[i]=pow(k,t,a[i]);
        }
        t=t%n;
        for(int i=n-t; i<n; i++)
        {
            printf("%I64d ",a[i]);
        }
        for(int i=0;i<n-t-1;i++)
        {
            printf("%I64d ",a[i]);
        }
        printf("%I64d\n",a[n-t-1]);
    }
    return 0;
}

1003

题意：数位dp暂时不懂，得补补。

思路：

找了下别人的代码：http://hi.baidu.com/chenwenwen0210/item/94fb64149dd8de433f87cef3

1004

题意：完全背包，很久没写了，这次在温习下。

代码：

#include<cstdio>
#include<cstring>
#define maxn 105
#define maxl 100005
int v[maxn],c[maxn],f[maxl];
int n,m;
int max(int x,int y)
{
    return x>y?x:y;
}
void Mback()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m;j++)//从小到大，完全背包 .从大到小，01背包
        {
            if(c[i]<=j)
            f[j]=max(f[j-c[i]]+v[i],f[j]);
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++)
        scanf("%d%d",&v[i],&c[i]);
        scanf("%d",&m);
        Mback();
        printf("%d\n",f[m]);
    }
    return 0;
}

1005

题意：典型的暴力法问题。

思路：按每件事的开始时间排序，开始时间相同的按结束时间排序。然后遍历一遍，找时间间距。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 500005
using namespace std;
struct T
{
    int st, en;
}a[maxn];
bool cmp(T x,T y)
{
    if(x.st==y.st)
    {
        return x.en<y.en;
    }
    else
    {
        return x.st<y.st;
    }
}
int main()
{
    int n,h,m;
    while(scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d:%d",&h,&m);
            a[i].st=h*60+m;
            scanf("%d:%d",&h,&m);
            a[i].en=h*60+m;
        }
        sort(a,a+n,cmp);
        int ans=0;
        int end=a[0].en;
        ans+=a[0].st;
        for(int i=1;i<n;i++)
        {
            if(a[i].st>end)
            {
                ans+=a[i].st-a[i-1].en;
                end=a[i].en;
            }
        }
        ans+=(24*60-end);
        printf("%d\n",ans);
    }
    return 0;
}