C++博客-Omni Inspirations

此OI博客废弃

jsn1993 — Sat, 21 Aug 2010 06:09:00 GMT

rt 请勿再来访问

jsn1993 2010-08-21 14:09 发表评论

NOI完挂，不解释

jsn1993 — Wed, 11 Aug 2010 06:19:00 GMT

http://hi.baidu.com/jsn1993/blog/item/dc909f3cf436080dbba16734.html

jsn1993 2010-08-11 14:19 发表评论

NOI bless

jsn1993 — Sun, 01 Aug 2010 13:24:00 GMT

bless.

jsn1993 2010-08-01 21:24 发表评论

来除草关于ceoi

jsn1993 — Tue, 27 Jul 2010 00:56:00 GMT

ceoi day1,2 我就没把该拿的分都拿了

day1 网络流除了建图考细节其他没trick 解方程那个我忘记判了1*1的情况导致只有10分第三题不会..
day2 mp3题太长了第二题容斥D=1, 2, 3都是对的, D=4的时候因为G[4]打成F[4]然后挂了30分.. 第三题问了hyc才成了个水题....本来只会45分的

总之我就是个傻子

jsn1993 2010-07-27 08:56 发表评论

COCI难题大作战

jsn1993 — Sat, 17 Jul 2010 07:23:00 GMT

难实在是难..

jsn1993 2010-07-17 15:23 发表评论

ceoi 2010 bless

jsn1993 — Wed, 14 Jul 2010 05:42:00 GMT

bless

jsn1993 2010-07-14 13:42 发表评论

饶了我吧！！

jsn1993 — Sun, 04 Jul 2010 14:15:00 GMT

CAVLI我知道你是个牛题虐倒无数人就让我过了吧。。饶了我吧 CAVLI！！

jsn1993 2010-07-04 22:15 发表评论

各种被虐

jsn1993 — Fri, 02 Jul 2010 08:23:00 GMT

KRTICA 想不出
CAVLI 写不出

再写不出就不出去了

jsn1993 2010-07-02 16:23 发表评论

继续被虐

jsn1993 — Wed, 30 Jun 2010 01:32:00 GMT

教主的模拟赛题太牛了。。

ALADIN太难写了。。

PALACINKE太难想了。。

如果这种题noi放出来我就弯蛋了

jsn1993 2010-06-30 09:32 发表评论

这两天净被虐

jsn1993 — Thu, 24 Jun 2010 01:58:00 GMT

做的我脑残死了....

话说SDOI2010 round2 的 k短路数据也太弱了吧....

jsn1993 2010-06-24 09:58 发表评论

COI 2010 hrastovi

jsn1993 — Sun, 20 Jun 2010 06:07:00 GMT

蛋疼无聊来发个水题

题意：给定N个点，M个询问，每次询问(x1,y1)与(x2,y2)为对点构成的正方形严格边缘上有多少个点。

做法：
把问题转化成求一条线段上的点个数对于每个询问只要查找四条直线上有多少点即可。
这个很简单，排序+二分即可。（注意处理细节，最好想好区间的开闭再写）
我偷懒用了lower_bound和upper_bound..

1 #include <cstdio>
2 #include <vector>
3 #include <cstdlib>
4 #include <algorithm>
5 using namespace std;
6 vector<pair<int,int> >    X,Y;
7 int N,Que,x,y,x1,y1,x2,y2;
8 inline int Q_fow(vector<pair<int,int> > &P,int x,int y1,int y2)
9 {
10     return upper_bound(P.begin(),P.end(),make_pair(x,y2))-upper_bound(P.begin(),P.end(),make_pair(x,y1));
11 }
12 inline int Q_rev(vector<pair<int,int> > &P,int x,int y1,int y2)
13 {
14     return lower_bound(P.begin(),P.end(),make_pair(x,y2))-lower_bound(P.begin(),P.end(),make_pair(x,y1));
15 }
16 int main()
17 {
18     scanf("%d",&N);
19     for (int i=0;i<N;++i)
20     {
21         scanf("%d%d",&x,&y);
22         X.push_back(make_pair(x,y));
23         Y.push_back(make_pair(y,x));
24     }
25     sort(X.begin(),X.end());
26     sort(Y.begin(),Y.end());
27     scanf("%d",&Que);
28     for (;Que--;)
29     {
30         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
31         printf("%d\n",Q_fow(X,x1,y1,y2)+Q_fow(Y,y2,x1,x2)+Q_rev(X,x2,y1,y2)+Q_rev(Y,y1,x1,x2));
32     }
33     return 0;
34 }
35

jsn1993 2010-06-20 14:07 发表评论

吐槽吐槽发泄心中不爽

jsn1993 — Wed, 16 Jun 2010 09:05:00 GMT

tmd昨天那个TLE还没解决

今天这道要求O(N)的题目我连nlogn都调不好想不通

唉...太2了

jsn1993 2010-06-16 17:05 发表评论

没事来吐sxngt

jsn1993 — Wed, 16 Jun 2010 06:27:00 GMT

朝鲜队v5

【4X+2】年的六月份总是这么带有激情...

上午看总决赛中间有个画面大概说1962年和1966年都是世界杯+总决赛
同样的lakers vs celtics 同样的3:2 同样的第六场lakers赢同样的celtics总冠军....

放这个东西的人意思是今年celtics拿总冠军是宿命?还在湖人主场比赛的时候这么放?.

好吧我想多了

jsn1993 2010-06-16 14:27 发表评论

youdao nanti4

jsn1993 — Tue, 15 Jun 2010 02:53:00 GMT

这场比赛就tmd一坨屎。。。。

在1:24 ACRush第一个过了CTSC2006的投篮游戏
然后当我想去看世界杯的时候他说第一题改成单组评分后两题也单组评分

然后我就被有道骗分大赛弄傻了

然后的然后我就只有72分最后就掉出了300名。

结果我就这么被虐傻了

jsn1993 2010-06-15 10:53 发表评论

...after 6.9 holy-war

jsn1993 — Thu, 10 Jun 2010 01:24:00 GMT

请看到此文的人编辑C:\WINDOWS\system32\drivers\etc\hosts
加入一行 203.208.39.99 www.baidu.com
然后在浏览器地址栏输入www.baidu.com
坚决抵制【全球最大的【中文】搜索引擎】baidu的nc行为

jsn1993 2010-06-10 09:24 发表评论

codejam R2

jsn1993 — Sun, 06 Jun 2010 03:22:00 GMT

。。我就是个杯具内幕不解释

B是个dp题 F[k][l][r]表示l到r从宽到窄被覆盖了k次用记忆化搜实现
每次枚举这层放不放从F[k(+1)][l][(l+r)>>1]和F[k(+1)][(l+r>>1)+1][r]推导得到

C-small是个傻子都会做的模拟

D-small是个公式

jsn1993 2010-06-06 11:22 发表评论

5.29

jsn1993 — Sat, 29 May 2010 14:04:00 GMT

今天真是个rp低的日子

省选第三题的骗分来不及了有道最后第三题来不及了都挂了挂了啊！都挂了！！！！

jsn1993 2010-05-29 22:04 发表评论

JSTSC 2010 group

jsn1993 — Wed, 26 May 2010 02:06:00 GMT

题意：
给你N<=1000个平面上的点让你将这些点划分为K<=N个部分，使得最靠近的两个部落尽量远离。

做法：
这个题初看好像没什么思路所以我们要发掘它的本质

本题等价于将初始N个连通块通过N-K次有效合并成K个连通块，使得剩下的连接两个不同连通块的最小边最大。
恰恰Kruskal算法的目标便是通过合并得到1个连通块，使最大的边最小，即剩下的最小边最小。

考虑这两者的联系，我们可以设计这样一个算法：
我们用Kruskal的做法，并查集合并N-K+1次时，这条边便是答案。
简单地不严谨地证明一下这个是最优解：
对于已经生成的划分边集E，其中有N-K条有效合并边
我们用一条不在E集合中的边去替换E集合中的边这两条边必然是同一个性质的
1.一条可合并边替换了一条有效合并边：剩下的连接不同连通块的最小边成为了换出来的边不可行
2.一条非可合并边替换一条非有效合并边：对原来的解不产生变化
所以这样就可以解决了此题

1 #include <cstdio>
2 #include <cmath>
3 #include <algorithm>
4 using namespace std;
5 struct TEdge
6 {
7     int w,x,y;
8 }    e[1000005];
9 int Ance[1005],X[1005],Y[1005],N,K,E;
10 inline TEdge TEdge_make(int w,int x,int y)
11 {
12     TEdge ret;
13     ret.w=w,ret.x=x,ret.y=y;
14     return ret;
15 }
16 inline int GetAnce(int x)
17 {
18     int p=x,q=x,k=Ance[x];
19     for (;p!=Ance[p];p=Ance[p]);
20     for (;q!=p;Ance[q]=p,q=k,k=Ance[q]);
21     return p;
22 }
23 inline bool cmp(const TEdge &a,const TEdge &b)
24 {
25     return a.w<b.w;
26 }
27 int main()
28 {
29     freopen("group.in","r",stdin);
30     freopen("group.out","w",stdout);
31     scanf("%d%d",&N,&K);
32     for (int i=1;i<=N;++i)
33         scanf("%d%d",&X[i],&Y[i]);
34     for (int i=1;i<N;++i)
35     for (int j=i+1;j<=N;++j)
36         e[++E]=TEdge_make((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]),i,j);
37     sort(e+1,e+E+1,cmp);
38     for (int i=1;i<=N;++i)
39         Ance[i]=i;
40     for (int i=1,cnt=N;i<=E;++i)
41     {
42         int u=GetAnce(e[i].x),v=GetAnce(e[i].y);
43         if (u!=v)
44         {
45             Ance[u]=v;
46             if (--cnt==K-1)    return printf("%.2lf\n",sqrt((double)e[i].w)),0;
47         }
48     }
49     return 0;
50 }
51

jsn1993 2010-05-26 10:06 发表评论

JSTSC 2010 express (CEOI 2005 service)

jsn1993 — Wed, 26 May 2010 00:56:00 GMT

题意：
有三个邮递员A,B,C 一开始分别在地点1,2,3(M<=200)，给定矩阵G，G[i][j]满足G[i][j]<=G[i][k]+G[k][j]，表示i到 j的代价，每天有一封邮件(共N<=1000)在第Ni个地点，需要派一个邮递员过去，不能有两个人在同一地点，每次只能移动一个人。

做法：
出题人没有道德这个题是CEOI2005的service
考虑朴素做法F[T][i][j][k]表示第T天，三个邮递员各在 i,j,k，转移即枚举哪个人去。
有个优化规定i但是这个复杂度是无法通过此题的
注意到第i天必然有个人要去Ni，所以可以将F[T][i][j][k]减到F[i][j][k]表示第i天另外两个邮递员在j,k
最后规定 j
（原题还要求输出方案在64M内存情况下只能用unsigned char记录方案，较恶心）

1 #include <cstdio>
2 #include <cstring>
3 int N,Q,G[205][205],list[1005];
4 int F[2][205][205];
5 inline void Update(int &u,int v)
6 {
7     if (u>v||u<0)    u=v;
8 }
9 int main()
10 {
11     scanf("%d",&N);
12     for (int i=1;i<=N;++i)
13     for (int j=1;j<=N;++j)
14         scanf("%d",&G[i][j]);
15     for (;scanf("%d",&list[++Q])!=EOF;);
16     --Q;
17     memset(F[1],-1,sizeof(F[1]));
18     F[1][2][3]=G[1][list[1]];
19     F[1][1][3]=G[2][list[1]];
20     F[1][1][2]=G[3][list[1]];
21     for (int i=1,pre=1;i<Q;++i,pre^=1)
22     {
23         memset(F[pre^1],-1,sizeof(F[pre^1]));
24         for (int j=1;j<N;++j)
25         for (int k=j+1;k<=N;++k)
26         if (F[pre][j][k]>=0)
27         {
28             if (list[i+1]!=j&&list[i+1]!=k)
29                 Update(F[pre^1][j][k],F[pre][j][k]+G[list[i]][list[i+1]]);
30             if (list[i+1]!=list[i]&&list[i+1]!=k)
31                 if (k<list[i])    Update(F[pre^1][k][list[i]],F[pre][j][k]+G[j][list[i+1]]);
32                 else    Update(F[pre^1][list[i]][k],F[pre][j][k]+G[j][list[i+1]]);
33             if (list[i+1]!=list[i]&&list[i+1]!=j)
34                 if (j<list[i])    Update(F[pre^1][j][list[i]],F[pre][j][k]+G[k][list[i+1]]);
35                 else    Update(F[pre^1][list[i]][j],F[pre][j][k]+G[k][list[i+1]]);
36         }
37     }
38     int ret=1<<30;
39     for (int i=1;i<N;++i)
40     for (int j=i+1;j<=N;++j)
41     if (F[Q&1][i][j]>=0)
42         Update(ret,F[Q&1][i][j]);
43     printf("%d\n",ret);
44     return 0;
45 }
46

jsn1993 2010-05-26 08:56 发表评论

JSTSC 2010 nova

jsn1993 — Wed, 26 May 2010 00:35:00 GMT

题意：
给你N个lich，M个wizard，K个半径为Ri的wood (N,M,K<=200)
第i个lich每Ti秒能杀死一个在Ri范围的wizard，但前提是lich跟wizard的连线与任何一个wood没有交
求最少多少时间lich能杀死所有wizard 或者判无解

做法：
首先可以想到如果固定一个时间那么每个lich能杀的个数是固定的
所以先二分答案
预处理每个lich可以到达的wizard
然后可以用网络流求解了 S向第i个lich连容量N/Ti+1，lich向能打到的wizard连容量1，wizard向T连容量1。
（难点不在于建图，在于计算几何预处理！）

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 #define n 1005
  6 #define m 200005
  7 struct TElement
  8 {
  9     int x,y,r,t;
10 }    lich[n],wizard[n],wood[n];
11 int vtx[m],ne[m],f[m],tot;
12 int L[n],d[n],pre[n],q[n];
13 int N,M,K,S,T,now,ret;
14 bool G[n][n];
15
16 inline int SQRdis(int x1,int y1,int x2,int y2)
17 {
18     return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
19 }
20 inline bool Inside(int x,int y)
21 {
22     for (int i=1;i<=K;++i)
23     if (SQRdis(x,y,wood[i].x,wood[i].y)<wood[i].r*wood[i].r)    return 1;
24     return 0;
25 }
26 inline bool Block(int i,int j)
27 {
28     int b=SQRdis(lich[i].x,lich[i].y,wizard[j].x,wizard[j].y);
29     for (int k=1;k<=K;++k)
30     {
31         int a=SQRdis(lich[i].x,lich[i].y,wood[k].x,wood[k].y);
32         int c=SQRdis(wizard[j].x,wizard[j].y,wood[k].x,wood[k].y);
33         if (a+b<c||c+b<a)    continue;
34         double y=c-(b+c-a)*(long long)(b+c-a)/(4.0*b);
35         if (y<=wood[k].r*wood[k].r)    return 1;
36     }
37     return 0;
38 }
39 inline void Ins(int u,int v,int fl)
40 {
41     vtx[++tot]=v;f[tot]=fl;ne[tot]=L[u];L[u]=tot;
42     vtx[++tot]=u;f[tot]=0;ne[tot]=L[v];L[v]=tot;
43 }
44 inline void push()
45 {
46     int fl=1<<30;
47     for (int i=T;i!=S;i=vtx[pre[i]^1])
48         fl=min(fl,f[pre[i]]);
49     ret+=fl;
50     for (int i=T;i!=S;i=vtx[pre[i]^1])
51     {
52         f[pre[i]]-=fl,f[pre[i]^1]+=fl;
53         if (!f[pre[i]])    now=vtx[pre[i]^1];
54     }
55 }
56 inline void dinic(int u)
57 {
58     if (u==T)    push();
59     else
60     {
61         for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
62         if (f[p]&&d[u]+1==d[v])
63         {
64             pre[v]=p,dinic(v);
65             if (d[now]<d[u])    return;
66             now=T;
67         }
68         d[u]=-1;
69     }
70 }
71 inline bool extend()
72 {
73     memset(d,63,sizeof(d));
74     d[q[1]=S]=0,now=T;
75     for (int h=1,t=1,u=q[h];h<=t;u=q[++h])
76     for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
77     if (f[p]&&d[v]>(1<<29))
78     {
79         d[v]=d[u]+1;
80         if (v==T)    return 1;
81         q[++t]=v;
82     }
83     return 0;
84 }
85 inline bool check(int Time)
86 {
87     memset(L,0,sizeof(L));
88     tot=1,ret=0;
89     for (int i=1;i<=N;++i)
90     if (lich[i].t)    Ins(S,i,1+Time/lich[i].t);
91     else    Ins(S,i,1<<30);
92     for (int i=1;i<=N;++i)
93     for (int j=1;j<=M;++j)
94     if (G[i][j])    Ins(i,j+N,1);
95     for (int j=1;j<=M;++j)
96         Ins(j+N,T,1);
97     for (;extend();dinic(S));
98     return ret==M;
99 }
100 int main()
101 {
102     scanf("%d%d%d",&N,&M,&K);
103     for (int i=1;i<=N;++i)
104         scanf("%d%d%d%d",&lich[i].x,&lich[i].y,&lich[i].r,&lich[i].t);
105     for (int i=1;i<=M;++i)
106         scanf("%d%d",&wizard[i].x,&wizard[i].y);
107     for (int i=1;i<=K;++i)
108         scanf("%d%d%d",&wood[i].x,&wood[i].y,&wood[i].r);
109     for (int i=1;i<=N;++i)
110     {
111         if (Inside(lich[i].x,lich[i].y))    continue;
112         for (int j=1;j<=M;++j)
113         {
114             if (Inside(wizard[j].x,wizard[j].y))    continue;
115             if (SQRdis(lich[i].x,lich[i].y,wizard[j].x,wizard[j].y)<=lich[i].r*lich[i].r)
116                 if (!Block(i,j))    G[i][j]=1;
117         }
118     }
119     S=N+M+1,T=S+1;
120     int l=0,r=2000000000,mid;
121     if (!check(r))    return puts("-1"),0;
122     if (check(l))    return puts("0"),0;
123     for (;l+1<r;)
124     if (mid=(l+r)>>1,check(mid))    r=mid;
125     else    l=mid;
126     printf("%d\n",r);
127     return 0;
128 }
129

jsn1993 2010-05-26 08:35 发表评论

【除草】Baltic OI 2010 day2 candies

jsn1993 — Fri, 21 May 2010 07:10:00 GMT

很久没写了。。。

题意：
给你一个装箱问题(N<=100 Ai<=7000) 记用这些有限物品能拼成的重量种数为Ans
求把i物品Ai 换成X后使新的能得到的重量种数Ret最大同时使X最小求X和Ret

做法：
这个题我做了一晚上加一上午！！

猜想：
换一个物品等价于先去掉这个物品做N-1个物品最后加入一个物品并更新
（写了个暴力是符合的）
然后就将问题变为了真正的两问：
第一问，求X使得除了X的N-1个物品能得到的种数Ans'最大
（因为最终方案一样所以得删一个最没用的）
第二问，添加一个物品使得最后得到的最大

对于第一问   一个简单的想法便是枚举去掉哪个物品做100次装箱问题
但是我们还是遇到了瓶颈做一次装箱问题复杂度O(100^2*7000) 枚举的话做一次就得0.5秒根本无法满足
（很不幸我想不到不枚举的方法只能用区间背包这个不好估计复杂度的来完成实际效果确实还得TLE）

【我的做法便是将100个物品分为10组枚举每10个物品先将另外90个物品做好区间背包保存这个答案数组
然后对于这10个物品每次添加9个物品
算下复杂度
原本要放进99*100=9900次物品
现在 90*10+9*9*10=2000次左右整整减少了5倍！】

对于第二问   事实上我们可以发现添加Y=(∑Ai)-X+1这个物品是肯定可以将方案数增加最多的因为
假设用N-1个物品能得到的装箱数组是
1 2 3 4 5 6 7 8 9 10 11 12
o x o o o x o o x o   x   x ....
那么11必然是一个使方案最大可行解亦可能是最优解
所以我们如果要找一个比Y更优的解必然要满足原本拥有的所有解加上Y'    原本都不可行！

这样就把问题转化为如下：
对于一个1..700000的布尔数组A 求一个最小的X
使得对于任意一个i A[i]=1 A[i+X]=0。
（很不幸除了枚举X 这一问我也不会做）

【我的做法
先预处理前缀和即从1开始到i能拼成的个数
先把这个枚举加些剪枝将原来拼不成的重量进行枚举
再从这些拼不成的重量里枚举X 因为区间背包算出来的是许多个区间最后枚举这些区间
对于一个区间[a,b] 如果X是可行的那必然有 sum(a+X,b+X)=0】

事实上这么做居然就过了！因为区间数不太多我能构造的最牛逼的数据也只能 O(300000*5000) 这个还是勉强能跑过的
对于官方数据每个点都能在0.2s内跑过！！

这样终于AC了此题！！

（另外求标准的优美的算法!!!!!!!!!）

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define n 20005
  5 using namespace std;
  6 struct Tintv
  7 {
  8     int x,y;
  9 }    P[n],Q[n],R[n],Ptmp[n];
10 int len,sum,lentmp,N,M,A[105],list[30];
11 int H[n],v[n],d[n],HLength,S[1400005];
12 bool F[1400005];
13 inline int Calc(int Left,int Right,int u,int v)
14 {
15     R[0].x=R[0].y=-2;
16     for (int l=Left;l<=Right;++l)
17     if (l<u||l>v)
18     {
19         for (int i=1;i<=len;++i)
20             Q[i].x=P[i].x+A[l],Q[i].y=P[i].y+A[l];
21         int r=0;
22         for (int p=1,q=1;p<=len||q<=len;)
23         if (p<=len&&(q>len||P[p].x<Q[q].x))
24         {
25             if (R[r].y+1>=P[p].x)    R[r].y=max(R[r].y,P[p].y);
26             else    R[++r].x=P[p].x,R[r].y=P[p].y;
27             ++p;
28         }
29         else
30         {
31             if (R[r].y+1>=Q[q].x)    R[r].y=max(R[r].y,Q[q].y);
32             else    R[++r].x=Q[q].x,R[r].y=Q[q].y;
33             ++q;
34         }
35         for (int i=1;i<=r;++i)
36             P[i]=R[i];
37         len=r;
38     }
39     int tmp=-1;
40     for (int i=1;i<=len;++i)
41         tmp+=P[i].y-P[i].x+1;
42     return tmp;
43 }
44 inline bool check(int u)
45 {
46     for (int i=1;i<=len;++i)
47         if (S[P[i].y+u]-S[P[i].x+u-1]>0)    return 0;
48     return 1;
49 }
50 int main()
51 {
52     scanf("%d",&N);
53     for (int i=1;i<=N;++i)
54         scanf("%d",&A[i]),M+=A[i];
55     sort(A+1,A+N+1);
56     int ret=0,Ret=0,tmp;
57     list[++list[0]]=1;
58     for (int i=1;i<=N;i+=10)
59     {
60         tmp=i+10;
61         if (tmp>N)    tmp=N+1;
62         list[++list[0]]=tmp;
63     }
64     for (int i=1;i<list[0];++i)
65     {
66         memset(P,0,sizeof(P)),len=1;
67         sum=Calc(1,N,list[i],list[i+1]-1);
68         memcpy(Ptmp,P,sizeof(P));
69         lentmp=len;
70         for (int j=list[i];j<list[i+1];++j)
71         if (A[j]!=A[j-1])
72         {
73             len=lentmp;
74             memcpy(P,Ptmp,sizeof(Ptmp));
75             tmp=Calc(list[i],list[i+1]-1,j,j);
76             if (tmp>Ret)    ret=j,Ret=tmp;
77         }
78     }
79     printf("%d ",A[ret]);
80     memset(P,0,sizeof(P)),len=1;
81     Calc(1,N,ret,ret);
82     for (int i=1;i<=len;++i)
83     for (int j=P[i].x;j<=P[i].y;++j)
84         S[j]=1;
85     for (int i=1;i<=1400000;++i)
86         S[i]+=S[i-1];
87     ++len;
88     P[len].x=P[len-1].y+2;
89     P[len].y=1<<30;
90     for (int i=1;i<len;++i)
91     {
92         bool mk=0;
93         for (int j=P[i].y+1;j<P[i+1].x;++j)
94         if (check(j))
95         {
96             ret=j;mk=1;break;
97         }
98         if (mk)    break;
99     }
100     printf("%d\n",ret);
101     return 0;
102 }
103

jsn1993 2010-05-21 15:10 发表评论

SDTSC 2010 goblin

jsn1993 — Wed, 19 May 2010 06:11:00 GMT

题意：
求长度为N的zig-zag序列数

做法：
设Up[i][j]表示长度为i以j开头的zig序列
Down[i][j]表示长度为i以j开头的zag序列
直接递推

1 #include <cstdio>
2 int Up[2][4205],Down[2][4205],N,P;
3 int main()
4 {
5     scanf("%d%d",&N,&P);
6     Up[1][1]=Down[1][1]=1;
7     for (int i=2,now=0;i<=N;++i,now^=1)
8     {
9         Up[now][i+1]=Down[now][0]=0;
10         for (int j=i;j;--j)
11             Up[now][j]=(Up[now][j+1]+Down[now^1][j])%P;
12         for (int j=1;j<=i;++j)
13             Down[now][j]=(Down[now][j-1]+Up[now^1][j-1])%P;
14     }
15     int ret=0;
16     for (int i=1;i<=N;++i)
17         ret=(ret+Up[N&1][i])%P;
18     printf("%d\n",(ret<<1)%P);
19     return 0;
20 }
21

jsn1993 2010-05-19 14:11 发表评论

SDTSC 2010 starrace

jsn1993 — Wed, 19 May 2010 06:09:00 GMT

题意：
给你一个图让你求经过所有点的一条最短路径终点无所谓

做法：
有人竟然费用流屎过。。
我的做法是上下界费用流
A->A' 下界是1 然后就建图了

1 #include <cstdio>
2 #include <cstring>
3 #define min(a,b) ((a)<(b)?(a):(b))
4 #define n 2047
5 #define e 300005
6 int vtx[e],w[e],f[e],ne[e],tot=1;
7 int L[n],q[n+1],pre[n],d[n],N,M,hidden,S,T,SuperS,SuperT,Cost;
8 bool vis[n];
9 inline void Ins(int u,int v,int fl,int cost)
10 {
11     vtx[++tot]=v;f[tot]=fl;w[tot]=cost;ne[tot]=L[u];L[u]=tot;
12     vtx[++tot]=u;f[tot]=0;w[tot]=-cost;ne[tot]=L[v];L[v]=tot;
13 }
14 inline bool spfa()
15 {
16     memset(vis,0,sizeof(vis));
17     memset(d,63,sizeof(d));
18     d[q[1]=SuperS]=0,vis[SuperS]=1;
19     for (int h=0,t=1,u;h!=t;vis[u]=0)
20     {
21         u=q[h=(h+1)&n];
22         for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
23         if (f[p]&&d[u]+w[p]<d[v])
24         {
25             d[v]=d[u]+w[p],pre[v]=p;
26             if (!vis[v])    vis[q[t=(t+1)&n]=v]=1;
27         }
28     }
29     return d[SuperT]<1<<29;
30 }
31 inline void push()
32 {
33     int fl=1<<30;
34     for (int i=SuperT;i!=SuperS;i=vtx[pre[i]^1])
35         fl=min(fl,f[pre[i]]);
36     Cost+=d[SuperT]*fl;
37     for (int i=SuperT;i!=SuperS;i=vtx[pre[i]^1])
38         f[pre[i]]-=fl,f[pre[i]^1]+=fl;
39 }
40 int main()
41 {
42     int u,v,w;
43     freopen("starrace.in","r",stdin);
44     freopen("starrace.out","w",stdout);
45     scanf("%d%d",&N,&M);
46     hidden=2*N+1;
47     S=hidden+1,T=S+1,SuperS=T+1,SuperT=SuperS+1;
48     Ins(S,hidden,1,0);
49     for (int i=1;i<=N;++i)
50     {
51         scanf("%d",&w);
52         Ins(hidden,i,1,w);
53         Ins(i+N,hidden,1,0);
54         Ins(i+N,T,1,0);
55         Ins(SuperS,i+N,1,0);
56         Ins(i,SuperT,1,0);
57     }
58     Ins(T,S,1<<30,0);
59     for (int i=1;i<=M;++i)
60     {
61         scanf("%d%d%d",&u,&v,&w);
62         if (u>v)    {int t=u;u=v;v=t;}
63         Ins(u+N,v,1,w);
64     }
65     for (;spfa();push());
66     printf("%d\n",Cost);
67     return 0;
68 }
69

jsn1993 2010-05-19 14:09 发表评论

Baltic OI 2010

jsn1993 — Sun, 16 May 2010 09:17:00 GMT

被虐成傻子了

这比赛五一节的时候进行的当时准备去ctsc&apio没做但是现在一看。。
lego 看懂了题意不禁一阵头晕。
bears 打算A了lego再去看。。
pcb 水题定义+树状数组

bins 水题
candies A了bears再来看。。
mines 一开始想这么大范围怎么做。。结果是“open input task”..

jsn1993 2010-05-16 17:17 发表评论

SDTSC 2010 sotomon

jsn1993 — Thu, 13 May 2010 09:12:00 GMT

题意：
给定N个点有些节点可以通往同行有些可以通往同列中的点有些可以通往八连通的点可以走过多次
问最多一次可以走过多少点

做法：
可以走过多次也就是说跟apio2009 atm一样一个强连通分量内可以无限走
然后就是走过场缩点拓扑排序 dp

问题在于。。。离散化后每次要寻找(x,y)这个点是否存在然后我的二分查找就因为小于大于号的问题挂了。。

（跟cqtsc2010 内部白点一样。。。挂在二分上了！！！）

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 #define n 300005
  5 #define m 3000005
  6 struct Tpnt
  7 {
  8     int x,y,kind,o;
  9 }    T[100005];
10 int vtx[m],ne[m],L[n],tot,Tot,All,Sub,E;
11 int N,R,C,dfn[n],F[n],cnt[n],low[n],Stk[n],Deg[n],sub[n],p[n];
12 int x[100005],y[100005],cnt_x[1000005],place_x[1000005],place_y[1000005];
13 int X[m],Y[m];
14 bool vis[n];
15 inline bool cmp_x(const Tpnt &a,const Tpnt &b)
16 {
17     return a.x<b.x||a.x==b.x&&a.y<b.y;
18 }
19 inline bool cmp_y(const Tpnt &a,const Tpnt &b)
20 {
21     return a.y<b.y||a.y==b.y&&a.x<b.x;
22 }
23 inline void Ins(int u,int v)
24 {
25     vtx[++tot]=v;ne[tot]=L[u];L[u]=tot;
26 }
27 inline int findx_x(int X)
28 {
29     int l=0,r=N,mid;
30     for (;l+1<r;)
31     if (mid=(l+r)>>1,T[mid].x<X)    l=mid;
32     else    r=mid;
33     if (T[r].x==X)    return r;
34     return -1;
35 }
36 inline int findx_y(int st,int en,int Y)
37 {
38     int l=st-1,r=en,mid;
39     for (;l+1<r;)
40     if (mid=(l+r)>>1,T[mid].y<Y)    l=mid;
41     else    r=mid;
42     if (T[r].y==Y)    return r;
43     return -1;
44 }
45 inline void Tarjan(int u)
46 {
47     dfn[u]=low[u]=++All;
48     vis[Stk[++Stk[0]]=u]=1;
49     for (p[u]=L[u];p[u];p[u]=ne[p[u]])
50     if (!dfn[vtx[p[u]]])    Tarjan(vtx[p[u]]),low[u]=min(low[u],low[vtx[p[u]]]);
51     else
52     if (vis[vtx[p[u]]])    low[u]=min(low[u],dfn[vtx[p[u]]]);
53     if (dfn[u]==low[u])
54         for (++Sub;;)
55         {
56             vis[Stk[Stk[0]]]=0;
57             sub[Stk[Stk[0]]]=Sub;
58             if (Stk[Stk[0]--]==u)    break;
59         }
60 }
61 inline void Topo()
62 {
63     Stk[0]=0;
64     for (int i=1;i<=Sub;++i)
65     if (!Deg[i])    F[i]=cnt[i],Stk[++Stk[0]]=i;
66     for (;Stk[0];)
67     {
68         int u=Stk[Stk[0]--];
69         for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
70         {
71             F[v]=max(F[v],F[u]+cnt[v]);
72             --Deg[v];
73             if (!Deg[v])    Stk[++Stk[0]]=v;
74         }
75     }
76 }
77 int main()
78 {
79     scanf("%d%d%d",&N,&R,&C);
80     for (int i=1;i<=N;++i)
81         scanf("%d%d%d",&T[i].x,&T[i].y,&T[i].kind),T[i].o=i;
82     sort(T+1,T+N+1,cmp_x);
83     E=0;
84     for (int i=1;i<=N;++i)
85     {
86         if (T[i].x!=T[i-1].x)
87         {
88             x[++x[0]]=T[i].x;
89             place_x[T[i].x]=x[0];
90         }
91         ++cnt_x[T[i].x];
92         Ins(x[0]+N,T[i].o);
93         X[++E]=x[0]+N,Y[E]=T[i].o;
94     }
95     sort(T+1,T+N+1,cmp_y);
96     for (int i=1;i<=N;++i)
97     {
98         if (T[i].y!=T[i-1].y)
99         {
100             y[++y[0]]=T[i].y;
101             place_y[T[i].y]=y[0];
102         }
103         Ins(y[0]+N+x[0],T[i].o);
104         X[++E]=y[0]+N+x[0],Y[E]=T[i].o;
105     }
106     Tot=N+x[0]+y[0];
107     sort(T+1,T+N+1,cmp_x);
108     for (int i=1;i<=N;++i)
109     if (T[i].kind==1)
110     {
111         Ins(T[i].o,place_x[T[i].x]+N);
112         X[++E]=T[i].o,Y[E]=place_x[T[i].x]+N;
113     }
114     else
115     if (T[i].kind==2)
116     {
117         Ins(T[i].o,place_y[T[i].y]+N+x[0]);
118         X[++E]=T[i].o,Y[E]=place_y[T[i].y]+N+x[0];
119     }
120     else
121         for (int dx=-1;dx<=1;++dx)
122         if (T[i].x+dx>0&&T[i].x+dx<=R)
123         {
124             int xst=findx_x(T[i].x+dx),xen;
125             if (xst<0)    continue;
126             xen=xst+cnt_x[T[i].x+dx]-1;
127             for (int dy=-1;dy<=1;++dy)
128             if (T[i].y+dy>0&&T[i].y+dy<=C)
129             {
130                 if (!dx&&!dy)    continue;
131                 int pos=findx_y(xst,xen,T[i].y+dy);
132                 if (pos<0||i==pos)    continue;
133                 Ins(T[i].o,T[pos].o);
134                 X[++E]=T[i].o,Y[E]=T[pos].o;
135             }
136         }
137     for (int i=1;i<=Tot;++i)
138     if (!dfn[i])    Tarjan(i);
139     for (int i=1;i<=N;++i)
140         ++cnt[sub[i]];
141     tot=0;
142     memset(L,0,sizeof(L));
143     for (int i=1;i<=E;++i)
144     if (sub[X[i]]!=sub[Y[i]])
145     {
146         Ins(sub[X[i]],sub[Y[i]]);
147         ++Deg[sub[Y[i]]];
148     }
149     Topo();
150     int ret=0;
151     for (int i=1;i<=Sub;++i)
152         ret=max(ret,F[i]);
153     printf("%d\n",ret);
154     return 0;
155 }
156

jsn1993 2010-05-13 17:12 发表评论

SDTSC 2010 landcraft

jsn1993 — Thu, 13 May 2010 09:08:00 GMT

题意：
给你一些点让你求1-N的最短路某个点能被访问前提是这个点的所有前继点都必须被访问过但是这个是可以同时进行的

做法：
很像最大权闭合子图之类的结果说白了就是个变种最短路。。N^2 dijkstra水过。。
（一开始点数组开了1000 wa到死）

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define n 3005
#define m 300005
int vtx[m],w[m],ne[m],L[n],tot;
long long d[n],e[n];
int cnt[n],N,M;
vector<int> list[n];
bool vis[n];
inline void Ins(int u,int v,int cost)
{
    vtx[++tot]=v;w[tot]=cost;ne[tot]=L[u];L[u]=tot;
}
inline long long dijkstra()
{
    memset(d,127,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[1]=0;
    for (int i=1;i<N;++i)
    {
        int k=0;
        long long dist=1LL<<60;
        for (int j=1;j<=N;++j)
        if (!vis[j]&&!cnt[j]&&max(d[j],e[j])<dist)    k=j,dist=max(d[j],e[j]);
        vis[k]=1,d[k]=max(d[k],e[k]);
        for (int j=0;j<list[k].size();++j)
            e[list[k][j]]=max(e[list[k][j]],d[k]),--cnt[list[k][j]];
        for (int p=L[k],v=vtx[p];p;v=vtx[p=ne[p]])
            d[v]=min(d[v],d[k]+w[p]);
    }
    return max(d[N],e[N]);
}
int main()
{
    int u,v,w;
    scanf("%d%d",&N,&M);
    for (int i=0;i<M;++i)
        scanf("%d%d%d",&u,&v,&w),Ins(u,v,w);
    for (int i=1,j;i<=N;++i)
    for (scanf("%d",&j);j--;)
        scanf("%d",&v),++cnt[i],list[v].push_back(i);
    cout<<dijkstra()<<endl;
    return 0;
}

jsn1993 2010-05-13 17:08 发表评论

APIO2010

jsn1993 — Mon, 10 May 2010 14:59:00 GMT

。。唉考腿了
第一题水题
第二题找两条最长链（每条边经过一次）
第三题直接利用数量积性质与凸性

100+30+30
第一题秒了第二题本来是yy2条不相交最长链这么写的
在想第三题时候已经通过数量积想到了利用角度可当时错误地认为一定要把那个弦枚举出来没注意到“没有四点共圆”。。
然后我就回去想第二题的更优算法发现如果从跳一次后回上来的深度为1的点直接跳到另外一个叶子这样更优第二个样例算出来是9！
考试完了发现。。如果这么跳的话必然是没有经过那条边。。然后就跑出了比答案更优的解。。自然完挂

然后颁奖时是银牌的第12名的样子。。。。在学校去的所有人中垫底了啊太菜了啊啊要被鄙视了啊啊啊

ps 本校1International Au 3National Au 2National Ag 写文章的2b便是分数最低的那个。。

jsn1993 2010-05-10 22:59 发表评论

CTSC2010

jsn1993 — Thu, 06 May 2010 11:43:00 GMT

好吧我被虐成屎了
强烈膜拜潘神两试标准分“30.0 30.0” 同时为菜妈惋惜。。

day1
最高潘神230
第一题贪心建了个最小割模型没调对
第二题概率记忆化这种题从来不会写。。
第三题数列转化 20分暴力 10分矩阵 20分循环矩阵 20分FFT或者分治 30分傅里叶优化

0+10+30。。那个循环矩阵可能已经想到了但是当时不知道有什么用

day2
最高潘神90
第一题费用流利用规律线段树优化想了个O(sigmaDi)的傻逼dp 本来可能想用线段树优化但是没写出来。。
第二题什么dfs序ST查询模型转化块状数组直接交了N^2M 膜拜教主的后缀树与漆神期望10-20分潘神拿了50分的dp。
第三题提交答案交了个规律点第一二个小点暴力由于套了map,vector >,bool>变的奇慢或者说卡掉了最优解
20+0+10

跟冬令营一样的分数....凄凉的铜牌中间名次.希望apio稍微好点吧

jsn1993 2010-05-06 19:43 发表评论

Codeforces #12

jsn1993 — Thu, 29 Apr 2010 13:07:00 GMT

好吧我承认做得实在太失败

A:一开始瞬间秒了A（wa1次因为把s2写成s3了 - -！）题意：给你一个3*3矩阵问你它是否中心对称
B:Wa2次没看到关于前导零的描述（- -！）题意：
C:1A 题意：给你N个数字与M个cnt 求min{∑cnt[i]*A[i]}与max{∑cnt[i]*A[i]}
D:最大失败，从19:30到21:00 （-10）与暴力拍不出错，却总是wa3 题意：给你N个三元组问有多少三元组满足“存在一个三元组的三个元素都比此三元组的对应三个元素大”
E:还没看

这次比赛最大的失误便是我先秒了A 然后写B B没看清题目就放了放先看D 结果就开始写D了 C这种终极水题都没看!
导致B C提交时间过晚由于没有过D题也就造成了大杯具啊！！！

呜呜！

jsn1993 2010-04-29 21:07 发表评论

Pku 2917 Diophantus of Alexandria

jsn1993 — Fri, 23 Apr 2010 02:54:00 GMT

题意：
求 1/x+1/y=1/z x,y的整数解对数

做法：
先将y表示成 y=(x*z)/(x-z)
然后呢...我就不知道然后了
baidu了题解后才知道了
设w=x-z 则x=z+w 那么 y=(z*z+w*z)/w=z*z/w+z
所以转化为了求z*z/w的整数解个数
即z*z的约数个数因为要求一对的所以答案是 (约数个数+1)/2

然后就解决了。

1 #include <cstdio>
2 #define n 50005
3 int p[n],T,N,ret;
4 bool mk[n];
5 inline void mkprime()
6 {
7     for (int i=2;i<n;++i)
8     if (!mk[i])
9         for (int j=i<<1;j<n;j+=i)
10             mk[j]=1;
11     for (int i=2;i<n;++i)
12     if (!mk[i])    p[++p[0]]=i;
13 }
14 inline int getlog(int &N,int prime)
15 {
16     int ret=0;
17     for (;N%prime==0;N/=prime,++ret);
18     return ret;
19 }
20 int main()
21 {
22     mkprime();
23     scanf("%d",&T);
24     for (int Te=1;Te<=T;++Te)
25     {
26         scanf("%d",&N);
27         ret=1;
28         for (int i=1;i<=p[0]&&p[i]*p[i]<=N;++i)
29         if (N%p[i]==0)    ret*=(getlog(N,p[i])<<1)+1;
30         if (N>1)    ret*=3;
31         printf("Scenario #%d:\n%d\n\n",Te,(ret+1)>>1);
32     }
33     return 0;
34 }
35

jsn1993 2010-04-23 10:54 发表评论

Pku 1845 Sumdiv

jsn1993 — Thu, 22 Apr 2010 10:58:00 GMT

题意：
给你N^M (N,M<=50000000) 让你求出N^M的所有约数之和mod 9901 (prime)

做法：
首先可以肯定的是给你N 让你求出N的所有约数之和的做法
便是分解质因数并将N表示成 p1^k1*p2^k2.....pm^km 然后将这些数字分为m类
用公式(1+p1+p1^2...+p1^k1)(1+p2+p2^2...+p2^k2)...(1+pm+pm^2+...+pm^km)便可以计算得到
因为从每类中选一种pi^j乘出来等价于将pi^j乘到这个约数中，所有的乘法可能之和便是约数和
对于N^M 其实本质一样 p1^(M*k1)*p2^(M*k2).....pm^(M*km)

问题转化为了如何求1+q+q^2+...+q^Q这个等比数列前N项和
高中数学告诉我们可以用(q^Q-1)/(q-1)这个公式快速幂解决
离散数学告诉我们可以用构造矩阵用矩阵乘法

用公式大部分情况都是对的
但是在比如 (q^Q-1)与(q-1)都能被 9901整除的情况下求出来的肯定是0 不是正确解
（我比较愚昧不知道如何解决求解决方法）

用矩阵其实也很简单构造一个2*2的矩阵即可
我就只讲讲我的大常数sb方法
A是答案矩阵
A11 表示i次幂的时候当前这个数 A12表示i次幂的时候当前这个数加上之前的和也就是前i项和
B是用来转移的矩阵
B11 = B12 = Num B21=0 B22=1
初始 A11=A12=1 A21=A22=0
要求 N^M次的时候只要把 B 重新构造把A乘上B的M次就可以了

这样就解决了此题虽然常数不咋地。。

1 #include <cstdio>
2 #include <cstring>
3
4 #define P 9901
5 #define n 3
6 int p[P],C[n][n],Mat[n][n],tmp[n][n],N,M,ret;
7 bool mk[P];
8 inline void mkprime()
9 {
10     for (int i=2;i<P;++i)
11     if (!mk[i])
12         for (int j=i<<1;j<P;j+=i)
13             mk[j]=1;
14     for (int i=2;i<P;++i)
15     if (!mk[i])    p[++p[0]]=i;
16 }
17 inline void matmul(int A[][n],int B[][n])
18 {
19     memset(C,0,sizeof(C));
20     for (int i=1;i<3;++i)
21     for (int j=1;j<3;++j)
22     for (int k=1;k<3;++k)
23         C[i][j]=(C[i][j]+A[i][k]*(long long)B[k][j])%P;
24     memcpy(A,C,sizeof(C));
25 }
26 inline int getlog(int &N,int prime)
27 {
28     int ret=0;
29     for (;N%prime==0;N/=prime,++ret);
30     return ret;
31 }
32 inline void Mult(int prime,int log)
33 {
34     Mat[1][1]=Mat[1][2]=1;
35     tmp[1][1]=tmp[1][2]=prime;
36     tmp[2][1]=0,tmp[2][2]=1;
37     for (;log;log>>=1,matmul(tmp,tmp))
38     if (log&1)    matmul(Mat,tmp);
39     ret=(ret*Mat[1][2])%P;
40 }
41 int main()
42 {
43     mkprime();
44     scanf("%d%d",&N,&M);
45     ret=1;
46     for (int i=1,j;i<=p[0]&&p[i]*p[i]<=N;++i)
47     if (N%p[i]==0)    Mult(p[i],getlog(N,p[i])*M);
48     if (N>1)    Mult(N,M);
49     printf("%d\n",ret);
50     return 0;
51 }
52

jsn1993 2010-04-22 18:58 发表评论

Pku 2480 Longge's Problem

jsn1993 — Thu, 22 Apr 2010 04:18:00 GMT

题意：
给定N(int) 求 ∑gcd(i,N) 1<=i<=N

又是数论题。。我太菜了想了很久

做法：
直接求不会
只能考虑对于gcd(M,N)=i 有Ci个M满足此式答案便是∑(Ci*i)
gcd(M,N)=i <=> gcd(M/i,N/i)=1
而求gcd(M/i,N/i)=1 有多少个M/i满足这便是欧拉函数Phi()的定义
所以就转化为了求Phi(N/i)

枚举每个 M|N 求出Phi(N/i) 答案便是 ∑(Phi(N/i)*i)
那么如何枚举每个 M|N 呢？
很简单枚举1到sqrt(N)的所有整数，所有的约数便是 j|N (N/j)|N
这样就搞定了

1 #include <cstdio>
2 #include <cmath>
3 #define n 50005
4 int p[n],N;
5 bool mk[n];
6 inline void mkprime()
7 {
8     for (int i=2;i<n;++i)
9     if (!mk[i])
10         for (int j=i<<1;j<n;j+=i)
11             mk[j]=1;
12     for (int i=2;i<n;++i)
13     if (!mk[i])    p[++p[0]]=i;
14 }
15 inline int Phi(int u)
16 {
17     int phi=u;
18     for (int i=1;i<=p[0]&&p[i]*p[i]<=u;++i)
19     if (u%p[i]==0)
20     {
21         phi=phi/p[i]*(p[i]-1);
22         for (;u%p[i]==0;u/=p[i]);
23     }
24     if (u>1)    phi=phi/u*(u-1);
25     return phi;
26 }
27 int main()
28 {
29     mkprime();
30     for (;scanf("%d",&N)!=EOF;)
31     {
32         long long ret=0;
33         for (int i=1,up=(int)sqrt((double)N);i<=up;++i)
34         if (N%i==0)
35         {
36             ret+=(N/i)*(long long)Phi(i);
37             if (i*i!=N)    ret+=i*(long long)Phi(N/i);
38         }
39         printf("%I64d\n",ret);
40     }
41     return 0;
42 }
43

jsn1993 2010-04-22 12:18 发表评论

Pku 2417 Discrete Logging

jsn1993 — Wed, 21 Apr 2010 06:58:00 GMT

题意：
求最小的离散对数B 使得A^B == C (mod P) P是质数或者判无解

做法：

数论题..对于比我大的同学肯定觉得很简单。。
由欧拉定理 A^phi(P) == 1 (mod P) (phi(prime)=prime-1)
得到 A^(B+phi(P)) == c (mod P) A^(B-Phi(P)) ==c (mod P)
所以可以肯定的一点是如果 [0,phi(P))内无解由此式子的周期性必然不会有更多解

一个朴素的想法：枚举 B∈[0,phi(P)) 检验 A^B是否 == C(mod P)
问题又出现了 P是个质数 phi(P)=P-1 必然TLE
所以就必须用空间换时间。

设得到的答案是B B=X*sqrt(P)+Y 注意到X,Y<=sqrt(P)
列式并化简：

A^(X*sqrt(P)+Y) == C (mod P)
(A*sqrt(P))^X*A^Y == C (mod P)

设 T=A*sqrt(P) 原式即 T^X*A^Y == C (mod P)
两边同除以 A^Y 得到 T^X == C/(A^Y) (mod P)

好吧到现在做法就已经浮出水面了

我们预处理T^i (mod P) 最多sqrt(P)个 (i手写hash或者用map直接存下来二元组 (T^X (mod P),X)

然后枚举 Y∈[0,sqrt(P)) 最多sqrt(P)个
对于每个Y 我们求出 C/(A^Y) (mod P) 然后在hash或者map中查找这个值
如果 (C/(A^Y) (mod P),X) 存在那么说明 X*sqrt(P)+Y 是可以作为答案的

最后答案便是所有满足条件的 X*sqrt(P)+Y 中的最小值。

如果你不知道 C/(A^Y) (mod P) 怎么求
那就继续看下去吧
C/(A^Y) (mod P) == C*((1/A^Y) mod P)
(1/A^Y) (mod P) == (A^Y)^-1 (mod P)
即 (A^Y)^(phi(P)-1) (mod P)
所以 C/(A^Y) (mod P) 就等于C*(A^Y)^(phi(P)-1) (mod P)

这样就解决了此题。

1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #define Prime 899037
5 #define oo 2000000005
6 #define min(a,b) ((a)<(b)?(a):(b))
7 int P,B,N;
8 int H[Prime],V[Prime];
9 inline int pow(int u,int v)
10 {
11     int ret=1;
12     for (int tmp=u;v;v>>=1,tmp=(tmp*(long long)tmp)%P)
13     if (v&1)    ret=(ret*(long long)tmp)%P;
14     return ret;
15 }
16 inline void Hpush(int u,int v)
17 {
18     int t=u%Prime;
19     for (;H[t];)
20     {
21         if (H[t]==u)    return;
22         if (++t==P)    t-=P;
23     }
24     H[t]=u,V[t]=v;
25 }
26 inline int Hpop(int u)
27 {
28     int t=u%Prime;
29     for (;H[t];)
30     {
31         if (H[t]==u)    return V[t];
32         if (++t==P)    t-=P;
33     }
34     return oo;
35 }
36 int main()
37 {
38     for (;scanf("%d%d%d",&P,&B,&N)!=EOF;)
39     {
40         int ret=oo+1;
41         memset(H,0,sizeof(H));
42         memset(V,-1,sizeof(V));
43         int sqrtP=(int)sqrt((double)P),Bsp=pow(B,sqrtP);
44         for (int i=0,val=1;i<=sqrtP;++i,val=(val*(long long)Bsp)%P)
45             Hpush(val,i);
46         for (int i=0,val=1;i<=sqrtP;++i,val=(val*(long long)B)%P)
47         {
48             int h=(N*(long long)pow(val,P-2))%P,v=Hpop(h);
49             if (v<oo&&v*sqrtP+i<ret)    ret=v*sqrtP+i;
50         }
51         if (ret>oo)    puts("no solution");
52         else    printf("%d\n",ret);
53     }
54     return 0;
55 }
56

jsn1993 2010-04-21 14:58 发表评论

SCTSC 2010 序列操作

jsn1993 — Mon, 19 Apr 2010 04:04:00 GMT

摘要: 题意：给定一个N<=100000个数的01序列，要你支持共Q<=100000个五种操作0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 做法... 阅读全文

jsn1993 2010-04-19 12:04 发表评论

CQTSC 2010 内部白点

jsn1993 — Sat, 17 Apr 2010 12:56:00 GMT

题意：
给你N<=100000个点同样x坐标的形成竖线段同样y坐标的形成横线段
让你求出竖线段和横线段的交点数，包括端点。

做法：
我的做法是先求出非端点的交点最后答案便是 tot+N

先将数组复制一遍一个数组按照1关键字x 2关键字y排序另一个关键字顺序反一反
将x或者y离散化这里以y为例
因为已经按y排过序所以所有横线段已经都能得到了(相邻一段相同y坐标的点属于同一条线段)
并标记每条横线段的两个端点。

然后我们枚举按x坐标由左边向右边的每条竖线段
我们只要求出有多少横线段与它有交便是这条竖线段形成的交点数
这等价于求出在当前x坐标的情况下横线段的右端点x坐标大于当前竖线段x坐标的线数
这样就可以用线段树或者树状数组维护y坐标的点（即维护当前还存在的线段）就可以了

如何维护呢？
对于一条竖线段我们枚举形成当前竖线的所有点如果某个点已经是横线段的结尾那就从树中删除这个y坐标
反之如果是横线段的开始那就加入这个y坐标
在枚举之前当然要求当前线的交点个数：
对于枚举到的相邻两个相同x坐标的点假设y1
这样就在NLogN时间内解决了此题

ps：发觉我的基础太差了。。二分查找[y1,y2)的两个端点时候竟然忘记了 (y2-1)这个坐标事实上可能不存在
所以二分查找找端点的时候挂了。。BS我把

本题加强版是 dhx学长出的 Religious

1 #include <cstdio>
2 #include <algorithm>
3 using namespace std;
4 #define n 100005
5 struct Tpoint
6 {
7     #define x0(i) p0[i].x
8     #define y0(i) p0[i].y
9     #define nod0(i) p0[i].nod
10     #define x1(i) p1[i].x
11     #define y1(i) p1[i].y
12     #define nod1(i) p1[i].nod
13     int x,y,nod;
14 }    p0[n],p1[n];
15 int N,ny[n],New,T[n],ret=0;
16 bool sta[n],end[n];
17 inline bool cmp0(const Tpoint &a,const Tpoint &b)
18 {
19     return a.y<b.y||a.y==b.y&&a.x<b.x;
20 }
21 inline bool cmp1(const Tpoint &a,const Tpoint &b)
22 {
23     return a.x<b.x||a.x==b.x&&a.y<b.y;
24 }
25 inline int find(int x)
26 {
27     int l=0,r=New;
28     for (int mid=(l+r)>>1;l+1<r;mid=(l+r)>>1)
29     if (ny[mid]<=x)    l=mid;
30     else    r=mid;
31     if (x<ny[r])    return l;
32     return r;
33 }
34 inline int Sum(int x)
35 {
36     int ret=0;
37     for (;x;x-=x&-x)
38         ret+=T[x];
39     return ret;
40 }
41 inline void Add(int x,int delt)
42 {
43     for (;x<=N;x+=x&-x)
44         T[x]+=delt;
45 }
46 int main()
47 {
48     scanf("%d",&N);
49     for (int i=0;i<N;++i)
50     {
51         scanf("%d%d",&x0(i),&y0(i));
52         nod0(i)=i;nod1(i)=i;
53         x1(i)=x0(i),y1(i)=y0(i);
54     }
55     sort(p0,p0+N,cmp0);
56     sta[nod0(0)]=end[nod0(N-1)]=1;
57     for (int i=1;i<N;++i)
58         sta[nod0(i)]=(y0(i)!=y0(i-1));
59     for (int i=0;i<N-1;++i)
60         end[nod0(i)]=(y0(i)!=y0(i+1));
61     ny[++New]=y0(0);
62     for (int i=1;i<N;++i)
63     if (y0(i)!=y0(i-1))    ny[++New]=y0(i);
64     sort(p1,p1+N,cmp1);
65     for (int i=0,k;i<N;i=k)
66     {
67         for (k=i+1;k<N&&x1(i)==x1(k);++k)
68         if (y1(k-1)<y1(k)-1)
69             ret+=Sum(find(y1(k)-1))-Sum(find(y1(k-1)));
70         for (int j=i;j<k;++j)
71         {
72             if (sta[nod1(j)]&&!end[nod1(j)])
73                 Add(find(y1(j)),1);
74             if (!sta[nod1(j)]&&end[nod1(j)])
75                 Add(find(y1(j)),-1);
76         }
77     }
78     printf("%d\n",N+ret);
79     return 0;
80 }
81

jsn1993 2010-04-17 20:56 发表评论

NEERC 2006 Hard Life

jsn1993 — Fri, 16 Apr 2010 08:29:00 GMT

摘要: 题意：给定一个图(V<=100,E<=1000) 求一个子图(V',E') 使得|E'| 与 |V'|的比值最大，要求出这个子集。做法：比较裸的最大密度子图。设密度为R 要令R最大R=max{|E'|/|'V'|} 化简得到 max{|E'|-R*|'V'|}=0设 g(x)=max{|E'|-x*|'V'|}由Dinkelbach定理与该函数的单调性得到： &n... 阅读全文

jsn1993 2010-04-16 16:29 发表评论

SPOJ DISQUERY

jsn1993 — Thu, 15 Apr 2010 01:40:00 GMT

摘要: 题意：给定一棵N<=100000个点的树，有Q<=100000个询问，求(u,v)路径上边权最大值和最小值做法：动态树直接上了。。发觉在这里写的题是越来越水..注意要判空节点或者将空节点的最值赋为极限 1#include 2#define min(a,b) ((a)<(b)... 阅读全文

jsn1993 2010-04-15 09:40 发表评论

SPOJ GSS6

jsn1993 — Wed, 14 Apr 2010 13:25:00 GMT

摘要: 题意：给定一个数列，要求支持以下操作：I x y 在第x个数所在位置插入数y并将后面的全部右移动一位D x 删除第x个位置上的数R x y 将第x个位置上的数替换为yQ x y 求[x,y]之间的最大子段和做法：如果不需要D和I操作那么线段树可以完美支持加入D和I操作后就... 阅读全文

jsn1993 2010-04-14 21:25 发表评论

SPOJ QTREE2

jsn1993 — Wed, 14 Apr 2010 01:54:00 GMT

摘要: 题意：给你一棵N个点的树要求支持两种操作：DIST a b 求a到b路径距离KTH a b k 求a到b路径上的第k个节点做法：还是动态树..跟QTREE本质没什么差别对于DIST 两次拉实然后求两段的SumKTH便是两次拉实后分情况讨论（在左边还是右边还是正好那个LCA)PS:如果本题改成求a到b路径上第k大的数字，那便是CTSC难度的了。。（network） &nbs... 阅读全文

jsn1993 2010-04-14 09:54 发表评论

CroatianOI 2009 OTOCI

jsn1993 — Mon, 12 Apr 2010 11:53:00 GMT

题意：
给定N个节点要求维护森林：
b x y表示查询x y的连通性如果连通输出"no"否则输出"yes"并在x,y之间连边
p x y表示将x节点权值修改为y
e x y表示查询x到y路径上的权值和如果连通输出答案否则输出"impossible"
N<=30000 Q<=300000

做法：
要在线么..动态树搞搞吧

对于B
查询两个节点是否在同一棵动态树中其实便是拉实后看根节点是否一样
如果不连通那么将其中一个节点变成所在动态树的根然后接到另一个节点上去

对于P 没什么好说的别忘了update

对于E 也没什么好说的两次拉实就可以了找到LCA然后查询

  1 #include <cstdio>
  2 struct Tsplay
  3 {
  4     #define Lch(t)    (T[t].l)
  5     #define Rch(t)    (T[t].r)
  6     #define Par(t)    (T[t].p)
  7     #define Sum(t)    (T[t].sum)
  8     #define Val(t)    (T[t].val)
  9     #define Rev(t)    (T[t].rev)
10     #define Root(t)    (Lch(Par(t))!=t&&Rch(Par(t))!=t)
11     int l,r,p;
12     int sum,val;
13     bool rev;
14 }    T[30005];
15 int Stk[30005],N,Q,x,y;
16 char cmd[1005];
17 inline void Down(int x)
18 {
19     if (Rev(x))
20     {
21         int t=Lch(x);Lch(x)=Rch(x);Rch(x)=t;
22         Rev(Lch(x))^=1,Rev(Rch(x))^=1,Rev(x)=0;
23     }
24 }
25 inline void Tupdate(int x)
26 {
27     Sum(x)=Sum(Lch(x))+Val(x)+Sum(Rch(x));
28 }
29 inline void zig(int x)
30 {
31     int y=Par(x),z=Par(y);
32     Lch(y)=Rch(x),Par(Lch(y))=Rch(x)=y;
33     if (Lch(z)==y)    Lch(z)=x;
34     else
35     if (Rch(z)==y)    Rch(z)=x;
36     Par(x)=z,Par(y)=x;
37     Tupdate(y);
38 }
39 inline void zag(int x)
40 {
41     int y=Par(x),z=Par(y);
42     Rch(y)=Lch(x),Par(Rch(y))=Lch(x)=y;
43     if (Lch(z)==y)    Lch(z)=x;
44     else
45     if (Rch(z)==y)    Rch(z)=x;
46     Par(x)=z,Par(y)=x;
47     Tupdate(y);
48 }
49 inline void splay(int x)
50 {
51     Stk[++Stk[0]]=x;
52     for (int u=x;!Root(u);u=Par(u))
53         Stk[++Stk[0]]=Par(u);
54     for (;Stk[0];--Stk[0])
55         Down(Stk[Stk[0]]);
56     for (int y,z;!Root(x);)
57     {
58         y=Par(x),z=Par(y);
59         if (Root(y))
60             if (Lch(y)==x)    zig(x);
61             else    zag(x);
62         else
63         if (Lch(z)==y)
64             if (Lch(y)==x)    zig(y),zig(x);
65             else    zag(x),zig(x);
66         else
67             if (Rch(y)==x)    zag(y),zag(x);
68             else    zig(x),zag(x);
69     }
70     Tupdate(x);
71 }
72 inline int Expose(int u)
73 {
74     int v=0;
75     for (;u;u=Par(u))
76         splay(u),Rch(u)=v,Tupdate(v=u);
77     for (;Lch(v);v=Lch(v));
78     return v;
79 }
80 inline void Modify(int x,int y)
81 {
82     splay(x),Val(x)=y,Tupdate(x);
83 }
84 inline void Query(int x,int y)
85 {
86     int Ry=Expose(y),Rx=Expose(x);
87     if (Rx!=Ry)    puts("impossible");
88     else
89     for (int u=y,v=0;u;u=Par(u))
90     {
91         if (splay(u),!Par(u))
92         {
93             printf("%d\n",Sum(Rch(u))+Val(u)+Sum(v));
94             return;
95         }
96         Rch(u)=v,Tupdate(v=u);
97     }
98 }
99 inline void Connect(int x,int y)
100 {
101     int Ry=Expose(y),Rx=Expose(x);
102     if (Rx==Ry)    puts("no");
103     else
104     {
105         splay(x);
106         Rch(x)=0,Rev(x)=1,Par(x)=y;
107         puts("yes");
108     }
109 }
110 int main()
111 {
112     freopen("otoci.in","r",stdin);
113     freopen("otoci.out","w",stdout);
114     scanf("%d",&N);
115     for (int i=1;i<=N;++i)
116         scanf("%d",&Val(i)),Sum(i)=Val(i);
117     for (scanf("%d",&Q);Q--;)
118     {
119         scanf("%s%d%d",cmd,&x,&y);
120         if (cmd[0]=='e')    Query(x,y);
121         else
122         if (cmd[0]=='b')    Connect(x,y);
123         else    Modify(x,y);
124     }
125     return 0;
126 }
127
128

jsn1993 2010-04-12 19:53 发表评论