题目描述
请了两位奆老来为自己种树,小X也稍稍有些不好意思了,于是他准备了一些零食和饮料来招待奆老们。
然而,小X有强迫症,他希望自己和好基友们所有的零食和饮料的质量都要完全相同。
由于小X是一个奆老,所以他看不起普通商店里卖的电子秤,他决定自己做一个。
他的称重工具是一架由金子制成的天平,这架天平的精度非常高,可以达到纳克的标准,1g=109ng,小X会把物品放在天平的右侧,然后在天平的左侧和右侧都放上一些砝码,直至天平平衡。该天平的砝码是用钻石制成的,每个砝码的质量依次为1ng、3ng、9ng、27ng、81ng……,每个砝码的质量都是3的幂次(如3的6次幂表示为3^6=729),且各不相同。
由于小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;
小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点体力
第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,小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片红色叶子的经过每个节点的年轻程度总和最小的生成树。
注意:保证数据有解。
他准备给两位奆老中的一个人绿叶配红花,另一个人红叶配绿花。
由于绿叶配红花大家说顺口了,所以小X家楼下的花店里就有出售,但红叶配绿花是小X口味独特的体现,花店里当然是不会有的,小X只能自行拼凑。
他家种了一棵枫树,现在有的枫叶是红色的,有的枫叶是黄色的,小X只要采摘红色的枫叶。每片枫叶有一个年轻程度,他希望他采摘的枫叶的年轻程度总和越小越好。
这棵枫树有n个节点(从0开始编号),m片叶子。他希望采摘到恰好k片红色叶子的经过每个节点的年轻程度总和最小的生成树。
注意:保证数据有解。
输入
第一行三个整数n,m,k,意思如题意。
接下来m行每行4个整数x,y,z,col。表示x号节点与y号节点之间有一片年轻程度为z的叶子,它的颜色是col(设0为红色,1为黄色)
接下来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需要回答出每个暗号的答案
现在小A需要回答出每个暗号的答案
输入
第一行两个整数,表示柱子的个数n以及操作的个数m。
第二行n个整数,第i个整数表示第i根柱子的高度。
接下来m行,每行三个整数opt, x, y。当opt=1时,表示把第x根柱子的高度改为y;当opt=2时,表示询问第x到第y根柱子的高度在升序排序后是否构成一段连续且上升的序列。若是,则输出Yes,否则输出No。
第二行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
提示