出题人：钟惠兴
| 题目名称 | 讨厌整除的小明 | 吸血鬼 | 鱼的感恩 |
| 题目类型 | 传统型 | 传统型 | 传统型 |
| 题目目录/可执行文件名 | ming | vamp | fool |
| 输入文件名 | ming.in | vamp.in | fool.in |
| 输出文件名 | ming.out | vamp.out | fool.out |
| 每个测试点时限 | 1s | 1s | 1s |
| 内存限制 | 512m | 512m | 512m |
| 测试点数目 | 10 | 10 | 10 |
| 每个测试点分值 | 10 | 10 | 10 |
讨厌整除的小明
小明作为一个数学迷，总会出于数字的一些性质喜欢上某个数字，然而当他喜欢数字k的时候，却十分讨厌那些能够整除k而比k小的数，认为那些数会分解数字k从而破坏掉k的美感……
有一天，他想：如果所有人都和自己一样，那么是不是喜欢两个含有倍数关系的不同数字的人就不能做朋友了？于是他想，至少用多少个集合，才能包括1到n的所有n个整数，使得所有存在倍数关系的两个不同数字在不同的集合里面？
小明脑子不好使，于是把问题交给了你。
输入格式
第一行一个数字q，表示询问次数
接下来q行，每一行一个数字n，表示问题中的n。
输出格式
共q行，每行一个数字，表示数字n对应的问题的答案。
| 输入输出样例 | 样例一 | 样例二 | 样例三 |
| 输入 | 1 5 | 2 7 10 | 2 1 200 |
| 输出 | 3 | 3 4 | 1 8 |
样例一解释
其中一种方案是{1}{2,5}{3,4}。
数据范围
| 数据编号 | q | n | 数据编号 | q | n |
| 1 | 1 | <=20 | 6 | 300 | <=5,000,000 |
| 2 | 3 | <=20 | 7 | 1,600 | <=1016 |
| 3 | 10 | <=2,000 | 8 | 10,000 | <=1016 |
| 4 | 20 | <=2,000 | 9 | 60,000 | <=1016 |
| 5 | 60 | <=5,000,000 | 10 | 100,000 | <=1016 |
对于前60%数据，所有n的和不超过30,000,000。
对于所有数据，n>=1。
注意输入规模对运行时间的影响。
考场脑洞:傻逼题，水水水水水水过
其实正解是二分答案。。。0.0 但是除以二，貌似...没问题？
#include#include #include #define ll long longusing namespace std;ll q,n,ans;inline ll init(){ ll x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int main(){ freopen("ming.in","w",stdin); freopen("ming.out","r",stdout); q=init(); while(q--) { n=init();ans=0; while(n) { ans++;n/=2; } printf("%d\n",ans); } fclose(stdin);fclose(stdout); return 0;}
吸血鬼
吸血鬼们总是喜欢吸取人的血液，这一次，n个吸血鬼决定到h市吸取血液，但当他们进入h市准备血的狂欢的时候，却发现h市充满雾霾，他们找不着路，还彼此走散了……
当下之急自然是找到彼此，重新汇合商量对策。刚进来的时候，吸血鬼失去了彼此的联系。他们决定用血建立直接的联系，这种联系不会因为h市的雾霾而中断，且能够及时地传递信息。在吸血鬼寻找彼此的时候，任意2个吸血鬼可能会恰巧碰面，并且建立血的联系，除非在碰面以前他们就已经有直接或间接的联系了。如果将吸血鬼抽象成节点，那么任意2个节点之间可能会建立一条边，除非这2个节点已经连通。
我们知道，经过足够长的时间以后，吸血鬼们通过m次碰面，已经全部连在一起，并成功地洗劫了h市。
但是，假设吸血鬼按照地位给予从1到n的编号，我们还想要知道，在这个过程中以血的联系构建的通信网络中，编号1的大佬联络每个吸血鬼各需要经过多少个其他吸血鬼。
输入格式
第一行2个数字n,m，为题目中对应的意义。
接下来m行，由于上帝在整理时间轴的问题上偷懒了，所以给出来的n次碰面没有按照时间顺序排序。
每行3个整数，t,u,v，表示在时刻t，编号为u和v的吸血鬼碰面了。
保证时刻t互不相同。且到最后吸血鬼总能够直接或间接地联络其他所有吸血鬼。
数字之间以空格隔开。
输出格式
输出m-1行，每行一个数字，第i行的数字表示从1号吸血鬼联络i+1号吸血鬼需要多少个其他吸血鬼，如果直接相连，输出0。
| 输入样例 | 输出样例 |
| 5 6 1 2 10 3 5 7 2 5 2 1 5 19 3 2 5 4 5 13 | 0 1 2 1 |
样例解释
一开始每个点不连通，在时刻2，2号和5号碰面并建立联系，在时刻5，2号和3号碰面并建立联系，在时刻7，3号和5号碰面，然而它们已经可以互相联络，故不需要建立联系，之后建立联系的依次还有1号和2号，4号和5号。因此1号能够直接联系2号，但是联系4号必须依次经过2号和5号。
数据范围
| 数据编号 | n | m | 数据编号 | n | m |
| 1 | 5 | 6 | 6 | 30000 | 50000 |
| 2 | 100 | 300 | 7 | 50000 | 80000 |
| 3 | 500 | 800 | 8 | 100000 | 160000 |
| 4 | 1000 | 5000 | 9 | 200000 | 199999 |
| 5 | 20000 | 30000 | 10 | 300000 | 500000 |
考场脑洞:按时间排序+并查集维护+建图+以1为根dfs处理深度(1s好像悬)
#include#include #include #include #define maxn 500005using namespace std;int fa[maxn],deep[maxn],head[maxn],vis[maxn];int cnt,num,n,m,ans,x,y,t;struct edge{ int u,v,next;}e[maxn<<1];struct node{ int x,y,t;}a[maxn<<1];inline int init(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}inline void add(int u,int v){ e[++num].v=v;e[num].next=head[u];head[u]=num;}int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]);}bool cmp(node a,node b){ return a.t
正解:最小生成树+bfs
#include#include #include #include #include using namespace std;struct E { int u,v,t; };E ed[500010];int next[600010],to[600010];int fir[300010],ans[300010],from[300010];int rk[300010],fa[300010];int q[300010];int n,m,i,e,h,t,u;int edges;int tu,tv;bool cmp(const E &a,const E &b){ return a.t
鱼的感恩
从前有一个渔夫抓到了一条特别的鱼，放走了。
渔夫再次抓到了这条鱼，正要再次放走之时，这条鱼吐出了一片迷雾，迷雾散去以后，渔夫不见了。
渔夫睁开眼，发现自己到了一个石碑面前，碑上有一行小写英文字符串S，下面写着：“汝等既有护生之念，应是善良之人，理当授以嘉奖。但是为了证明你的善良，你需要展现你的智慧，以确保吾所见之善良，并非出于汝之愚笨。上面的字符串，你若于其中找到最长的子串，使得这个子串既出现在前缀，又出现在后缀，还出现在字符串的中间，也就是既非前缀又非后缀的位置，则该石碑会将其所藏之物拱手相送。”
渔夫听完以后，可谓一脸懵逼，遂将这个问题分享给你，希望你能够解决。若能解决，渔夫愿意拿出10,000,000,000,000 mod 250 元，作为解决这个问题的报酬。
输入格式
第一行是一个数字q，表示这个问题有q组不同问题。
接下来q行每行一个由小写英文字母组成的字符串S，意义见于上文。
输出格式
输出共q行，每行一个字符串，表示对于每组问题，所求的字符串，如果不存在长度大于0且满足要求的字符串，就改成输出”---”（不包含引号）
| 输入样例 | 1 niconiconi | 2 abcdabc ababacaba |
| 输出样例 | ni | --- aba |
| 样例解释 | ni既是字符串的前缀，还是字符串的后缀，而且在字符串的中间(字符串第5位开始)也能找到ni | 第一个字符串不存在这样的子串，而aba除了前缀和后缀以外从第3位开始也能找到，也就是说允许和前后缀部分重叠。 |
数据范围
设n为测试点中单个S的长度的最大值，m为测试点中S的长度之和。
前10%的数据，q<=10，n<=100，m<=1,000
前30%的数据，q<=30，n<=500，m<=15,000
前50%的数据，q<=100，n<=2,000，m<=200,000
所有数据，q<=200,000，n<=100,000，m<=10,000,000
考场脑洞:正解一定非hash！(好吧是我写的不熟练),然后一眼秒过;这不是kmp的next数组么(又秒了一道题好开心。。。)
然后就开始写写写...2h+并没有写出来，漏洞百出...然后考完后就迷茫了......是不是自己还是太弱了！！！！！！！
唉，最后究其根本是...自己不会输出一部分字符串......所以就只能奇技淫巧不断向前找next，然后不会处理呀....光荣暴0......
其实只需要在后面插个'0'然后printf就好了......
#include#include #include #include #include using namespace std;int n,i,j,q,ti;int next[200010];char st[200010];int getstr(char *st){ int ret=0; st[0]=getchar(); while (st[0]<'a'||st[0]>'z') st[0]=getchar(); while (st[ret]>='a'&&st[ret]<='z') st[++ret]=getchar(); st[ret]='\0'; return ret;}int main(){ freopen("fool10.in","r",stdin); freopen("fool10.out","w",stdout); scanf("%d",&q); for (ti=1;ti<=q;ti++) { n=getstr(st+1); next[0]=-1; next[1]=0; j=0; for (i=2;i<=n;i++) { while (j>=0&&st[i]!=st[j+1]) j=next[j]; next[i]=++j; } for (i=1;i
期望得分:100+90+100=290实际得分:ZERO我是不是很萌......首先是以后freopen再打反就剁手......然后是基础知识不牢！回去一本通补起来(回炉重修)......最后是关于时间复杂度不大会算这个事......哪位大佬救救我？这次题这么简单，noip哪里会有这样的题？！！！！这么简单都不能拿到手，更别说难题了！！！还有一个问题一定注意：如果感觉自己没有十足把握写出这道题，那就打暴力！！！！！！！！！！！！！！！！！！！！！！！！！！！要养成这个习惯！还要养成对牌的习惯(回去开始练)！自己所做的每一道题的得分都有可能是noip考场得分！切记不可疏忽！！