NO.1
题目描述:一个十进制整数被叫做权势二进制,当他的十进制表示的时候只由0或1组成。当给定一个n的时候,计算一下最少要多少个权势二进制相加才能得到n。
思路:贪心
因为每一位最多为1,所以就求出最大的数字(每个位置上)代码:
var i,k,n,l,x,j:longint; s:string;begin assign(input,'a.in'); assign(output,'a.out'); reset(input); rewrite(output); readln(k); for i:=1 to k do begin readln(n); l:=0; while n>0 do begin x:=0; inc(l); str(n,s); for j:=1 to length(s) do if (s[j]='1')or(s[j]='0') then begin x:=x*10+ord(s[j])-48; end else x:=x*10+1; n:=n-x; end; writeln(l); end; close(input); close(output);end.
NO.2
题目描述: KC邀请他的两个小弟K和C玩起了数字游戏。游戏是K和C轮流操作进行的,K为先手。KC会先给定一个数字Q,每次操作玩家必须写出当前数字的一个因数来代替当前数字,但是这个因数不能是1和它本身。例如当前数字为6,那么可以用2,3来代替,但是1和6就不行。现在规定第一个没有数字可以写出的玩家为胜者。K在已知Q的情况,想知道自己作为先手能不能胜利,若能胜利,那么第一次写出的可以制胜的最小数字是多少呢?整个游戏过程我们认为K和C用的都是最优策略。
思路:数学
求出q的质因数的个数 这道题分为三种情况: 1:n为质数,writeln(1); write(0); 2:n为两个质数的乘积(两个质数可以相等),write(2) 3:n很复杂,则输出n最小的两个质因数(可以相等,即n=k*t*t, t为此质因数)的积代码:
#include#include using namespace std;long long x,q;int l=0;int main(){ freopen("num.in","r",stdin); freopen("num.out","w",stdout); scanf("%lld",&q); x=q; for (int i=2;i<=trunc(sqrt(q-0.1));i++) while (q%i==0) l++,q=q/i; if (trunc(sqrt(q))==sqrt(q)) l++; q=x; if (l==0) printf("1\n0"); else if (l==1) printf("2"); else { x=1; printf("1\n"); for (int i=2;i<=trunc(sqrt(q));i++) while (q%i==0) { x=x*i; q=q/i; if (x!=i) { printf("%lld",x); fclose(stdin); fclose(stdout); return 0; } } } fclose(stdin); fclose(stdout); return 0;}
NO.3
题目描述:这n个山峰在一条直线上,每个山峰都有不同的高度,只知道这些山峰的相对位置。霍普可以将这些山峰左右移动但不能改变他们的相对位置(要保证两两山峰间距为整数且大于等于1)。霍普要从最矮的山峰开始跳,每次跳向第一个比现在她所在的山峰高的山峰,一共跳n-1次,由于能力有限,每次跳跃的水平距离小于等于d。
霍普想知道如何移动这些山峰,使得在可以经过所有的山峰并跳到最高的山峰上的基础下,又要使最矮的山峰和最高的山峰的水平距离最远,霍普要你求出最远的水平距离。如果无论如何也不能经过所有的山峰并跳到最高的山峰上,那么输出-1。思路:最短路(SPFA)+排序
1、两个山峰之间水平距离至少为1(因为山峰不能再同一位置上)。 2、霍普每次最多跳d的水平距离。 对于第一个条件,对于两个相邻的山峰,相对位置(即输入顺序)大的向相对位置小的连一条-1的边。 对于第二个条件,对于两个高度排名相邻的山峰,相对位置小的向相对位置大的连一条d的边。 然后比较最高和最低的山峰,从相对位置小的那个山峰出发,跑一遍SPFA最短路,输出到相对位置大的山峰的距离。代码:
#include#include #include #include #define fo(i,x,y) for(int i=x;i<=y;i++)using namespace std;struct A{ int x,y;};int map[5010][2],last[1010],t[5010],n,m,dis[1010],dt[10000010],len,aa,bj[1010];A a[1010];bool bz[1010];bool cmp(A x,A y){ if(x.x dis[x]+map[c][0]) { dis[map[c][1]]=dis[x]+map[c][0]; bj[map[c][1]]++; if(bj[map[c][1]]<1000) if(!bz[map[c][1]]) { bz[map[c][1]]=true; dt[++en]=map[c][1]; } } c=t[c]; } bz[x]=false; }}int main(){ freopen("attack.in","r",stdin); freopen("attack.out","w",stdout); int tt; scanf("%d",&tt); fo(p,1,tt) { memset(t,0,sizeof(t));memset(last,0,sizeof(last)); memset(map,0,sizeof(map));len=0; memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); fo(i,1,n) { scanf("%d",&a[i].x);a[i].y=i; if(i!=1)add(i,i-1,-1); } sort(a+1,a+n+1,cmp); fo(i,2,n) if(a[i].y
NO.4
题目描述: “尼伯龙根是一棵由n-1条高架路连起n 个地区的树,每一次Load,你都会重生在某一个地区。如果重生点是整个尼伯龙根的重心,也就是这个树的重心,那么你就能在最短时间内带诺诺逃脱啦。”
“对了,再给你一点方便咯,你可以选一条高架桥断掉,再连接另外两个地方,每次Load只能用一次技能,而又必须使整个它仍构成树形结构。你的Save点在这里,Load自然会恢复原始的尼伯龙根咯。”思路:未写出,dalao说这题是提高+/省选
找到树的重心,询问x个点,去掉任意一条边,又连上任意两点,求出它能否成为树的重心 就可以找出重心的最大和次大子树,如果i在最大子树上,就将次大子树连上x,不然就将最大子树连上x,在判断这个点是否符合重心