一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）
&1. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以（ &&）形式进行的。
&A. 二进制码 B.
八进制码 &C.
十进制码 &D.
智能拼音码 &
学过的都知道=。=
2.&下列说法正确的是（ &&）。 &
A.&CPU的主要任务是执行数据运算和程序控制
B. 存储器具有记忆能力，其中信息任何时候都不会丢失
C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同
D. 个人用户只能使用Wifi的方式连接到Internet &&
CPU包括控制器和运算器，显然它的主要任务就是A
存储器有主存和辅存，主存中有ROM和RAM，RAM在关机或停电情况下内容全部丢失
C显然不对=。=
Internet上网的几种常用连接方式：1、拨号上网2、ISDN
3、宽带上网 4.无线上网
具体了解请见百度百科：/link?url=J1MSLO-SX-LJaMTSt_-XjHCXnTMfVPZmV7lyiXo9Y1OVf_edlwQWhTisZFYGNDDrdwlA_yG1ruDep9OcyMDoaJH6JU6k1gKUoStEowhciNe
3.&与二进制小数0.1相等的十六进制数是（ &&）。
A. 0.8 B. 0.4 &C. 0.2 &D. 0.1 &&
又是送分的进制转换
&4. 下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为 十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（ &&）。
&A. 120 82 50 B. 144 100 68 &C. 300 200 C8 &D. F2 &&&
送分的进制转换，就算变了变形式我也认识你=w=
5.&线性表若采用链表存储结构，要求内存中可用存储单元地址（ &&）。
A.&必须连续 B. 部分地址必须连续
C. 一定不连续
D. 连续不连续均可
数据结构问题=w=，链表结构与顺序结构最大的不同在于链表存储地址可以不连续，便于元素的插入和删除&&&&
6.&今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈， 进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为（
A. f &B. c &C. a &D. b
学过的导一下就可以了
7.&前序遍历序列与后序遍历序列相同的二叉树为（ &&）。
A.&非叶子结点只有左子树的二叉树 B.
只有根结点的二叉树 &
C. 根结点无右子树的二叉树 D.
非叶子结点只有右子树的二叉树 &&
前序遍历：根左右，后序遍历：左右根，然后画个图试试就知道了&
8.&如果根的高度为1，具有61个结点的完全二叉树的高度为（ &&）。
A. 5 B. 6 &C. 7 &D. 8 &&&
B，学过的应该没问题，没学过的画一画、算一算应该也能过
9. 6个顶点的连通图的最小生成树，其边数为（ &&）。
A. 6 B. 5 &C. 7 &D. 4 &&&
它都是棵树了还有什么可说的=。=
10.&设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n（n为正整数）及T(0) = 1，则
该算法的时间复杂度为（ &&）。 A. O(log n) B. O(n log n) &C. O(n) &D. O(n2) &&&
T(n)=T(n-1)+n
&&&=T(n-2)+n-1+n
&&&=T(0)+1+2+3+……+n
&&&=1+n*(n+1)/2
所以是O（n^2)
11.&具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运 算的时间复杂度均为（ &&）。
A.&Θ(n2) B. Θ(e2) &C.
Θ(ne) &D.
Θ(n + e) &&&
遍历算法中，时间复杂度主要取决于搜索邻接点的个数；
邻接矩阵存储时，对于n个顶点每个顶点要遍历n次，显然是O(n^2)的
邻接表存储时，有n个头结点和e个表结点，所有节点遍历一遍，所以是D
12.&在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ &&）思想的算法
&A. 贪心 B.
没什么可说的，不知道的用排除法也应该没问题
13.&双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的
一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（
A.&p^.llink := q^.rlink := &p^.llink^.rlink := q^.llink := p^.
B. q^.llink := p^. p^.llink^.rlink := &q^.rlink := p^.llink := q^.
C. q^.rlink := p^.rlink := &p^.llink^.rlink := q^.rlink :=
&D. p^.llink^.rlink := q^.rlink := &q^.llink := p^. p^.llink := &&
导一下就ok了
14.&对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常 着色。正常着色图G所必需的最少颜色数，称为G的色数。那么下图的色数是（
A. 3 B. 4 C. 5 D. 6 &&&
自己试一试应该没问题吧
15.&在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选 手自带的是（ &&）。
身份证 &D.
准考证 &&&
二、不定项选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选或少选均不得分）
1.&以下属于操作系统的有（ &&）。 A. Windows XP B. UNIX &C. Linux &D. Mac OS &&
不清楚的建议上网查一下因为这应该是第二次考了&
2.&下列属于视频文件格式的有（ &&）。 A. AVI B. MPEG &C. WMV &D. JPEG &&
常见的视频格式：视频文件格式有不同的分类，如：
：wmv、asf、asx
Real Player
MPEG视频 ：mpg、mpeg、mpe
Apple视频 ：mov
Sony视频 ：mp4、m4v
其他常见视频：avi、dat、mkv、flv、vob
——来自百度百科
3下列选项不是正确的IP地址的有（ &&）。
A. 202.300.12.4 B. 192.168.0.3 &C. 100:128:35:91 &D. 111-103-35-21
IP地址的范围0~225
IP地址用“点分十进制”&&&
&4. 下列有关树的叙述中，叙述正确的有（ &&）。
A.&在含有n个结点的树中，边数只能是(n-1)条
B. 在哈夫曼树中，叶结点的个数比非叶结点个数多1
&C. 完全二叉树一定是满二叉树 &
D. 在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先
A显然对，B的话了解哈夫曼树的形成的话显然是对的，
C完全二叉树：只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，
D：根左右，在前面的也可能是根的左结点
5.&以下图中一定可以进行黑白染色的有（ &&）。（黑白染色：为各个结点分别指定黑白
两种颜色之一，使相邻结点颜色不同。） A.
二分图 B. 完全图 &C.
若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n
- 1) / 2条边，B显然是不可以的；
对于连通图，形成环的话也是显然不行的，所以是不一定的
容斥原理，反着想
1~2015，有503个能被4整除的，有403个能被5整除的，有335个能被6整除的
其中能被4、5的最小公倍数20整除的算了两遍有100个，
的最小公倍数12整除的算了2遍有167个，
的最小公倍数30整除的算了两遍有67个，
所以503+403+335-100-167-67=907；
在减的时候，能被4、5、6
的最小公倍数120整除的数减了3遍，
在一开始算的时候也算了3遍，所以907种中没有能被120整除的数，所以907+33=940；
所以共有940个能被4、
6 中任意一个数整除的数
答案就是：5
（当然你最小公倍数求错了的话怪我喽=。=）
二叉树的按结点个数，不同形态数按照Catalan序列
其中，结点数为5的有(10)!/(5!*5!)/(5+1) = 42种
（其实我也不大懂，旁边的一位大神告诉我，其实在草稿上画出指针和修改过程就很清楚了）
3、citizen（就是输出最长的字符串
4、31(递归，其实推着推着会发现凡是fun(0,*，*）的结果都为0，
&&&然后凡是fun（1，*，*）=0+1+0=1
&&&然后凡是fun(2,*,*)=1+1+1=3
&&&然后凡是fun(3,*,*)=3+3+1=7
&&&然后凡是fun(4,*,*)=7+7+1=15
&&&最后凡是fun(5,*,*)=15+1+15=31
【pascal答案】
1、（1）rmax[n]:=x[n];
（2）rmax[i]:=x[i];
（3）rmax[i]:=rmax[i-1]+x[i];
（4）rmax[i]:=rmax[i+1];
（5）lmax[i-1]+rmax[i+1]（因为要最少间隔一个数）
个人感觉这题还是蛮简单的，看清楚题目要求直接一遍就应该没什么问题了，而且就算不会写也可以照着上面对称着改一改就可以了=。=
2、（1）v:=-1
(2)dist[i]&dist[v]
（3）v:=i;
(4)used[v]:=1;
(5)dist[i]&dist[v]+w[v,i]
个人感觉只要会Dijkstra的应该填个大概或满分应该没问题的，对于我这种已经淡忘Dijkstra而只会SPFA的渣渣看了好几遍才填完然而还错了一个空，也是醉了=。=
总体感觉这一年的最后一道题简单不少=。=
& & & & & & & & & & & & & & & & & & &——by Eirlys
转载请注明出处=w=
本文已收录于以下专栏：
相关文章推荐
[NOIP2015]提高组初赛答案及题解
NOIP 2015 提高组 初赛
疑难点 学习 感悟。
示例如下（来自自个的理解）：
101.101 十进制 转十进制1*10^2+0*10^1+1*10^0+1*10^-1+0*10^...
比赛几个星期前就结束了，玩乐了一会儿，开始学术。
此文非题解。只是我自己的现场解题实录。
到宾馆后紧张的要死。晚上写了一堆基础模板：spfa最短路径，prim和kruskal的最...
NOIP2016 惨烈的初赛错题总结反思
2．如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序来回按键，即CapsLock、...
由于网上还没有题目所以这里便没有题目=w=
蒙也是能蒙对的=w=
注意，它问的是输出的第81个字符，不是按的，所以选B的童鞋好好读题=w=
依旧看做6个一组，81 div 6...
一、单项选择题
1.这题不是zz都能选对。
2.不难看出按键的顺序是五个一循环，于是可以求出共有多少个循环，进而求出按了多少次CapsLock，最后就可以得出答案。
3.异或就是按位运算，相同取...
直接根据题目描述的模拟就可以了，水。
int n,m,i,j,
总时间限制: 1000ms 内存限制: 65536kB
随着信息技术的蓬勃发展，医疗信息化已经成为医院建设中必不可少的一部分。计算机可以很好地辅助医院管...
他的最新文章
讲师：董晓杰
讲师：姚远
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)NOIP2015提高组复赛试题Day1+Day2纯Word版_文库下载
1亿文档 免费下载
当前位置： &
& NOIP2015提高组复赛试题Day1+Day2纯Word版
NOIP2015提高组复赛试题Day1+Day2纯Word版
NOIP2015提高组复赛试题Day1+Day2纯Word版
CCF 全国信息学奥林匹克联赛（NOIP2015）复赛
提高组 day1
（请选手务必仔细阅读本页内容）
一．题目概况
注意事项：
1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，内存 4G，上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、特别提醒：评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以其为准。
Word文档免费下载：（下载1-12页，共12页）
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day2 (请选手务必仔细阅读本页内容)一.题目概况中文题目...NOIP2015提高组复赛 DAY1+DAY2 试题_学科竞赛_高中教育_教育专区。CCF NOIP2015提高组复赛 DAY1+DAY2 试题 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1...全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目...NOIP2014提高组复赛试题day1+day2_从业资格考试_资格考试/认证_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (...NOIP2015 提高组复赛 Day1 第二题解题报告 By 某Xm zrw 1. 题目大概描述(因为写的时候题目还没放出来)几个小盆友们在传递自己的信息(生日) ,并且每个小盆...NOIP2015复赛提高组day2_学科竞赛_高中教育_教育专区。NOIP2015复赛提高组day2试题。全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day2 CCF 全国信息学奥林匹克...NOIP2015提高组Day1题解_学科竞赛_高中教育_教育专区。NOIP2015提高组 题解 NOIP2015 Day1 题解 Yang Jiaqi 2015 年 11 月 10 日 1 1 神奇的幻方 2 1 ...全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况中文题目...NOIP2013提高组复赛试题day1+day2_财会/金融考试_资格考试/认证_教育专区 暂无评价0人阅读0次下载举报文档 NOIP2013提高组复赛试题day1+day2_财会/金融考试_...b CCF NOIP2015 初赛提高组 C 语言试题 第 1 页,共 9 页 7. 前序遍历序列与后序遍历序列相同的二叉树为( A. C. 非叶子结点只有左子树的二叉树 根结点...NOIP2015试题【noip吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：21,039贴子：
NOIP2015试题收藏
NOIP2015 普及组试题& NOIP2015 提高组 Day 1&
noip编程课哪个好?选择由2500名中小学生共同推荐的傲梦编程素质教育!1V1老师授课+量身定制的noip课,助力孩子升学+加分,超越同龄小伙伴!
下载留名，感谢分享
码趣学院,专注于6-16岁青少儿noip教育,包括scratch,Python,Javanoip辅导!
感谢！有样例数据么？
NOIP2015 提高组 Day 1 试题与数据&
楼主快点把Day2的分享出来
刚考完没拿到，我考挂了，明年继续（时间还长…）
NOIP2015 提高组 Day 2&
登录百度帐号推荐应用7181人阅读
题解（1095）
T1 &直接根据题目描述的模拟就可以了，水。
#include&iostream&
#include&cstring&
#include&cstdio&
int n,m,i,j,
int a[50][50];
int main(){
scanf(&%d&,&n);
m=(n/2)+1;
a[1][m]=1;
while (num&n*n){
if (i==1&&j!=n) {a[n][j+1]=++ i=n; ++j;}
else if (i!=1&&j==n) {a[i-1][1]=++ --i; j=1;}
else if (i==1&&j==n) {a[i+1][j]=++ ++i;}
else if (i!=1&&j!=n){
if (!a[i-1][j+1]) {a[i-1][j+1]=++ --i; ++j;}
else {a[i+1][j]=++ ++i;}
for (int i=1;i&=n;++i){
for (int j=1;j&n;++j)
printf(&%d &,a[i][j]);
printf(&%d\n&,a[i][n]);
T2 &读了一遍题就看出来是最小环。刚开始忽略了有好几个联通块，大数据跑不对。最后写了个并查集+dfs，AC。水。
#include&iostream&
#include&cstring&
#include&cstdio&
#define inf
#define N 200005
int n,ans,y;
int f[N],next[N],h[N];
bool b[N];
inline int in(){
int x=0; char ch=getchar();
while (ch&'0'||ch&'9') ch=getchar();
while (ch&='0'&&ch&='9') x=x*10+ch-'0',ch=getchar();
int find(int x){
if (x==f[x])
f[x]=find(f[x]);
return f[x];
void merge(int x,int y){
int f1=find(x);
int f2=find(y);
void dfs(int x,int dep){
b[x]= h[x]=
if (!b[next[x]])
dfs(next[x],dep+1);
int k=h[x]-h[next[x]]+1;
ans=min(ans,k);
int main(){
n=in(); ans=
for (int i=1;i&=n;++i)
for (int i=1;i&=n;++i){
next[i]=y;
if (find(i)!=find(y))
merge(i,y);
memset(b,0,sizeof(b));
printf(&%d&,ans);
T3 &时限2s内存1G就知道这道题一定很神。刚开始看到了之后一点思路都没有，以为是dp但是发现状态太多压不下。而且还有多组数据一旦跑不对就挂了。30分打表。
后来听到TA大爷说就是个dfs，把每一种情况编上号之后搜索就可以了。
好像也有dfs+dp的做法，不过我觉得这个更好理解。
1、单顺子 2、双顺子 3、三顺子 4、三带一、三带二 &5、四带二、四带两对
由于每张牌的数量最多有4张，所以能保证这一种牌只要有就一定能一次打出去，所以出牌总次数的上限就是手牌的种类数。而每一次dfs都有一个新的上限，就是当前步数+现有的手牌的种类数。dfs过程中要进行最优化剪枝。
这题比较好理解，不过忘得差不多干净了之后又重写了一遍。
觉得现在的码风比原来好很多，所以把代码换掉_(:з」∠)_
#include&iostream&
#include&cstring&
#include&cstdio&
int T,n,x,y,
int a[20];
void clear()
memset(a,0,sizeof(a));
bool check()
for (int i=1;i&=15;++i)
void dfs(int dep)
if (dep&ans)
if (check())
ans=min(ans,dep);
int sum=0;
for (int i=1;i&=13;++i)
if (a[i]) sum++;
if (a[14]+a[15]) sum++;
ans=min(ans,dep+sum);
// 1 单顺子 2 双顺子 3 三顺子 4 三带一、三带二 5 四带二、四带两对
for (int kind=1;kind&=5;++kind)
if (kind==1)
for (int i=1;i&=8;++i)
bool flag=
for (int j=i+1;j&=i+3;++j)
if (!a[j]) {flag=}
if (!flag)
for (int j=i+4;j&13&&a[j];++j)
for (int k=i;k&=j;++k) --a[k];
dfs(dep+1);
for (int k=i;k&=j;++k) ++a[k];
if (kind==2)
for (int i=1;i&=10;++i)
if (a[i]&=2&&a[i+1]&=2)
for (int j=i+2;j&13&&a[j]&=2;++j)
for (int k=i;k&=j;++k) a[k]-=2;
dfs(dep+1);
for (int k=i;k&=j;++k) a[k]+=2;
if (kind==3)
for (int i=1;i&=11;++i)
if (a[i]&=3)
if (a[i+1]&3)
for (int j=i;j&13&&a[j]&=3;++j)
for (int k=i;k&=j;++k) a[k]-=3;
dfs(dep+1);
for (int k=i;k&=j;++k) a[k]+=3;
if (kind==4)
for (int i=1;i&=13;++i)
if (a[i]&=3)
for (int j=1;j&=15;++j)
dfs(dep+1);
for (int j=1;j&=15;++j)
if (a[j]&=2)
dfs(dep+1);
if (kind==5)
for (int i=1;i&=15;++i)
if (a[i]&=4)
for (int j=1;j&=15;++j)
for (int k=j;k&=15;++k)
dfs(dep+1);
for (int i=1;i&=15;++i)
if (a[i]&=4)
for (int j=1;j&=15;++j)
if (a[j]&=2)
for (int k=j;k&=15;++k)
if (a[k]&=2)
dfs(dep+1);
int main()
scanf(&%d%d&,&T,&n);
while (T--)
for (int i=1;i&=n;++i)
scanf(&%d%d&,&x,&y);
if (!x) a[y+13]++;
if (x==1||x==2) a[x+11]++;
if (x&=3) a[x-2]++;
for (int i=1;i&=13;++i)
if (a[i]) ans++;
if (a[14]+a[15]) ans++;
printf(&%d\n&,ans);
T1 &二分答案+贪心枚举，考前做过原题，但是还是调了一会，水。
#include&algorithm&
#include&iostream&
#include&cstring&
#include&cstdio&
#define N 50005
int L,n,m,l,r,mid,
int ok(int x){
int ans=0,k=0;
for (int i=1;i&=n+1;++i)
if (a[i]-a[k]&x)
int main(){
scanf(&%d%d%d&,&L,&n,&m);
for (int i=1;i&=n;++i)
scanf(&%d&,&a[i]);
sort(a+1,a+n+1);
a[0]=0; a[n+1]=L;
while(l&=r){
mid=(l+r)/2;
num=ok(mid);
if (num&=m) l=mid+1;
else r=mid-1;
printf(&%d&,l-1);
T2 &一眼就能看出来是dp，但是dp学的不好，想了一会没大有思路，就只写了30分的部分分。dfs没跑出来就只得了10分。
动规的思路看了ShallWe的代码才勉强理解，要是让我自己想是绝对想不到的，因为我当时连前缀和优化是什么都不怎么清楚。
f[i][j][k][l]表示第一个串的前i个，第二个串的前j个，分成k段，还有一维是前缀和，也可理解为选还是不选。注意这里的第一维要加一个滚动数组。
#include&iostream&
#include&cstring&
#include&cstdio&
#define N 1005
#define M 205
char s1[N],s2[M];
int n,m,k;
int f[2][M][M][2];
inline void in(){
char ch=getchar();
while (ch&'a'||ch&'z') ch=getchar();
for (int i=2;i&=n;++i) s1[i]=getchar();
ch=getchar();
while (ch&'a'||ch&'z') ch=getchar();
for (int i=2;i&=m;++i) s2[i]=getchar();
int main(){
scanf(&%d%d%d&,&n,&m,&k);
f[0][0][0][0]=1;
f[1][0][0][0]=1;
for (int i=1;i&=n;++i)
for (int j=1;j&=min(i,m);++j)
for (int l=1;l&=k;++l){
int now=i&1,last=(i-1)&1;
if (s1[i]==s2[j]){
f[now][j][l][1]=((f[last][j-1][l-1][0]+f[last][j-1][l-1][1])%p+f[last][j-1][l][1])%p;
f[now][j][l][0]=(f[last][j][l][0]+f[last][j][l][1])%p;
f[now][j][l][0]=(f[last][j][l][0]+f[last][j][l][1])%p;
f[now][j][l][1]=0;
printf(&%d&,(f[n&1][m][k][0]+f[n&1][m][k][1])%p);
注意上文的“勉强理解”，今天把当时写的代码翻出来看看然后一脸懵逼，推翻重写。
可能是最近这种类型的dp做的比较多，现在看这道题就比较简单了。
同样是把代码先贴出来，详细题解
撒花撒花~~
#include&iostream&
#include&cstring&
#include&cstdio&
#define N 1005
#define M 205
#define Mod
int n,m,p;
int f[2][N][M],s[2][N][M],g[N][M];
char a[N],b[M];
void init()
for (int i=1;i&=n;++i)
for (int j=1;j&=m;++j)
g[i][j]=min(i,j);
for (int k=1;k&=min(i,j);++k)
if (a[i-k+1]!=b[j-k+1])
g[i][j]=k-1;
int main()
scanf(&%d%d%d\n&,&n,&m,&p);
gets(a+1);gets(b+1);
for (int i=1;i&=m;++i)
for (int j=i;j&=n;++j)
f[1][j][i]=f[1][j-1][i];
if (g[j][i]==i) f[1][j][i]++;
s[1][j][i]=s[1][j-1][i-1]+f[1][j][i];
for (int i=2;i&=p;++i)
memset(f[i&1],0,sizeof(f[i&1]));
memset(s[i&1],0,sizeof(s[i&1]));
for (int j=1;j&=n;++j)
for (int k=1;k&=m;++k)
f[i&1][j][k]=f[i&1][j-1][k];
if (g[j][k])
int x=s[(i-1)&1][j-1][k-1];
f[i&1][j][k]=(f[i&1][j][k]+s[(i-1)&1][j-1][k-1])%M
int J=max(j-g[j][k]-1,0),K=max(k-g[j][k]-1,0);
int y=s[(i-1)&1][J][K];
f[i&1][j][k]=((f[i&1][j][k]-s[(i-1)&1][J][K])%Mod+Mod)%M
s[i&1][j][k]=(s[i&1][j-1][k-1]+f[i&1][j][k])%M
printf(&%d\n&,f[p&1][n][m]);
T3 &第一眼觉得是倍增，然后各种写，越写越觉得太繁琐，好像实现不了。最后只写了一个链，时间复杂度还算错了，所以只有5分。其实还是有很多部分分的，但是考试时没有时间写了。
考完试思考了一下感觉还是做不大出来，听学长说了二分，不是很懂，下面的来自Rivendell的博客：
总的来说，NOIP2015做的还是可以的，简单一点的题没有丢分，但是有一些思考复杂度高一点的题目没有做出来，下一步应该加强训练。
update&时至今日，懒惰的Po终于把自己过掉的T3贴出来。
#include&iostream&
#include&cstring&
#include&cstdio&
#define N 300005
#define sz 19
int n,m,x,y,z,Max,dfs_clock,
int tot,point[N],nxt[N*2],v[N*2],c[N*2];
int h[N],dis[N],val[N],num[N],tmp[N],f[N][sz+5];
struct hp{int x,y,lca,}edge[N];
void addedge(int x,int y,int z)
++ nxt[tot]=point[x]; point[x]= v[tot]=y; c[tot]=z;
++ nxt[tot]=point[y]; point[y]= v[tot]=x; c[tot]=z;
void build(int x,int fa)
num[++dfs_clock]=x;
for (int i=1;i&++i)
if ((h[x]-(1&&i))&1)
f[x][i]=f[f[x][i-1]][i-1];
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
f[v[i]][0]=x;
h[v[i]]=h[x]+1;dis[v[i]]=dis[x]+c[i];val[v[i]]=c[i];
build(v[i],x);
int lca(int x,int y)
if (h[x]&h[y]) swap(x,y);
int k=h[x]-h[y];
for (int i=0;i&++i)
if ((1&&i)&k) x=f[x][i];
for (int i=sz-1;i&=0;--i)
if (f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
bool check(int mid)
int cnt=0,limit=0;memset(tmp,0,sizeof(tmp));
for (int i=1;i&=m;++i)
if (edge[i].dis&mid)
++tmp[edge[i].x];++tmp[edge[i].y];tmp[edge[i].lca]-=2;
limit=max(limit,edge[i].dis-mid);
for (int i=n;i&1;--i) tmp[f[num[i]][0]]+=tmp[num[i]];
for (int i=2;i&=n;++i)
if (val[i]&=limit&&tmp[i]==cnt)
int find()
int l=0,r=Max,mid,
while (l&=r)
mid=(l+r)&&1;
if (check(mid)) ans=mid,r=mid-1;
else l=mid+1;
int main()
scanf(&%d%d&,&n,&m);
for (int i=1;i&n;++i)
scanf(&%d%d%d&,&x,&y,&z);
addedge(x,y,z);Max+=z;
build(1,0);
for (int i=1;i&=m;++i)
scanf(&%d%d&,&edge[i].x,&edge[i].y);
edge[i].lca=lca(edge[i].x,edge[i].y);
edge[i].dis=dis[edge[i].x]+dis[edge[i].y]-dis[edge[i].lca]*2;
ans=find();
printf(&%d\n&,ans);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：524916次
积分：16707
积分：16707
排名：第680名
原创：1151篇
评论：156条
QQ： 加好友请备注省份和ID
E-mail：fiona_
(1)(26)(70)(136)(94)(123)(72)(96)(47)(20)(31)(76)(90)(68)(37)(46)(32)(22)(16)(12)(43)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'完美退役。。。说好的不卡常呢QAQ
T1：模拟题？。。考察选手将题目描述翻译成代码的能力233
　　//其实真相是考验rp。。论代码雷同的危害233&
T2：简单图论，每个点出度为1所以是基环内向树（可能很多棵），要求出最短的环的长度
　　各种做法应该都行吧。。可以强上tarjan或者是裸搜时注意一下走过的点别走了或者是拓扑排序？。。。都是O(n)
T3：丧病模拟？注意一下姿势就可过吧（然而考场上整个人都傻逼了
　　目前见过的最快的做法就是开个数组存一下每种牌有多少张（花色实际没影响）然后强上dfs。。。
　　先试顺子或者是四带二这些出牌数多的（感觉优先顺子的话很可能不是最优解然而腾爷实力2ms打脸）
　　如果没把同花色的弄到一起的话可能会导致判断能不能出牌的时候耗时过多。。。可以开个2^n的数组记忆化一下（uoj数据去掉记忆化就从85掉到25了= =）。。结果就是初始化超时233
　　注意K后面可以连1啊什么的（按照数码大小）。。还有就是大王和小王不算一对（数码大小不同）
　　会打QQ斗地主的都惹不起。。。
T1：二分答案。。。。USACO银组题。。。。
　　唯一的区别就是现在终点的石子不能挪走（银组题没说这个
　　原来现在CCF是先把USACO的题抄到自家OJ上再抄到NOIP里面的啊。。真是用心良苦（喷
T2：简单DP。。。f[i][j][k]表示从A串前i个字符中取出j段，去对应B串中前k个字符的方案数（要不要强制i字符一定选这个随意。。）
　　正常解法是对于每个A串中的字符考虑一下是并到上一段还是开一个新段。。。（前提是A[i]==B[k]）
　　f[i][j][k]=f[i-x][j][k-x]+f[i-1][j-1][k-1](A[i-x.....i]与B[k-x......k]相等)，然后x那里前缀和一下就好了
　　然而4kw个int会爆空间QAQ。。。所以j那一维滚动一下保平安。。。
　　考场上傻逼写了个常数巨大的写法= =。。。然后为了压一下常数就改成滚动的了。。。自始至终没想过会爆空间QAQ。。然而目测正式测试最后一个点会被卡常
　　听说uoj上得跑500ms内北航老爷机（听说是？）上才能过= =
　　其实发现还是挺水的？QAQ。。考场上果断暴力+开rand贪心= =
　　用各种方法求出每条路径的长度，再降序排序。。
　　首先被弄成0的边一定是最长路径上的边（不然对答案没贡献），但又不一定是最长路径上最长的边，因为可能弄完就不是最长路径了。。
　　假如弄掉最长路径上最长的那条边，此时答案就是max(dis[1]-最长边权值,dis[2])。。。（dis[i]表示第i长路径长度）
　　所以我们对前i长的路径求交，再删去交集中最长的边,答案是max(dis[1]-交集中最长边权值,dis[i+1])。。。
　　至于快速求交。。。随便搞？（逃。。反正我只是嘴巴选手
　　树上的两条路径的交集一定是连续的一段。。所以直接把最长路径扒下来，然后每次求交时判断 当前那段交集的两端的边是否在新枚举的路径 上就好了。。
　　对于一条边(u,v)（u是v的父亲），如果路径有一个端点在v子树里，并且另一个端点在v子树外，那么这条边就在路径上
　　维护最大值的话按边权排序的时候记录一下每条边原来的位置，每次把已被踢出交集的最长边去掉就好了= =。。。
　　总复杂度是O(nlogn)。。。就是求路径长度和排序那块。。。后面的操作都是O(n)的
　　应该是可以过的。。。吧？（逃
想了想还是把在UOJ上能过的代码扔上来吧。当然要是在noip的老爷机上测的话还是会TLE的
1 #include&cstdio&
2 #include&iostream&
3 #include&algorithm&
4 #include&cstring&
5 #define ll long long
6 using namespace
7 const int maxn=300233;
8 struct zs{
11 }e[maxn&&1];
12 struct zs1{
15 }a[maxn];
16 struct zs2{
18 }b[maxn];
19 int tot,last[maxn],dep[maxn],bii[maxn],size[maxn],fae[maxn],pos[maxn];
20 int fa[maxn][20];
21 int i,j,k,n,m,aa,bb,cc,tmp,
22 int dl[maxn],l,r,
23 charint
25 ll dis[maxn];
26 inline void insert(int a,int b,int c){
e[++tot].too=b;e[tot].dis=c;e[tot].pre=last[a];last[a]=
e[++tot].too=a;e[tot].dis=c;e[tot].pre=last[b];last[b]=
30 inline int read(){
rx=getchar();rans=0;
while(rx&'0'||rx&'9')rx=getchar();
while(rx&='0'&&rx&='9')rans*=10,rans+=rx-48,rx=getchar();return
35 void dfs(int x,int pre){
dep[x]=dep[pre]+1;bii[x]=bii[pre];size[x]=1;pos[x]=++
if((dep[x]&(-dep[x]))==dep[x])bii[x]++;
for(i=1;i&=bii[x];i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(i=last[x];i;i=e[i].pre)if(e[i].too!=pre){
fa[e[i].too][0]=x;dis[e[i].too]=dis[x]+e[i].
fae[e[i].too]=i;
dfs(e[i].too,x);
size[x]+=size[e[i].too];
47 int lca(int a,int b){
if(dep[a]&dep[b])swap(a,b);short
for(i=bii[a];i&=0;i--)if(dep[fa[a][i]]&=dep[b])a=fa[a][i];
for(i=bii[a];i&=0;i--)if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];
a=fa[a][0];
56 inline bool onroute(int st,int ed,int num){
int u=e[num].too,v=e[((num-1)^1)+1].
if(fa[u][0]==v)swap(u,v);
return (pos[v]&=pos[ed]&&pos[v]+size[v]&pos[ed]) ^ (pos[v]&=pos[st]&&pos[v]+size[v]&pos[st]);
62 bool cmp(zs1 a,zs1 b){
return a.dis&b.
65 bool cmp1(zs2 a,zs2 b){
return a.dis&b.
68 int main(){
n=read();m=read();
for(i=1;i&n;i++)aa=read(),bb=read(),cc=read(),insert(aa,bb,cc);
bii[0]=-1;
for(i=1;i&=m;i++){
a[i].st=read();a[i].ed=read();cc=lca(a[i].st,a[i].ed);
a[i].dis=dis[a[i].st]+dis[a[i].ed]-(dis[cc]&&1);
sort(a+1,a+1+m,cmp);
aa=a[1].bb=a[1].cc=lca(aa,bb);
while(aa!=cc)dl[++r]=fae[aa],aa=fa[aa][0];tmp=r;
while(bb!=cc)dl[++tmp]=fae[bb],bb=fa[bb][0];
for(i=r+1;i&=r+(tmp-r)/2;i++)swap(dl[i],dl[tmp-i+r+1]);r=
for(i=1;i&=r;i++)b[i].pos=i,b[i].dis=e[dl[i]].
sort(b+1,b+1+r,cmp1);
l=1;top=1;
for(i=l;i&=r;i++)printf("
\n",e[dl[i]].too,e[((dl[i]-1)^1)+1].too,e[dl[i]].dis);
ans=max(a[1].dis-b[1].dis,a[2].dis);
for(i=2;i&=m&&l&=r;i++){
while(l&=r&&!onroute(a[i].st,a[i].ed,dl[r]))r--;
while(l&=r&&!onroute(a[i].st,a[i].ed,dl[l]))l++;
for(j=l;j&=r;j++)printf("
\n",e[dl[j]].too,e[((dl[j]-1)^1)+1].too,e[dl[j]].dis);
while(top&=tmp&&(b[top].pos&l||b[top].pos&r))top++;
ans=min(ans,max(a[1].dis-b[top].dis,a[i+1].dis));
printf("%lld\n",ans);
&UPD:事实证明还是被卡了QAQ。。uoj极限数据要700+ms。。然后时间复杂度主要跪在求lca上了。。。所以也许换成tarjan就行了。。吧。。sort倒是没什么影响TAT
所以说今年noip用到最高级的东西就是求lca么。。。。老板给我来一打刀片吧TAT
阅读(...) 评论()}