NOIP2007提高组解题报告
NOIP2007提高组解题报告（待更新...）
本站原创，转载时请注明转自[url=https://www.sodocs.net/doc/607785927.html,]https://www.sodocs.net/doc/607785927.html,[/url]
网络虾客
第一题：
开个足够大的数组，把所有数读入，NlogN的qsort排一遍，然后一边统计以便输出。
用C++内置的qsort异常简洁，甚至代码输入量比普及还少！
但是由于考虑到传说中的cin cout比fscanf,fprintf慢，所以这里用了后者……
遗憾的是，我在考试的时候由于太过自大和自信，用了一个n^2的算法……唉，只得了50分，要知道多这50分，我就很有可能得到全国一等了
参考C++代码[code]#include
#include
using namespace std;
FILE *in = fopen("count.in","r");
FILE *out = fopen("count.out","w");
int compare(const void *aa,const void *bb)
{
int a=(*((int*)aa)),b=(*((int*)bb));
if(a>b)
return 1;
else if(a==b)
return 0;
else return -1;
}
int main()
{
long n,total=0;
long *number = new long [200000];//直接定义在windows下可能会栈溢出
fscanf(in,"%ld",&n);
for(long i=0;i
qsort(number,n,sizeof(long),compare);
fprintf(out,"%ld ",number[0]);
total++;
for(int i=1;i
if(number[i]!=number[i-1])
{
fprintf(out,"%ld\n%ld ",total,number[i]);
total=1;
continue;
}
total++;
}
fprintf(out,"%ld\n",total);
fclose(in);
fclose(out);
return 0;
}[/code]第二题：
一个显而易见的字符串处理。很简单（对于我来说），不过很考细节（阴险的数据），和细心程度（看清楚题没有），逻辑思维（头脑不清楚逻辑顺序很容易乱，逻辑顺序一乱编程复杂度就上去了），编程熟悉度（经验啦，如果没写过足够多的程序，一不小心写错了调试会弄死你滴！）
首先，看清楚题，是扩展的条件：
1、出现了'-'号
2、'-'号两边同为[color=Red]小写字母[/color]或同为数字，注意看，同为小写字母！这里不知道害死多少粗心的人呐
3、按照ascii码的顺序，右边的字符严格大于左边
这样，我们就显而易见地想到：从第一个字符开始，逐个查询：
1、不为'-'号，直接输出
2、为减号：
一、不符合扩展要求，输出
二、符合扩展要求，进行扩展并输出扩展后内容。
三、输出扩展后的字符串
再仔细分析，我们不难看到，不管p1、p3如何，如果需要扩展，那么需要扩展的个数总是不变的，所以我们先根据p2进行扩展。我是另外开了一个数组，按照ascii码顺序和p2进行输出。
扩展了p2以后，我们可以发现，p1输出什么对p3是没有影响的，也就是说，我们可以先考虑p3再考虑p1。根据p3来处理是否逆序
最后再根据p1进行扩展，这就无非是大小写交换和*号的问
题了，无须多提
不过，说一下，其实刚才上面p1、p2、p3的参数是互不影响的，但是会对你的编程复杂度有影响。大家可以自己去想一下。
另外，出了刚才题目的意思让不少“马大哈”栽了，提示一下几个阴险的地方
1、考虑第一个是'-'的情况，因为如果是'-'你要查前一个字符，那么有可能造成数组越界程序错误而退出
2、考虑最后一个是'-'的情况，因为如果是'-'，你要查询后一个字符，同样有可能造成数组越界
3、100是输入时的长度……所以你处理时数组要开得足够大
综上所述，考虑了这些这道题就基本上可以完美解决了。
具体实现方法可参见我的C++代码。我加了足够多的注释。[code]#include
#include
using namespace std;
ifstream fin ("expand.in");
ofstream fout ("expand.out");
inline void check(int x,int &last,int &next);
inline void prepare();
string input,work;
char working[5000];
inline bool letter(char a,char b)//判断'-'两端的字符是否同为数字或同为小写字母
{
if(a>='A'&&a<='Z'&&b>='A'&&b<='Z')
return true;
else return false;
}
inline void changeletter(char &a,int x)//字符串变换，根据参数p1来变换字符串为大写/小写/*
{
if(x==1)
{
if(a>='A'&&a<='Z')
a=a-'A'+a;
return ;
}
else if(x==2)
{
if(a>='a'&&a<='z')
a=a-'a'+'A';
return ;
}
else if(x==3)
{
a='*';
}
}
int main()
{
int p1,p2,p3;
fin >> p1 >> p2 >> p3;
fin >> input;
work = input;
fout << input[0];
for(int i=0;i
work[i]=(work[i]-'A'+'a');
for(int i=1;i
if(input[i]!='-')
fout << input[i];
else if(input[i]=='-')
{
int last,next;
check(i,last,next);
if(last!=next||work[i-1]>work[i+1]||letter(input[i-1],input[i+1])||input[i-1]==input[i+1])//考虑以下情况时不需要扩展：
//1、last!=next，就是左右两边不同为数字或同为字母
//2、左右两边都不同为小写字母
//3、左右两边的ascii码的值相等
{
fout << input[i];
goto loop;
}
else if(input[i-1]+1==input[i+1]&&(!letter(input[i-1],input[i+1])))//这里是如果后者是前者的后继，那么就不输出'-'号
goto loop;
else
{
prepare();
int chN;
for(int ii=(int)input[i-1]+1,j=0;ii<(int)input[i+1];ii++)//先根据p2函数进行扩展，chN是根据p2扩展后的字符长度
{
for(int k=0;k
chN=j;
}
if(p3==2)//
根据p3参数确定是否需要逆序
{
for(int ii=0,j=chN-1;ii
char t;
t=working[ii];
working[ii]=working[j];
working[j]=t;
}
}
for(int ii=0;ii
changeletter(working[ii],p1);
fout << working[ii];
}
}
}
loop:1;//一个跳出循环的语句（MS算法书中说goto是有害的，罪过……）
}
fout << endl;
return 0;
}
inline void check(int x,int &last,int &next)
//这里的last和next与主函数中的last和next实际上是一个数值，这里变了那里也变了。
//这里是判断，如果是字母，则值为0，如果是数字，值为1，其它则值为2
{
if(work[x-1]>='a'&&work[x-1]<='z'||work[x-1]>='A'&&work[x-1]<='Z')
last=0;
else if(work[x-1]>='0'&&work[x-1]<='9')
last=1;
else last=2;
if(work[x+1]>='a'&&work[x+1]<='z'||work[x+1]>='A'&&work[x+1]<='Z')
next=0;
else if(work[x+1]>='0'&&work[x+1]<='9')
next=1;
else next=2;
}
inline void prepare()//数组初始化
{
for(int i=0;i<500;i++)
working[i]='\0';
}[/code]第三题：
我用贪心+搜索+卡时（搜索如果超过900ms输出贪心解），第一次测40分，第二次改了数据以后测20分（我后来发现我卡时放错地方了，TLE8个），莫名其妙的有人就多了40~50分（多是pascal），唉。听说卡时复测时会有问题！
其实这是一道简单的DP，递推方程很明显，但我不会（至少现在不会），我过两天等请教了那些高中部的大哥们再说吧~
不过这道题要考虑的一个是精度的问题。我一朋友说要用高精度，但我设想似乎浮点变量是可以承受这个精度的。
[code]
我的想法（不知有没有错）:
对每一行分别处理，
n为列数, v[i][j]表示处理当前行时取第i次完成后左边取掉j个时的最大获得, 0 <= j <= i <= n, i != 0
d[0] ~ d[n - 1]为当前行的数据
v[1][0] = d[n - 1] << 1
v[1][1] = d[0] << 1
v[i][0] = v[i - 1][0] + (d[n - i] << i)
v[i][i] = v[i - 1][j - 1] + (d[j - 1] << i)
其余情况v[i][j] = max {
v[i - 1][j] + (d[n - i + j] << i),
v[i - 1][j - 1] + (d[j - 1] << i)
}
answer = max{v[n][x], 0 <= x <= n}
<<运算符参阅c/c++语言参考
[/code][quote]-- by [url=https://www.sodocs.net/doc/607785927.html,/bbs/space.php?action=viewpro&uid=2]liangent[/url][/quote]
第四题：
题目描述没看懂。直接输出5……
今年的测试数据又来搞乱七八糟的。
考场上发生了灵异事件，我两个朋友用pascal的考试的是否无法读入数据（数组读入的
时候全是按顺序1、2、3、4、5），最后搞成是先读入变量再赋值（绝对不是自身问题）。另外，pascal的评测也是一波三折。先是count错了3个数据（没按样例给，该换行的没换行），导致部分用了readln的选手错误。然后第三题，莫名其妙的后来一些选手多了40分……另外，我的两个同学pascal全部编译失败，未知原因（在考试时是通过的）。
没换行的问题又导致一部分人的分数有影响。
所以今年广西搞的乱七八糟的不清楚……
[color=Red]由于第三第四题的没时间打，所以贴了个别人的：[/color]https://www.sodocs.net/doc/607785927.html,/post/noip07.html[code]
第三题，很容易想到DP，不过要加一个高精度。至于很多人抱怨自己在高精度上出错，那就没什么好说的了，都是基础的东西。简单说下DP的过程，高精度略
过。我们可以把问题转化为每次要取完一整行，一共取m次。然后这m次是相互独立的，所以我们可以把每行的结果计算出来后求和。对于每一行：data[i]
表示这行的第i个数；f[i][j]表示在行首取了i次，行末取了j次的最大值。f[i][j] = max{f[i - 1][j] +
data[i] * 2 ^ (i + j), f[i][j - 1] + data[n - j + 1] * 2 ^ (i + j)}
(我的程序里使用了ZJU ACM的高精度运算模板，BigNum是一个封装好的高精度类...不方便发上来)
第四题，开始把这题想的
复杂了。我们首先来考虑只有一条直径的时候，后面会说明有多条直径的时候可以当作一条来处理。首先可以通过经典的O(n)的算法求出树上的最远点，即一条
直径（做法是从任意一点开始DFS一次求出一个最远的点，这是直径的一个端点；再从这个最远点开始再次DFS，再找到的最远点就是直径的另外一个端点）。
然后顺序枚举这条最长路径上的每条长度小于s的最长子路径（说不太清楚看代码吧...），用一个队列维护。这样每一条可能的路径就是一个可能的核，再求出
对应的偏心距就可以了。我是先用了一个floyed预处理出所有顶点之间的最点路备用。 ok，来说有多条直径的问题：
题目中已经说了，如果有多条直径的话他们的中心也一定重合，换言之一定至少有一个节点或一条路径重合。假设有两条直径分别为AB和CD，它们重合的部分是
EF。那么一定有AE的长度等于CE的长度，FB的长度等于FD的长度。其次核一定是在直径的中央部分。下面分两种情况讨论： 1.
如果给定的s能够覆盖重合的点或者路径，那么我们在任一条直径上选择一个核，那么对于另外的直径而言，就是只选择了重合的部分，对于这个核的偏心距“有贡
献”的只可能是在非选中的直径上，而对于每条直径除去重合部分剩下的两部分的长度都是相等的，所以选择任意一条直径均可。 2.
如果不能覆盖，那么对于所有直径选择的部分都是相同的了，更是可以任选了。 两点还可以改进的地方，由于数据不是很强，我也就没改： 1.
核一定是在直径的中央部分，所以可以从直径的中心向两边扩展求核。 2. 距离核最远的点一定是度为1的点，floyed预处理有点浪费了。
可能证明的还不够完善，有问题请指出，多谢！[/code]
我支持用C++，各位，看了今年的第一题和Pascal那么多问题以后，你还在犹豫吗？还在彷徨吗？来吧，赶快加入C++的队伍！P转C++其实就两节晚自习，再透一点就两个星期！绝对有大优势！绝对不比pascal慢！
11月19日 22:36
290
第三题弱。。。
网络虾客 11月20日 12:50
确实，只是这几天上课，暂时没时间写……
足兆叉虫 11月23日 16:42
第一题C语言描述（无偿版权提供给FLS）
[color=#000000][color=#800000][b]#include[/b][/color] [color=#0000ff]<[/color]stdio[color=#0000ff].[/color]h[color=#0000ff]>[/color]
#define SIZE 10001
#define INFILE [color=#ff00ff]"count.in"[/color]
#define OUTFILE [color=#ff00ff]"count.out"[/color]
using namespace std[color=#0000ff];[/color]
[color=#5000a0]int[/color] counter[color=#0000ff]=[/color]1[color=#0000ff];[/color]
[color=#5000a0]int[/color] result[color=#0000ff][[/color]SIZE[color=#0000ff]][/color][color=#0000ff][[/color]2[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]{[/color]0[color=#0000ff]}[/color][color=#0000ff];[/color]
[color=#0000ff]void[/color] insert[color=#0000ff]([/color][color=#5000a0]int[/color] num[color=#0000ff])[/color][color=#0000ff];[/color]
main[color=#0000ff]([/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#5000a0]int[/color] num[color=#0000ff]=[/color]0[color=#0000ff];[/color]
[color=#5000a0]int[/color] i[color=#0000ff]=[/color]0[color=#0000ff],[/color]temp[color=#0000ff]=[/color]0[color=#0000ff],[/color]j[color=#0000ff];[/color]
FILE [color=#0000ff]*[/color]file[color=#0000ff];[/color]
file[color=#0000ff]=[/color]fopen[color=#0000ff]([/color]INFILE[color=#0000ff],[/color][color=#ff00ff]"r"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
fscanf[color=#0000ff]([/color]file[color=#0000ff],[/color][color=#ff00ff]"%d"[/color][color=#0000ff],[/color][color=#0000ff]&[/color]num[color=#0000ff])[/color][color=#0000ff];[/color]
fscanf[color=#0000ff]([/color]file[color=#0000ff],[/color][color=#ff00ff]"%d"[/color][color=#0000ff],[/color][color=#0000ff]&[/color]temp[color=#0000ff])[/color][color=#0000ff];[/color]
result[color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff]=[/color]temp[color=#0000ff];[/color]
result[color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff]=[/color]1[color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][col
or=#0000ff]([/color]i[color=#0000ff]=[/color]0[color=#0000ff];[/color]i[color=#0000ff]<[/color]num[color=#0000ff]-[/color]1[color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
fscanf[color=#0000ff]([/color]file[color=#0000ff],[/color][color=#ff00ff]"%d"[/color][color=#0000ff],[/color][color=#0000ff]&[/color]temp[color=#0000ff])[/color][color=#0000ff];[/color]
insert[color=#0000ff]([/color]temp[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
fclose[color=#0000ff]([/color]file[color=#0000ff])[/color][color=#0000ff];[/color]
file[color=#0000ff]=[/color]fopen[color=#0000ff]([/color]OUTFILE[color=#0000ff],[/color][color=#ff00ff]"w"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]1[color=#0000ff];[/color]i[color=#0000ff]<[/color][color=#0000ff]=[/color]counter[color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
fprintf[color=#0000ff]([/color]file[color=#0000ff],[/color][color=#ff00ff]"%d %dn"[/color][color=#0000ff],[/color]result[color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff],[/color]result[color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
fclose[color=#0000ff]([/color]file[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]void[/color] insert[color=#0000ff]([/color][color=#5000a0]int[/color] num[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#5000a0]int[/color] find[color=#0000ff]([/color][color=#5000a0]int[/color] num[color=#0000ff],[/color][color=#5000a0]int[/color] low[color=#0000ff],[/color][color=#5000a0]int[/color] high[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]void[/color] move[color=#0000ff]([/color][color=#5000a0]int[/color] low[color=#0000ff],[/color][color=#5000a0]int[/color] high[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#5000a0]int[/color] pos[color=#0000ff]=[/color]0[color=#0000ff];[/color]
pos[color=#0000ff]=[/color]find[color=#0000ff]([/color]num[color=#0000ff],[/color]1[color=#0000ff],[/color]counter[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]pos[color=#0000ff]<[/color][color=#0000ff]=[/color]0[color=#0000ff])[/color]
[color=#0000ff]{[/color]
move[color=#0000ff]([/color][color=#0000ff]-[/color]pos[color=#0000ff],[/color]counter[color=#0000ff])[/color][color=#0000ff];[/color]
result[color=#0000ff][[/color][color=#0000ff]-[/color]pos[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff]=[/color]num[color=#0000ff];[/color]
result[color=#0000ff][[/color][color=#0000ff]-[/colo
r]pos[color=#0000ff]][/color][color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff]=[/color]1[color=#0000ff];[/color]
counter[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color]
[color=#0000ff]{[/color]
result[color=#0000ff][[/color]pos[color=#0000ff]][/color][color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#5000a0]int[/color] find[color=#0000ff]([/color][color=#5000a0]int[/color] num[color=#0000ff],[/color][color=#5000a0]int[/color] low[color=#0000ff],[/color][color=#5000a0]int[/color] high[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#5000a0]int[/color] i[color=#0000ff]=[/color]0[color=#0000ff];[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]low[color=#0000ff]<[/color]high[color=#0000ff])[/color]
[color=#0000ff]{[/color]
i[color=#0000ff]=[/color][color=#0000ff]([/color]low[color=#0000ff]+[/color]high[color=#0000ff])[/color][color=#0000ff]/[/color]2[color=#0000ff];[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]num[color=#0000ff]=[/color][color=#0000ff]=[/color]result[color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]return[/b][/color] i[color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color] [color=#800000][b]if[/b][/color][color=#0000ff]([/color]num[color=#0000ff]>[/color]result[color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]return[/b][/color] find[color=#0000ff]([/color]num[color=#0000ff],[/color]i[color=#0000ff]+[/color]1[color=#0000ff],[/color]high[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color]
[color=#0000ff]{[/color]
[color=#800000][b]return[/b][/color] find[color=#0000ff]([/color]num[color=#0000ff],[/color]low[color=#0000ff],[/color]i[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color] [color=#800000][b]if[/b][/color][color=#0000ff]([/color]low[color=#0000ff]=[/color][color=#0000ff]=[/color]high[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]num[color=#0000ff]>[/color]result[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color] [color=#800000][b]return[/b][/color] [color=#0000ff]-[/color]low[color=#0000ff]-[/color]1[color=#0000ff];[/color]
[color=#800000][b]else[/b][/color] [color=#800000][b]if[/b][/color][color=#0000ff]([/color
]num[color=#0000ff]=[/color][color=#0000ff]=[/color]result[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color] [color=#800000][b]return[/b][/color] low[color=#0000ff];[/color]
[color=#800000][b]else[/b][/color] [color=#800000][b]if[/b][/color][color=#0000ff]([/color]num[color=#0000ff]<[/color]result[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color] [color=#800000][b]return[/b][/color] [color=#0000ff]-[/color]low[color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#0000ff]void[/color] move[color=#0000ff]([/color][color=#5000a0]int[/color] low[color=#0000ff],[/color][color=#5000a0]int[/color] high[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#5000a0]int[/color] i[color=#0000ff]=[/color]0[color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]high[color=#0000ff];[/color]i[color=#0000ff]>[/color][color=#0000ff]=[/color]low[color=#0000ff];[/color]i[color=#0000ff]-[/color][color=#0000ff]-[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
result[color=#0000ff][[/color]i[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff]=[/color]result[color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff];[/color]
result[color=#0000ff][[/color]i[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff]=[/color]result[color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color][/color]
[[i] 本帖最后由 足兆叉虫 于 11月30日 20:38 编辑 [/i]]
足兆叉虫 11月23日 16:44
到大学了真的很无聊。。。。。。
所以就回来写NOIP了。。
这个我测试过了，虽然没有用测评系统，不过我正在下。。。
同时向FLS的同学们表示问候
--------------------------------------------------
E:programingworkfile>fc count1.ans count1.out
正在比较文件 count1.ans 和 COUNT1.OUT
FC: 找不到相异处
E:programingworkfile>fc count2.ans count2.out
正在比较文件 count2.ans 和 COUNT2.OUT
FC: 找不到相异处
E:programingworkfile>fc count3.ans count3.out
正在比较文件 count3.ans 和 COUNT3.OUT
FC: 找不到相异处
E:programingworkfile>fc count4.ans count4.out
正在比较文件 count4.ans 和 COUNT4.OUT
FC: 找不到相异处
E:programingworkfile>fc count5.ans count5.out
正在比较文件 count5.ans 和 COUNT5.OUT
FC: 找不到相异处
E:programingworkfile>fc count6.ans count6.out
正在比较文件 count6.ans 和 COUNT6.OUT
FC: 找不到相异处
E:programingworkfile>fc count7.ans count7.out
正在比较文件 count7.ans 和 COUNT7.OUT
FC: 找不到相异处
E:programin
gworkfile>fc count8.ans count8.out
正在比较文件 count8.ans 和 COUNT8.OUT
FC: 找不到相异处
E:programingworkfile>fc count9.ans count9.out
正在比较文件 count9.ans 和 COUNT9.OUT
FC: 找不到相异处
E:programingworkfile>fc count10.ans count10.out
正在比较文件 count10.ans 和 COUNT10.OUT
FC: 找不到相异处
------------------------------------------------------
Liangent 11月24日 00:09
[quote]loop:1;//一个跳出循环的语句（MS算法书中说goto是有害的，罪过……）[/quote]
我觉得类似java中的label的goto使用不算有害...
（只用于多层循环时指明break和continue到的循环）
Liangent 11月24日 00:11
回复 #1 网络虾客 的帖子
[quote]2、'-'号两边同为小写字母或同为数字，注意看，同为小写字母！这里不知道害死多少粗心的人呐[/quote]有大写的情况？
反正我用的islower()...
足兆叉虫 11月26日 18:46
第二题C语言描述
[color=#000000][color=#800000][b]#include[/b][/color] [color=#0000ff]<[/color]stdio[color=#0000ff].[/color]h[color=#0000ff]>[/color]
[color=#800000][b]#include[/b][/color] [color=#0000ff]<[/color]stdlib[color=#0000ff].[/color]h[color=#0000ff]>[/color]
[color=#800000][b]#include[/b][/color] [color=#0000ff]<[/color]ctype[color=#0000ff].[/color]h[color=#0000ff]>[/color]
#define INFILE [color=#ff00ff]"expand.in"[/color]
#define OUTFILE [color=#ff00ff]"expand.out"[/color]
#define SIZE 101
[color=#0000ff]void[/color] expand[color=#0000ff]([/color]FILE [color=#0000ff]*[/color]outfile[color=#0000ff],[/color]char a[color=#0000ff],[/color]char b[color=#0000ff],[/color][color=#5000a0]int[/color] p1[color=#0000ff],[/color][color=#5000a0]int[/color] p2[color=#0000ff],[/color][color=#5000a0]int[/color] p3[color=#0000ff])[/color][color=#0000ff];[/color]
main[color=#0000ff]([/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
char string[color=#0000ff][[/color]SIZE[color=#0000ff]][/color][color=#0000ff];[/color]
[color=#5000a0]int[/color] p1[color=#0000ff],[/color]p2[color=#0000ff],[/color]p3[color=#0000ff];[/color]
[color=#5000a0]int[/color] i[color=#0000ff];[/color]
FILE [color=#0000ff]*[/color]infile[color=#0000ff],[/color][color=#0000ff]*[/color]outfile[color=#0000ff];[/color]
infile[color=#0000ff]=[/color]fopen[color=#0000ff]([/color]INFILE[color=#0000ff],[/color][color=#ff00ff]"r"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
outfile[color=#0000ff]=[/color]fopen[color=#0000ff]([/color]OUTFILE[color=#0000ff],[/color][color=#ff00ff]"w"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
fscanf[color=#0000ff]([/color]infile[color=#0000ff],[/color][color=#ff00ff]"%d %d %d"[/color][color=#0000ff],[/color][color=#0000ff]&[/color]p1[color=#0000ff],[/color][color=#0000ff]&[/color]p2[color=#0000ff],[/color][color=#0000ff]&[/color]p3[color=#0000ff])[/color][color=#0000ff];[/color]
fscanf[color=#0000ff]([/color]infile[c
olor=#0000ff],[/color][color=#ff00ff]"%s"[/color][color=#0000ff],[/color]string[color=#0000ff])[/color][color=#0000ff];[/color]
#ifdef DEBUG
printf[color=#0000ff]([/color][color=#ff00ff]"%d %d %dn"[/color][color=#0000ff],[/color]p1[color=#0000ff],[/color]p2[color=#0000ff],[/color]p3[color=#0000ff])[/color][color=#0000ff];[/color]
printf[color=#0000ff]([/color][color=#ff00ff]"%s"[/color][color=#0000ff],[/color]string[color=#0000ff])[/color][color=#0000ff];[/color]
#endif
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]0[color=#0000ff];[/color]string[color=#0000ff]![/color][color=#0000ff]=[/color][color=#ff00ff]''[/color][color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]string[color=#0000ff]=[/color][color=#0000ff]=[/color][color=#ff00ff]'-'[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color] [color=#0000ff]([/color][color=#0000ff]([/color]islower[color=#0000ff]([/color]string[color=#0000ff][[/color]i[color=#0000ff]-[/color]1[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff]&[/color][color=#0000ff]&[/color]islower[color=#0000ff]([/color]string[color=#0000ff][[/color]i[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff])[/color][color=#0000ff]|[/color][color=#0000ff]|[/color]
[color=#0000ff]([/color]isdigit[color=#0000ff]([/color]string[color=#0000ff][[/color]i[color=#0000ff]-[/color]1[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff]&[/color][color=#0000ff]&[/color]isdigit[color=#0000ff]([/color]string[color=#0000ff][[/color]i[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff])[/color] [color=#0000ff])[/color]
[color=#0000ff]&[/color][color=#0000ff]&[/color][color=#0000ff]([/color]string[color=#0000ff][[/color]i[color=#0000ff]-[/color]1[color=#0000ff]][/color][color=#0000ff]<[/color]string[color=#0000ff][[/color]i[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff])[/color]
expand[color=#0000ff]([/color]outfile[color=#0000ff],[/color]string[color=#0000ff][[/color]i[color=#0000ff]-[/color]1[color=#0000ff]][/color][color=#0000ff],[/color]string[color=#0000ff][[/color]i[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff],[/color]p1[color=#0000ff],[/color]p2[color=#0000ff],[/color]p3[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]else[/b][/color]
fprintf[color=#0000ff]([/color]outfile[color=#0000ff],[/color][color=#ff00ff]"-"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color]
fprintf[color=#0000ff]([/color]outf
ile[color=#0000ff],[/color][color=#ff00ff]"%c"[/color][color=#0000ff],[/color]string[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
#ifdef DEBUG
system[color=#0000ff]([/color][color=#ff00ff]"pause"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
#endif
[color=#0000ff]}[/color]
[color=#0000ff]void[/color] expand[color=#0000ff]([/color]FILE [color=#0000ff]*[/color]outfile[color=#0000ff],[/color]char a[color=#0000ff],[/color]char b[color=#0000ff],[/color][color=#5000a0]int[/color] p1[color=#0000ff],[/color][color=#5000a0]int[/color] p2[color=#0000ff],[/color][color=#5000a0]int[/color] p3[color=#0000ff])[/color]
[color=#0000ff]{[/color]
char i[color=#0000ff];[/color]
[color=#5000a0]int[/color] j[color=#0000ff];[/color]
[color=#5000a0]int[/color] [color=#0000ff]([/color][color=#0000ff]*[/color]to[color=#0000ff])[/color][color=#0000ff]([/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#5000a0]int[/color] tostar[color=#0000ff]([/color]char a[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]switch[/b][/color][color=#0000ff]([/color]p1[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]case[/b][/color] 1[color=#0000ff]:[/color]
to[color=#0000ff]=[/color]tolower[color=#0000ff];[/color]
[color=#800000][b]break[/b][/color][color=#0000ff];[/color]
[color=#800000][b]case[/b][/color] 2[color=#0000ff]:[/color]
to[color=#0000ff]=[/color]toupper[color=#0000ff];[/color]
[color=#800000][b]break[/b][/color][color=#0000ff];[/color]
[color=#800000][b]case[/b][/color] 3[color=#0000ff]:[/color]
to[color=#0000ff]=[/color]tostar[color=#0000ff];[/color]
[color=#800000][b]break[/b][/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]p3[color=#0000ff]=[/color][color=#0000ff]=[/color]1[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]a[color=#0000ff]+[/color]1[color=#0000ff];[/color]i[color=#0000ff]<[/color][color=#0000ff]=[/color]b[color=#0000ff]-[/color]1[color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]j[color=#0000ff]=[/color]0[color=#0000ff];[/color]j[color=#0000ff]<[/color]p2[color=#0000ff];[/color]j[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
fprintf[color=#0000ff]([/color]outfile[color=#0000ff],[/color][color=#ff00ff]"%c"[/color][color=#0000ff],[/color]to[color=#0000ff]([/color]i[color=#0000ff])[/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color]
[color=#0000ff]{[/color]
[color=#800000][b]for[/b
][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]b[color=#0000ff]-[/color]1[color=#0000ff];[/color]i[color=#0000ff]>[/color][color=#0000ff]=[/color]a[color=#0000ff]+[/color]1[color=#0000ff];[/color]i[color=#0000ff]-[/color][color=#0000ff]-[/color][color=#0000ff])[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]j[color=#0000ff]=[/color]0[color=#0000ff];[/color]j[color=#0000ff]<[/color]p2[color=#0000ff];[/color]j[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
fprintf[color=#0000ff]([/color]outfile[color=#0000ff],[/color][color=#ff00ff]"%c"[/color][color=#0000ff],[/color]to[color=#0000ff]([/color]i[color=#0000ff])[/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#5000a0]int[/color] tostar[color=#0000ff]([/color]char a[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]return[/b][/color] [color=#ff00ff]'*'[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color][/color]
[[i] 本帖最后由 足兆叉虫 于 11月30日 20:41 编辑 [/i]]
足兆叉虫 11月30日 20:17
第三题C语言描述
[color=#000000][color=#008080]/*
首先说说这道题,又中了NOIP必考动态规划(咦,我忘记了是不是这么叫的了......)的怨念,虽然我一开始用的不是动态规划,不过贪心向来在NOIP拿不到满分
回到这道题,去除上文中说过了的,先从递归的方向发现,题目的答案就是取出第1个加上剩余序列和取出第m个加上剩余序列中的最大值,所以就是我的第一个程序,用的就是递归的方法.(使用的时候去除#define DONGGUI ) 这样可以得40分
然后,很显然的,超时,因为很多东西是计算过的,所以,在之前加上一个数组计算已经计算过的值,也就是加上 #define DONGGUI 的效果
不过很恶心的是,这样只能得50分,剩下的解要用万恶的高精,这个就是后面那个代码.同时,仔细观察可以发现原来的递归方法中,数组的解是从1,1 1,2 1,3 .... 1,m的方式逐步得到的,所以我完全地用动规写了第二扁
*/[/color]
[color=#800000][b]#include[/b][/color] [color=#0000ff]<[/color]stdio[color=#0000ff].[/color]h[color=#0000ff]>[/color]
[color=#800000][b]#include[/b][/color] [color=#0000ff]<[/color]stdlib[color=#0000ff].[/color]h[color=#0000ff]>[/color]
#define INFILE [color=#ff00ff]"game.in"[/color]
#define OUTFILE [color=#ff00ff]"game.out"[/color]
#define SIZE 80
#define DONGGUI
#ifdef DONGGUI
long long [color=#5000a0]int[/color] b[color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff];[/color]
#endif
long long [color=#5000a0]int[/color] game[color=#0000ff]([/color][color=#5000a0]int[/color] a[color=#0000ff][[/color][color=#0000ff]][/color][color=#0000ff],[/color][color=#5000a0]in
t[/color] low[color=#0000ff],[/color][color=#5000a0]int[/color] high[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]void[/color] blank[color=#0000ff]([/color][color=#5000a0]int[/color] [color=#008000]size[/color][color=#0000ff])[/color][color=#0000ff];[/color]
main[color=#0000ff]([/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#5000a0]int[/color] a[color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff];[/color]
[color=#5000a0]int[/color] n[color=#0000ff],[/color]m[color=#0000ff];[/color]
[color=#5000a0]int[/color] i[color=#0000ff],[/color]j[color=#0000ff];[/color]
long long [color=#5000a0]int[/color] temp1[color=#0000ff],[/color]temp2[color=#0000ff];[/color]
long long [color=#5000a0]int[/color] sum[color=#0000ff]=[/color]0[color=#0000ff];[/color]
FILE [color=#0000ff]*[/color][color=#800000][b]in[/b][/color][color=#0000ff],[/color][color=#0000ff]*[/color]out[color=#0000ff];[/color]
[color=#800000][b]in[/b][/color][color=#0000ff]=[/color]fopen[color=#0000ff]([/color]INFILE[color=#0000ff],[/color][color=#ff00ff]"r"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
out[color=#0000ff]=[/color]fopen[color=#0000ff]([/color]OUTFILE[color=#0000ff],[/color][color=#ff00ff]"w"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
fscanf[color=#0000ff]([/color][color=#800000][b]in[/b][/color][color=#0000ff],[/color][color=#ff00ff]"%d %d"[/color][color=#0000ff],[/color][color=#0000ff]&[/color]n[color=#0000ff],[/color][color=#0000ff]&[/color]m[color=#0000ff])[/color][color=#0000ff];[/color]
#ifdef DONGGUI
blank[color=#0000ff]([/color]m[color=#0000ff])[/color][color=#0000ff];[/color]
#endif
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]j[color=#0000ff]=[/color]0[color=#0000ff];[/color]j[color=#0000ff]<[/color]n[color=#0000ff];[/color]j[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]1[color=#0000ff];[/color]i[color=#0000ff]<[/color][color=#0000ff]=[/color]m[color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
fscanf[color=#0000ff]([/color][color=#800000][b]in[/b][/color][color=#0000ff],[/color][color=#ff00ff]"%d"[/color][color=#0000ff],[/color][color=#0000ff]&[/color]a[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
temp1[color=#0000ff]=[/color]a[color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff]+[/color]game[color=#0000ff]([/color]a[color=#0000ff],[/color]2[color=#0000ff],[/color]m[color=#0000ff])[/color][color=#0000ff];[/color]
temp2[color=#0000ff]=[/color]a[color=#0000ff][[/color]m[color=#0000ff]][/color][color=#0000ff]+[/colo
r]game[color=#0000ff]([/color]a[color=#0000ff],[/color]1[color=#0000ff],[/color]m[color=#0000ff]-[/color]1[color=#0000ff])[/color][color=#0000ff];[/color]
sum[color=#0000ff]+[/color][color=#0000ff]=[/color][color=#0000ff]([/color]temp1[color=#0000ff]>[/color]temp2[color=#0000ff]?[/color]temp1[color=#0000ff]:[/color]temp2[color=#0000ff])[/color][color=#0000ff]*[/color]2[color=#0000ff];[/color]
#ifdef DONGGUI
blank[color=#0000ff]([/color]m[color=#0000ff])[/color][color=#0000ff];[/color]
#endif
[color=#0000ff]}[/color]
fprintf[color=#0000ff]([/color]out[color=#0000ff],[/color][color=#ff00ff]"%.0lf"[/color][color=#0000ff],[/color]sum[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
long long [color=#5000a0]int[/color] game[color=#0000ff]([/color][color=#5000a0]int[/color] a[color=#0000ff][[/color][color=#0000ff]][/color][color=#0000ff],[/color][color=#5000a0]int[/color] low[color=#0000ff],[/color][color=#5000a0]int[/color] high[color=#0000ff])[/color]
[color=#0000ff]{[/color]
long long [color=#5000a0]int[/color] temp1[color=#0000ff],[/color]temp2[color=#0000ff];[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]low[color=#0000ff]<[/color]high[color=#0000ff])[/color]
[color=#0000ff]{[/color]
#ifdef DONGGUI
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]b[color=#0000ff][[/color]low[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]high[color=#0000ff]][/color][color=#0000ff]+[/color]1[color=#0000ff]=[/color][color=#0000ff]=[/color]0[color=#0000ff])[/color]
temp1[color=#0000ff]=[/color]a[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff]+[/color][color=#0000ff]([/color]b[color=#0000ff][[/color]low[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]high[color=#0000ff]][/color][color=#0000ff]=[/color]game[color=#0000ff]([/color]a[color=#0000ff],[/color]low[color=#0000ff]+[/color]1[color=#0000ff],[/color]high[color=#0000ff])[/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]else[/b][/color]
temp1[color=#0000ff]=[/color]a[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff]+[/color]b[color=#0000ff][[/color]low[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]high[color=#0000ff]][/color][color=#0000ff];[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]b[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff][[/color]high[color=#0000ff]-[/color]1[color=#0000ff]][/color][color=#0000ff]+[/color]1[color=#0000ff]=[/color][color=#0000ff]=[/color]0[color=#0000ff])[/color]
temp2[color=#0000ff]=[/color]a[color=#0000ff][[/color]high[color=#0000ff]][/color][color=#0000ff]+[/color][color=#0000ff]([/color]b[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff][[/color]high[color=#0000ff]-[/colo
r]1[color=#0000ff]][/color][color=#0000ff]=[/color]game[color=#0000ff]([/color]a[color=#0000ff],[/color]low[color=#0000ff],[/color]high[color=#0000ff]-[/color]1[color=#0000ff])[/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]else[/b][/color]
temp2[color=#0000ff]=[/color]a[color=#0000ff][[/color]high[color=#0000ff]][/color][color=#0000ff]+[/color]b[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff][[/color]high[color=#0000ff]-[/color]1[color=#0000ff]][/color][color=#0000ff];[/color]
#else
temp1[color=#0000ff]=[/color]a[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff]+[/color]game[color=#0000ff]([/color]a[color=#0000ff],[/color]low[color=#0000ff]+[/color]1[color=#0000ff],[/color]high[color=#0000ff])[/color][color=#0000ff];[/color]
temp2[color=#0000ff]=[/color]a[color=#0000ff][[/color]high[color=#0000ff]][/color][color=#0000ff]+[/color]game[color=#0000ff]([/color]a[color=#0000ff],[/color]low[color=#0000ff],[/color]high[color=#0000ff]-[/color]1[color=#0000ff])[/color][color=#0000ff];[/color]
#endif
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color]
[color=#800000][b]return[/b][/color] a[color=#0000ff][[/color]low[color=#0000ff]][/color][color=#0000ff]*[/color]2[color=#0000ff];[/color]
[color=#800000][b]return[/b][/color] [color=#0000ff]([/color]temp1[color=#0000ff]>[/color]temp2[color=#0000ff]?[/color]temp1[color=#0000ff]:[/color]temp2[color=#0000ff])[/color][color=#0000ff]*[/color]2[color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]void[/color] blank[color=#0000ff]([/color][color=#5000a0]int[/color] [color=#008000]size[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#5000a0]int[/color] i[color=#0000ff],[/color]j[color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]1[color=#0000ff];[/color]i[color=#0000ff]<[/color][color=#0000ff]=[/color][color=#008000]size[/color][color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]j[color=#0000ff]=[/color]1[color=#0000ff];[/color]j[color=#0000ff]<[/color][color=#0000ff]=[/color][color=#008000]size[/color][color=#0000ff];[/color]j[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
b[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff][[/color]j[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]-[/color]1[color=#0000ff];[/color]
[color=#0000ff]}[/color]
[/color]
[[i] 本帖最后由 足兆叉虫 于 11月30日 20:48 编辑 [/i]]
足兆叉虫 11月30日 20:30
第三题C语言描述(动态规划+高精)
[color=#000000][color=#008000][b]#include[/b][/color] [color=#0000ff]<[/color]stdio[color=#0000ff].[/color]h[color=#0000ff]>[/color]
[color=#008000][b]#include[/b][/color] [colo
r=#0000ff]<[/color]stdlib[color=#0000ff].[/color]h[color=#0000ff]>[/color]
[color=#008000][b]#define[/b][/color] INFILE [color=#ff00ff]"game.in"[/color]
[color=#008000][b]#define[/b][/color] OUTFILE [color=#ff00ff]"game.out"[/color]
[color=#008000][b]#define[/b][/color] SIZE 80
[color=#008000][b]#define[/b][/color] BIG 10
[color=#008000][b]#define[/b][/color] BASE 100000
[color=#ff8000][b]void[/b][/color] game[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] a[color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]BIG[color=#0000ff]][/color][color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]result[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] m[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#ff8000][b]void[/b][/color] add[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]a[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]b[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]c[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#ff8000][b]void[/b][/color] copy[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]a[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]b[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#ff8000][b]int[/b][/color] compare[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]a[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]b[color=#0000ff])[/color][color=#0000ff];[/color]
main[color=#0000ff]([/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#ff8000][b]int[/b][/color] a[color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]BIG[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]{[/color]0[color=#0000ff]}[/color][color=#0000ff];[/color]
[color=#ff8000][b]int[/b][/color] n[color=#0000ff],[/color]m[color=#0000ff];[/color]
[color=#ff8000][b]int[/b][/color] i[color=#0000ff],[/color]j[color=#0000ff],[/color]k[color=#0000ff],[/color]l[color=#0000ff];[/color]
[color=#ff8000][b]int[/b][/color] result[color=#0000ff][[/color]BIG[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]{[/color]0[color=#0000ff]}[/color][color=#0000ff];[/color]
FILE [color=#0000ff]*[/color]in[color=#0000ff],[/color][color=#0000ff]*[/color]out[color=#0000ff];[/color]
in[color=#0000ff]=[/color]fopen[color=#0000ff]([/color]INFILE[color=#0000ff],[/color][color=#ff00ff]"r"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
out[color=#0000ff]=[/color]fopen[color=#0000ff]([/color]OUTFILE[color=#0000ff],[/color][color=#ff00ff]"w"[/color][color=#0000ff])[/color][color=#0000ff];[/color]
fscanf[color=#0000ff]([/color]in[color=#0000ff],[/color][color=#ff00ff]"%d %d"[/color][color=#0000ff],[/color][
color=#0000ff]&[/color]n[color=#0000ff],[/color][color=#0000ff]&[/color]m[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]k[color=#0000ff]=[/color]1[color=#0000ff];[/color]k[color=#0000ff]<[/color][color=#0000ff]=[/color]n[color=#0000ff];[/color]k[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]l[color=#0000ff]=[/color]1[color=#0000ff];[/color]l[color=#0000ff]<[/color][color=#0000ff]=[/color]m[color=#0000ff];[/color]l[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
fscanf[color=#0000ff]([/color]in[color=#0000ff],[/color][color=#ff00ff]"%d"[/color][color=#0000ff],[/color][color=#0000ff]&[/color]a[color=#0000ff][[/color]l[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff];[/color]
game[color=#0000ff]([/color]a[color=#0000ff],[/color]result[color=#0000ff],[/color]m[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]BIG[color=#0000ff]-[/color]1[color=#0000ff];[/color]i[color=#0000ff]>[/color]0[color=#0000ff]&[/color][color=#0000ff]&[/color]result[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]=[/color]0[color=#0000ff];[/color]i[color=#0000ff]-[/color][color=#0000ff]-[/color][color=#0000ff])[/color][color=#0000ff];[/color]
fprintf[color=#0000ff]([/color]out[color=#0000ff],[/color][color=#ff00ff]"%d"[/color][color=#0000ff],[/color]result[color=#0000ff][[/color]i[color=#0000ff]-[/color][color=#0000ff]-[/color][color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]while[/b][/color][color=#0000ff]([/color]i[color=#0000ff]>[/color][color=#0000ff]=[/color]0[color=#0000ff])[/color]
[color=#0000ff]{[/color]
fprintf[color=#0000ff]([/color]out[color=#0000ff],[/color][color=#ff00ff]"%05d"[/color][color=#0000ff],[/color]result[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff];[/color]
i[color=#0000ff]-[/color][color=#0000ff]-[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#ff8000][b]void[/b][/color] game[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] a[color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]BIG[color=#0000ff]][/color][color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]result[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] m[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#ff8000][b]int[/b][/color] i[color=#0000ff],[/color]j[color=#0000ff];[/color]
[color=#ff8000][b]int[/b][/color] b[color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]
2[color=#0000ff]][/color][color=#0000ff][[/color]SIZE[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]BIG[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]{[/color]0[color=#0000ff]}[/color][color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]0[color=#0000ff];[/color]i[color=#0000ff]<[/color]SIZE[color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]j[color=#0000ff]=[/color]1[color=#0000ff];[/color]j[color=#0000ff]+[/color]i[color=#0000ff]<[/color][color=#0000ff]=[/color]m[color=#0000ff];[/color]j[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#ff8000][b]int[/b][/color] temp1[color=#0000ff][[/color]BIG[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]{[/color]0[color=#0000ff]}[/color][color=#0000ff],[/color]temp2[color=#0000ff][[/color]BIG[color=#0000ff]][/color][color=#0000ff]=[/color][color=#0000ff]{[/color]0[color=#0000ff]}[/color][color=#0000ff];[/color]
add[color=#0000ff]([/color][color=#0000ff]&[/color]a[color=#0000ff][[/color]j[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff],[/color][color=#0000ff]&[/color]b[color=#0000ff][[/color]j[color=#0000ff]+[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]j[color=#0000ff]+[/color]i[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff],[/color]temp1[color=#0000ff])[/color][color=#0000ff];[/color]
add[color=#0000ff]([/color][color=#0000ff]&[/color]a[color=#0000ff][[/color]j[color=#0000ff]+[/color]i[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff],[/color][color=#0000ff]&[/color]b[color=#0000ff][[/color]j[color=#0000ff]][/color][color=#0000ff][[/color]j[color=#0000ff]+[/color]i[color=#0000ff]-[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff],[/color]temp2[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]compare[color=#0000ff]([/color]temp1[color=#0000ff],[/color]temp2[color=#0000ff])[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
add[color=#0000ff]([/color]temp1[color=#0000ff],[/color]temp1[color=#0000ff],[/color]temp1[color=#0000ff])[/color][color=#0000ff];[/color]
copy[color=#0000ff]([/color]temp1[color=#0000ff],[/color][color=#0000ff]&[/color]b[color=#0000ff][[/color]j[color=#0000ff]][/color][color=#0000ff][[/color]j[color=#0000ff]+[/color]i[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#800000][b]else[/b][/color]
[c
olor=#0000ff]{[/color]
add[color=#0000ff]([/color]temp2[color=#0000ff],[/color]temp2[color=#0000ff],[/color]temp2[color=#0000ff])[/color][color=#0000ff];[/color]
copy[color=#0000ff]([/color]temp2[color=#0000ff],[/color][color=#0000ff]&[/color]b[color=#0000ff][[/color]j[color=#0000ff]][/color][color=#0000ff][[/color]j[color=#0000ff]+[/color]i[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
add[color=#0000ff]([/color]result[color=#0000ff],[/color][color=#0000ff]&[/color]b[color=#0000ff][[/color]1[color=#0000ff]][/color][color=#0000ff][[/color]m[color=#0000ff]][/color][color=#0000ff][[/color]0[color=#0000ff]][/color][color=#0000ff],[/color]result[color=#0000ff])[/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#ff8000][b]void[/b][/color] add[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]a[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]b[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]c[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#ff8000][b]int[/b][/color] temp[color=#0000ff]=[/color]0[color=#0000ff];[/color]
[color=#ff8000][b]int[/b][/color] i[color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]0[color=#0000ff];[/color]i[color=#0000ff]<[/color]BIG[color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
c[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]=[/color]a[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]+[/color]b[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]+[/color]temp[color=#0000ff];[/color]
temp[color=#0000ff]=[/color]c[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]/[/color]BASE[color=#0000ff];[/color]
c[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]=[/color]c[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]%[/color]BASE[color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#ff8000][b]void[/b][/color] copy[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]a[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]b[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#ff8000][b]int[/b][/color] i[color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]0[color=#0000ff];[/color]i[color=#0000ff]<[/color]BIG[color=#0000ff];[/color]i[color=#0000ff]+[/color][color=#0000ff]+[/color][color=#0000ff])[/color]
[color=#0000ff]{[/color]
b[color=#0000ff][[/color
]i[color=#0000ff]][/color][color=#0000ff]=[/color]a[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff];[/color]
[color=#0000ff]}[/color]
[color=#0000ff]}[/color]
[color=#ff8000][b]int[/b][/color] compare[color=#0000ff]([/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]a[color=#0000ff],[/color][color=#ff8000][b]int[/b][/color] [color=#0000ff]*[/color]b[color=#0000ff])[/color]
[color=#0000ff]{[/color]
[color=#ff8000][b]int[/b][/color] i[color=#0000ff];[/color]
[color=#800000][b]for[/b][/color][color=#0000ff]([/color]i[color=#0000ff]=[/color]BIG[color=#0000ff]-[/color]1[color=#0000ff];[/color]i[color=#0000ff]>[/color][color=#0000ff]=[/color]0[color=#0000ff];[/color]i[color=#0000ff]-[/color][color=#0000ff]-[/color][color=#0000ff])[/color]
[color=#800000][b]if[/b][/color][color=#0000ff]([/color]a[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]>[/color]b[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff])[/color]
[color=#800000][b]return[/b][/color] 1[color=#0000ff];[/color]
[color=#800000][b]else[/b][/color] [color=#800000][b]if[/b][/color][color=#0000ff]([/color]b[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff]>[/color]a[color=#0000ff][[/color]i[color=#0000ff]][/color][color=#0000ff])[/color]
[color=#800000][b]return[/b][/color] 0[color=#0000ff];[/color]
[color=#800000][b]return[/b][/color] 0[color=#0000ff];[/color]
[color=#0000ff]}[/color][/color]