多校 2013 1

首页 > 代码库 > 多校 2013 1

2024-10-19 09:53:39 207人阅读

HDU 4602

求n 的分解方式 k 出现了几次

先把 n 分解成 n个1 然后考虑 1 k 在边上 2*2^(n-k-1)

2 k 在中间左边 t1 右边t2 个1 那么就是 2^(t1-1)*2^(t2-1)*(n-k-1)

加起来就是有些特殊的判断下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include<set>
#include<deque>

using namespace std;

#define inf 1000000007
#define MAXN 100010
#define ll __int64

ll Quick(ll a,ll b,ll c)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1)
            ans=(ans*a)%c;
        b>>=1;
        a=(a*a)%c;
    }
    return ans;
}


int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,k;
        scanf("%I64d%I64d",&n,&k);
        ll ans;
        if(k>n)
            ans=0;
        else if(k==n)
            ans=1;
        else if(k==n-1)
            ans=2;
        else
            ans=(Quick(2,n-k,inf)+((n-k-1)*Quick(2,n-k-2,inf))%inf)%inf;
        printf("%I64d\n",ans);
    }
    return 0;
}

View Code

HDU 4604

n个数放到deque里面 deque 要求不递减求DQ最大长度

从后往前针对每个点求出他的最长不下降自序列最长不上升子序列

然后去一下同可以取相反数

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include<set>
#include<deque>
#include<queue>

using namespace std;

#define inf 1000000007
#define MAXN 100010
#define ll __int64

int z[MAXN];
int dp1[MAXN],dp2[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&z[i]);
        int cnt1,cnt2;
        cnt1=cnt2=0;
        int mx=0;

        for(int i=n;i>=1;i--)
        {
            int a=upper_bound(dp1,dp1+cnt1,z[i])-dp1;
            int b=lower_bound(dp1,dp1+cnt1,z[i])-dp1;
            if(a==cnt1)
                dp1[cnt1++]=z[i];
            else
                dp1[a]=z[i];
            int len1=a+1;
            int same=a-b+1;
            a=upper_bound(dp2,dp2+cnt2,-z[i])-dp2;
            b=lower_bound(dp2,dp2+cnt2,-z[i])-dp2;
            if(a==cnt2)
                dp2[cnt2++]=z[i];
            else
                dp2[a]=-z[i];
            int len2=a+1;
            same=min(same,a-b+1);
            mx=max(len1+len2-same,mx);

        }
        printf("%d\n",mx);
    }
    return 0;
}

View Code

HDU 4606

n个城市的坐标 m个障碍的坐标 p个士兵然后城市占领的顺序

士兵走路需要食物开始是满的士兵占有城市就可以充满食物然后城市不能在占有走i的路消耗i的食物

求最少的开始的食物

1 求每个点之间的距离 2 floyd 算法求最短 3 二分带的食物那么边小于食物的就可以建上去 4 最小路径覆盖

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include<set>
#include<deque>
#include<queue>

using namespace std;

#define inf 1000000007
#define MAXN 510
#define ll long long

int n,m,p;

struct point
{
    double x,y;
    point operator - (point a)const
    {
        point b;
        b.x=x-a.x;
        b.y=y-a.y;
        return  b;
    }
    double operator ^ (const point a)
    {
        return x*a.y-a.x*y;
    }
}z[1010];

struct li
{
    double x1,y1,x2,y2;
}l[1010];
double d[310][310];
int y[MAXN];

bool jud(int a,int b,int c)
{
    point cc,dd;
    cc.x=l[c].x1;
    cc.y=l[c].y1;
    dd.x=l[c].x2;
    dd.y=l[c].y2;

    if(((z[b]-z[a])^(cc-z[a]))*(((z[b]-z[a])^(dd-z[a])))<0&&(((dd-cc)^(z[a]-cc))*(((dd-cc)^(z[b]-cc))))<0)
        return 1;
    return 0;
}
double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int head[MAXN],cnt,fa[MAXN];
bool vis[MAXN];
struct node
{
    int v,next;
}edge[MAXN*MAXN];

void add(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
bool dfs(int u)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(vis[v]==1)
            continue;
        if(fa[v]==-1)
        {
            fa[v]=u;
            return 1;
        }
        vis[v]=1;
        if(dfs(fa[v]))
        {
            fa[v]=u;
            return 1;
        }
    }
    return 0;
}
int deal()
{
    int ans=0;
    memset(fa,-1,sizeof(fa));
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            ans++;
    }
    return ans;
}
bool check(double a)
{
    cnt=0;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(d[y[i]][y[j]]<=a)
                add(y[i],y[j]+n);
        }
    }
    return n-deal()<=p;
}
void solve()
{
    double l=0,r=inf;
    for(int i=0;i<=50;i++)
    {
        double mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else
            l=mid;
    }
    printf("%.2lf\n",l);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&p);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&z[i].x,&z[i].y);
        for(int i=1;i<=m;i++)
        {
            scanf("%lf%lf%lf%lf",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
            z[n+i*2-1].x=l[i].x1;
            z[n+i*2-1].y=l[i].y1;
            z[n+i*2].x=l[i].x2;
            z[n+i*2].y=l[i].y2;
        }
        memset(d,0,sizeof(d));
        for(int i=1;i<=n+m*2;i++)
        {
            for(int j=1;j<=n+m*2;j++)
            {
                if(i==j)
                    d[i][j]=0;
                else
                {
                    int ok=0;

                    for(int k=1;k<=m;k++)
                    {
                       // printf("%d %d %d %d\n",i,j,k,jud(i,j,k));
                        if(jud(i,j,k))
                         {
                             ok=1;
                             break;
                         }
                    }
                    if(ok==1)
                        d[i][j]=d[j][i]=inf;
                    else
                        d[i][j]=d[j][i]=dis(z[i].x,z[i].y,z[j].x,z[j].y);
                }

            }
        }
        for(int k=1;k<=n+m*2;k++)
        {
            for(int i=1;i<=n+m*2;i++)
            {
                for(int j=1;j<=n+m*2;j++)
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&y[i]);
        solve();

    }
    return 0;
}

View Code

HDU 4607

一棵树边 1 查询访问 k 个定点要最少走多少路

求树上最长链长度len 1 k<len+1 那么就是 k-1

2 画个图 len+2*(k-(len+1)) 后面那一半就是个来回

dfs 或者bfs

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include<set>
#include<deque>
#include<queue>

using namespace std;

#define inf 1000000007
#define MAXN 100010
#define ll __int64

struct node
{
    int to,next;
}edge[MAXN<<1];

int head[MAXN],cnt,d[MAXN];
void add(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
queue<int>q1;
bool vis[MAXN];
int n,m,mx1;

int bfs(int s)
{
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    q1.push(s);
    vis[s]=1;
    while(!q1.empty())
    {
        int now=q1.front();
        q1.pop();
        for(int i=head[now];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(!vis[v])
            {
                d[v]=d[now]+1;
                q1.push(v);
                vis[v]=1;
            }
        }
    }
    int mx,dis;
    dis=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>dis)
        {
            dis=d[i];
            mx=i;
            mx1=dis;
        }
    }
    return mx;
}
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        cnt=0;
        mx1=0;
        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        int a=bfs(1);
        a=bfs(a);
        while(m--)
        {
            int a;
            scanf("%d",&a);
            if(a<=mx1+1)
                printf("%d\n",a-1);
            else
                printf("%d\n",mx1+(a-(mx1+1))*2);
        }
    }
    return 0;
}

View Code

HDU 4608

+1 大数模拟下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include<set>
#include<deque>

using namespace std;

#define inf 1000000007
#define MAXN 100010
#define ll __int64

char s[MAXN];
int  z[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        int len=strlen(s);
        memset(z,0,sizeof(z));
        for(int i=len-1,j=0;i>=0;j++,i--)
            z[j]=s[i]-‘0‘;
        while(1)
        {
            z[0]++;
            for(int i=0;i<len;i++)
            {
                if(z[i]>9)
                {
                    z[i]=0;
                    z[i+1]++;
                }
            }
            if(z[len]>0)
                len++;
            int sum=0;
            for(int i=0;i<len;i++)
                sum=sum+z[i];
            if(sum%10==0)
                break;
        }
        for(int i=len-1;i>=0;i--)
            printf("%d",z[i]);
        printf("\n");
    }

    return 0;
}

View Code

多校 2013 1

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 多校 2013 1

多校 2013 1

看完仍有疑问？有类似问题直接问程序猿