[BZOJ 1477]青蛙的约会
设用时为，则本题可视为解方程
。
整理变形得。
明显需要扩欧求解。注意此题有很多细节，可参见下代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | /************************************************************** Problem: 1477 User: danihao123 Language: C++ Result: Accepted Time:0 ms Memory:1288 kb****************************************************************/ #include <iostream>using namespace std;typedef long long ll;ll gcd(ll a,ll b){ if(!b) return a; else return gcd(b,a%b);}void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ if(!b){ d=a; x=1; y=0; }else{ exgcd(b,a%b,d,x,y); ll t=x; x=y; y=t-a/b*y; }}int main(){ ll a,b,c,t,M,k; ll x,y,m,n,L; cin>>x>>y>>m>>n>>L; a=n-m; b=L; c=x-y; k=gcd(a,b); if(c%k!=0){ cout<<"Impossible"<<endl; return 0; } a/=k; b/=k; c/=k; exgcd(a,b,k,t,M); t=(((c*t)%b)+b)%b; if(!t) t+=b; cout<<t<<endl; return 0;} |
[BZOJ 3224]普通平衡树
很好，这很interesting。
最大坑点是数可能重复。然后前驱后驱赶脚也挺坑的……
还有好像BZOJ不滋磁time(0)哎。所以我就用了wyy的生日做随机数种子辣！
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | /************************************************************** Problem: 3224 User: danihao123 Language: C++ Result: Accepted Time:376 ms Memory:1880 kb****************************************************************/ #include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;struct Node{ Node *ch[2]; int v; int r; int s; int cnt; Node(){ v=s=cnt=0; r=-1; ch[0]=ch[1]=NULL; } Node(int key,Node *lc,Node *rc){ v=key; r=rand(); s=1; cnt=1; ch[0]=lc; ch[1]=rc; } void maintain(){ s=ch[0]->s+ch[1]->s+cnt; }};struct Treap{ Node *null,*root; Treap(){ null=new Node(); root=null; } void rotate(Node* &o,int d){ Node* k=o->ch[d^1]; o->ch[d^1]=k->ch[d]; k->ch[d]=o; o->maintain(); k->maintain(); o=k; } void insert(Node* &o,int x){ if(o==null){ o=new Node(x,null,null); }else{ if(o->v==x){ o->cnt++; o->s++; }else{ int d=x>(o->v); insert(o->ch[d],x); if(((o->ch[d])->r)>(o->r)) rotate(o,d^1); } } o->maintain(); } void del(Node* &o,int x){ if(o->v==x){ if(o->cnt>1){ o->cnt--; o->s--; }else{ if(o->ch[0]==null){ Node *u=o; o=o->ch[1]; delete u; }else{ if(o->ch[1]==null){ Node *u=o; o=o->ch[0]; delete u; }else{ int d=(o->ch[1]->r)>(o->ch[0]->r); rotate(o,d^1); del(o->ch[d^1],x); } } } }else{ int d=x>(o->v); del(o->ch[d],x); } if(o!=null) o->maintain(); } int kth(Node *o,int k){ if(k<=(o->ch[0]->s)){ return kth(o->ch[0],k); }else{ k-=o->ch[0]->s; if(k<=o->cnt) return o->v; else return kth(o->ch[1],k-(o->cnt)); } } int rank(Node *o,int x){ if(o==null) return 0; if(x<(o->v)){ return rank(o->ch[0],x); }else{ if(x==o->v) return o->ch[0]->s+1; else return o->ch[0]->s+o->cnt+rank(o->ch[1],x); } } int pre(int x){ Node *cur=root; int ans=0; while(cur!=null){ if(cur->v<x){ ans=cur->v; cur=cur->ch[1]; }else{ cur=cur->ch[0]; } } return ans; } int suc(int x){ Node *cur=root; int ans=0; while(cur!=null){ if(cur->v>x){ ans=cur->v; cur=cur->ch[0]; }else{ cur=cur->ch[1]; } } return ans; }};int main(){ int n; int opt,x; Treap T; scanf("%d",&n); srand(20020601); while(n--){ scanf("%d%d",&opt,&x); if(opt==1){ T.insert(T.root,x); }else{ if(opt==2){ T.del(T.root,x); }else{ if(opt==3){ printf("%d\n",T.rank(T.root,x)); }else{ if(opt==4){ printf("%d\n",T.kth(T.root,x)); }else{ if(opt==5){ printf("%d\n",T.pre(x)); }else{ printf("%d\n",T.suc(x)); } } } } } } return 0;} |
[BZOJ 3223]文艺平衡树
三大平衡树题中的第二道……
果然文艺啊，轻音体柔易推倒，果然是萝莉
很明显伸展树辣！
代码：
