NOIP模拟题 2015.8.2 T1
题解：考场上面感觉这就是个容斥，于是一直在推式子，一直推到考试结束= =后来讲题才知道这是个DP，设ai,j代表第i轮那个人选数后gcd变成j的概率，然后用j和所有数做一次gcd，然后就可以转移了，但是其中有i个gcd为j的不能转移。然后第二问就可以直接SG搞了，复杂度n^2m
P.S.不知道为毛用SmartC++调试了一下之后代码在sublime里面就不能看了= =
后来手动加空格总算是好了些了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 305
#define M 1050
int n,m,sg[N][M],g[M][M],v[N],b[M],st=0;double s[N][M],ans=0;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int gcd(int x,int y)
{
if (g[x][y])
return g[x][y];else
return g[x][y]=(y?gcd(y,x%y):x);
}
void Down(int x,int y)
{
if (!s[x][y]) return;
int w=0,e=0;double q=s[x][y]/(n-x);
for (int i=1;i<=n;i++)
{
e=gcd(y,v[i]);
if (e==y) w++;else
if (e!=1) s[x+1][e]+=q;else
ans+=(x&1)*q;
}
s[x+1][y]+=q*(w-x);
}
void Solve(int x,int y)
{
if (!s[x][y]) return;
int k=0;st++;
for (int i=1;i<=n;i++)
{
if (g[y][v[i]]==y) k++;else
if (g[y][v[i]]!=1) b[sg[x+1][g[y][v[i]]]]=st;
}
if (k!=x) b[sg[x+1][y]]=st;
for (int i=0;i<=n;i++)
if (b[i]!=st) {sg[x][y]=i;return;}
}
int main()
{
freopen("game.in","r",stdin);freopen("game.out","w",stdout);
n=Read();
for (int i=1;i<=n;i++) v[i]=Read();
s[0][0]=1;Down(0,0);
for (int i=1;i<n;i++)
for (int j=1;j<=1000;j++)
Down(i,j);
if (n&1)
for (int i=1;i<=1000;i++) ans+=s[n][i];
printf("%.9lf ",ans);
for (int i=n;i>0;i--)
for (int j=1000;j>=1;j--)
Solve(i,j);Solve(0,0);
if (sg[0][0]) puts("1.000000000");else
puts("0.000000000");
return 0;
}
NOIP模拟题 2015.8.2 T3
题解：有一个暴力是将r-l+1个数排序之后从小到大加，设已经加的数的和为s，当前要加ai，如果s<ai-1则不能加s（然而这个我在考场上面都没想到）于是正解就是优化一下，考虑每次加数把可以加的都加进来，于是s每次扩大一倍，至于加哪些数可以用主席树，复杂度为n log^2 n。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 1073741824
int gf[N],st=0,s[N*50],c[N*50][2],v[N],n,m;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int Set_up(int x,int y,int z,int o)
{
int i=x + y >> 1,j=++st;
if (x==y) {s[j]=s[z]+o;return j;}
if (o<=i) c[j][1]=c[z][1],c[j][0]=Set_up(x,i,c[z][0],o);else
c[j][0]=c[z][0],c[j][1]=Set_up(i+1,y,c[z][1],o);
s[j]=s[c[j][0]]+s[c[j][1]];
return j;
}
int Find(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=0;
if (x==p&&y==u) return s[o]-s[z];
if (p<=i) j=Find(x,i,c[z][0],c[o][0],p,min(u,i));
if (u>i) j+=Find(i+1,y,c[z][1],c[o][1],max(p,i+1),u);
return j;
}
int Solve(int y,int x)
{
int k=0,l=0,q=0;
do
{
l=Find(0,M-1,gf[x-1],gf[y],q+1,k+1);
if (!l) return k+1;
q=k+1;k=k+l;
} while (1);
}
int main()
{
freopen("hhsum.in","r",stdin);
freopen("hhsum.out","w",stdout);
n=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=n;i++)
gf[i]=Set_up(0,M-1,gf[i-1],v[i]);
m=Read();
while (m--)
printf("%d\n",Solve(Read(),Read()));
return 0;
}
NOIP模拟题 2015.8.1 T2
感觉题解还是要放的正常向一点，还是一题一题放吧= =
题意：给定一张无向图，每条边有通过这条边消耗的油量，有一些点是加油点，可以补满油，然后有q个询问从一个加油点往另外一个加油点走，油箱容量为v，问能否到达。
输入格式：第一行四个整数n m p k分别是点、边、询问和加油点数，第二行k个加油点的编号，接着m行每行三个整数u、v和d代表u和v之间有耗油为d的边相连，最后p行每行三个整数u、v、d询问u到v在容量只有d的时候能否到达
输出格式：q行“YES”或者“NO”
Sample Input:
题解：这题之前VFK讲课时讲过，不，应该说则就是VFK出的题。然而并忘（睡）了= =，而且T3是一道恶心的点分治/set启发式合并题，写的比较蛋痛，也没时间想这道题了。
然而这题有个结论：设点i的最近加油点为Ai，这两点的距离为Si，于是我们考虑重建一个只有加油点的图，原来的连i-j的边变成Ai-Aj，边权变成Si+Sj+Vi-j。由于脑补可以发现这样是不会使两点之间距离变大，如果有一条经过非加油点u、v的路径i->u->v->j并且i和j不是u、v的最近点的话画一画图可以发现在走去Ai和Aj一定是会更优的
于是设一个S连向所有加油点，SPFA一下求出所有点的Ai，然后就是最小生成树还有倍增了= =
话说在这里贴一张VFK题解：
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
#define N 300050
#define M 1000050
#define fr first
#define sc second
#define INF 0x7f7f7f7f
pair <int,int> yz[M];
int ne[M*2][3],ln[M][3],fi[N],nr[N],sg[N],n,m,ff[N];
int ss=1,s[N],gf,qu,zy,fa[N][20],ma[N][20],h[N];
queue <int> li;
bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
ne[++ss][0]=y;ne[ss][1]=fi[x];ne[ss][2]=z;fi[x]=ss;
ne[++ss][0]=x;ne[ss][1]=fi[y];ne[ss][2]=z;fi[y]=ss;
}
void SPFA()
{
for (int i=1;i<=n;i++) s[i]=INF;
for (int i=1;i<=zy;i++)
s[sg[i]]=0,li.push(sg[i]),b[sg[i]]=1,nr[sg[i]]=sg[i];
while (!li.empty())
{
int k=li.front();li.pop();b[k]=0;
for (int i=fi[k];i;i=ne[i][1])
if (s[ne[i][0]]>s[k]+ne[i][2])
{
s[ne[i][0]]=s[k]+ne[i][2];nr[ne[i][0]]=nr[k];
if (!b[ne[i][0]])
b[ne[i][0]]=1,li.push(ne[i][0]);
}
}
return;
}
int Find(int x)
{return ff[x]==x?x:(ff[x]=Find(ff[x]));}
void Kruskal()
{
sort(yz+1,yz+m+1);
for (int i=1;i<=m;i++)
{
int k=nr[ln[yz[i].sc][0]],l=nr[ln[yz[i].sc][1]],
q=Find(k),w=Find(l);
if (q==w) continue;
ff[q]=w;Line(k,l,yz[i].fr);
}
return;
}
void Set_up()
{
memset(s,0,sizeof(s));
gf=sg[1];li.push(gf);s[gf]=1;
while (!li.empty())
{
int k=li.front();li.pop();
for (int i=fi[k];i;i=ne[i][1])
if (!s[ne[i][0]])
s[ne[i][0]]=s[k]+1,fa[ne[i][0]][0]=k,
ma[ne[i][0]][0]=ne[i][2],li.push(ne[i][0]);
}
for (int i=1;i<=18;i++)
{
for (int j=1;j<=zy;j++)
ma[sg[j]][i]=max(ma[sg[j]][i-1],
ma[fa[sg[j]][i-1]][i-1]),
fa[sg[j]][i]=fa[fa[sg[j]][i-1]][i-1];
}
return;
}
int Query(int x,int y)
{
int k=0;
if (s[x]<s[y]) swap(x,y);
for (int i=18;i>=0;i--)
if (s[x]-(1 << i)>=s[y])
k=max(k,ma[x][i]),x=fa[x][i];
for (int i=18;i>=0;i--)
if (fa[x][i]!=fa[y][i])
k=max(max(k,ma[x][i]),ma[y][i]),x=fa[x][i],y=fa[y][i];
if (x!=y)
k=max(max(k,ma[x][0]),ma[y][0]);
return k;
}
int main()
{
freopen("petrol.in","r",stdin);freopen("petrol.out","w",stdout);
n=Read();m=Read();zy=Read();qu=Read();
for (int i=1;i<=zy;i++) sg[i]=Read(),ff[sg[i]]=sg[i];
for (int i=1;i<=m;i++)
ln[i][0]=Read(),ln[i][1]=Read(),ln[i][2]=Read(),
Line(ln[i][0],ln[i][1],ln[i][2]);
SPFA();ss=1;
memset(fi,0,sizeof(fi));
for (int i=1;i<=m;i++)
yz[i].sc=i,yz[i].fr=ln[i][2]+s[ln[i][0]]+s[ln[i][1]];
Kruskal();Set_up();
while (qu--)
{
int q=Read(),w=Read(),e=Read();
if (e>=Query(q,w)) puts("YES");else
puts("NO");
}
return 0;
}
UOJ #134
题面：给定一张无向图，然后将其中一些边定向，要求将剩下的无向边也定向，使得原无向图中的连通块在变成有向图之后还是在同一个强连通分量。（n,m<=5000）
题解：好神啊，考场上面并没有想出来，连60分暴力都斜挂了= =
有一个性质：在当前还没定向完的图中对于每条边的两个点u和v要不就u不通过这条边可以到达v，要不就是v可以不通过这条边可以到达u。然后就可以暴力遍历整张图然后判断是哪种情况就可以定向了。
看完证明感觉还是很有道理，移步这♂里♂
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 5050
int b[N][N],d[N],n,m,fi[N],c[N*2][2],ss=1,ln[N][3],now;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;b[x][y]++;}
void DFS(int x)
{
d[x]=now;
for (int i=fi[x];i;i=c[i][1])
if (b[x][c[i][0]]&&d[c[i][0]]!=now) DFS(c[i][0]);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
ln[i][0]=Read();ln[i][1]=Read();ln[i][2]=Read();
Line(ln[i][0],ln[i][1]);
if (!ln[i][2]) Line(ln[i][1],ln[i][0]);
}
for (int i=1;i<=m;i++)
if (!ln[i][2])
{
now++;b[ln[i][0]][ln[i][1]]--;
DFS(ln[i][0]);b[ln[i][0]][ln[i][1]]++;
if (d[ln[i][1]]==now)
b[ln[i][0]][ln[i][1]]--,puts("1");else
b[ln[i][1]][ln[i][0]]--,puts("0");
} else puts("0");
return 0;
}
最近的几次比赛
最近感觉RP好吼，打了场BC的Rank1，还有UOJ的rank12，之前还有场CF div1
CF那场第三题挂的莫名其妙，但还是涨了100+RT，真是不知道smg
BC那场T2纯暴力一开始不敢写，还naive以为要用什么回文自动机这种我不会的高端东西，想了很久没想出来。后来弃疗去看UOJ群发现暴力大法可以过，虽然知道肯定会被hack但是还是交了一发暴力= =然后构造了一个可以hack掉我这个数据的N/2-1个a+1个b+1个c+N/2-1个d，感觉可以卡的死死的。room还是第五。后来hack时间随便点开了几个跟我的代码长得比较面善的hack掉了，而且还有个人一开始准备hack我，但是并没有得逞。然而我感觉这种暴力并很好hack啊，但是至少我们房间没什么人屑于= =不知道为什么。于是非常愉快的hack了4个人之后就结束了，复测完之后发现几个三题爷都挂掉了，然后本来还坐等第二题挂掉结果没能如愿，uwi十分魔性的在10分钟之内切掉前两题（主要是看出了第二题暴力），但是不屑于hack于是我神奇的rank1了，拿68元真是感到喜闻乐见。
然后后面那场BC感觉就比较caodan了，第二题题面简直什么鬼，rating掉掉掉！！！（话说最近几场BC的质量都很拙计啊）
昨天还用我那个负rating的大号考了UOJ，前面半小时撸完第一题，第二题弃疗之后交了个理论60分暴力，第三题提答题sxbk，我还不会用终端，于是后面耗掉一个小时摸索+膜duyege怎么破，然后30分钟准备随机十个点，然而喜闻乐见的是由于时间分配只搞出了6个点，并且在最后被网速成功卡掉最后的交题，不过还好分本来就不多，名次也只会升一名。后来看到12名感觉非常吓人（虽然之前考过一次rank 7的Goodbye Jiawu）但是看到参加人数感觉又比较正常。复测粗来第二题成功写跪20分，但是还好第一题只跪了extra test，第三题爆两分了，感觉还是比没分好TATQAQ2333。后面的人虽然都不是很认识，然而发现yali的两个大爷好像在后面的样子，主要都是T1跪了。。。
所以感觉最近RP还有rating都涨的比较喜闻乐见，我自然也喜闻乐见。
