题目描述

请了两位奆老来为自己种树,小X也稍稍有些不好意思了,于是他准备了一些零食和饮料来招待奆老们。
然而,小X有强迫症,他希望自己和好基友们所有的零食和饮料的质量都要完全相同。
由于小X是一个奆老,所以他看不起普通商店里卖的电子秤,他决定自己做一个。
他的称重工具是一架由金子制成的天平,这架天平的精度非常高,可以达到纳克的标准,1g=109ng,小X会把物品放在天平的右侧,然后在天平的左侧和右侧都放上一些砝码,直至天平平衡。该天平的砝码是用钻石制成的,每个砝码的质量依次为1ng、3ng、9ng、27ng、81ng……,每个砝码的质量都是3的幂次(如3的6次幂表示为3^6=729),且各不相同。
由于小X是一个奆老,他有对各个物品未卜先知的能力,他会告诉你他的物品的质量,希望你给他一个方案,使得天平的两侧平衡。

输入

输入数据仅有一行包含一个正整数W,表示小X给出的物品的质量,重量单位是纳克(ng)

输出

输出数据共有两行,分别输出左右两端各个砝码及物体的质量,同一行砝码重量必须从小到大排序后按次序输出,第二行的第一个数必须先输出物体的质量,然后才是各个砝码的重量。相邻两个数之间必须严格用一个空格隔开。
注意:输入数据保证一定有解!如有多组解,输出任意一组即可!

样例输入

67

样例输出

1 3 9 81
67 27

提示

小X给出的物品的质量为67pg,你可以在天平的左边放上4个砝码,重量依次为1,3,9,81总重量94ng,而右边放一个砝码质量为27ng,加上物体的重量67ng,恰好也是94ng,满足题目要求,此时天平的左右两端平衡。

对于20%的数据,W<=100
对于另外20%的数据,W<=10000,最多只用到5个砝码
对于另外20%的数据,W<=1000000,所有砝码都放在左边
对于另外20%的数据,W<=1000000
对于100%的数据,W<=1015。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll w,ww,kk=1,k,m,n,a[10000],b[10000],f[10000];
inline ll read()
{
    ll res=0,f=1;
    char ch=getchar();
    while (!isdigit(ch))
    {
        if (ch=='-')
        {
            f=-f;
        }
        ch=getchar();
    }
    while (isdigit(ch))
    {
        res=(res<<3)+(res<<1)+ch-'0';
        ch=getchar();
    }
    return f*res;
}
int main()
{
    w=read();
    ww=w;
    while (ww)
    {
        f[++k]=ww%3;
        ww/=3;
    }
    for (int i=1; i<=k+1; i++)
    {
        if (f[i]==1)
        {
            if (a[n]==kk)
            {
                a[n]=kk*3;
                b[++m]=kk;
            }
            else
            {
                a[++n]=kk;
            }
        }
        if (f[i]==2)
        {
            if (a[n]==kk)
                a[n]=kk*3;
            else
            {
                a[++n]=kk*3;
                b[++m]=kk;
            }
        }
        kk*=3;
    }
    for (int i=1; i<=n; i++)
    {
        printf("%lld",a[i]);
        if (i!=n)
            printf(" ");
        else
            printf("\n");
    }
    printf("%lld",w);
    for (int i=1; i<=m; i++)
    {
        printf(" %lld",b[i]);
    }
    printf("\n");
    return 0;
}

题目描述

由于小X是一位奆老,奆老总是忙得一刻也停不下来。他刚刚准备完食物,小X童年的挚友小S和小Z来找他帮忙了……
小S和小Z十分喜欢看网络写手“25”的小说,但由于需要付费才能阅读,而小S和小Z的零花钱有非常少,他们只能找小X靠黑科技侵入给网站,把小说给他们。
然而小X又非常的爱慕虚荣,他要小S和小Z到自己家里来取小说。
小S、小Z和小X都居住在扬中市,扬中市共有n个小区,m条主干道(假设每条主干道都是双行线)。小S家住在1号小区,小X家住在n号小区。小S每经过一条主干道需要耗费z点体力,但由于小S的人脉非常广,每当他到达一个小区,他都会和好友攀谈直到体力回满。
由于小Z也希望能看到小说,所以他答应帮助小S k次,这k次小S经过主干道不需要耗费体力。
由于小S生性懒惰,他希望耗费最少的体力到达小X家,请问他最少耗费多少体力?
注意:如果小S到小X家可以一路上都由小Z背着,那么体力上限为0;
如果小S到不了小X家,小S会很伤心,体力上限为-1;

输入

第1行三个整数n,m,k,意思如题目描述。
第2到第n+1行是x,y,z指走连接x号小区和y号小区的主干道要耗费z点体力

输出

一行一个整数,表示小S最少耗费的体力。

样例输入

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

样例输出

4

提示

小S的行走路线:1->3->2->5,其中2->5这条主干道由小Z帮助小S通过。

对于30%的数据:n<=20;m<=100;
对于60%的数据:n<=100;m<=1000;
对于100%的数据:n<=1000;m<=10000;z<=1000000;

#include <bits/stdc++.h>

using namespace std;
const int maxn=21000;
struct node
{
    int v,nxt,w;
} e[maxn];
int n,k,t,head[maxn],vis[maxn],d[maxn],m;

void add(int u,int v,int w)
{
    t++;
    e[t].v=v;
    e[t].w=w;
    e[t].nxt=head[u];
    head[u]=t;
}

bool check(int mid)
{
    memset(vis,0,sizeof(vis));
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    q.push(make_pair(d[1],1));
    while (!q.empty())
    {
        int u=q.top().second;
        q.pop();
        vis[u]=1;
        for (int i=head[u]; i; i=e[i].nxt)
        {
            int v=e[i].v,w=d[u];
            if (vis[v])
                continue;
            if (e[i].w>=mid)
                w++;
            if (d[v]>w)
            {
                d[v]=w;
                q.push(make_pair(d[v],v));
            }
        }
    }
    return d[n]>=k+1;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1,u,v,w; i<=m; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    int l=0,r=1e6+100,ans=-1;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else
            r=mid-1;
    }
    if (ans>1e6)
        printf("-1\n");
    else if (r<0)
        printf("0\n");
    else
        printf("%d",ans);
    return 0;
}

  

题目描述

近日,清华大学挖出来一个明清古墓。小A决定冒充考古系科研人员去盗墓。他遇到的第一个难关是来自校门口保安的质疑,因为小没有清华学生证,所以保安决定通过问问题的方式验证小A的身份。

保安会说出两个整数n和k,小A需要回答的阶乘在进制下末尾零的个数。

输入

一行两个整数,表示n和k。

输出

一个整数表示n的阶乘在k进制下末尾零的个数。

样例输入

10 40

样例输出

2

提示

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll ans=0x3f3f3f3f3f3f3f3f,n,k,tot,a[100000],b[10000],c[10000],f;

inline ll read()
{
    ll res=0,f=1;
    char ch=getchar();
    while (!isdigit(ch))
    {
        if (ch=='-')
        {
            f=-f;
        }
        ch=getchar();
    }
    while (isdigit(ch))
    {
        res=(res<<3)+(res<<1)+ch-'0';
        ch=getchar();
    }
    return f*res;
}
int main()
{
    n=read();
    k=read();
    ll kk=sqrt(k);
    for (ll i=2; i<=kk; i++)
    {
        if (k%i==0)
        {
            tot++;
            a[tot]=i;
            while (k%i==0)
            {
                b[tot]++;
                k/=i;
            }
        }
    }
    if (k>1)
    {
        tot++;
        a[tot]=k;
        b[tot]++;
    }
    for (int i=1; i<=tot; i++)
    {
        ll nn=n,aa=a[i];
        while (nn>=aa)
        {
            c[i]+=nn/aa;
            f=1;
            nn/=aa;
        }
    }
    if (tot==0||f==0)
    {
        printf("0\n");
        return 0;
    }
    for (int i=1; i<=tot; i++)
    {
        ans=min(ans,c[i]/b[i]);
    }
    printf("%lld\n",ans);
}

题目描述

招待完奆老后,小X准备送几片叶子和几朵花给奆老们作为感谢和礼物。
他准备给两位奆老中的一个人绿叶配红花,另一个人红叶配绿花。
由于绿叶配红花大家说顺口了,所以小X家楼下的花店里就有出售,但红叶配绿花是小X口味独特的体现,花店里当然是不会有的,小X只能自行拼凑。
他家种了一棵枫树,现在有的枫叶是红色的,有的枫叶是黄色的,小X只要采摘红色的枫叶。每片枫叶有一个年轻程度,他希望他采摘的枫叶的年轻程度总和越小越好。
这棵枫树有n个节点(从0开始编号),m片叶子。他希望采摘到恰好k片红色叶子的经过每个节点的年轻程度总和最小的生成树。
注意:保证数据有解。

输入

第一行三个整数n,m,k,意思如题意。
接下来m行每行4个整数x,y,z,col。表示x号节点与y号节点之间有一片年轻程度为z的叶子,它的颜色是col(设0为红色,1为黄色)

输出

一行一个整数表示所求年轻程度总和最小的生成树。

样例输入

2 2 1
0 1 1 1
0 1 2 0

样例输出

2

提示

 

题目描述

小A终于通过了保安的考验,来到了古墓门前,古墓门前有n根柱子,第i根柱子的高度是整数。古墓的门上会弹出一些暗号,机智小A猜到这个暗号表示询问第l到第r根柱子的高度在升序排序后是否构成一段连续且上升的序列。并且这些柱子的高度还可能在弹出暗号的过程中出现变化。

现在小A需要回答出每个暗号的答案

输入

第一行两个整数,表示柱子的个数n以及操作的个数m。

第二行n个整数,第i个整数表示第i根柱子的高度。

接下来m行,每行三个整数opt, x, y。当opt=1时,表示把第x根柱子的高度改为y;当opt=2时,表示询问第x到第y根柱子的高度在升序排序后是否构成一段连续且上升的序列。若是,则输出Yes,否则输出No。

输出

对于每个询问输出一行Yes或No。

样例输入

5 5
1 2 3 4 5
2 1 5
2 2 3
2 3 3
1 3 6
2 3 5

样例输出

Yes
Yes
Yes
Yes

提示

  

01-15 11:05