NOIp系列题目及CF小结
长期更新中2333
2018/7/2
先看一下昨晚的cf
| Codeforces Round #493 (Div. 2) |
|---|
A. Balloons
这个题。。。直接模拟233
B. Cutting
来一下奇加偶减。统计合适位置然后排个序，贪心减
C. Convert to Ones
连续的0或者1显然可以表示为一个
那么可能的情况就只有0101010……或者101010……
交换一次可以少一个需要覆盖的区间。
所以统计0区间的个数然后贪心的翻转或者覆盖
if(Rev<Cov) {
ans=Rev*(cnt-1);
ans+=Cov;
}
else ans=Cov*cnt;就这样
D. Roman Digits
打表。。。发现11个之后差值均为49。。。。
人类智慧啊
#include<bits/stdc++.h>
using namespace std;
long long n,a[20]={0,4,10,20,35,56,83,116,155,198,244,292};
int main() {
cin>>n;
if(n<=11) cout<<a[n];
else cout<<a[11]+(n-11ll)*49ll;
return 0;
}然后是今天的NOIp模拟。
T1是一个杨辉三角，预处理一下阶乘和逆元就好
void prepare(int lim) {
fac[0]=1; inv[0]=1;
for(int i=1;i<=lim;++i) fac[i]=fac[i-1]*i%mod;
inv[lim]=Ksm(fac[lim],mod-2);
for(int i=lim-1;i;--i) inv[i]=(i+1)*inv[i+1]%mod;
return ;
}//阶乘求逆元的独特技巧2333T2。。。
字典中有 m 个单词，每个单词长度不超过50。
读题的重要性。。。这个题目是一个很菜的Trie树。
由于单词长度不超过50，所以对于匹配串每一个位置都暴力匹配一次进行dp
T3
一道构造题。。。所以说贪心可以得80分，还是不要去挑战人类智慧算了
/****************************************我是日期的分割线****************************************************/
2018/7/3
T1
一道不是很难的数学题，搞一下阶乘的质因数就好
for(long long i=1;i<=psize;++i) {
long long cnt=0,temp=prime[i];
while(temp<=n) {
cnt+=n/temp;
temp*=prime[i];
}
if(cnt&1) --cnt;
ans=ans*Ksm(prime[i],cnt)%mod;
}
T2
情报传输
从前有一个间谍组织，一共派遣了 n 个人潜伏在 E 国刺探情报。为了防止情报泄露，一个间谍可能只认识其他几个人。
认识的人之间有上下级的关系，并且只有一个头目为 1 号，也就是说他们的关系形成了一棵有根树的结构，每个人既可以向直接上级传递情报，也可以向直接下级传递情报。一个人拿到情报后需要一天的处理时间才能传递这个情报，传递情报的时间忽略不计。
因为各种各样的突发情况，头目可能会变更，或者两个人之间暂时联系不上了。
现在给出 m 个突发事件：可能是头目发生了变更；或者是一个人拿到了情报，但他到头目的传递过程中有两个人之间失去了联系。求他把情报传给所有能接收到的人手里的时间。
注意，第一个人拿到情报的人不需要处理情报，其他人拿到情报后处理完才算接收完情报。更换头目是永久的，会影响后面的查询；失去联系是暂时的，仅影响当前查询，不影响后面的查询。
1<=n,m<=200000
这个题啊，本来是NOIp模拟来着。听说正解是什么树上的倍增再加上根与节点位置的讨论做出来的。
不过我最近沉迷数据结构啊，所以就无脑暴力了一波
首先树链剖分方便计算两点距离然后将所用的询问离线下来，用LCT预处理出每一次询问时断掉了哪条边。
找树上的k级祖先可以Access之后在Splay上二分。
然后得到每一条边的存在时间之后，用线段树分治处理，使得只有加边的情况。
这个时候我们就用带撤销的并查集维护当前联通块的最长链。
答案就是当前点到最长链两端的较大值树剖+动态树+线段树分治+启发式合并并查集，总时间复杂度O(nlogn)。
代码长度7k+,常数极大。(考场A了2333)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int Maxn=200005;
inline int read() {
char c; int rec=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();
return rec;
}
int n,m;
struct Edge {int a,b;} e[Maxn];
map< pair<int,int> , int > table;
namespace Graph {
struct Branch {int next,to;} branch[Maxn<<1];
int h[Maxn],cnt=0;
inline void add(int x,int y) {
branch[++cnt].to=y; branch[cnt].next=h[x]; h[x]=cnt; return ;
}
int size[Maxn],deep[Maxn];
int top[Maxn],fa[Maxn],son[Maxn];
void Dfs1(int v,int pre,int dep) {
size[v]=1; fa[v]=pre; deep[v]=dep;
for(int i=h[v];i;i=branch[i].next) {
int j=branch[i].to;
if(j==pre) continue;
Dfs1(j,v,dep+1); size[v]+=size[j];
if(size[son[v]]<size[j]) son[v]=j;
} return ;
}
void Dfs2(int v,int T) {
top[v]=T; if(son[v]) Dfs2(son[v],T);
for(int i=h[v];i;i=branch[i].next) {
int j=branch[i].to;
if(j==fa[v]||j==son[v]) continue;
Dfs2(j,j);
} return ;
}
inline int Lca(int x,int y) {
while(top[x]!=top[y])
deep[top[x]]<deep[top[y]]?y=fa[top[y]]:x=fa[top[x]];
return deep[x]<deep[y]?x:y;
}
inline int Dist(int x,int y) {
return deep[x]+deep[y]-(deep[Lca(x,y)]<<1);
}
}
namespace Lct{
struct Splay {
int F,s[2],size,rev;
inline void NewNode(int fa) {
F=fa; s[0]=s[1]=rev=0; size=1; return ;
}
}tree[Maxn];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].size=tree[tree[v].s[0]].size+1+tree[tree[v].s[1]].size; return ;}
inline void Rev(int v){if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}
inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v) {
int p=tree[v].F,g=tree[p].F;
int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];
if(!Isroot(p)) Set(g,v,t2); else tree[v].F=g;
Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v) {
for(Lazy(v);!Isroot(v);Rotate(v)) {
int p=tree[v].F,g=tree[p].F;
if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);
} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F){Splay(v); tree[v].s[1]=u; Pushup(v);} return ;}
inline void Make_Root(int v){Access(v); Splay(v); Rev(v);}
inline int Kth(int k,int v) {
Pushdown(v);
while(tree[tree[v].s[0]].size+1!=k&&v) {
if(tree[tree[v].s[0]].size+1>k) v=tree[v].s[0];
else k-=tree[tree[v].s[0]].size+1,v=tree[v].s[1];
Pushdown(v);
} return v;
}
inline pair<int,int> Get_Kth(int v,int k) {
Access(v); Splay(v);
if(tree[v].size<=k) return make_pair(0,0);
int goal=tree[v].size-k;
int u=Kth(goal,v);
Splay(u); v=tree[u].s[1]; Pushdown(v);
while(tree[v].s[0]) v=tree[v].s[0],Pushdown(v);
if(u>v) swap(u,v);
return make_pair(u,v);
}
inline void Build(int v,int pre) {
tree[v].NewNode(pre);
for(int i=Graph::h[v];i;i=Graph::branch[i].next) {
int j=Graph::branch[i].to;
if(j==pre) continue;
Build(j,v);
} return ;
}
}
namespace Union {
int fa[Maxn],size[Maxn];
inline int getfa(int x){
while(x!=fa[x]) x=fa[x];
return x;
}
struct chain {
int a,b,len;
} A[Maxn];
int top=0;
struct node {
int x,y,a,b,len;
} S[Maxn];
inline void reset() {
for(int i=1;i<=n;i++)
fa[i]=i,size[i]=1;
for(int i=1;i<=n;i++)
A[i].a=A[i].b=i,A[i].len=0;
top=0; return ;
}
inline void Sov(int id) {
int x=e[id].a,y=e[id].b;
int fx=getfa(x),fy=getfa(y);
if(size[fx]>size[fy]) swap(fx,fy);
fa[fx]=fy; size[fy]+=size[fx];
S[++top]=(node){fx,fy,A[fy].a,A[fy].b,A[fy].len};
int a=A[fx].a,b=A[fx].b,c=A[fy].a,d=A[fy].b;
int maxx=A[fx].len,temp; x=a; y=b;
if(maxx<A[fy].len){maxx=A[fy].len; x=c; y=d;}
temp=Graph::Dist(a,c); if(maxx<temp){maxx=temp; x=a; y=c;}
temp=Graph::Dist(a,d); if(maxx<temp){maxx=temp; x=a; y=d;}
temp=Graph::Dist(b,c); if(maxx<temp){maxx=temp; x=b; y=c;}
temp=Graph::Dist(b,d); if(maxx<temp){maxx=temp; x=b; y=d;}
A[fy].a=x; A[fy].b=y; A[fy].len=maxx;
return ;
}
inline void Undo(int lim) {
while(top>lim) {
node temp=S[top--];
int x=temp.x,y=temp.y;
fa[x]=x; size[y]-=size[x];
int a=temp.a,b=temp.b,c=temp.len;
A[y].a=a; A[y].b=b; A[y].len=c;
} return ;
}
inline int Ask(int x) {
int fx=getfa(x);
int a=A[fx].a,b=A[fx].b;
int maxx=max(Graph::Dist(x,a),Graph::Dist(x,b));
return maxx;
}
}
int qpos[Maxn];
vector<int> broken[Maxn];
namespace Sgt {
struct Segment_Tree {
int L,R; vector<int> id;
}tree[Maxn<<2];
void Build(int v,int L,int R) {
tree[v].L=L; tree[v].R=R;
if(L==R) return ;
int mid=(L+R)>>1;
Build(v<<1,L,mid); Build(v<<1|1,mid+1,R);
return ;
}
inline void Cover(int v,int L,int R,int x) {
if(tree[v].L>R||tree[v].R<L) return ;
if(L<=tree[v].L&&tree[v].R<=R) {
tree[v].id.push_back(x); return ;
}
Cover(v<<1,L,R,x); Cover(v<<1|1,L,R,x); return ;
}
inline void Sov(int v) {
int top=Union::top;
for(int i=0;i<tree[v].id.size();++i)
Union::Sov(tree[v].id[i]);
if(tree[v].L==tree[v].R) {
cout<<Union::Ask(qpos[tree[v].L])<<'\n';
Union::Undo(top); return ;
}
Sov(v<<1); Sov(v<<1|1); Union::Undo(top);
return ;
}
}
int main() {
n=read();
for(int i=1;i<n;i++) {
int x=read(),y=read();
if(x>y) swap(x,y);
e[i].a=x; e[i].b=y;
Graph::add(x,y); Graph::add(y,x);
table[make_pair(x,y)]=i;
}
table[make_pair(0,0)]=0;
Graph::Dfs1(1,0,1); Graph::Dfs2(1,1); Lct::Build(1,0);
m=read();
int qcnt=0; char ch;
for(int i=1;i<=m;i++) {
while((ch=getchar())!='Q'&&ch!='C');
if(ch=='Q') {
int x=read(),k=read();
++qcnt; qpos[qcnt]=x;
pair<int,int> temp=Lct::Get_Kth(x,k);
int id=table[temp];
if(id==0) continue;
else broken[id].push_back(qcnt);
}
else {
int x=read(); Lct::Make_Root(x);
}
}
Sgt::Build(1,1,qcnt);
for(int i=1;i<n;++i) {
int L=1;
for(int j=0;j<broken[i].size();++j) {
Sgt::Cover(1,L,broken[i][j]-1,i);
L=broken[i][j]+1;
}
Sgt::Cover(1,L,qcnt,i);
}
Union::reset();
Sgt::Sov(1);
return 0;
}————————————————————我是日期的分割线———————————————————————
2018.8.1
隔了很久才考第二次啊2333
今天似乎是考了一套noip混合题目
T1是【NOIP 2007】字符串的展开
多读读题目，直接暴力模拟。
(说起来两年前做的适合只写了0.92k，这次就有2.46k了。。。)
主要是嫌麻烦的话就多写一点代码，也就是说会有复制粘贴一样的代码。
虽然很丑很长很难看，但是不是很容易错就对了。
T2 【NOIP 2005】篝火晚会
看上去像一个置换类的题目(有点想多了)
根据题意模拟出一种可行圆排列的展开。
然后找出对应位置最多的一种排列方式，再找出没有对应的个数。
（最后一个过程确实很像置换，但是只求总代价而没有涉及到置换次数，所以答案就是没有直接对位的个数了）
T3 【NOIP 2007】矩阵取数游戏
emm
显然的有一个似乎有点比较浅显的dp(似乎这行很难读？2333)
我们发现两行之间是没有影响的，把每一行的最大值相加就能够直接得到全局的最大值。
dp方程：
定义代表从第i个取到第j个的最高价值。
那么，显然有
Base就是那个啥，就是当前的2^i次方。
然后初始值就是
就是高精度(2^80次方你怕不怕)有点烦(__int128好像也行)
存一下高精度的部分
const long long mod=100000000;
struct Big_number {
long long a[10]; int top;
Big_number(){memset(a,0,sizeof(a)); top=1; return ;}
inline void operator = (const long long x) {a[1]=x; top=1; return ;}
inline void Print() {
int x=top;
cout<<a[x--];
while(x) printf("%08lld",a[x--]);
return ;
}
}A,B,C;
inline Big_number operator * (const Big_number &x,const Big_number &y){
Big_number rec;
for(int i=1;i<=x.top;++i)
for(int j=1;j<=y.top;++j)
rec.a[i+j-1]+=x.a[i]*y.a[j];
rec.top=x.top+y.top-1;
for(int i=1;i<=rec.top;++i)
rec.a[i+1]+=rec.a[i]/mod,rec.a[i]%=mod;
while(rec.a[rec.top+1]) ++rec.top;
return rec;
}
inline Big_number operator + (const Big_number &x,const Big_number &y) {
Big_number rec;
int lim=max(x.top,y.top);
for(int i=1;i<=lim;++i) {
rec.a[i]+=x.a[i]+y.a[i];
rec.a[i+1]+=rec.a[i]/mod;
rec.a[i]%=mod;
}
rec.top=lim;
if(rec.a[rec.top+1]) ++rec.top;
return rec;
}
inline bool operator > (const Big_number &x,const Big_number &y) {
if(x.top>y.top) return 1;
else if(x.top<y.top) return 0;
for(int i=x.top;i;--i)
if(x.a[i]>y.a[i]) return 1;
else if(x.a[i]<y.a[i]) return 0;
return 0;
}感觉还行。。。
dp还是贴一些吧(CSDN代码片不能折叠，绝望。)
long long ans=0;
for(int i=1;i<=n;++i) {
long long base=1ll<<m;
for(int k=1;k<=m;++k)
f[k][k]=map[i][k]*base;
for(int len=2;len<=m;++len) {
base>>=1ll;
for(int j=1;j+len-1<=m;++j)
f[j][j+len-1]=max(f[j][j+len-2]+map[i][j+len-1]*base,f[j+1][j+len-1]+map[i][j]*base);
}
ans+=f[1][m];
}
cout<<ans;T4 【NOIP 2008】双栈排序
经典的老题目了。
首先二分图匹配一下来找找合法性。（一个数字肯定是要进一个栈，对吧）（没错）
然后就在图上找字典序最小的输出方案就是了。
emm，没有代码。(网上辣么多)
————————————————————我是日期的分割线———————————————————————
2018.8.2
今天是由高三毕业的ZY学长带来的模拟题。
（我有点毒瘤啊。。。3道题一道没A总分上了250【果然吗】）
T1
简明题意：有A,B,C三种物品。物品的代价分别为2,5,1，总收益为A+B*C。
在总收益为n的情况下，使得代价最小。
若有多个，则优先使B最小。
n<=10^14
*******************************
考场上感觉有点复杂，所以直接做了一个n^2的dp开始打表，找到了一些规律，但实际上并不用这么麻烦。
显然，对于总收益贡献更大的部分是后边的B*C，我们使得它最大化是能够得到最优解的。
然后B的代价更大，所以B的大小一定不会超过√n。
直接枚举B，得到最大的C(n/b)，然后剩下的就是A了。
取一下最小值。这样问题的规模就是10^7，O(√n)的算法就可以解决问题了。
（考试的时候打表的出来的规律计算时间复杂度也是O(√n)，但是会多一些乘除法的运算。所以T成90分）
T2
简明题意：你有n堆石子，每次任选k堆，从这k堆中分别取出一颗石子。当总的石子堆数不足k时结束，最大化取石子次数。
其中，k<n<=10^5,ai(个数)<=10^9
显然，我们每一次都取最大的k堆一定能够得到最优解，所以n^2的算法就很显然了。
（然后加上奇奇怪怪骗来的30分一共有80分了）
正解：二分
说来这个二分非常的神奇。
我们直接二分答案(答案的范围在【0,10^14】)，就是取石子的次数。
分别对每一堆石子考虑：
如果石子个数大于取石子的次数m，那么显然每一次都可以取这个石子,也就是说，这一堆石子的贡献最大为m。
否则，这一堆石子可能被全部取完，则贡献最大为a[i]。
要使得这个次数m满足要求，则总共取出的石子要大于等于m*k。
那么我们就可以在O(n)的时间内完成检测了。
T3
可以说是最常见的题目了。
给定一棵树，询问节点x子树中前k大节点的权值和。
由于时限两秒，n<=10^5，不用在线，所以有很多奇怪的解法。
首先可以直接莫队+Splay(真有人这样写)，O(n√nlogn)，能够拿80分(卡卡常，松一松说不定能过)
然后还是莫队+权值分块，O(n√n)稳过。
接着就是启发式合并的权值线段树/Splay，O(nlog^2n)，标解给的就是这个。
显然可以考虑离线+线段树合并，时空复杂度均为O(nlogn)。
当然，Dfs序展开之后直接上主席树也可以O(nlogn)。
我写的启发式+Splay，由于有100000的单链数据所以爆栈了两组（80分）。
大概就是这样(我可能是全场唯一一个一道题都没有A的蒟蒻了)。
————————————————————我是日期的分割线———————————————————————
2018.8.3
ZY模拟赛第二套
T1
只有三行的O(n)dp。（其实该放在昨天第一题）
T2
给定一个n*m的矩形，用2*2的方块来覆盖，每一个格子都有权值，求最大能够得到的权值。
n,m<=11
非常显然的状压Dp，有效状态只有144个。
也就是说时间复杂度最大就是O(11*144*144)【标解居然是爆搜】
（事实上这个题是一个简化版本，原来的要求是用任意个大小互不相同的正方形来覆盖，这样的话就只能够爆搜了Orz）
T3
n个点的完全图，两个点之间的权值为点权的异或值。
求最小生成树的权值。
一行五个整数，n，v[1]，A，B，P，其中 n 表示点的数量，v[1] 表示点 1 的权值。 对于 2≤i≤n，v[i]=(v[i-1]*A+B)%P。
对于n<=10^5,没有特殊约定
对于n<=10^9,有v[1]=0,A=1,B=1.
————————————————————我是日期的分割线———————————————————————
2018.8.4
今天又是4道noip老题。
T1【NOIP 2009】潜伏者
模拟
T2【NOIP 2009】Hankson的趣味题
数学分析一下之后直接√n枚举过去
T3【NOIP 2009】最优贸易
我们发现答案只和路径上的最大和最小值有关。
然后我们可以直接两次Spfa，第一次从1号点去更新最小值。
然后将有向图的边反向，第二次从n号点去更新最大值。
然后答案就是同一个点的最大最小值之差的最大值
T4【NOIP 2006】2^k进制数
emmm。简单发现显然和组合数相关，然后上高精度做一下就好了。
（emm，根本不会卡空间啊）
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Mod=1000000;
int n,k;
int a[105],b[105];
inline void Print(int *a) {
cout<<a[a[0]];
for(int i=a[0]-1;i>=1;i--)
printf("%06d",a[i]);
return ;
}
inline void Mul(int *a,int b) {
for(int i=1;i<=a[0];++i) a[i]*=b;
for(int i=1;i<=a[0];++i)
a[i+1]+=a[i]/Mod,a[i]%=Mod;
while(a[a[0]+1])
a[a[0]+1]+=a[a[0]]/Mod,a[a[0]]%=Mod,++a[0];
return ;
}
inline void Add(int *a,int *b) {
a[0]=max(a[0],b[0]);
for(int i=1;i<=a[0];i++) {
a[i]+=b[i];
a[i+1]+=a[i]/Mod;
a[i]%=Mod;
}
if(a[a[0]+1]) ++a[0];
return ;
}
inline void Div(int *a,int b) {
int x=0;
for(int i=a[0];i>=1;i--) {
x=x*Mod+a[i];
a[i]=x/b; x%=b;
}
while(a[0]&&(a[a[0]]==0)) --a[0];
return ;
}
inline void Cal(int *a,int m,int n) {
a[0]=1; a[1]=1;
if(n>m){a[1]=0; return ;}
if(m==n){a[1]=1; return ;}
for(int i=1;i<=n;++i) {
Mul(a,m-i+1); Div(a,i);
}
return ;
}
int main(){
b[0]=1;b[1]=0;
cin>>n>>k;
int len=k/n;
if(k<=n){cout<<0;return 0;}
int x=(1<<n)-1;
for(int i=2;i<=len;i++) {
Cal(a,x,i); Add(b,a);
memset(a,0,sizeof(a));
}
if(k>len*n){
int p=k-len*n;
p=(1<<p)-1;
for(int i=1;i<=p;i++){
Cal(a,x-i,len); Add(b,a);
memset(a,0,sizeof(a));
}
}
Print(b);
return 0;
}————————————————————我是日期的分割线———————————————————————
2018.8.5
emm四道老题
T1【NOIP 2011】计算系数
直接杨辉三角递推(都知道二项式定理吧)
T2【NOIP 2011】选择客栈
我们发现k很小，所以就依据k来进行O(n)的递推
T3【NOIP 2010】关押罪犯
要使得剩下两部分的边权最大值最小，那么被断开的边权就要尽量的大。
所以就是把原图分成一张二分图，且使得这个二分图匹配的最小值最大。
二分+二分图判定。
听说有用并查集维护的方式，以后再看看。
T4【NOIP 2006】2^k进制数
emm手推一下求和的柿子。
然后写一个高精度就行了(居然有高精度除以单精度)
————————————————————我是日期的分割线———————————————————————
2018.8.6
今天还是四道题，但是不是老题了。
T1
Description
在直角坐标系上，有N个边平行于坐标轴的矩形。你的任务是把其中的K个矩形染色，使按次序放下后，可以看见的有色面积最大。可看见的意思就是这一部分没有被后面的矩形覆盖。
你的答案是返回K个整数，表示你染色的是哪K个矩形。如果有多种答案，输出字典序最小的。
Input
第一行两个整数：N K
后面有N行，每行4个整数: x1 y1 x2 y2, 分别表示先后各个矩形的左下角坐标和右上角坐标。
Output
一行，K个整数：你的方案。
Sample Input
3 2
1 1 5 3
3 2 7 4
2 5 9 7
Sample Output
1 2
数据范围
1<=N<=50； 1<=K<=N。
每个坐标值为[-10000,10000]之间的整数。
数据范围很小啊。
显然后来的矩形会覆盖之前的矩形，之前的矩形不会影响之后的矩形。
所以我们倒序算出每一个矩形的面积，选出最大的K个即可。
怎样算出面积呢？
由于数据过小，甚至可以暴力容斥。(我是不会的)
矩形面积可以用扫描线法。
由于坐标范围小，矩形个数少，所以可以暴力枚举扫描线。
(当然是可以使用线段树维护的。。。)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read() {
static char c;
int rec=0,f=0;
while((c=getchar())<'0'||c>'9') f|=c=='-';
while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();
return f?-rec:rec;
}
int n,K;
struct Squar {int x1,y1,x2,y2;} a[55];
int v[20005];
int ans[55],Y[105],X[105];
struct Mat {int id,S;} e[55];
inline bool operator < (const Mat &A,const Mat &B) {return A.S>B.S||A.S==B.S&&A.id<B.id;}
int main() {
n=read(); K=read();
for(int i=1;i<=n;++i) {
a[i]=(Squar){read(),read(),read(),read()};
e[i].id=i,e[i].S=0;
X[(i<<1)-1]=a[i].x1; X[i<<1]=a[i].x2;
}
sort(X+1,X+(n<<1)+1);
for(int i=1;i<=n<<1;++i)
if(X[i]!=X[i-1])
Y[++Y[0]]=X[i];
for(int i=1;i<=Y[0]-1;++i) {
memset(v,0,sizeof(v));
for(int j=n;j;--j) {
int sum=0;
if(a[j].x1<=Y[i]&&a[j].x2>=Y[i+1]) {
for(int pos=a[j].y1+1;pos<=a[j].y2;++pos)
if(v[10000+pos]==0) {
++sum;
v[10000+pos]=1;
}
e[j].S+=sum*(Y[i+1]-Y[i]);
}
}
}
sort(e+1,e+n+1);
for(int i=1;i<=K;++i) ans[i]=e[i].id;
sort(ans+1,ans+K+1);
for(int i=1;i<=K;++i) cout<<ans[i]-1<<" ";
return 0;
}T2
Description
对于排列 ( P 1 , P 2 ,..., P N ) ，定义 ( i , j ) 为逆序对当且仅当 i < j 且 P i > P j 。统计{1,2,..., N } 的所有排列中，逆序对数量为 M 的排列数量。
Input
第一行包含两个正整数 N ， M 。
Output
应包含一个整数 ， 表示满足条件的排列数除以 124567 的余数。
Sample Input
3 1
Sample Output
2
Hint
【数据规模和约定】
30%的数据 ， N ≤ 10 ；
100%的数据 ， 0 < N ， M ≤ 1000 。
【【【坑点：模数是124567,(3?,不存在的)】】】
我们考虑一下dp。
n^2的dp是可以接受的。
定义f(i,j)为前i个数组成了j个逆序对的排列方案数
对于新加入的第n个数，由于之前的数都比他小，所以把它放在第k个位置会增加n-k个逆序对。
这样我们就得到了一个n^3的dp(卡卡说不定能过？)
我们定义一下前缀和来优化就好了
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int dp[1005][1005];
int n,m;
int main(){
cin>>n>>m;
int i,j,k;
for(i=0;i<=n;i++)dp[i][0]=1;
for(i=1;i<=n;i++){
for(j=1;j<=min(m,i*(i-1)/2);j++){
dp[i][j]=(dp[i][j-1]+dp[i-1][j])%124567;
if(j>=i)dp[i][j]=(dp[i][j]-dp[i-1][j-i]+124567)%124567;
}
}
cout<<dp[n][m];
return 0;
}T3
【问题描述】
小PP因为整天思考如何摆放农田的问题，每天晚上都失眠，于是小PP每天晚上都在数羊。
对于每个羊i，都有一个吵闹程度a[i]，每个羊的吵闹程度都不同。
小PP要数的是对于羊i,j,k(i<j<k)满足(a[i]<a[k])而且(a[k]<a[j])的羊的3 元排列(i,j,k)组数。但是数到一半，小PP发现羊太多了，于是大吼一声：“你们别吵啦！”。
现在小PP想请你帮他数这样的羊的组数。
【输出】
输入的第一行有一个正整数N，即羊的总个数。
接下来一行有N个不同的正整数，第i个数表示第i 头羊的吵闹程度。
【输出】
输出有且仅有一个整数，即要求的羊的组数。
【输入样例】
3
1 3 2
【输出样例】1
【数据规模】
对于20%的数据,有N<=100；
对于40%的数据,有N<=1000；
对于60%的数据,有N<=100000；
10w的数据。。。
显然只能够nlogn了。
其实暴力数据结构一波就行，但是似乎需要树套树log^2。
所以我们运用一下补集转换的思想（由于是一个1~n的排列）
我当时脑残用了主席书，其实树状数组就行了。
贴一下考场的代码算了
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=200005;
inline int read() {
static char c; int rec=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();
return rec;
}
int n,a[Maxn];
#define mid ((L+R)>>1)
int root[Maxn],ind=0;
struct Persistent_Segment_Tree {int s[2],d;} tree[Maxn*30];
inline void Infix(int &v,int p,int L,int R,int x) {
v=++ind; tree[v]=tree[p]; ++tree[v].d;
if(L==R) return ;
int f=(x>mid); f?L=mid+1:R=mid;
Infix(tree[v].s[f],tree[p].s[f],L,R,x);
return ;
}
inline int Lower(int v,int L,int R,int lim) {
if(L>lim) return 0;
if(R<=lim) return tree[v].d;
return Lower(tree[v].s[0],L,mid,lim)+Lower(tree[v].s[1],mid+1,R,lim);
}
inline int Upper(int v,int L,int R,int lim) {
if(R<lim) return 0;
if(L>=lim) return tree[v].d;
return Upper(tree[v].s[0],L,mid,lim)+Upper(tree[v].s[1],mid+1,R,lim);
}
int main() {
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) Infix(root[i],root[i-1],1,n,a[i]);
long long ans=0;
for(int i=1;i<=n;++i) {
long long x=Lower(root[i],1,n,a[i]-1);
long long y=n-a[i]-(Lower(root[i],1,n,n)-Lower(root[i],1,n,a[i]));
ans+=y*(y-1-2*x)/2;;
}
cout<<ans;
return 0;
}T4
题面极长而且读不懂导致考场当场爆零
。。。
简化版题面：
给定一张无向图，要把这张无向图分为两个部分，分割的代价是断边中权值最大的一条。
现在有 Q次询问，每次给定两个点x、y,要求这两个点不能够分在同一侧，求最小的分割代价。
求出最大生成树之后输出x，y两点之间的最小边即可。
具体做法可以使用Kruskal重构树获得更加优越的时空复杂度以及代码复杂度。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=50005,Maxm=100005;
inline char C(){
static char buf[1<<20],*S=buf,*T=S;
return S==T&&(T=(S=buf)+fread(buf,1,1<<20,stdin),S==T)?EOF:*S++;
}
inline int read() {
static char c; int rec=0;
while((c=C())<'0'||c>'9');
while(c>='0'&&c<='9') rec=rec*10+c-'0',c=C();
return rec;
}
int n,m,Q,mod;
struct Edge {int a,b,w;} e[Maxm];
inline bool operator < (const Edge &A,const Edge &B) {return A.w>B.w;}
struct Branch {int next,to;} branch[Maxn<<1];
int h[Maxn<<1],cnt=0;
inline void add(int x,int y) {
branch[++cnt].to=y; branch[cnt].next=h[x]; h[x]=cnt; return ;
}
int fa[Maxn<<1],val[Maxn<<1];
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void Ex_Calibur() {
int ind=n,lim=n<<1; sort(e+1,e+1+m);
for(int i=1;i<=lim;++i) fa[i]=i;
for(int i=1;i<=m;++i) {
int fx=getfa(e[i].a),fy=getfa(e[i].b);
if(fx!=fy) {
fa[fx]=fa[fy]=++ind;
val[ind]=e[i].w;
add(ind,fx); add(ind,fy);
if(ind==lim-1) break;
}
} return ;
}
int size[Maxn<<1],deep[Maxn<<1];
int top[Maxn<<1],son[Maxn<<1];
inline void Dfs1(int v,int pre,int dep) {
size[v]=1; fa[v]=pre; deep[v]=dep;
for(int i=h[v];i;i=branch[i].next) {
int j=branch[i].to;
Dfs1(j,v,dep+1); size[v]+=size[j];
if(size[son[v]]<size[j]) son[v]=j;
} return ;
}
inline void Dfs2(int v,int T) {
top[v]=T; if(son[v]) Dfs2(son[v],T);
for(int i=h[v];i;i=branch[i].next) {
int j=branch[i].to;
if(j^fa[v]&&j^son[v]) Dfs2(j,j);
} return ;
}
inline int Ask(int x,int y) {
while(top[x]!=top[y]) deep[top[x]]<deep[top[y]]?y=fa[top[y]]:x=fa[top[x]];
return deep[x]<deep[y]?val[x]:val[y];
}
int main() {
n=read(); m=read(); Q=read(); mod=read();
for(int i=1;i<=m;++i)
e[i]=(Edge){read(),read(),read()};
Ex_Calibur();//突然...
Dfs1((n<<1)-1,0,1); Dfs2((n<<1)-1,(n<<1)-1);
int ans=1;
for(int i=1;i<=Q;++i) {
int x=read(),y=read();
ans=(1ll*ans*Ask(x,y))%mod;
}
cout<<ans;
return 0;
}————————————————————我是日期的分割线———————————————————————
2018.8.7
三道新题
T1
奇怪排序
【问题描述】
小明写了如下代码来完成排序，他的代码现在是这样的：
------------------
sorted = false
while (not sorted):
sorted = true
moo
for i = 0 to N-2:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = N-2 downto 0:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = 0 to N-2:
if A[i+1] < A[i]:
sorted = false
----------------------
moo 是一个输出语句，代码为缩进风格。给定一个输入数组，请预测该代码会输出多少次“moo”。
【输入格式】
输入的第一行包含N(1≤N≤100,000)。接下来N行描述了A[0]…A[N-1]，每个数都是一个范围为0…10^9的整数。输入数据不保证各不相同。
【输出格式】
输出“moo”被输出的次数。
【样例输入1】
5
1
8
5
3
2
【样例输出1】
2
这个"moo"，额，奶牛？USACO？
先不管这些，这道题看起来是一道智商题目。
我们读一下伪代码，发现好像是一个像冒泡排序的东西。(考场确实没有看出来)
显然，每一次操作都会至少把最小的数放在最前面，最大的数放在最后面。
对于一个数，如果有比它大的数在它的左边，那么一定会被交换一次。
如果只有简单的单向冒泡的话，那么答案就是所有数的逆序对中最大的一个，但是由于这段伪代码是双向的冒泡，所以有可能当前数自己去和前面的数交换。
我们把这些数字记下原有位置之后按照值的大小排序，然后由小到大判断逆序对的个数。
对于已经被访问过的数（就是有数已经略过了它），那么逆序个数减1
（其实还是不太懂）
#include<bits/stdc++.h>
using namespace std;
inline int read() {
static char c; int rec=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();
return rec;
}
int n,vis[100005],ans=1,cnt=0;
struct node {int x,id;} a[100005];
inline bool operator < (const node &A,const node &B) {return A.x<B.x||A.x==B.x&&A.id<B.id;}
int main() {
n=read();
for(int i=1;i<=n;++i)
a[i]=(node){read(),i};
sort(a+1,a+1+n);
for(int i=1;i<=n;++i) {
if(a[i].id>i) ++cnt;
if(vis[i]) --cnt;
ans=max(ans,cnt);
vis[a[i].id]=1;
} cout<<ans;
return 0;
}T2
观察顺序
【问题描述】
有一个编号为1…N（1≤N≤10^5）的排列，小明对数列进行了M次观察（1≤M≤50,000）。每个观察结果都是某些数的一个有序序列，表示这些数出现的顺序。比方说，如果小明的一次观察结果是序列2、5、1，则2在5的前面，5在1的前面。小明的观察结果是按优先级排列的，所以他的目标是最大化X的值，使得最终完整排列顺序能够符合前X个观察结果描述的状态。当多种排列顺序都能符合前X个状态时，小明会让编号较小的数放前面。请帮助小明求出该排列。
【输入格式】
第一行包含N和M。
接下来的M行，每行描述了一个观察结果。
第i+1行描述了观察结果i，第一个数是观察结果中的数的数量mi，后面是一列mi个整数，给出这次观察中的顺序。
所有mi的和至多为200,000
【输出格式】
输出N个空格分隔的整数，给出一个1…N的排列，为小明求出的该排列。
【样例输入】
4 3
3 1 2 3
2 4 2
3 3 4 1
【样例输出】
1 4 2 3
显然，我们可以认为形如 “A B” 的顺序意味着A>B。
这是一个单向的关系，对于一个合法的排列，一定不存在 A>B 且 B>A 的情况。
所以我们直接连一张有向图，判定是否为DAG即可。
简单来说，就是二分+Topsort。（字典序注意使用优先队列）
考试的时候犯傻用了Tarjan检验DAG（时间复杂度倒是没差）
T3
选数
【问题描述】
小明有N个数，方便起见编号为1…N，每个数俩个属性。他的第i个数属性1为wi，属性2为ti，两者都是整数。选数有如下规则：
（一）选出的一组数属性1之和至少为W
并且
（二）属性2总值与属性1总值的比值最大。
小明的有N个数属性1总值不小于W，所以他能够选出符合规则（一）的数。
【输入】
输入的第一行包含N和W。下面N行，每行用两个整数wi和ti描述了一个数。
1≤N≤250，1≤W≤1000，1≤wi≤10^6，1≤ti≤10^3
【输出】
请求出小明选数的最大可能达到的比值。如果你的答案是A，输出1000A向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。
【输入样例】
3 15
20 21
10 11
30 31
【输出样例】
1066
emmm考试的时候居然不知道什么是01分数规划（什么时候漏掉的知识点？）
好吧。
模板题啦，二分最值之后O(nw)dp判定
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const double eps=1e-9;
inline int read() {
static char c; int rec=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();
return rec;
}
int n,W;
int w[305],t[305];
double f[1005];
inline bool Check(double lim) {
for(int i=1;i<=W;i++) f[i]=-1e9;
for(int i=1;i<=n;i++){
double temp=(double)t[i]-(double)w[i]*lim;
for(int j=W;j>=W-w[i]&&~j;j--){
f[W]=max(f[W],f[j]+temp);
}
for(int j=W-1;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+temp);
}
}
return f[W]>=0;
}
int main() {
n=read(); W=read();
for(int i=1;i<=n;++i) w[i]=read(),t[i]=read();
double L=0,R=1000000,mid;
while(L+eps<R) {
mid=(L+R)/2;
if(Check(mid)) L=mid;
else R=mid;
}
cout<<int(L*1000);
return 0;
}————————————————————我是日期的分割线———————————————————————
2018.8.8
今天又回到了NOIp老题四连
T1【NOIP 2011】铺地毯
并不想说话。。。倒序判定即可
T2【NOIP 2011】聪明的质检员
我们发。。。。
算了，就是二分+判定，就是在二分的过程中注意一下更新答案即可。
T3【NOIP 2011】Mayan游戏
哇塞，noip特产之爆搜题。
贴一下程序。注意一个小优化（看注释啦）
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n;
int map[10][10];
struct ANS {int x,y,opt;} a[5];
inline bool Down() {
int F=0;
for(int i=1;i<=5;++i) {
for(int j=2;j<=7;++j) {
if(map[i][j]) {
int x=i,y=j;
while(map[x][y-1]==0&&y>1) {
F=1;
swap(map[x][y-1],map[x][y]);
--y;
}
}
}
} return F;
}
int flag[10][10];
inline void Clear() {
for(int i=1;i<=5;++i) {
for(int j=1;j<=7;++j) {
if(map[i][j]) {
int col=map[i][j];
if(i+2<=5) {
int x=i;
while(x+1<=5&&map[x+1][j]==col)
++x;
if(x-i>=2)
for(int t=i;t<=x;++t)
flag[t][j]=1;
}
if(j+2<=7) {
int y=j;
while(y+1<=7&&map[i][y+1]==col)
++y;
if(y-j>=2)
for(int t=j;t<=y;++t)
flag[i][t]=1;
}
}
}
}
for(int i=1;i<=5;++i)
for(int j=1;j<=7;++j)
if(flag[i][j])
map[i][j]=flag[i][j]=0;
return ;
}
inline bool Cleaned() {
for(int i=1;i<=7;++i)
for(int j=1;j<=5;++j)
if(map[i][j]) return 0;
return 1;
}
int FFLLAAGG=0;
void Dfs(int step) {
if(step==n) {
if(Cleaned()) {
for(int i=0;i<n;++i)
cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].opt<<'\n';
exit(0);
}
return ;
}
int temp[10][10];
memcpy(temp,map,sizeof(map));
for(int i=1;i<=5;++i) {
for(int j=1;j<=7;++j) {
if(map[i][j]) {
if(i<5) {
a[step].x=i-1; a[step].y=j-1; a[step].opt=1;
swap(map[i][j],map[i+1][j]);
Down();
do {
Clear();
} while(Down());
Dfs(step+1);
memcpy(map,temp,sizeof(map));
}
if(i>1&&!map[i-1][j]) {
//由于优先向右移，所以如果左边位置不是空格的话一定会先被向右的置换搜索到
a[step].x=i-1; a[step].y=j-1; a[step].opt=-1;
swap(map[i][j],map[i-1][j]);
Down();
do {
Clear();
} while(Down());
Dfs(step+1);
memcpy(map,temp,sizeof(map));
}
}
}
}
return ;
}
int main() {
cin>>n;
for(int i=1;i<=5;++i) {
int x,cnt=0;
while(1) {
cin>>x;
if(x==0) break;
map[i][++cnt]=x;
}
}
Dfs(0);
cout<<-1;
return 0;
}T4【NOIP 2011】观光公交
我们考虑一下没有Ｎ２的情况。
显然，汽车到达每一个点的时间t[i]=max(t[i-1],last[i-1])+d[i-1]
其中，last是到达第i个站点最晚的乘客的到达时间，d是两站之间的距离
如果有一段距离变短了会怎么样呢？
假设到第i个站点的距离减少了1，那么到达第i站的时间会减少1，到达第i+1站的时间也会减少1，以此类推。
《《《》》》
等等，好像有什么问题。
我们确实能够提前到达第i站，但是是否能够提前离开呢？
这就不一定吧。
所以我们再处理出来每一段路能够影响的最远的站点，那么如果在这一段路上使用了N2就会使得所有终点站在这一区间的乘客总等待时间减一。
显然，两次N2的使用是相互独立的，所以我们可以贪心的来取最大值，计算出人数的前缀之后查分是计算的好方法。
注意取值的时候不能取到距离为负，取完之后记得更新距离和到达时间。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=1005,Maxm=10005;
inline int read() {
static char c; int rec=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();
return rec;
}
int n,m,K,ans=0;
int d[Maxn],lastpsn[Maxn],t[Maxn],pcnt[Maxn],dic[Maxn];
struct Psn {int t,a,b;} a[Maxm];
int main() {
n=read(); m=read(); K=read();
for(int i=1;i<n;++i) d[i]=read();
for(int i=1;i<=m;++i)
a[i]=(Psn){read(),read(),read()};
for(int i=1;i<=m;++i) {
lastpsn[a[i].a]=max(lastpsn[a[i].a],a[i].t);
++pcnt[a[i].b];
}
for(int i=1;i<=n;++i) pcnt[i]+=pcnt[i-1];
t[1]=0;
for(int i=2;i<=n;++i)
t[i]=max(t[i-1],lastpsn[i-1])+d[i-1];;
for(int i=1;i<=m;++i)
ans+=t[a[i].b]-a[i].t;
while(K--) {
dic[n-1]=n;
for(int i=n-2;i;--i)
if(t[i+1]>lastpsn[i+1])
dic[i]=dic[i+1];
else dic[i]=i+1;
int maxx=0,id;
for(int i=1;i<n;++i)
if(pcnt[dic[i]]-pcnt[i]>maxx&&d[i]>0)
maxx=pcnt[dic[i]]-pcnt[i],id=i;
--d[id]; ans-=maxx;
for(int i=id+1;i<=n;++i)
t[i]=max(t[i-1],lastpsn[i-1])+d[i-1];
}
cout<<ans;
return 0;
}
下一篇： 实现session版本购物车
推荐阅读