NOIP2017提高组 模拟赛13（总结）
第一题 函数
【题目描述】
【输入格式】
三个整数。
1≤t＜109+7,2≤l≤r≤5*106
【输出格式】
一个整数。
【输出样例】
2 2 4
【输出样例】
19
【解题思路】
证明：对于n个人，分解成质因数，按质数个人分为一组（从小到大）。
例如：30可以分成2 * 3 * 5，那么一开始2人为一组，共有15组。再分成3人为一组，然后有5组。再分成5人一组，有1组。
为什么这是最优的？
ａ,ｂ是n的质因数
设\(\frac{n}{ab}=x\)
\(bx\frac{a(a-1)}{2}+x\frac{b(b-1)}{2}=\frac{bx}{2}(a²-a+b-1)\)
\(x\frac{ab(ab-1)}{2}=\frac{bx}{2}(a²b-a)\)
∵a,b>=2
∴(a²b-a)>(a²-a+b-1)
由(a²-a+b-1)可得，a＜b会比a>b优。
证毕。
【代码】
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mods=1e9+7;
const int N=7000000;
int pr[N],lp,n,L,R,t;
bool inp[N],re[N];
ll F[N],ans,tl;
void getpr()
{
inp[1]=1;
for(int i=2;i<=n;i++)
{
if(!inp[i]) { pr[++lp]=i; F[i]=(((ll)i*(i-1))>>1)%mods; re[i]=1; }
for(int j=1;(ll)i*pr[j]<=n && j<=lp;j++)
{
F[pr[j]*i]=(F[pr[j]]*i%mods+F[i])%mods;
inp[pr[j]*i]=1;
if(!(i%pr[j])) break;
}
}
}
int main()
{
freopen("2233.in","r",stdin);
freopen("2233.out","w",stdout);
scanf("%d%d%d",&t,&L,&R);
n=R; getpr(); tl=1ll; ans=0ll;
for(int i=L;i<=R;i++)
{
ll k=F[i];
ans=(ans+tl*k%mods)%mods;
tl=tl*t%mods;
}
printf("%lld\n",ans);
return 0;
}
第二题 部落
【题目描述】
部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。
现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。
同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。
如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。
你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
【输入格式】
第一行一个整数N
接下来N行每行两个整数T1，T2，表示修该建筑需要T1秒，要在T2秒之前修完。
【输出格式】
一个整数表示最多能抢救的建筑数量。
【输入样例】
4
100 200
200 1300
1000 1250
2000 3200
【输出样例】
3
【数据规模】
对于40%的数据，T2<=1000000
对于100%的数据，N <= 150,000; T1 < T2 < maxlongint
【解题思路】
一个简单的推论：假若建筑i的T2＜建筑j的T2，而且建筑i的T1≥建筑j的T1，总时间+T1＜建筑j的T2，那么将i替换成j，答案会更优。（贪心）
所以，用大根堆维护最大值，每次将最大值判断一下，是否需要替换掉即可。
【代码】
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mods=1e9+7;
const int N=150500;
struct data { int a,b,id; } d[N];
int n,ans,h[N],cnt;
bool cmp(data A,data B) { return (A.b<B.b); }
void add(int x)
{
cnt++; h[cnt]=x;
int now=cnt;
while((now>1) && (d[h[now>>1]].a<d[h[now]].a))
{
swap(h[now>>1],h[now]);
now>>=1;
}
}
void down()
{
h[1]=h[cnt]; cnt--;
int now=1;
while((now<<1)<=cnt)
{
int uw;
if((now<<1|1)>cnt) uw=now<<1; else uw=(d[h[now<<1]].a>d[h[now<<1|1]].a)?(now<<1):(now<<1|1);
if(d[h[now]].a<d[h[uw]].a) swap(h[now],h[uw]); else break;
now=uw;
}
}
int main()
{
freopen("2234.in","r",stdin);
freopen("2234.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&d[i].a,&d[i].b),d[i].id=i;
sort(d+1,d+1+n,cmp);
int tim=0;
for(int i=1;i<=n;i++)
{
if(tim+d[i].a<=d[i].b)
{
tim+=d[i].a;
ans++; add(i);
} else
{
int yu=h[1];
if(d[yu].a>d[i].a)
{
tim+=d[i].a-d[yu].a;
down(); add(i);
}
}
}
printf("%d\n",ans);
return 0;
}
第三题 sunny图（原题 codeforces 603E）
【题目描述】
【输入格式】
第一行两个整数n和m。
接下来m行每行三个整数。ai,bi,li。
【输出格式】
共m行，每行一个整数表示每次操作的答案。
【输入样例】
4 4
1 3 4
2 4 8
1 2 2
3 4 3
【输出样例】
-1
8
8
3
【数据规模】
１≤ai,bi≤n，1≤li≤10^9
对于20%的数据，2≤n小于等于15，1≤m≤15。
对于40%的数据，2≤n小于等于100，1≤m≤100。
对于60%的数据，2≤n小于等于500，1≤m≤2000。
对于100%的数据，2≤n小于等于100000，1≤m≤300000。
【解题思路】
一个重要的推论（然而并没有推出来）：
将图分成若干个联通块，每个联通块的点数均为偶数，那么就是sunny图。
为什么？（分类讨论）
假如有一个偶数点的图，一定可以划分成一棵树。
那么设根节点为father，father的点数为奇数的儿子sonY一定为奇数个，奇 * 奇+偶 * （偶 或 奇）+1=偶。那么将sonX与father的边cut掉，就满足了father的度数为奇数（奇数条与儿子的边）的情况。
那么点数为奇数的儿子sonY，仍保留与father的边。那么sonY的点数为奇数的儿子Y一定有偶数个，奇 * 偶+偶 * （偶 或 奇）+1=奇。那么将X与sonY的边cut掉，就满足了sonY的度数为奇数（偶数条与儿子的边+与父亲的边）的情况。
点数为偶数的儿子sonX的情况与第一种类似（是完全一样好吧）。
那么，树是自己造的，边随便搞，加入一条x->y的边，若x，y之前已经连通，就把路径上的最大边删了，加入新边（在新边小于最大边的情况下）
至于联通块分成两个偶数块，判断删除最大边L后，剩下的两个联通块点数是否为偶数就行了。
需要用LCT维护子树大小。
具体应该是这样：
多个splay树通过parent边相连。
在每个splay树记录一个sub，表示整棵splay树的奇偶（仅仅是splay树）
再记一个all，表示整个子树i包括相连的splay树的奇偶（在splay树合并或断开的时候更新）
【代码】
//codeforce 603E
#include<cstdio>
#include<algorithm>
#include<set>
#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))
using namespace std;
const int N=400010;
struct tree { int mx,val,sub,all,zi; } s[N];
int c[N][2],fa[N],rev[N];
int H[N],ht,W[N];
int n,m,odd,cnt;
int stack[N];
//int F[N];
struct godD { int a,b,l; } d[N];
//set <pair<int,int> > hp;
bool gd(int x) { return (c[fa[x]][1]==x); }
bool isroot(int x) { return (c[fa[x]][0]!=x && c[fa[x]][1]!=x); }
int MAX(int x,int y)
{
if(!x || !y) return x+y;
return ((s[x].val>s[y].val)?(x):(y));
}
void up(int x)
{
s[x].all=s[x].sub^s[x].zi;
s[x].mx=x;
if(c[x][0]) s[x].all^=s[c[x][0]].all;
if(c[x][1]) s[x].all^=s[c[x][1]].all;
s[x].mx=MAX(s[x].mx,s[c[x][0]].mx);
s[x].mx=MAX(s[x].mx,s[c[x][1]].mx);
}
void down(int x)
{
if(rev[x])
{
rev[x]^=1;
rev[c[x][0]]^=1; rev[c[x][1]]^=1;
swap(c[x][0],c[x][1]);
}
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int l=gd(x),r=!l;
if(!isroot(y)) c[z][gd(y)]=x;
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
up(y); up(x);
}
void splay(int x)
{
int hy=0; stack[++hy]=x;
for(int i=x;!isroot(i);i=fa[i]) stack[++hy]=fa[i];
for(int i=hy;i;i--) down(stack[i]);
for(;!isroot(x);)
{
int y=fa[x];
if(!isroot(y)) (gd(x)^gd(y))?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x)
{
int y=0;
while(x)
{
splay(x);
down(x);
if(y) s[x].sub^=s[y].all;
if(c[x][1]) s[x].sub^=s[c[x][1]].all;
c[x][1]=y;
up(x);
y=x;
x=fa[x];
}
}
void evert(int x)
{
access(x); splay(x); rev[x]^=1;
}
int findroot(int x)
{
access(x); splay(x);
while(c[x][0]) x=c[x][0];
return x;
}
void link(int x,int y)
{
evert(x); evert(y);
fa[x]=y; s[y].sub^=s[x].all;
up(y);
}
void cut(int x,int y)
{
evert(x); access(y); splay(y);
fa[x]=0; c[y][0]=0;
up(y);
}
void Cut(int u)
{
int x=d[u].a,y=d[u].b;
cut(x,u+n); cut(y,u+n);
}
bool cle(int u)
{
int x=d[u].a,y=d[u].b;
cut(x,u+n); cut(y,u+n);
if(!s[x].all && !s[y].all) return 1;
link(x,u+n); link(y,u+n);
return 0;
}
void add(int x)
{
H[++ht]=x; int now=ht;
while((now>1) && d[H[now>>1]].l<d[H[now]].l)
{
swap(H[now>>1],H[now]);
now>>=1;
}
}
void hdown()
{
H[1]=H[ht--]; int now=1;
while((now<<1)<=ht)
{
int uw;
if(((now<<1)|1)>ht) uw=(now<<1); else uw=(d[H[now<<1]].l>d[H[now<<1|1]].l)?(now<<1):(now<<1|1);
if(d[H[now]].l<d[H[uw]].l)
{
swap(H[now],H[uw]);
} else break;
now=uw;
}
}
//int findroot(int x) { return ((F[x]<0)?(x):(F[x]=findroot(F[x]))); }
/*void uni(int x,int y)
{
int ix=findroot(x),iy=findroot(y);
if(F[ix]>F[iy]) swap(ix,iy);
F[ix]+=F[iy]; F[iy]=ix;
}*/
int main()
{
freopen("2235.in","r",stdin);
freopen("2235.out","w",stdout);
scanf("%d%d",&n,&m);
odd=n; ht=0;
for(int i=1;i<=n;i++) s[i].all=s[i].zi=1;
for(int i=1;i<=m;i++)
{
int lx,ly,cost;
scanf("%d%d%d",&lx,&ly,&cost);
d[i].a=lx; d[i].b=ly; d[i].l=cost;
s[i+n].val=cost; s[i+n].mx=i+n;
if(findroot(lx)!=findroot(ly))
{
evert(lx); evert(ly);
if(s[lx].all && s[ly].all) odd-=2;
link(lx,i+n); link(ly,i+n);
W[i]=1; add(i); //uni(lx,ly);
//hp.insert(make_pair(-cost,i));
} else
{
evert(ly); access(lx); splay(lx);
int yu=s[lx].mx;
if(s[yu].val>cost)
{
Cut(yu-n);
link(lx,i+n); link(ly,i+n);
W[i]=1; W[yu-n]=0; add(i);
//hp.erase(make_pair(-s[yu].val,yu-n));
//hp.insert(make_pair(-cost,i));
}
}
if(odd==0)
{
for(;;)
{
int yu=H[1];
if(!W[yu] || cle(yu)) hdown(); else break;
}
printf("%d\n",d[H[1]].l);
} else printf("-1\n");
/*if(odd==0)
{
for(;;)
{
int e=(*hp.begin()).second;
if(cle(e)) hp.erase(hp.begin()); else break;
}
printf("%d\n",-(*hp.begin()).first);
} else printf("-1\n");*/
}
return 0;
}