首页 > 代码库 > 小测(noip2005的两道题) 2017.3.3
小测(noip2005的两道题) 2017.3.3
过河
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
输入第一行有一个正整数L（1<=L<=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。
10
2 3 5
2 3 5 6 7
2
对于30%的数据，L<=10000；
对于全部的数据，L<=109。
对于全部的数据范围直接dp都只能叫暴力，由于只有100个石子，每次跳的长度又只有10，于是便可以考虑一下压缩一下没有石子的部分。
一个没有什么可以质疑的结论是，当存在某一段，长度为s，且这一段每一个点都能被青蛙跳到（对于这中间的每个点往后跳s个点，就是下一段了），那么考虑最令人厌恶的周期，当t和(t - 1)只有这两种长度的时候（因为对于其他任意两种长度会更早地开始每个点都可以被跳到），在[t(t-1)-s + 1]到t(t-1)这一段上，每一点都能被跳到了，这后面的点都等于废掉了，于是当两个石头之间的距离大于t(t-1)时，就直接改成t(t-1)好了。为了简便，下面的代码判断的是它是否大于100。
另外，特判s == t的情况。
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 #include<cstdlib> 6 #include<fstream> 7 #include<sstream> 8 #include<algorithm> 9 #include<map>10 #include<set>11 #include<queue>12 #include<vector>13 #include<stack>14 using namespace std;15 typedef bool boolean;16 #define INF 0xfffffff17 #define smin(a, b) a = min(a, b)18 #define smax(a, b) a = max(a, b)19 20 ifstream fin("river.in");21 ofstream fout("river.out");22 23 int M, L;24 int l, r;25 int* d;26 int* s;27 int* f;28 29 inline void init() {30 fin >> L;31 fin >> l >> r >> M;32 d = new int[(const int)(M + 1)];33 for(int i = 1; i <= M; i++)34 fin >> d[i];35 sort(d + 1, d + M + 1);36 }37 38 inline void solve() {39 if(l == r) {40 int res = 0;41 for(int i = 1; i <= M; i++) {42 if(d[i] % l == 0)43 res++;44 }45 fout << res;46 return;47 }48 s = new int[(const int)(M * 100 + 5)];49 memset(s, 0, sizeof(int) * (M * 100 + 5));50 d[0] = 0;51 int newd = 0;52 for(int i = 1; i <= M; i++) {53 if(d[i] - d[i - 1] > 100)54 newd += 100;55 else newd += d[i] - d[i - 1];56 s[newd]++;57 }58 f = new int[(const int)(newd + 1 + r)];59 memset(f, 0x3f, sizeof(int) * (newd + 1 + r));60 f[0] = 0;61 for(int i = 0; i <= newd; i++) {62 if(f[i] > M) continue;63 for(int j = l; j <= r; j++)64 smin(f[i + j], f[i] + s[i + j]);65 }66 int res = M;67 for(int i = newd; i <= newd + r; i++)68 if(f[i] >= 0)69 smin(res, f[i]);70 fout << res;71 }72 73 int main() {74 init();75 solve();76 return 0;77 }
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：
(b1,b2,...bm-1,bm)
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？
输入第一行是一个整数n（3<=n<=50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。
这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。
4
3 4
4 3
1 2
1 2
2
【数据规模】
对于30%的数据，n<=1000；
对于全部的数据，n<=50000。
因为这是一个环，所以可以剖环成链，因为剖开点不一样，就会导致结果不一样，所以正着反着每个地方都去剖一次。
接下来是考虑如何快速地求解需要付出的代价。这个代价等于所有在它不该在的位置的数量。
这个结论可以这么来说明，对于一个在它不该在的位置的i，那么必定存在它占掉另一个的位置且另一个占掉了它的位置，当按照这个关系连接起来就等于一个环，刚好可以按照题目中的变换方式(旋转这个环)，把环上的数变到它应该在的位置。
但是这么做仍然会超时，所以得继续考虑优化。对于改变剖开点的位置，我们规定每次改变把剖开点向前挪动一次，那么我们可以记录每个位置上的数，离它第一次回到自己正确位置上需要挪动剖开点多少次，然后就找个最大值，然后用n一减就可以出结果。
注意判断是否可以满足所有需求。主要的原因是:a希望坐在b，c旁边，但是b,c中有人不是最希望坐在a的旁边。
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 #include<cstdlib> 6 #include<fstream> 7 #include<sstream> 8 #include<algorithm> 9 #include<map> 10 #include<set> 11 #include<queue> 12 #include<vector> 13 #include<stack> 14 using namespace std; 15 typedef bool boolean; 16 #define INF 0xfffffff 17 #define smin(a, b) a = min(a, b) 18 #define smax(a, b) a = max(a, b) 19 20 template<typename T>class Matrix{ 21 public: 22 T *p; 23 int lines; 24 int rows; 25 Matrix():p(NULL){ } 26 Matrix(int rows, int lines):lines(lines), rows(rows){ 27 p = new T[(lines * rows)]; 28 } 29 T* operator [](int pos){ 30 return (p + pos * lines); 31 } 32 }; 33 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows) 34 35 ifstream fin("fire.in"); 36 ofstream fout("fire.out"); 37 38 int n; 39 Matrix<int> sit; 40 int* exist; 41 42 inline void init() { 43 fin >> n; 44 sit = Matrix<int>(n + 1, 2); 45 exist = new int[(const int)(n + 1)]; 46 memset(exist, 0, sizeof(int) * (n + 1)); 47 for(int i = 1; i <= n; i++) { 48 fin >> sit[i][0] >> sit[i][1]; 49 for(int j = 0; j < 2; j++) { 50 exist[sit[i][j]]++; 51 if(exist[sit[i][j]] > 2 || sit[i][j] == i) { 52 fout << "-1"; 53 exit(0); 54 } 55 } 56 } 57 for(int i = 1, c; i <= n; i++) { 58 for(int j = 0; j < 2; j++) { 59 c = sit[i][j]; 60 if(sit[c][0] != i && sit[c][1] != i) { 61 fout << "-1"; 62 exit(0); 63 } 64 } 65 } 66 } 67 68 int myabs(int x) { return (x < 0) ? (x + n) : (x); } 69 70 int* list; 71 int* round; 72 73 int calc(int x) { 74 list[1] = 1; 75 list[2] = sit[1][x]; 76 int last = list[2]; 77 memset(round, 0, sizeof(int) * (n + 1)); 78 round[0]++, round[myabs(2 - last)]++; 79 int ret = max(round[0], round[myabs(2 - last)]); 80 for(int i = 3, j; i <= n; i++) { 81 if(sit[last][0] == list[i - 2]) 82 list[i] = sit[last][1]; 83 else list[i] = sit[last][0]; 84 last = list[i]; 85 j = myabs(i - last); 86 round[j]++; 87 smax(ret, round[j]); 88 } 89 return ret; 90 } 91 92 int res = INF; 93 inline void solve() { 94 list = new int[(const int)(n + 1)]; 95 round = new int[(const int)(n + 1)]; 96 for(int i = 0, a; i < 2; i++) { 97 a = calc(i); 98 smin(res, n - a); 99 }100 fout << res;101 }102 103 int main() {104 init();105 solve();106 return 0;107 }
小测(noip2005的两道题) 2017.3.3