关键词：
北京中关村；海淀黄庄；北京大学；清华大学。少儿编程；中小学编程；信息学竞赛；计算机竞赛；NOIP竞赛；CSP-J/S竞赛；NOI竞赛。2006年、提高组、复赛，第12届。
A、试题类型：
算法考虑。
B、算法模型：
STL。
C、试题说明：
石子合并成环形，考虑将珠子剪开，将原有的序列变为两倍，例如：1，2，3，4 可以展成 1，2，3，4，3，2，1，用 dp[i][j] 表示合并区间 i 到 j 的最大能量。
第一重循环表示珠子分组的终点，第二重循环的表示从珠子分组的起点 ，第三重循环表示截断的点就可以。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 201
#define MOD 10007
#define E 1e-6
#define LL long long
using namespace std;
LL a[N];
LL dp[N][N];
int main()
{
int n;
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
memset(dp,0,sizeof(dp));
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=2*n;i++)
{
int j=len+i-1;
for(int k=i;k<j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
}
}
LL maxx=0;
for(int i=1;i<=n;i++)
maxx=max(maxx,dp[i][i+n-1]);
cout<<maxx<<endl;
}
return 0;
}
A、试题类型：
复合考察。
B、算法模型：
动态规划与背包应用。
C、试题说明：
首先，题目描述中说所有价格都是10的整数倍，所以在读入数据的时候就可以直接除以十，输出答案时再乘回来即可（防止超时超空间）。
状态设定：f[i]表示重量还剩i时所能取得的最大价值。
每个物品的价格就是重量，其重要度imp[i]乘以价格pri[i]就是价值。
对于每一件主件Mi会有不超过2件的附件，所以枚举每个附件是否购买即可。
那么就会有四个转移方程:
dp[j]=max(dp[j-w[mitem[i]]]+v[mitem[i]],dp[j]);//只取主件
dp[j]=max(dp[j-w[mitem[i]]-w[item[mitem[i]][1]]]+v[mitem[i]]+v[item[mitem[i]][1]],dp[j]);//取一号附件
dp[j]=max(dp[j-w[mitem[i]]-w[item[mitem[i]][2]]]+v[mitem[i]]+v[item[mitem[i]][2]],dp[j]);//取二号附件
dp[j]=max(dp[j-w[mitem[i]]-w[item[mitem[i]][1]]-w[item[mitem[i]][2]]]+v[mitem[i]]+v[item[mitem[i]][1]]+v[item[mitem[i]][2]],dp[j]);//两个附件都取
mitem[i]表示第i个主件的编号，item[mitem[i]][j]表示第i个主件的第j个附件的编号。
#include<cstdio>
#include<iostream>
#include<ctime>
#include<string>
#include<algorithm>
#include<cmath>
#define maxn 100000
#define maxm 100000
#define inf 99999999
using namespace std;
int item[maxn][5];
int mitem[maxn];
int dp[maxn];
int w[maxn],v[maxn];
int n,m,mcnt,maxx;
int main()
{
scanf("%d%d",&n,&m);
n/=10;
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c==0)
{
mitem[++mcnt]=i;
w[i]=a/10;
v[i]=a*b/10;
}
else
{
item[c][++item[c][0]]=i;
w[i]=a/10;
v[i]=a*b/10;
}
}
for(int i=1;i<=mcnt;i++)
{
for(int j=n;j>=0;j--)
{
if(j-w[mitem[i]]>=0)
dp[j]=max(dp[j-w[mitem[i]]]+v[mitem[i]],dp[j]);
if(item[mitem[i]][1]&&j-w[mitem[i]]-w[item[mitem[i]][1]]>=0)
dp[j]=max(dp[j-w[mitem[i]]-w[item[mitem[i]][1]]]+v[mitem[i]]+v[item[mitem[i]][1]],dp[j]);
if(item[mitem[i]][2]&&j-w[mitem[i]]-w[item[mitem[i]][2]]>=0)
dp[j]=max(dp[j-w[mitem[i]]-w[item[mitem[i]][2]]]+v[mitem[i]]+v[item[mitem[i]][2]],dp[j]);
if(item[mitem[i]][1]&&item[mitem[i]][2]&&j-w[mitem[i]]-w[item[mitem[i]][1]]-w[item[mitem[i]][2]]>=0)
dp[j]=max(dp[j-w[mitem[i]]-w[item[mitem[i]][1]]-w[item[mitem[i]][2]]]+v[mitem[i]]+v[item[mitem[i]][1]]+v[item[mitem[i]][2]],dp[j]);
}
}
for(int i=0;i<=n;i++)
maxx=max(maxx,dp[i]);
printf("%d",maxx*10);
return 0;
}
A、试题类型：
调度问题。
B、算法模型：
多数组连用。
C、试题说明：
无。
#include <cstdio>
int n, m, sx[ 405 ], cnt[ 25 ], t[ 25 ][ 25 ], j[ 25 ][ 25 ], Time[ 25 ], Ans_;
bool f[ 25 ][ 1005 ];
//sx[]代表输入顺序，即安排顺序
//cnt[i]的值表示第i号工件执行到哪一道工序
//t[i][j]表示第i号工件第j道工序用的时间
//j[i][j]表示第i号工件第j道工序需要的机器
//Time[i]表示第i号工件上一道工序结束时间
//f[i][j]表示第i号工件的j时刻是否被用过
int main ()
{
//freopen("jsp.in", "r", stdin);
//freopen("jsp.out", "w", stdout);
scanf ("%d %d", &n, &m);
for (int i = 1; i <= m * n; i ++)
{
scanf ("%d", &sx[ i ]);
}
for (int i = 1; i <= m; i ++)
{
for (int k = 1; k <= n; k ++)
{
scanf ("%d", &j[ i ][ k ]);
}
}
for (int i = 1; i <= m; i ++)
{
for (int k = 1; k <= n; k ++)
{
scanf ("%d", &t[ i ][ k ]);
}
}
//过于复杂的输入
for (int i = 1; i <= n * m; i ++)
{
int w = j[ sx[ i ] ][ ++ cnt[ sx[ i ] ] ], T = t[ sx[ i ] ][ cnt[ sx[ i ] ] ], tot = 0, l;
//w是当前工件工序所需机器， T是当前工序所需时间， tot是当前找到的连续时间长度
for (l = Time[ sx[ i ] ] + 1; ; l ++)
{//枚举时间
if (f[ w ][ l ] == false)
{//当时间l未用过
tot ++;
if (tot == T)
{
for (int k = l - tot + 1; k <= l; k ++) {//将要用的时间置为true
f[ w ][ k ] = true;
}
break;//跳出循环
}
}
else
{
tot = 0;//由于当前连续时间少于所需，而中间有一个时间点已被用过，所以只能抛弃前段时间。
}
}
Time[ sx[ i ] ] = l;//更新结束时间
Ans_ = Ans_ < l ? l : Ans_;//更新答案
}
printf ("%d\n", Ans_);
}
A、试题类型：
进制问题。
B、算法模型：
逻辑组合问题。
C、试题说明：
题目描述中的“另一个角度”揭示答案。
这个2k进制数最多能有s=(w+k)/k位，且最高位的值不超过m=2wmodk−1。（当w可整除k时，虽然s多算了一位，但此时最高位的最大值m的值为0，不影响正确答案）。这就是条件1和条件3的含义。
就剩条件2了，它本质上是告诉递推关系。有两种思路：
第一种，用f(i,j)代表长度为i且最右边一位不超过j的数的个数，则有f(i,j)=f(i,j−1)+f(i−1,j−1)，即f(i,j) =最右边一位不是j的方案数f(i,j−1)加上最右边一位是j的方案数f(i−1,j−1)
答案ans=Σs−1i=2f[i][2k−1]+Σmi=1f[s−1][n−i]。
相当于长度小于s的最高位不超过2k−1的数的个数加上长度等于s的最高位不超过m的数的个数。
这里f[s−1][n−i]的意思是长为s的数已确定最高位为i，还剩s−1位。这些位的数字可以是(i+1,i+2,...,n)，共n−i个数，所以长为s−1，最左边为i+1而最右边不超过n的数的个数与最左边为1而最右边为n−i的数的个数相同，为f[s−1][n−i]。
第二种用组合的思想，实际上f(i,j)是一个组合数。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int M = 100000000;
int k, w;
int m, n, s;
//又一坨高精，因为只涉及加法，所以用int压8位
struct highNum
{
int num[27];
highNum(int length = 1)
{
memset(num, 0, sizeof(num));
num[0] = length;
}
highNum operator = (int b)
{
memset(num, 0, sizeof(num));
num[0] = 1; num[1] = b;
int ret = num[1] / M, iter = 1;;
while(ret != 0)
{
num[iter] %= M;
num[++iter] += ret;
ret = num[iter] / M;
}
while(num[num[0] + 1] != 0) ++num[0];
return *this;
}
highNum operator + (highNum& b) const
{
highNum c = highNum(max(num[0], b.num[0]));
for(int i = 1; i <= c.num[0]; ++i)
{
c.num[i] += num[i] + b.num[i];
c.num[i + 1] += c.num[i] / M;
c.num[i] %= M;
}
while(c.num[c.num[0] + 1] != 0)
++c.num[0];
return c;
}
};
ostream& operator << (ostream& o, highNum& b)
{
o << b.num[b.num[0]];
o.setf(ios::fixed);
for(int i = b.num[0] - 1; i >= 1; --i)
{
o.width(8); //这些东西一定要紧跟在输出之前
o.fill('0');
o << b.num[i];
}
return o;
}
highNum ans, f[600][514];
//按题意，当w=30000而k=2时，f[a][514]中的a要很大，但数据要求a不超过600（不要问我是怎么知道的）
void init()
{
cin >> k >> w;
s = (w + k) / k;
m = (1 << (w % k)) - 1;
n = (1 << k) - 1;
}
void work()
{
for(int i = 1; i <= n; ++i)
f[1][i] = i;
for(int i = 2; i <= s; ++i)
for(int j = i; j <= n; ++j)
f[i][j] = f[i - 1][j - 1] + f[i][j - 1];
for(int i = 2; i < s; ++i)
ans = ans + f[i][n];
for(int i = 1; i <= m; ++i)
ans = ans + f[s - 1][n - i];
cout << ans;
}
int main()
{
init();
work();
return 0;
}
IT航班支持----中小学编程比赛汇总：
第一部分：国内比赛(IT航班支持)
1、软件能力认证(CSP-JS)
2、全国青少年信息学奥林匹克联赛(NOIP)
3、全国青少年信息学奥林匹克竞赛(NOI)
4、中国青少年………………………
5、………………………创新挑战赛
6、全国青少年………………………
7、………………………
8、 恩欧希教育信息化发明创新奖
9、世界机器人大赛(WRC)
10、………………………大赛
11、少………………………智能教育成果展示大赛
12、“明天小小科学家”奖励活动
13、………………………
14、………………………
15、国际信息学………………………
16、………………………
第二部分：国际比赛(IT航班支持)
17、………………………
18、国际………………………
19、………………………
20、美国信息学………………………
21、加拿大………………………
22、官方邀请赛 (CCO)
23、国际计算思维………………………
24、美国计算机………………………
25、澳大利亚………………………
第三部分：企业比赛(IT航班支持)
26、微软MTA
27、………………………挑战赛
28、………………………科学奖
29、………………………学奖
30、………………………创新挑战赛
31、………………………挑战赛
32、………………………芯计算机表演赛
33、………………………大赛
第四部分：Scratch相关竞赛(IT航班支持)
34、全国中小学生电脑制作大赛
35、………………………
36、………………………
37、………………………
第五部分：其它(IT航班支持)
38、NOI夏令营
39、NOI冬令营(NOIWC)
40、全国青少年………………………
41、国际青少年………………………
联系方式：
A、官方网址：
B、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
