很明显我是想发提高组合集的。普及组考纲……用发么。
当然如果你想看的话也可以,就一点点:
递归、排序……
很明显上面那都不是重点。普及组只要掌握搜索、二分、单调队列、数学、随机化等等,一等奖没问题的,但是要想AK普及组题目的话也不是那么容易,这得有熟练的调试和查细节能力才行。比如noip2017普及组的t3,你可能顺手打个搜索就过了但是忘了右下角终点是白格子的情况,从而痛失50分。总之普及组拿一等奖很容易,练过一年编程的相信都没问题(当然你是认真学),但要AK就得提高编程水平了,一般等你拿了省一(提高组一等奖)之后才能AK普及组题目(但如果你是dalao就请无视这句话)
普及组考点不多,基本考代码能力和数学知识,而提高组才考真正有水平的算法。因此大家一般以省一为目标。那么就得掌握提高组在各方面的考点了。
结尾处有卡时等OIer随身技巧。
D1T1(Day1 第1题)
众所周知d1t1一般都会考简单的模拟或数学知识。下面我列一下所有可能考到的知识:
1.模拟
略。很多年的d1t1都是模拟,不会的话请自觉回普及组补习。
2.数学知识
略。noip2017的d1t1就是靠数学知识(答案是ab-a-b的那题),这种题只能靠背小学奥数知识或者推结论,如果无法推出结论就手玩(自觉理解“手玩”)。
(您要是想看这题的题解请点跳转)
D1T2
d1t2的考点比较杂,一般情况下都考简单算法,当然也有天天爱跑步这样高难度的题。
1.搜索(DFS?BFS?)
noip可是哪里都有搜索的!这个位置的题当然可以选择打搜索。但是一定要注意一个事情,那就是搜索≠暴力,不要把两种说法弄混了!
这里为了节省篇幅,不说方法,只弄一个样题。
【样题】noip2015 信息传递
传送门:
题解:按照题意把玩家之间的传递信息弄成有向边,无权值。本题就变成了求最小环(点数最少的环)的问题。从每个环中的任意一点出发跑dfs即可。
#include#include #include #define maxn 200010using namespace std;inline int read(){ int x=0;bool f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=0; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; if(!f) return 0-x; return x;}int to[maxn],fa[maxn],dfn[maxn],vis[maxn],n,huancnt,ans=2147483647;int dfs(int cur,int cnt){ if(dfn[cur]){ if(vis[cur]==huancnt) return cnt-dfn[cur];//记录该环的大小(环外的毛不算) else return 2147483647;//vis标记不在本轮中,说明跑到其它环去了,不更新答案 } vis[cur]=huancnt; dfn[cur]=cnt; return dfs(to[cur],cnt+1);}int main(){ n=read(); int i; for(i=1;i<=n;i++) to[i]=read(); for(i=1;i<=n;i++){ if(dfn[i]) continue;//已经访问过 huancnt++,ans=min(ans,dfs(i,1)); } printf("%d",ans); return 0;}