|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 |
题1 高低位交换【问题描述】 给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。 例如，数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。【输入数据】 读入一个小于2^32的正整数。【输出数据】 新的数。【样例输入】1314520【样例输出】249036820 |
T1：纯模拟
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 |
#include<cstdio>#include<cstring>using
namespace std;int f[33],n,a[33],i=1;long
long ans=1,sum=0;void
exchange(int
x){ int
r; while(x>0){ r=x%2; x/=2; f[i]=r; i++; }}void
change(){ for(int
x=1;x<=32;x++){ if(a[x]==1) sum+=ans;ans*=2; }}int
main(){ freopen("swap.in","r",stdin); freopen("swap.out","w",stdout); memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); scanf("%d",&n); exchange(n); for(int
j=16;j>0;j--){ a[j]=f[j+16]; a[j+16]=f[j]; } change(); printf("%lld",sum); return
0;} |
T2：
|
1
2
3
4
5
6
7
8
9
10
11
12
13 |
题2数列排序【问题描述】 给定一个数列{an}，这个数列满足ai≠aj(i≠j)，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？【输入格式】 第一行，正整数n (n<=100,000)。 以下若干行，一共n个数，用空格分隔开，表示数列{an},任意-231<ai<231。【输出格式】 只有一行，包含一个数，表示最少的交换次数。【输入样例】 8 8 23 4 16 77 -5 53 100【输出样例】 5 |
写这一题收获还是不少的，首先依旧表示自己打的题太少了，这样类型的题目没有碰到过40都看不下去了....TAT..
这是一题图论题，要找环
就比如
4
3 7 6 1
你sort一下，排好正确的顺序
1 3 6 7
发现，原序列的3应该和7交换，而7应该和1交换，1应该和3交换；
那么就恭喜你找到了最少的交换次数，2次，这也就是说找环的次数就为最少交换的次数；
ps:这里说一下自己年轻的地方：
1.交换过得数记得mark
2.刚开始超级年轻的这样记录每一个数正确的位置：
d[a[i]]=i;
之后崩溃掉了，喜闻乐见。
一直忘了数组的序号是不能为负的，逗了....这里用自定义即可；
TAT...程序放在机房了，改天附上吧
T3：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 |
题3 路标设置【问题描述】 B市和T市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。 请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。【输入格式】 第1行包括三个数L、N、K，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。 第2行包括递增排列的N个整数，分别表示原有的N个路标的位置。路标的位置用距起点的距离表示，且一定位于区间[0,L]内。【输出格式】 输出1行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。【输入样例】road.in 101 2 1 0 101【输出样例】road.out 51【样例说明】 公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点50或51个单位距离处，这样能达到最小的空旷指数51。【数据规模与约定】 50%的数据中，2 ≤ N ≤100，0 ≤K ≤100 100%的数据中，2 ≤N ≤100000, 0 ≤K ≤100000 100%的数据中，0 ＜ L ≤10000000 |
二分答案即可...
=-=还是很不熟练啊...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 |
#include<cstdio>#include<cstring>using
namespace std;int a[100001],l,n,k,d=0;int judge(int
x){ int
now=0; for(int
i=1;i<n;i++){ if(a[i]%x==0) now+=a[i]/x-1; else
now+=a[i]/x; } if(now<=k) return
1; else
return 0;}int
main(){ freopen("road.in","r",stdin); freopen("road.out","w",stdout); scanf("%d%d%d",&l,&n,&k); scanf("%d",&a[1]); for(int
i=2;i<=n;i++){ scanf("%d",&a[i]); } for(int
i=1;i<n;i++) a[i]=a[i+1]-a[i]; int
ll=1,r=l,t,mid; while(ll!=r){ mid=(r+ll)>>1; if(judge(mid)) r=mid; else
ll=mid+1; } printf("%d",ll); return
0;} |
T4树形DP,想之后单独附上
原文：http://www.cnblogs.com/polebug/p/3736007.html