题1 ： Orchestra
题意：
给你一个 n*m 的矩阵，其中有一些点是被标记过的。
现在让你求标记个数大于 k 个的二维区间个数。
n、m 、k 最大是 10 。
分析：
part 1：
10 的范围 ，直接暴力 $O(n^{6})$ 也能过，
具体就是枚举区间的上边界、下边界、左边界、右边界，然后暴力累加这个区间内所有的标记点个数。
代码不给出（因为比 part 2 的代码还长）。
part 2：
（考虑的是算法的优化，可以选择性看）
我们可以考虑用矩阵前缀和优化。
前缀和就是记录从开头到某个位置上所有值的和，这个大家应该都知道。
那么二维其实就是记录从开头（一般是 ($1,1$)）到某个位置（比如 ($i,j$)）上所有值的和。
这个可以看代码领会（其中 $val[i][j]$ 表示当前点是否被标记）：
for(int i=;i<=n;++i) for(int j=;j<=m;++j)
mp[i][j]=val[i][j]+mp[i-][j]+mp[i][j-]-mp[i-][j-];
这里 我们假设 $ mp[i-1,j],mp[i][j-1],mp[i-1][j-1] $ 已经处理好了，那么 $mp[i-1][j], mp[i][j-1], mp[i-1][j-1]$ 与 mp[i][j] 的关系如下：
那么我们要求某个矩形区间的标记点个数的办法也是差不多的。
比如要求出 u,l 到 d,r 这段区间 的标记点数量，那么答案就是： mp[d][r]+mp[u-1][l-1]-mp[u-1][r]-mp[d][l-1].
代码如下：
//by Judge
#include<cstdio>
#include<iostream>
using namespace std;
const int M=;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[<<],*p1=buf,*p2=buf;
inline int read(){ int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
} int n,m,c,k,ans,mp[M][M];
inline int check(int l,int r,int u,int d){
return mp[d][r]+mp[u-][l-]-mp[u-][r]-mp[d][l-];
}
int main(){
n=read(),m=read(),
c=read(),k=read();
for(int i=,x,y;i<=c;++i)
x=read(),y=read(),++mp[x][y];
for(int i=;i<=n;++i) for(int j=;j<=m;++j)
mp[i][j]+=mp[i-][j]+mp[i][j-]-mp[i-][j-]; for(int u=;u<=n;++u) for(int d=u;d<=n;++d)
for(int l=;l<=m;++l) for(int r=l;r<=m;++r)
if(check(l,r,u,d)>=k) ++ans; return printf("%d\n",ans),;
}
part 3:
（分析过度，不宜观看）
这道题的数据有点小啊？如果说是100 的范围呢？（1000的话可能过大了，不过应该也不是没办法解）
我们可以观察这区间之间的单调性：
假设我们固定了边界：r、u、d 作为右边界、上边界和下边界，那么左边界越靠左，整个区间所会包含的标记点是单调不减的。
然后这里就要用二分，如果你想知道具体内容的话就 Q 我吧（不要羞涩，撩就行了），我懒得写了。
代码也不给出了（作者懒癌晚期）
评价：
大水题，应该拿满分。
题2 ： 质数
题意：
让你求一个区间范围内满足条件的数的个数，询问有多组。
其中满足条件的数为：1.质数； 2.两个质数的乘积
分析：
只要你学过筛质数的话，这道题应该十分钟过的，又没什么套路。
筛质数的话建议用欧拉筛法（关于欧拉，他非常牛皮，很多数论算法都是他发明的，可自行了解）
题目没什么亮点，就是筛完质数后预处理一下前缀信息，询问的时候O(1) 回答就好了
代码如下：
//by Judge
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int M=1e7+;
const int MX=1e7;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[<<],*p1=buf,*p2=buf;
inline int read(){ int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
} char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x,char chr='\n'){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]=chr;
} int T,cnt,f[M],is[M],in[M],prim[M];
inline void prep(){ is[]=;
for(int i=;i<=MX;++i){
if(!is[i]) prim[++cnt]=i,in[i]|=;
for(int j=;j<=cnt&&i*prim[j]<=MX;++j){
is[i*prim[j]]|=;
if(!is[i]) in[i*prim[j]]|=;
if(i%prim[j]==) break;
}
}
}
int main(){
T=read(),prep();
for(int i=;i<=MX;++i)
f[i]=f[i-]+in[i];
for(int l,r;T;--T)
l=read(),r=read(),
print(f[r]-f[l-]);
return Ot(),;
}
评价：
没什么难度的，最好 A 掉，起步 90 分（话说这题不卡常，基本只有 0 和 100 ）
题3 ：Hanoi Factorys
题意：
几个空心环，让你依次叠高，要求下面的外径比上面的大，且内径下小上大，求最大高度。
分析：
这题有点鬼畜，还好之前打过直接 A 了。
但其实没什么难的，首先维护外径单调递增，外径相同比较内径，内径大的放下面，
为什么外径相同则内径大的放下面？
因为这样能保证上面的环内径小，那么就能容纳外径更小的环。
然后单调栈求解。
想学单调栈的看看这篇博客（顺便可以把单调队列学了）：click here
然后刷一下这些题目就差不多会了：click here
//by Judge
1 #include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#define P make_pair
#define ll long long
using namespace std;
const int M=1e6+;
const int inf=1e9;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
int n,head=,tail;
priority_queue< pair<ll,ll> > q;
ll res=-inf;
struct Node{
ll a,b,h;
friend bool operator < (const Node& x,const Node& y){
return x.b!=y.b ? x.b>y.b : x.a>y.a; //b相同则先放a大的汉诺块
}
}p[M]; int main(){
n=read();
for(int i=;i<n;++i)
p[i].a=read(),
p[i].b=read(),
p[i].h=read();
sort(p , p+n); for(int i=;i<n;++i){
ll tmp=p[i].h;
while(!q.empty() && q.top().second>=p[i].b)
q.pop();
if(!q.empty()) tmp+=q.top().first;
q.push(P(tmp,p[i].a));
res=max(res , tmp);
}
cout<<res<<endl;
return ;
}
评价：
没 A 掉？没关系，抓紧在剩下的时间提升自己，为战斗做准备，拿个 50+ 的暴力分差不多，最好当然是 A 掉。
结论：
OI 选手还是多学点算法的好。
题4 ：Distinct Paths
题意：
题意有点绕，就是让你求出一个矩阵中满足条件的方案数。
条件是：对于从 1,1 到 n,m 的任意一条路径，使得路径上的点的颜色互不相同。
难点在于：有些点的颜色已经给出。
如果所有的点的颜色都不固定，这就是道数学题。
分析：
有点复杂，不会也正常（毕竟说实话我也没有解出来_(:з」∠)_）
建议学会搜索以及简单的状压（不是状压dp，但是 状压 dp 这个东西学一下也行）
首先你要发现题目的数据范围是假的。
因为 k 很小，最大只有 10 ，只要 n+m-1 大于 k 了，那么必然不存在任意一种满足条件的方案。
这点还是不难发现的。
然后你不能太优秀。
也就是不能一开始想的是 状压dp ，否则你就会陷入无休无止的修改状态表示以及思考状态转移之中。。。（好吧我就是这样耗了一个多小时）
其次你要会搜索。
这里搜索+剪枝才是本题正确打开方式。
另外 noip 普及一般都有搜索题，而且爆搜适用于任何题目的骗分，如果加了剪枝或者记忆化之类的那就基本是正解
最后你要会剪枝。
这道题的亮点，各种鬼畜剪枝。
搜索题，基本考的是剪枝，就算不考剪枝，大多也是可以用剪枝卡时间的。
（卡时间真的非常重要，你怎么知道一个小小的剪枝会不会神奇让你分数过线？）
代码如下：
//by Judge
#include<cstdio>
#include<iostream>
using namespace std;
const int M=(<<)|;
const int mod=1e9+;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[<<],*p1=buf,*p2=buf;
inline int read(){ int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
} int n,m,K,mp[][],cant[][],vis[];
inline void MOD(int& a){ if(a>mod) a-=mod; }
#define lowbit(x) (x&-x)
int dfs(int x,int y){
if(y>m) y=,++x;
if(x>n) return ;
cant[x][y]=cant[x-][y]|cant[x][y-];
int dx=x,dy=y+,num=;
int S=cant[x][y],T=cant[x][y];
while(S) S-=lowbit(S),++num;
if(K-num<n+m-x-y+) return ; int ans=,tmp=-;
for(int i=;i<=K;++i){
if((T>>i-)&) continue;
if(!mp[x][y]||mp[x][y]==i){
cant[x][y]=T|(<<i-),++vis[i];
if(vis[i]==) ans+=(tmp>=?tmp:tmp=dfs(dx,dy));
else ans+=dfs(dx,dy); MOD(ans),--vis[i];
}
} return ans;
}
int main(){
n=read(),m=read(),K=read();
if(n+m->K) return puts(""),;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j){
mp[i][j]=read();
++vis[mp[i][j]];
}
printf("%d\n",dfs(,));
return ;
}
作为搜索 A 掉了去年普及第三题的 OI 选手，没有A掉这题，我只能说，老了。
评价：
略（guo）显（fen）毒瘤，拿个暴力分（这个好像没有）。。。额，能拿多少是多少，越多越好
结论：
搜索很重要！
一等水平估计：
240总有吧？ （看在t4比较毒瘤的份上，不然肯定300+）