关键词：
GTMD这么水的一套题没有AK
T1：妥妥的二分答案，贪心check。
T2：问题可以转化为最长上升（还是下降我记不住了）子序列。
T3：发现点被覆盖上的顺序是一定的。求出这个顺序，第一个操作在线段树上二分，第二个操作是找到这个点最上面那个有人的点，把他的状态变为没人。
P.S.常数这么大也能过。。。
然而一开始260为什么呢。。
anc开的maxv*20还TMfor到了20。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define maxn 100500 #define eps 1e-6 #define inf 0x7f7f7f7f7f7f7f7fLL using namespace std; long long n,h,x; double l=1,r=2000000000,ans; vector <long long> v[maxn]; bool check(double x) { double ret=0; for (long long i=1;i<=n;i++) { double mx=-inf; for (long long j=1;j<=h;j++) mx=max(mx,(double)v[i][j]-x*j); ret+=mx; } if (ret>=0) return true; return false; } int main() { scanf("%lld%lld",&n,&h); for (long long i=1;i<=n;i++) { v[i].push_back(0); for (long long j=1;j<=h;j++) { scanf("%lld",&x); v[i].push_back(v[i][j-1]+x); } } while (r-l>=eps) { double mid=(l+r)/2; if (check(mid)) {ans=l=mid;} else r=mid; } printf("%.4lf ",ans); return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; int n,a[maxn],b[maxn],x,t[maxn],ans=0,ret=0; int lowbit(int x) {return (x&(-x));} void modify(int x,int val) { for (int i=x;i<=n;i+=lowbit(i)) t[i]=max(t[i],val); } int ask(int x) { int ret=0; for (int i=x;i>=1;i-=lowbit(i)) ret=max(ret,t[i]); return ret; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) { scanf("%d",&x); b[x]=i; } for (int i=1;i<=n;i++) { ret=ask(n-b[a[i]]+1); ans=max(ans,ret+1); modify(n-b[a[i]]+1,ret+1); } printf("%d ",ans); return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define maxv 100500 using namespace std; int n,m,x,y,g[maxv],nume=1,op,dfn[maxv],fdfn[maxv],times=0,dis[maxv],anc[maxv][20]; int root,tot=0,ls[maxv<<2],rs[maxv<<2],sum[maxv<<2],lazy[maxv<<2]; vector <int> v[maxv]; void dfs(int x,int fath) { for (int i=0;i<v[x].size();i++) { int pos=v[x][i]; if (pos==fath) continue; anc[pos][0]=x;dis[pos]=dis[x]+1; dfs(pos,x); } dfn[x]=++times;fdfn[times]=x; } void get_table() { for (int i=1;i<=19;i++) for (int j=1;j<=n;j++) anc[j][i]=anc[anc[j][i-1]][i-1]; } void build(int &now,int left,int right) { now=++tot;sum[now]=right-left+1;lazy[now]=0; if (left==right) return; int mid=left+right>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } void pushdown(int now) { if (!lazy[now]) return; lazy[ls[now]]=lazy[rs[now]]=lazy[now]; sum[ls[now]]=sum[rs[now]]=0;lazy[now]=0; } void pushup(int now) { sum[now]=sum[ls[now]]+sum[rs[now]]; } int ask1(int now,int left,int right,int x) { pushdown(now); if (left==right) return left; int mid=left+right>>1,k=sum[ls[now]]; if (x<=k) return ask1(ls[now],left,mid,x); else return ask1(rs[now],mid+1,right,x-k); } void modify1(int now,int left,int right,int l,int r) { if ((left==l) && (right==r)) { lazy[now]=1;sum[now]=0; return; } int mid=left+right>>1; if (r<=mid) modify1(ls[now],left,mid,l,r); else if (l>=mid+1) modify1(rs[now],mid+1,right,l,r); else { modify1(ls[now],left,mid,l,mid); modify1(rs[now],mid+1,right,mid+1,r); } pushup(now); } int ask2(int now,int left,int right,int pos) { pushdown(now); if (left==right) return sum[now]; int mid=left+right>>1; if (pos<=mid) return ask2(ls[now],left,mid,pos); else return ask2(rs[now],mid+1,right,pos); } void modify2(int now,int left,int right,int pos) { pushdown(now); if (left==right) {sum[now]=1;return;} int mid=left+right>>1; if (pos<=mid) modify2(ls[now],left,mid,pos); else modify2(rs[now],mid+1,right,pos); pushup(now); } void work1() { int pos=ask1(root,1,n,x); printf("%d ",fdfn[pos]); modify1(root,1,n,1,pos); } void work2() { int ret=x; for (int i=19;i>=0;i--) { if (!anc[ret][i]) continue; if (!ask2(root,1,n,dfn[anc[ret][i]])) ret=anc[ret][i]; } printf("%d ",dis[x]-dis[ret]); modify2(root,1,n,dfn[ret]); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); v[x].push_back(y);v[y].push_back(x); } for (int i=1;i<=n;i++) sort(v[i].begin(),v[i].end()); dfs(1,0);get_table(); build(root,1,n); for (int i=1;i<=m;i++) { scanf("%d%d",&op,&x); if (op==1) work1(); else work2(); } return 0; }
noip2016模拟拼接mf(模拟)
1#include"bits/stdc++.h"2usingnamespacestd;3typedeflonglongLL;4constintMAX=10;5charn[105];6structCube{7intc[MAX][MAX][MAX];//前后左右上下8voidout(){9inti,j,k;10for(i=1;i<=6;i++){11for(j=1;j&l 查看详情
学军联赛模拟第十八测题解
(A.)首先有个朴素的动态规划思路，记(f_i,j)表示前(i)个位置，最后一个位置的颜色是(j)的方案数。转移要用到容斥原理，用总方案数减去(j)连续出现(a_j+1)次的方案数。记(g_i=sumf_i,j)。则(f_i,j=g_i-1-(g_i-a_j-1-f_i-a_j-1,j))。注意到对于(a_... 查看详情
noip2016模拟妹子(矩阵快速幂)
1#include"bits/stdc++.h"2#definemem(a,b)memset(a,b,sizeof(a))3usingnamespacestd;4typedeflonglongLL;5constintMAX=105;6constintMOD=1000000007;7LLn,m;8structMat{9LLx,y;10LLmat[MAX][MAX];11Mat(){x=y=0,mem 查看详情
2016.10.30noip模拟赛day2am整理
题目+数据：链接：http://pan.baidu.com/s/1gfBg4h1密码：ho7o总共得了：130分，1：100分 2:30分（只会这30分的暴力）3：0（毫无思路）虽然不高，但是比较满意，因为把自己会的分数都拿到了。T1：100分1/*2T1明显是个数论题。3正确的思... 查看详情
玩具谜题（noip2016）(纯模拟)
原题传送门神奇的题目。。朝左朝右异或一下就好了细节处理一下，输出now的字符串下面贴代码#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;charzy[100001][12];boolcx[100001];intnow=1;intn,m;intmain(){scanf("%d 查看详情
noip2016提高a组模拟10.15总结
第一题，就是将原有的式子一步步简化，不过有点麻烦，搞了很久。第二题，枚举上下边界，维护一个单调队列，二分。比赛上没有想到，只打了个暴力，坑了80分。第三题，贪心，最后的十多分钟才想到，没有打出来。心得1、... 查看详情
2016.10.29noip模拟赛pm考试整理
300分的题，只得了第三题的100分。题目+数据：链接：http://pan.baidu.com/s/1o7P4YXs密码：4howT1：这道题真的是跪在游戏玩少了。我忽视了游戏中的两个常识：1.开始的序列是无法消除的（这与题目描述明显不符啊），即使有很多可以... 查看详情
noip2016提高a组模拟10.15算循环(代码片段)
题目分析一步步删掉循环，首先，原式是\[\sum_i=1^n\sum_j=1^m\sum_k=i^n\sum_l=j^m\sum_p=i^k\sum_q=j^l1\]删掉最后两个循环\[\sum_i=1^n\sum_j=1^m\sum_k=i^n\sum_l=j^m(k-i+1)(l-j+1)\]发现，当\(i,j\)固定，随着\(k,l\)的变化，\((k 查看详情
noip2016提高a组模拟8.14总结
第一题是几何题，没去想直接弃疗。。。、第二题觉得很像背包，但是单挑人的顺序不同，答案也会不同，我比较了每个人先后的优劣性，成功搞定了这道题。但是再输出时不小心搞错了，爆零。第三题，我答案了整整一个小时... 查看详情
bzoj4551noip2016模拟7.11树(代码片段)
题目在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：1.标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个... 查看详情
jzoj4742noip2016提高a组模拟9.2快速幂单峰(代码片段)
【NOIP2016提高A组模拟9.2】单峰Link题面解题思路CodeLinkJzoj【4742】【NOIP2016提高A组模拟9.2】单峰题面DescriptionInputOutputSampleInput2SampleOutput2DataConstraint解题思路证明不太会，考场上打了个暴搜，然后找到的规律答案=2^(n-1)ÿ... 查看详情
noip2016提高a组模拟9.15math(代码片段)
题目分析因为\((-1)^2=1\)，所以我们只用看\(\sum_j=1^md(i·j)\)的值模2的值就可以了。易证，一个数x，只有当x是完全平方数时，d(x)才为奇数，否则为偶数。那么设\(i=p*q^2\)，p不包含任何平方因子，要使\(i·j\)为完全平方数，则\(j=p*k^2... 查看详情
noip2016提高a组模拟9.17序列(代码片段)
题目分析首先用\(a_i\)表示达到目标的步数\(B_i-A_i(mod4)\)根据粉刷栅栏，先不管mod4的情况，答案就是\(\sum\max(a_i-a_i+1,0)\)那我们刚才做个差分\(a_i-=a_i+1\)当我们给i增加高度，那么\(a_i-4，a_i+1+4\)当我们给区间增加高度,那么因为中间... 查看详情
noip2016提高a组模拟8.15password(代码片段)
题目分析首先我们知道，原A序列其实表示一个矩阵，而这个矩阵的对角线上的数字就是答案B序列。接着\(a、b>=gcd(a,b)\)，所以序列A中的最大的数就是ans[1]，第二大的数就是ans[2]。但是ans[3]并不一定就是序列A中的第三大的数，... 查看详情
bzoj4552tjoi2016&heoi2016noip2016模拟7.12排序(代码片段)
题目在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，... 查看详情
$noip2016day1$模拟考试题解报告(代码片段)
没有摘要的摘要目录$NOIP\\2016\\Day1$模拟考试题解报告得分情况考试过程题解$T1$玩具谜题$T2$天天爱跑步$T3$换教室\\(NOIP\\2016\\Day1\\)模拟考试题解报告得分情况\\(T1\\)\\(85\\Pts\\)\\(T2\\)\\(15\\Pts\\)\\(T3\\)\\(100\\Pts\\)总分:\\(200\\Pts\\)考试过... 查看详情
noip2016模拟赛
——那些年，我们学过的文化课 考场得分140分。 背单词(word.c/cpp/pas)【题目描述】fqk退役后开始补习文化课啦，于是他打开了英语必修一开始背单词。看着满篇的单词非常头疼，而每次按照相同的顺序背效果并... 查看详情
noip2016模拟最长公共子序列
其实题目是这个样子的：仔细看能够知道，每条轨道上火车的编号都是递减的，这样就等价于求他的最大上升子序列的长度，由于N比较大，所以采用nlogn的LIS方法 f[i]表示长度为i的最长上升子序列最后一个最小为f[i]，首先易... 查看详情