首页 > 代码库 > NOIP2017SummerTraining0717
NOIP2017SummerTraining0717
个人感受：自己水平是真的差劲，和他们不是一个档次的，第二题，如果不是陈载元暴力过了，我也不会那么早去A了第二题，第一题真的是无语，以前做到过，还想到了每个对应值a[i]-i,但是没想出来，真的是
可惜，这套题的话前两题都比提高组的要水，但这样下去，别说省选,TG一等都难拿。
改造二叉树
提交: 365 解决: 95
[提交][状态][讨论版]
题目描述
小Y在学树论时看到了有关二叉树的介绍：在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。
什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p，若其存在左孩子lch，则key[p]>key[lch]；若其存在右孩子rch，则key[p]<key[rch]；注意，本题中的二叉搜索树应满足对于所有结点，其左子树中的key小于当前结点的key，其右子树中的key大于当前结点的key。
小Y与他人讨论的内容则是，现在给定一棵二叉树，可以任意修改结点的数值。修改一个结点的数值算作一次修改，且这个结点不能再被修改。若要将其变成一棵二叉搜索树，且任意时刻结点的数值必须是整数（可以是负整数或0），所要的最少修改次数。
相信这一定难不倒你！请帮助小Y解决这个问题吧。
输入
第一行一个正整数n表示二叉树结点数。结点从1~n进行编号。
第二行n个正整数用空格分隔开，第i个数ai表示结点i的原始数值。
此后n - 1行每行两个非负整数fa, ch，第i + 2行描述结点i + 1的父亲编号fa，以及父子关系ch，(ch = 0 表示i + 1为左儿子，ch = 1表示i + 1为右儿子)。
结点1一定是二叉树的根。
输出
仅一行包含一个整数，表示最少的修改次数。
样例输入
3 2 2 2 1 0 1 1
样例输出
2
提示
【数据范围】
20 % ：n <= 10 , ai <= 100.
40 % ：n <= 100 , ai <= 200
60 % ：n <= 2000 .
100 % ：n <= 10 ^ 5 , ai < 2 ^ 31.
这道题做完后我发现自己是真的菜，推了10多分钟已经推出了二叉树的中序遍历，然后真的就讲问题转化为了将一个序列改变最小的数，使其满足各个数不同且单调递增，这个思维想下去就联想到了LIS
然后想了许久，到了13:50，陈载元A了第二题，说是什么暴力，然后我也去打了一个，花了半小时左右就A了，然后第三题去打了个暴力，这时14:45左右，然后又开始打第一题，真的恶心，想了，暴力，
DP，二分，妈的一个都套不进去，绝望了，最后半小时，。。。。。
最后题解就是先顺着我的思路下去，然后就是求一遍a[i]-i后求一次LIS（这个我还真想到了，但是我求的是最长上升序列，不是最长不下降序列），无语了。
1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 8 const int NN=100007; 9 10 int n,cnt; 11 int a[NN],vis[NN],pre[NN]; 12 struct node 13 { 14 int left,right; 15 void init(){left=right=0;} 16 }tree[NN]; 17 void dfs(int num) 18 { 19 if (tree[num].left!=0) dfs(tree[num].left); 20 vis[++cnt]=a[num]; 21 if (tree[num].right!=0) dfs(tree[num].right); 22 } 23 void mid_find(int x) 24 { 25 int mid,l=1,r=cnt; 26 while (l<r) 27 { 28 mid=(l+r)/2; 29 if (pre[mid]<=x) l=mid+1; 30 else r=mid; 31 } 32 if (pre[l]>x) pre[l]=x; 33 else pre[++cnt]=x; 34 } 35 int main() 36 { 37 scanf("%d",&n); 38 for (int i=1;i<=n;i++) 39 { 40 scanf("%d",&a[i]); 41 tree[i].init(); 42 } 43 int x,y; 44 for (int i=2;i<=n;i++) 45 { 46 scanf("%d%d",&x,&y); 47 if (y==0) tree[x].left=i; 48 else tree[x].right=i; 49 } 50 cnt=0; 51 memset(vis,0,sizeof(vis)); 52 memset(pre,0,sizeof(pre)); 53 dfs(1); 54 for (int i=1;i<=n;i++) 55 vis[i]-=i; 56 cnt=1,pre[cnt]=vis[1]; 57 for (int i=2;i<=n;i++) 58 mid_find(vis[i]); 59 cout<<n-cnt<<endl; 60 }
问题 B: 数字对
时间限制: 2 Sec 内存限制: 256 MB提交: 307 解决: 101
[提交][状态][讨论版]
题目描述
小H是个善于思考的学生，现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L, R](1 <= L <= R <= n)。
这个特殊区间满足，存在一个k(L <= k <= R)，并且对于任意的i(L <= i <= R)，ai都能被ak整除。这样的一个特殊区间 [L, R]价值为R - L。
小H想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些区间又分别是哪些呢？你能帮助她吧。
输入
第一行，一个整数n.
第二行，n个整数，代表ai.
输出
第一行两个整数，num和val,表示价值最大的特殊区间的个数以及最大价值。
第二行num个整数，按升序输出每个价值最大的特殊区间的L.
样例输入
5 4 6 9 3 6
样例输出
1 3 2
提示
【样例输入2】
5
2 3 5 7 11
【样例输出2】
5 0
1 2 3 4 5
【数据范围】
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.
这题思维主要来自于陈载元，他说暴力过了，然后我就打了个n^2，但我仔细想过，绝对不会到N^2的，因为枚举每个点，从前往后扫和从后往前扫时如果不是最小的数怕几个就扫完了，而且还要考虑能否整除的关系，所以还是可以行的通的。
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 using namespace std; 7 8 const int NN=500007; 9 10 int n; 11 int a[NN]; 12 13 bool cmp(int x,int y) 14 { 15 return x<y; 16 } 17 int main() 18 { 19 scanf("%d",&n); 20 for (int i=1;i<=n;i++) 21 scanf("%d",&a[i]); 22 int maxlen=-NN; 23 int c[NN],cnt=0,b[NN]; 24 c[0]=-1; 25 for (int i=1;i<=n;i++) 26 { 27 int j=i-1,k=i+1; 28 while (j>=1) {if (a[j]%a[i]!=0) break;j--;} 29 while (k<=n) {if (a[k]%a[i]!=0) break;k++;} 30 j++,k--; 31 k=k-j; 32 if (k>maxlen) 33 { 34 cnt=0; 35 maxlen=k; 36 c[++cnt]=j; 37 } 38 else if (k==maxlen) c[++cnt]=j; 39 } 40 sort(c+1,c+cnt+1,cmp); 41 int num=0; 42 for (int i=1;i<=cnt;i++) 43 if (c[i]!=c[i-1]) b[++num]=c[i]; 44 cout<<num<<‘ ‘<<maxlen<<endl; 45 for (int i=1;i<num;i++) 46 cout<<b[i]<<‘ ‘; 47 cout<<b[num]<<endl; 48 }
交换
时间限制: 1 Sec 内存限制: 256 MB提交: 167 解决: 47
[提交][状态][讨论版]
题目描述
给定一个{0, 1, 2, 3, … , n - 1}的排列 p。一个{0, 1, 2 , … , n - 2}的排列q被认为是优美的排列，当且仅当q满足下列条件：
对排列s = {0, 1, 2, 3, ..., n - 1}进行n – 1次交换。
<!--[if !supportLists]-->1. <!--[endif]-->交换s[q0],s[q0 + 1]
<!--[if !supportLists]-->2. <!--[endif]-->交换s[q1],s[q1 + 1]
…
最后能使得排列s = p.
问有多少个优美的排列，答案对10^9+7取模。
输入
第一行一个正整数n.
第二行n个整数代表排列p.
输出
仅一行表示答案。
样例输入
3 1 2 0
样例输出
1
提示
【样例解释】
q = {0,1} {0,1,2} ->{1,0,2} -> {1, 2, 0}
q = {1,0} {0,1,2} ->{0,2,1} -> {2, 0, 1}
【数据范围】
30%: n <= 10
100%: n <= 50
这道题考试的时候没怎么去想，因为****的第一题关系，然后第三题随便 暴力了一下，还编译错误。听力班长wsj大神的讲解后，算是大概理解了，实现了一下，也是一次AC
题意就是给你一个序列，问有多少种完美序列可以从原序列（0,1,2,n-1）推过来，完美序列是什么还和它的次序，有关，，自己理解为主。
然后就可以发现交换a[i]和a[i+1]后i前面和i后面就断绝联系了，前面的无法到后面，后面的无法到前面，然后就可以进行DP如果可以交换，就进行一次dfs，因为完美序列和次序有关，
然后就是累加，记忆化搜索就可以了，n^4 随便过这里有C数组的预处理，好好学学才行。
1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 8 const int NN=57,MOD=1e9+7; 9 10 int n; 11 int p[NN]; 12 long long f[NN][NN],c[NN][NN]={0}; 13 14 long long dfs(int l,int r) 15 { 16 if (l>r) return 0; 17 if (f[l][r]!=-1) return f[l][r]; 18 if (l==r){f[l][r]=1;return 1;} 19 f[l][r]=0; 20 for (int i=l;i<r;i++) 21 { 22 int left=p[i+1]; 23 int right=p[i]; 24 for (int j=l;j<i;j++)left=max(p[j],left); 25 for (int j=i+2;j<=r;j++)right=min(right,p[j]); 26 if (left<right) 27 { 28 swap(p[i],p[i+1]); 29 f[l][r]=(f[l][r]+dfs(l,i)*dfs(i+1,r)%MOD*c[r-l-1][i-l])%MOD; 30 swap(p[i],p[i+1]); 31 } 32 } 33 return f[l][r]; 34 } 35 int main() 36 { 37 scanf("%d",&n); 38 for (int i=1;i<=n;i++) 39 scanf("%d",&p[i]); 40 for (int i=0;i<=n;++i) 41 { 42 c[i][0]=1; 43 for (int j=1;j<=i;++j) 44 c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD; 45 } 46 memset(f,-1,sizeof(f)); 47 long long ans=dfs(1,n); 48 printf("%d",ans); 49 }
NOIP2017SummerTraining0717