分类： 技术

这题网上没找到较好的算法（数学方法），只好自己写暴力版本的了。。。这题真的不好做什么报告，提交就是。

#include <stdio.h>

int main(void)
{
 double n;
 int i;
 double ans = 0;
 scanf(%lf, &n);
 for(i = 1; ans <= n; i++){
 ans += (double)1.0 / i;
 }
 printf(%d\\n, i - 1);
 return 0;
}

看到这个题目，不知道怎么做，到网上搜了下最小公倍数和最大公约数之间的公式，就找到了思路，p q = x0 y0..那么我就枚举所有的p，然后求出q，再判断之间的最大公约数是不是x0，就Ok了。

#include <stdio.h>

int gcd(int x, int y)
{
 int t;
 while(y > 0){
 t = x % y;
 x = y;
 y = t;
 }
 return x;
}

int main(void)
{
 int i, ans = 0; //忘记初始化了... 
 int x, y, t, s;
 scanf(%d%d, &x, &y);
 t = x * y;
 for(i = x; i <= y; i += x){
 s = t / i;
 if((s * i == t) && (gcd(s, i) == x)){
 ans++;
 }
 }
 printf(%d\\n, ans);
 return 0;
}

什么都不说了，简单的DP，直接上代码。
唯一注意的一点，我不是用的剩余做DP值，而是和普通的DP一样，最后再用总质量剪掉这个DP值。

C语言:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))

int f[20001];

int main(void)
{
 int i, j, t;
 int v, m;
 scanf(%d%d, &v, &m);
 for(i = 0; i < m; i++){
 scanf(%d, &t);
 for(j = v; j >= t; j--){
 f[j] = max(f[j], f[j - t] + t);
 }
 }
 printf(%d\\n, v - f[v]);
 return 0;
}

在车上想了好久，终于找到了突破口，后序遍历不就是说最后一个节点就是当前书的根节点吗？那不就好说了，先把后序中的最后一个节点在中序中找到下标i，那小于i的便是左子树了，大于的的便是右子树了，而题目要的是先序，那就先把第i个（即后序的最后一个）输出来，然后再分别对左子树和右子树进行递归，然后后序从0~i-1都是左子树，后序i~len – i – 1（len是树的长度）是右子树。
现在解释一下，0~i-1是后序的长度的原因是无论是先序还是后序还是中序都是同一棵树，长度必然相同，现在把一棵树分成了两棵树，长度一定还是相同的，所以这是可以成立的。
然后别的什么我不说了，祝大家细心一点，这题我提交了n次才AC（哪里错了注释在里面的）。。

C语言:

#include <stdio.h>
char mid[90];
char last[90];
char first[90];

void srch(int start, int len, int start2)
/* 第一个参数代表中序中的开头位置, len代表长度, start2 代表后序开头的位置 */
{
 int i;
 if(len <= 0){ //掉了....=_=||| 
 return ;
 }
 printf(%c, last[start2 + len - 1]);
 for(i = 0; i < len; i++){
 if(mid[i + start] == last[start2 + len - 1]){
 break;
 }
 }
 srch(start, i, start2);
 srch(i + 1 + start, len - i - 1, i + start2);
 /* 巨大的错误, 第一个参数忘记加start了, 第三个参数忘记加start2了 */
}

int main(void)
{
 scanf(%s %s, mid, last);
 srch(0, strlen(mid), 0);
 printf(\\n);
 return 0;
}

刚看到题目被吓到了，下面有一个Hit（提示），说用高精度，高精度我以前写过一次，几乎忘干净了……后来琢磨了好久，发现能够使用动态规划，注意观察一下样例，输入是6，共有：
6
16
26
126
36
136
设f[i]是以自然数i在最左边的个数，那么很容易发现方程f[i] = f[1] + f[2] + f[3] + …. + f[i/2] + 1;于是就产生了下面的代码：

C语言:

#include <stdio.h>
unsigned f[1001];

int main(void)
{
 int n;
 int i, j;
 scanf(%d, &n);
 for(i = 1; i <= n; i++){
 f[i] = 1;
 for(j = 1; j <= i / 2; j++){
 f[i] += f[j];
 }
 }
 printf(%u\\n, f[n]);
 return 0;
}

有更好的算法的高手请留个言，我在不断学习中。。

哈，这题拿到手时刚开始不知道怎么开始，后来找到了突破点，用f[i][j]记录第i个字符串和第j个字符串重复的字符数，就是说把第i个字符串和第j个字符串之间接起来重合的字符数目。
把这个处理好了就好下手了，不过这里我忽略了两点，导致提交了几次。第一点f[i][j]中的i,j可以重复！也就是说自己可以接在自己后面，再一个就是记录f[i][j]的时候要注意，从字符串的后面开始搜索，这两点弄了我半个小时到一个小时的时间，具体代码如下。

C语言:

#include <stdio.h>
#include <string.h>
int n;
char str[20][101];
int len[20];
int f[20][20];
int ans = 0;
char used[20];

void srch(int now, int length)
{
 int i;
 if(ans < length){
 ans = length; //是等于而不是加等 
 }
 used[now]++;
 for(i = 0; i < n; i++){
 if((used[i] < 2) && (f[now][i] > 0)){
 srch(i, length + len[i] - f[now][i]);
 }
 }
 used[now]--;
}

int check(int x, int y)
{
 char *a = str[x], *b = str[y];
 char *t = str[x] + len[x] - 1;
 while(t != a){
 if(*t == b[0]){ //要从后面往前面搜, 我是从前面往后面搜的.. 
 if(strncmp(t, str[y], len[x] - (t - a)) == 0){
 if(t != a){
 return (len[x] - (t - a));
 }
 }
 }
 t--;
 }

 return 0;
}

int main(void)
{
 int i, j;
 int ch;
 scanf(%d\\n, &n);
 for(i = 0; i < n; i++){
 scanf(%s\\n, str[i]);
 len[i] = strlen(str[i]);
 }

 for(i = 0; i < n; i++){
 for(j = 0; j < n; j++){ //我本来是i,j 相等就continue;了, 结果发现还是要 
 f[i][j] = check(i, j);
 }
 }

 ch = getchar();
 for(i = 0; i < n; i++){
 if(str[i][0] == ch){
 srch(i, len[i]);
 }
 }
 printf(%d\\n, ans);
 return 0;
}

自认为本程序效率不错，望高手指出可改进之处。

拿到题目就想到是一个深搜的题目（可能有其他更快的算法，比如什么用数学解的啊，那种。），便开始下手，对所有的情况进行枚举，算出乘值，与ans变量进行比较，比ans大就覆盖ans，否则继续枚举下一种情况，直至全部枚举完。结果忘记考虑会分成0的情况，导致被除数为0！（所以还是提交了两次，）

等下我还到网上搜搜看有没有什么高效率的算法，我的代码如下：

C语言:

#include <stdio.h>
int n, k;
char str[41];
int tmp = 1, ans = 0;

void srch(int now, int count, int sum)
{
 if(now == n || count == k){
 int i;
 for(i = now; i < n; i++){
 sum *= 10;
 sum += str[i] - \'0\';
 }
 if(count == k && tmp * sum > ans){
 ans = tmp * sum;
 }
 return ;
 }
 if(sum != 0){ //忘记考虑sum为0的情况了 
 tmp *= sum;
 srch(now + 1, count + 1, str[now] - \'0\');
 tmp /= sum; //被除数不能为0 
 }
 srch(now + 1, count, sum * 10 + str[now] - \'0\');
}

int main(void)
{
 scanf(%d%d\\n, &n, &k);
 scanf(%s, str);
 srch(1, 0, str[0] - \'0\');
 printf(%d\\n, ans);
 return 0;
}

到网上找到了动态规划解法，等我看完了再发上来。
实在是看不懂，不看算了，因为发现NOIP2000提高组里也有一个乘积最大，那个时候我再仔细看吧。

这个题目确实简单（我还是犯了一些比较低级的错误，提交了几次才AC），本来是想用一个链表来保存的，后来发现不需要专门去实现，因为毕竟题目里只有两种情况，即未知数的幂为0或1，用一个数组就可以了，int a[2][2]; 其中a[0]是保存左边的式子，a[1]保存右边的式子，a[x][0] 用来保存式子中的常数之和，a[x][1]保存未知数的系数之和。
比如：5a+1-3+5=-2a-3+4+a，那么a[0][0] = 1 – 3 + 5，(左边式子常数和)a[0][1] = 5，a[1][0] = -3 + 4，a[1][1] = -2 + 1。代码如下：

C语言:

#include <stdio.h>
#include <ctype.h>
struct link{
 int value;
 int count;
};
int a[2][2];
int x;

int chin(void)
{
 int ch;
 do{
 ch = getchar();
 }while(ch == \' \');
 return ch;
}

void getnum(struct link *to)
{
 int ch, k = 1;
 to->value = to->count = 0;
 ch = chin();
 if(ch == \'\\n\' || ch == \'=\'){
 to->count = -1;
 return ;
 }
 switch(ch){
 case \'-\':
 k = -1;
 ch = chin(); //掉了这行 
 break;
 case \'+\': //没考虑这种情况 
 ch = chin();
 break;
 }
 do{
 if(isalpha(ch)){
 x = ch;
 to->count = 1;
 }else{
 to->value *= 10;
 to->value += ch - \'0\';
 }
 ch = chin();
 }while(ch != \'+\' && ch != \'-\' && ch != \'=\' && ch != \'\\n\');
 ungetc(ch, stdin);
 if(to->value == 0){
 to->value = 1;
 }
 to->value *= k;
}

int main(void)
{
 int i = 0; //忘记初始化了 
 struct link t;
 do{
 getnum(&t);
 if(t.count < 0){
 i++;
 }
 switch(t.count){
 case 0:
 a[i][0] += t.value;
 break;
 case 1:
 a[i][1] += t.value;
 break;
 }
 }while(i != 2);
 a[1][0] -= a[0][0];
 a[0][1] -= a[1][1];

 printf(%c=%.3f\\n, x, (float)a[1][0] / a[0][1]); // 顺序写反了 

 return 0;
}

其实这个代码完全有改进的余地，甚至可能还有错误（刚刚写这篇报告的时候就发现了一个错误）

我一直以为普及组的题目都非常简单，几天看到这题我错了。读了两天题目，硬是不知道题目讲的是什么，悲哀。。
到网上找到一份不错的结题报告，想自己写，估计没那个水平。直接转上来吧，至于代码，等下我会把C的代码写上（自己写）。

我先来说说题目的意思。就从样例开始分析。
输入是：
31
28 130
30 120
31 110
-1 -1
15

意思就是政府预期价是31元。成本28元，按成本销售的时候可以买130件产品。
每个卖30元的时候可以卖120个，
每个卖31元(输入的最高价位)的时候可以卖110个，
每个卖32元的时候可以卖：110-15=95个。
每个卖33元的时候可以卖：110-15-15=80个。
每个卖34元的时候可以卖：110-15-15-15=65个。
…
因为“相邻价位之间的销量变化是均匀的”，因此28元卖130个,30元卖120个就可以知道
29元卖125个(平均每元减少的销量是(130-120) div (30-28)=5)

输出是4，我们来解释一下为什么是4。
4代表补贴是4元，所以:
在卖28元的时候，总利润是：(28-28+4)130=520元，
在卖29元的时候，总利润是：(29-28+4)125=625元，
在卖30元的时候，总利润是：(30-28+4)120=720元，
在卖31元的时候，总利润是：(31-28+4)110=770元，
在卖32元的时候，总利润是：(32-28+4)95=760元，
…
在卖38元的时候，总利润是：(38-28+4)5=70元，
显然可能的价位就是28~38了。(不能低于成本，卖39的时候销售量就是负数了)

可以看出，现在卖31元最划算，所以人们都愿意卖31元，这样一来不就达到政府的目的了吗！！
而当补贴是0,1,2,3的时候卖31元并不是最划算的，政府的目的达不到，你当然就没有分啦！

题意清楚了吗？好，下面分析思路。
穷举显然可以，但是没有什么意思，留给大家自己写。下面讲我的另外一种算法，数学味道要浓一些，
希望大家坚持看完。

由于需要N元钱最划算，相当于使N元钱的利润大于等于每种价格的利润。因此可以分别考虑。
设补贴为x，则N元钱的利润是：(p为成本)
(N-p+x)d[N]=(N-p)d[N]+x*d[N]

因此N元钱比M元钱划算的时候有：
(N-p)d[N]+xd[N]>=(M-p)d[M]+xd[M],即：
x(d[N]-d[M])>=Md[M]-Nd[N]-p*(d[M]-d[N])

这样，要使N元钱比M元钱划算，x必须在区间[k1,k2] (k1,k2根据上面的式子得出)

例如上面的例子：
31元比28元划算时有：
(31-28+x)110>=(28-28+x)130
即：330+110x>=130x,故x<=16.5

31元比30元划算时有：
330+110x>=240+120x,故x<=9

31元比32元划算时有：
330+110x>=380+95x,故x>=3.33
…
最后所有式子取交集，就得到了x的范围。要求绝对值最小值还不容易吗？ 😛
大家注意我在求出了k1,k2后做的最后的处理。可能有一边或两边无界的情况。
正数和负数的处理也有区别。

有一点需要注意：题目没有说输入价位是从小到大排序好的，虽然测试数据都是排序好的。
我就偷个懒如何？:-P

我的程序：

var
 p0,s0,n,d,i,pp,ss,o,tmp:longint;
 p,s:array[-32767..32767]of longint;

begin
 readln(p0);
 n:=1;
 readln(p[1],s[1]);
 readln(pp,ss);
 while ss<>-1 do
 begin
 d:=(ss-s[n])div(pp-p[n]);
 tmp:=p[n];
 for i:=tmp+1 to pp do
 begin
 inc(n);
 p[n]:=p[n-1]+1;
 s[n]:=s[n-1]+d;
 end;
 readln(pp,ss);
 end;
 readln(d);
 while s[n]-d>=0 do
 begin
 inc(n);
 p[n]:=p[n-1]+1;
 s[n]:=s[n-1]-d;
 end;

 for o:=1 to n do if p[o]=p0 then break;
 for i:=0 to 1000000 do
 begin
 if ((p[o]+i-p[1])*s[o]>=(p[o-1]+i-p[1])*s[o-1])and
 ((p[o]+i-p[1])*s[o]>=(p[o+1]+i-p[1])*s[o+1]) then
 begin writeln(i);halt;end;
 if p[o]-i-p[1]>=0 then
 if ((p[o]-i-p[1])*s[o]>=(p[o-1]-i-p[1])*s[o-1])and
 ((p[o]-i-p[1])*s[o]>=(p[o+1]-i-p[1])*s[o+1]) then
 begin writeln(-i);halt;end;
 end;
 writeln(\'NO SOLUTION\');
end.

我的C代码等下再交上来，写死我了，昨晚上从十点写到一十二点半一直都没写出来，今天找CodeWays要了这题的数据才发现问题的所在，总之代码写的太丑了。。。哎，晚点再看看那人写的pascal代码，再修改修改吧。

C语言:

#include <stdio.h>
#include <math.h>
#define add(a, b) do{\\
 goods[count].priece = (a);\\
 goods[count].number = (b);\\
 count++;\\
}while(0)
#define min(a, b) ((a)<(b)?(a):(b))
#define max(a, b) ((a)>(b)?(a):(b))
struct goods{
 int priece;
 int number;
}goods[10000];
int count;
int x, number, cost;

void init(void)
{
 int i;
 int a, b;
 int c, d;
 int k, f;

 scanf(%d, &x);
 scanf(%d%d, &a, &b);
 cost = a;
 x -= cost;
 while(scanf(%d%d, &c, &d), (c != -1 || d != -1)){
 k = (d - b) / (c - a);
 f = d - c * k;
 for(i = a; i <= c - 1; i++){
 add(i - cost, k * i + f);
 }
 a = c, b = d;
 }
 scanf(%d, &k);
 for(i = a; (b - (i - a) * k) > 0; i++){
 add(i - cost, (b - (i - a) * k));
 }
}

int main(void)
{
 int i, j;
 int a, b, k;
 double up = -100000, down = 1000000;
 init();
 for(i = 0; i < count; i++){
 if(goods[i].priece == x){
 number = goods[i].number;
 break;
 }
 }
 for(i = 0; i < count; i++){
 k = 1;
 a = goods[i].priece * goods[i].number - number * x;
 b = number - goods[i].number;
 if(b < 0){
 k = -1;
 }
 if(b != 0){ //排除goods[i].priece == x的情况
 if(k == 1){
 up = max(up, (double)a / b);
 }else{
 down = min(down, (double)a / b);
 }
 }
 }
 if(up <= down){
 if(up > 0){
 printf(%d\\n, (int)ceil(up));
 }else{
 down = fabs(down);
 printf(%d\\n, - (int)ceil(down));
 }
 }else{
 printf(NO SOLUTION\\n);
 }
 return 0;
}

这个题目从一开始我就看错题了，我以为是要从输入的那个矩阵通过ABC三种方式变换到最初的矩阵（1，2，3，4，5，6，7，8），后来才知道是要从最初的矩阵通过变换到目标矩阵（即输入的）。不过看错提了我还是没做出来，就直接看了标称，标称里面的encode函数看了几次都没看懂，最后打算自己写一个encode函数，毕竟它的功能就是康拓展开，就是一个Hash函数。接下来就介绍我的解题思路：
首先，分析程序的上界，因为一共有8个方格，每个方格又有8种数据，但是又不能重复，根据乘法原理可以计算出一共有40320（即8!）种不同的矩阵，于是我用dist[40320]来存储所有矩阵通过多少步可以逆向（顺向是{1,2,3,4,5,6,7,8}变成输入的，我这里是从输入的变成{1,2,3,4,5,6,7,8}）变换成初始状态。然后使用一个函数Hash(即上面的encode函数)来讲矩阵转换成dist的下标。
然后主程序先让dist[目标状态（输入的矩阵）] = 1;，在输出时再减一（至于为什么等于1而不是0看下面。）然后试用BFS对所有的状态进行搜索每遇到一个dist中为0的状态（上面目标状态是从1开始的原因就在这里，不然的话目标状态又会变成别的数字），直到遇到初始状态再停止。
输入dist[初始状态]的值减一（因为dist[目标状态]等于一而不是零）。
最后通过dist之间的关系再输出步骤。
具体代码如下：

/*
LANG: C
ID: zqynux2
PROG: msquare
*/
#include <stdio.h>
#include <string.h>
#define MAX 40320

int dist[40320];
int hash(int *board)
{
 int i, j;
 int look[8] = {0, 1, 2, 3, 4, 5, 6, 7};
 int mult[8] = {1, 8, 8*7, 8*7*6, 8*7*6*5, 8*7*6*5*4, 
 8*7*6*5*4*3, 8*7*6*5*4*3*2};
 int rv = 0;
 for(i = 0; i < 8; i++){
 rv += look[board[i]] * mult[i];
 for(j = board[i] + 1; j < 8; j++){
 look[j]--;
 }
 }
 return rv;
}

int ways[3][8] = {{8, 7, 6, 5, 4, 3, 2, 1}, {4, 1, 2, 3, 6, 7, 8, 5},
 {1, 7, 2, 4, 5, 3, 6, 8}};
void change(int *to, int *from, int way)
{
 int i;
 for(i = 0; i < 8; i++){
 to[i] = from[ways[way][i] - 1];
 }
}

void rechange(int *to, int *from, int way)
{
 int i;
 for(i = 0; i < 8; i++){
 to[ways[way][i] - 1] = from[i];
 }
}

int queue[MAX][8];
void count(int *board)
{
 int head = 0, tail = 1;
 int t, d, i;
 memcpy(queue[0], board, sizeof(int [8]));
 t = dist[hash(board)] = 1;
 while(1){
 t = dist[hash(queue[head])];
 for(i = 0; i < 3; i++){
 rechange(queue[tail], queue[head], i);
 d = hash(queue[tail]);
 if(dist[d] == 0){
// tail = (tail + 1) % MAX;
 tail++; //这一句比上面一句快一些, 但是要求queue数组大些 
 dist[d] = t + 1;
 }
 if(d == 0){
 return ;
 }
 }
// head = (head + 1) % MAX;
 head++; //这一句比上面一句快一些, 但是要求queue数组大些
 }
}

void output(int t)
{
 int board[8];
 int tmp[8];
 int i;
 for(i = 0; i < 8; i++){
 board[i] = i;
 }
 while(t > 1){
 for(i = 0; i < 3; i++){
 change(tmp, board, i);
 if(dist[hash(tmp)] == t - 1){
 t--;
 break;
 }
 }
 memcpy(board, tmp, sizeof(tmp));
 printf(%c, i + \'A\');
 }
 printf(\\n);
}

int main(void)
{
 int i;
 int board[8];
 freopen(msquare.in, r, stdin);
 freopen(msquare.out, w, stdout);
 for(i = 0; i < 8; i++){
 scanf(%d, board + i);
 board[i]--; //忘记这里了 
 }
 count(board);
 for(i = 0; i < 8; i++){
 board[i] = i;
 }
 printf(%d\\n, i = dist[hash(board)] - 1);
 output(i + 1);
 return 0;
}