A-欧几里得
题目描述
欧几里得算法是一种求最大公约数的有效算法,在算法竞赛中很常用。
Python代码实现如下:
1 2 3 4 def gcd (a,b ): if b == 0 : return a return gcd(b,a%b)
现在,如果已知 gcd(a,b) 共递归了 n次,求所有可能的a,b中满足a>b>=0且a+b最小的一组的a与b之和。
输入描述
第一行一个整数,T。
接下来T行一行一个整数,n。
输出描述
T行,每行一个整数,代表a+b。
示例1
输入
1
0
输出
1
说明
gcd(1,0) 由于 b=0,不会递归,即是递归0次。
示例2
输入
1
1
输出
3
说明
gcd(2,1)会递归一次至gcd(1,0)。
思路
题给的两个样例非常具有启发性。(2,1)递归一次变为(1,0)。那么我们给出的(a,b)最终必定会递归至(2,1)–>(1,0)。(a,b)一步递归后变为(b,a%b),这是一定的;但是从(b,a%b)反推(a,b)有多种情况,而使a+b最小的情况是(a,b)=(b+a%b,b)。于是有序列(1,0),(2,1),(3,2)。求这个序列我们可以直接递推,也可以用斐波那契数列递推。能够产生这样的递推方式,是因为此题满足“最优子结构”“无后效性”“重复子问题”,此题本质上是动态规划。
代码1
直接递推
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 #include <iostream> #include <algorithm> #include <cstdio> using namespace std;struct node { long long a; long long b; }p[100 ]; int main () { p[0 ].a=1 ; int i; p[0 ].b=0 ; p[1 ].a=2 ; p[1 ].b=1 ; for (i=2 ;i<=90 ;i++) { p[i].b=p[i-1 ].a; p[i].a=p[i-1 ].a+p[i-1 ].b; } int t; scanf ("%d" ,&t); while (t--) { int k; scanf ("%d" ,&k); printf ("%lld\n" ,p[k].a+p[k].b); } return 0 ; }
代码2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> using namespace std;typedef long long ll;ll fib[110 ]={0 }; int main () { fib[0 ]=1 ; fib[1 ]=2 ; int i; for (i=2 ;i<=100 ;i++) fib[i]=fib[i-1 ]+fib[i-2 ]; int T,n; cin>>T; while (T--) { cin>>n; if (n==0 )cout<<1 <<endl; else cout<<fib[n]+fib[n-1 ]<<endl; } return 0 ; }
B-括号序列
题目描述
给出一个仅包含’[‘,’]‘,’(‘,’)‘,’{‘,’}'六种字符的括号序列,判断其是否合法。
空串是一个合法的括号序列。
如果A, B 都是合法的括号序列,那么AB也是合法的括号序列。
如果A是合法的括号序列,(A) , [A], {A}都是合法的括号序列。
输入描述
一行一个字符串S,只包含题目中的六种括号字符。
输出描述
输出为一行"Yes" 或"No"。
示例1
输入
(){}[]
输出
Yes
示例2
输入
({[]})
输出
Yes
示例3
输入
([)]
输出
No
备注
1≤∣S∣≤1000000
思路
这是一个配对问题。不合法有两种情况,一种是左右括号数量不一致,另一种是左右括号种类不一致。运用简单的数据结构:栈。非常坑的是用STL会导致堆栈溢出,于是手写了一个。
代码
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 #include <iostream> #include <string> using namespace std;char stack[1000005 ];int main () { string s; cin>>s; bool flag=1 ; int i; int head=0 ; for (i=0 ;i<s.length ();i++) { if (s[i]=='(' ) stack[++head]=s[i]; else if (s[i]==')' ) { if (stack[head]!='(' ) { flag=0 ; break ; } else head--; } else if (s[i]=='[' ) stack[++head]=s[i]; else if (s[i]==']' ) { if (stack[head]!='[' ) { flag=0 ; break ; } else head--; } else if (s[i]=='{' ) stack[++head]=s[i]; else if (s[i]=='}' ) { if (stack[head]!='{' ) { flag=0 ; break ; } else head--; } } if (!flag||head) cout<<"No" ; else cout<<"Yes" ; return 0 ; }
C-子段乘积
题目描述
给出一个长度为 n n n 的数列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a 1 , a 2 , ... , a n ,求其长度为 k 的连续子段的乘积对 998244353 取模余数的最大值。
输入描述
第一行两个整数n,k。
第二行n个整数,a1,a2,…,an。
输出描述
输出一个整数,代表最大余数。
示例1
输入
5 3
1 2 3 0 8
输出
6
说明
1∗2∗3mod998244353=6
备注
1≤k≤n≤2∗10⁵
0≤ai<998244353
思路
用尺取法,前缀和之类的,似乎都要注意串中存在0的情况,但是我又不知道有0怎么处理。于是就规避这件事,用线段树维护区间内所有数的乘积。
我们只要枚举所有长度为k的区间,找出最大值即可。此题只有查询操作,没有更新操作,用线段树显得异常简单,可以视作一道线段树的板子题。然而比赛的时候wa了8次,赛后才发现错误。
代码
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 #include <iostream> #include <cstdio> #define N 200002 #define ll long long using namespace std;const ll mod=998244353 ;struct Segment { int l,r; ll v; }tree[N<<2 ]; ll a[N]; void build (int id,int l,int r) { tree[id].l=l; tree[id].r=r; if (l==r) { tree[id].v=a[l]%mod; return ; } int mid=(l+r)>>1 ; build (id<<1 ,l,mid); build (id<<1 |1 ,mid+1 ,r); tree[id].v=tree[id<<1 ].v*tree[id<<1 |1 ].v%mod; } ll query (int id,int l,int r) { if (l<=tree[id].l&&tree[id].r<=r) { return tree[id].v%mod; } ll res=1 ; int mid=(tree[id].l+tree[id].r)>>1 ; if (l<=mid) res=res*query (id<<1 ,l,r)%mod; if (r>=mid+1 ) res=res*query (id<<1 |1 ,l,r)%mod; return res; } int main () { int n,k; scanf ("%d%d" ,&n,&k); int i; for (i=1 ;i<=n;i++) scanf ("%lld" ,&a[i]); build (1 ,1 ,n); ll ans=0 ; for (i=1 ;i<=n-k+1 ;i++) { ans=max (ans,query (1 ,i,i+k-1 )%mod); } printf ("%lld" ,ans%mod); return 0 ; }
D-子段异或
题目描述
输入一个数列a,你需要输出其中异或值为0的不同子段的数量。一个子段 [l,r] (1≤l≤r≤n)的异或值为a[l]⊕a
[l+1]⊕a[l+2]⊕…⊕a [r],其中⊕符号代表异或运算。
两个子段被视为相同的,当且仅当其开始和结束位置均对应相同。
输入描述
第一行一个整数n,代表数列长度。
第二行n个整数,代表数列。
输出描述
输出一个整数,代表答案。
示例1
输入
5
1 2 3 2 1
输出
2
说明
子段 [1,3] 和子段 [3,5] 是合法子段。
备注
$n≤200000,0≤ai≤{2^{30}}-1$
思路
定义前缀异或和prefix[]。区间[l,r]的异或和为0,说明prefix[l-1]^prefix[r]=0,即prefix[l-1]=prefix[r]。
由于异或数据可能很大,我们用map<long long,int>cnt进行离散化操作,记录每一个异或前缀和的值出现的次数。假设某一个异或值出现了n次,我们要从其中选出两个值组合,组合数为$C_n^2 = \frac{{n(n - 1)}}{2}$,这显然对应这一个和S n = 0 + 1 + 2 + ⋯ + ( n − 1 ) {S_n} = 0 + 1 + 2 + \cdots + (n - 1) S n = 0 + 1 + 2 + ⋯ + ( n − 1 ) 。于是我们只要每找到一个值prefix,ans需要加上(cnt[prefix] - 1)。
代码
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 #include <iostream> #include <map> using namespace std;typedef long long ll;int main () { ios::sync_with_stdio (false ); int n; ll prefix=0 ; cin>>n; map<ll,int >cnt; int i; ll t; ll ans=0 ; cnt[0 ]=1 ; for (i=1 ;i<=n;i++) { cin>>t; prefix^=t; cnt[prefix]++; ans=ans+cnt[prefix]-1 ; } cout<<ans; return 0 ; }
E-最小表达式
题目描述
给出一个包含数字1-9和加号的字符串,请你将字符串中的字符任意排列,但每种字符数目不变,使得结果是一个合法的表达式,而且表达式的值最小。输出那个最小表达式的值
合法的表达式的定义如下:
一个数字,如233,是一个合法的表达式
A + B是合法的表达式,当且仅当 A , B 都是合法的表达式
保证给出的表达式经过重排,存在一个合法的解。
输入描述
一行输入一个字符串,仅包含数字1-9和加号+。
字符串的长度小于5 × 1 0 5 5 \times {10^5} 5 × 1 0 5 。
输出描述
一行输出一个数字,代表最小的解。
示例1
输入
111+1
输出
22
说明
11+11=22
示例2
输入
9998765432111
输出
1112345678999
示例3
输入
12+35
输出
38
说明
25+13=38
示例4
输入
23984692+238752+2+34+
输出
5461
说明
嗯,这个答案是可以得到的
备注
注意,答案长度可能长达500000个字符。
思路
首先,我们要读取字符串,统计加号的个数plus,因为字符是随意组合的,所以我们不妨将字符从小到大排序,这时候加号会排在最前面。
从小到大排序是一种贪心的策略,有plus个加号,我们就需要把字符串分成group=(plus+1)份,要做到每一份数字的个数都较为均匀,且最高位要尽可能小。
于是我们只要将字符从大到小排序,枚举group个数字的最高位,每一次枚举最高位,都需要隔group个字符选取该数字的每一位。
因为数字很庞大,在此抄一下BigInteger的板子。
代码
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 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 #include <iostream> #include <cstring> #include <algorithm> #include <string> #include <vector> using namespace std;struct BigInteger { static const int BASE=100000000 ; static const int WIDTH=8 ; bool sign; size_t length; vector<int > num; BigInteger (long long x=0 ) { *this =x; } BigInteger (const string &x) { *this =x; } BigInteger (const BigInteger &x) { *this =x; } void cutLeadingZero () { while (num.back ()==0 &&num.size ()!=1 ) { num.pop_back (); } int tmp=num.back (); if (tmp==0 ) length=1 ; else { length=(num.size ()-1 )*WIDTH; while (tmp>0 ) { length++; tmp/=10 ; } } } BigInteger &operator =(long long x) { num.clear (); if (x>=0 ) sign=true ; else { sign=false ; x=-x; } do { num.push_back (x%BASE); x/=BASE; }while (x>0 ); cutLeadingZero (); return *this ; } BigInteger &operator =(const string &str) { num.clear (); sign=(str[0 ]!='-' ); int x,len=(str.size ()-1 -(!sign))/WIDTH+1 ; for (int i=0 ;i<len;i++) { int End=str.size ()-i*WIDTH; int start=max ((int )(!sign),End-WIDTH); sscanf (str.substr (start,End-start).c_str (),"%d" ,&x); num.push_back (x); } cutLeadingZero (); return *this ; } BigInteger &operator =(const BigInteger &tmp) { num=tmp.num; sign=tmp.sign; length=tmp.length; return *this ; } BigInteger abs () const { BigInteger ans (*this ) ; ans.sign=true ; return ans; } const BigInteger &operator +() const { return *this ; } BigInteger operator -() const { BigInteger ans (*this ) ; if (ans!=0 ) ans.sign=!ans.sign; return ans; } BigInteger operator +(const BigInteger &b) const { if (!b.sign) { return *this -(-b); } if (!sign) { return b-(-*this ); } BigInteger ans; ans.num.clear (); for (int i=0 ,g=0 ;;i++) { if (g==0 &&i>=num.size ()&&i>=b.num.size ()) break ; int x=g; if (i<num.size ()) x+=num[i]; if (i<b.num.size ()) x+=b.num[i]; ans.num.push_back (x%BASE); g=x/BASE; } ans.cutLeadingZero (); return ans; } BigInteger operator -(const BigInteger &b) const { if (!b.sign) { return *this +(-b); } if (!sign) { return -((-*this )+b); } if (*this <b) { return -(b-*this ); } BigInteger ans; ans.num.clear (); for (int i=0 ,g=0 ;;i++) { if (g==0 &&i>=num.size ()&&i>=b.num.size ()) break ; int x=g; g=0 ; if (i<num.size ()) x+=num[i]; if (i<b.num.size ()) x-=b.num[i]; if (x<0 ) { x+=BASE; g=-1 ; } ans.num.push_back (x); } ans.cutLeadingZero (); return ans; } BigInteger operator *(const BigInteger &b) const { int lena=num.size (),lenb=b.num.size (); BigInteger ans; for (int i=0 ;i<lena+lenb;i++) ans.num.push_back (0 ); for (int i=0 ,g=0 ;i<lena;i++) { g=0 ; for (int j=0 ;j<lenb;j++) { long long x=ans.num[i+j]; x+=(long long )num[i]*(long long )b.num[j]; ans.num[i+j]=x%BASE; g=x/BASE; ans.num[i+j+1 ]+=g; } } ans.cutLeadingZero (); ans.sign=(ans.length==1 &&ans.num[0 ]==0 )||(sign==b.sign); return ans; } BigInteger e (size_t n) const { int tmp=n%WIDTH; BigInteger ans; ans.length=n+1 ; n/=WIDTH; while (ans.num.size ()<=n) ans.num.push_back (0 ); ans.num[n]=1 ; while (tmp--) ans.num[n]*=10 ; return ans*(*this ); } BigInteger operator /(const BigInteger &b) const { BigInteger aa ((*this ).abs()) ; BigInteger bb (b.abs()) ; if (aa<bb) return 0 ; char *str=new char [aa.length+1 ]; memset (str,0 ,sizeof (char )*(aa.length+1 )); BigInteger tmp; int lena=aa.length,lenb=bb.length; for (int i=0 ;i<= lena-lenb;i++) { tmp=bb.e (lena-lenb-i); while (aa>=tmp) { str[i]++; aa=aa-tmp; } str[i]+='0' ; } BigInteger ans (str) ; delete [] str; ans.sign=(ans==0 ||sign==b.sign); return ans; } BigInteger operator %(const BigInteger &b) const { return *this -*this /b*b; } BigInteger &operator ++() { *this =*this +1 ; return *this ; } BigInteger &operator --() { *this =*this -1 ; return *this ; } BigInteger &operator +=(const BigInteger &b) { *this =*this +b; return *this ; } BigInteger &operator -=(const BigInteger &b) { *this =*this -b; return *this ; } BigInteger &operator *=(const BigInteger &b) { *this =*this *b; return *this ; } BigInteger &operator /=(const BigInteger &b) { *this =*this /b; return *this ; } BigInteger &operator %=(const BigInteger &b) { *this =*this % b; return *this ; } bool operator <(const BigInteger &b) const { if (sign!=b.sign) { return !sign; } else if (!sign&&!b.sign) { return -b<-*this ; } if (num.size ()!=b.num.size ()) return num.size ()<b.num.size (); for (int i=num.size ()-1 ;i>=0 ;i--) { if (num[i]!=b.num[i]) return num[i]<b.num[i]; } return false ; } bool operator >(const BigInteger &b) const { return b<*this ; } bool operator <=(const BigInteger &b) const { return !(b<*this ); } bool operator >=(const BigInteger &b) const { return !(*this <b); } bool operator !=(const BigInteger &b) const { return b<*this ||*this <b; } bool operator ==(const BigInteger &b) const { return !(b<*this )&&!(*this <b); } bool operator ||(const BigInteger &b) const { return *this !=0 ||b!=0 ; } bool operator &&(const BigInteger &b) const { return *this !=0 &&b!=0 ; } bool operator !() { return (bool )(*this ==0 ); } friend ostream &operator <<(ostream &out,const BigInteger &x) { if (!x.sign) out<<'-' ; out<<x.num.back (); for (int i=x.num.size ()-2 ;i>=0 ;i--) { char buf[10 ]; sprintf (buf,"%08d" ,x.num[i]); for (int j=0 ;j<strlen (buf);j++) out<<buf[j]; } return out; } friend istream &operator >>(istream &in,BigInteger &x) { string str; in>>str; size_t len=str.size (); int start=0 ; if (str[0 ]=='-' ) start=1 ; if (str[start]=='\0' ) return in; for (int i=start;i<len;i++) { if (str[i]<'0' ||str[i]>'9' ) return in; } x.sign=!start; x=str.c_str (); return in; } }; int main () { ios::sync_with_stdio (0 ); string s; cin>>s; sort (s.begin (),s.end ()); int len=s.length (); int plus=0 ; int i; for (i=0 ;i<len;i++) { if (s[i]=='+' ) plus++; } int group=plus+1 ; string temp; BigInteger ans=0 ; int j,step; for (i=group-1 ,step=1 ;step<=group;i++,step++) { temp="" ; for (j=i;j<len;j+=group) temp+=s[j]; ans+=BigInteger (temp); } cout<<ans; return 0 ; }
F-树上博弈
题目描述
现有一个 n 个点,n-1条边组成的树,其中 1 号点为根节点。
牛牛和牛妹在树上玩游戏,他们在游戏开始时分别在树上两个不同的节点上。
在游戏的每一轮,牛牛先走一步,而后牛妹走一步。他们只能走到没有人的空节点上。如果谁移动不了,就输掉了游戏。现在牛牛和牛妹决定随机选择他们分别的起点,于是他们想知道,有多少种游戏开始的方式,使得牛牛存在一种一定获胜的最优策略。
两种开始方式相同,当且仅当在两种开始方式中牛牛,牛妹的开始位置是分别相同的,否则开始方式就被视作不同的。
输入描述
第一行输入为一个整数 n,代表树的点数。
第二行n-1个整数p 2 , p 3 , . . . , p n {p_2},{p_3},...,{p_n} p 2 , p 3 , ... , p n ,分别代表2,3,…,n号点的父节点编号。
输出描述
一行一个整数,代表答案。
示例1
输入
3
1 2
输出
2
说明
当且仅当牛牛在1号点,牛妹在3号点,或者牛牛在3号点,牛妹在1号点时,牛牛才获胜。
示例2
输入
2
1
输出
0
说明
由于无论如何牛牛都无路可走,因此必然牛妹获胜。
示例3
输入
30
1 1 2 1 2 1 3 2 3 4 2 3 1 2 3 4 2 4 5 6 3 4 12 12 12 13 13 13 13
输出
428
说明
QwQ
备注
n ⩽ 1 0 6 , 1 ⩽ p i ⩽ i n \leqslant {10^6},1 \leqslant {p_i} \leqslant i n ⩽ 1 0 6 , 1 ⩽ p i ⩽ i .
思路
首先,注意到输掉的唯一方法是自己的唯一一条边有另一个人,那么自己一定是在叶子上。
令两个人之间的距离为D。每人行动后D增加1或减少1。 因此,每有人走一步D的奇偶性都会改变。
假设最初,在牛牛移动之前,D是偶数。那么当牛牛移动时D将始终为偶数,而当牛妹移动时D将始终为奇数。
请注意,只要牛牛和牛妹的令牌位于相邻的节点中,D=1。因此,如果D为偶数,则他们不在相邻的单元格中,并且牛牛始终可以移动。
另一方面,由于牛牛总是可以移动,因此他可以向牛妹的方向移动,将牛妹必然会最终移动到叶子上。同样,如果最初D是奇数,则牛妹获胜。
因此,答案取决于距离的奇偶性:如果是偶数,则牛牛获胜,否则牛妹获胜。
可以发现,只有牛牛的初始位置和牛妹的初始位置距离为偶数时,牛牛获胜。只需要分别求出深度为奇数的点和深度为偶数的点的数量即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream> using namespace std;int n;int depth[1000001 ];int main () { ios::sync_with_stdio (false ); int i; cin>>n; int father; long odd=0 ,even=0 ; for (i=2 ;i<=n;i++) { cin>>father; depth[i]=depth[father]+1 ; if (depth[i]&1 ) odd++; else even++; } even++; cout<<odd*(odd-1 )+even*(even-1 ); return 0 ; }
G-音乐鉴赏
题目描述
作为“音乐鉴赏”课的任课老师,你的课程作为刷学分好课一直受到广泛欢迎。但这一学期,学校制定了新的标准,你的课的优秀率(分数超过90分的人数)被限制在10%以下!
为了应对这个调整,你要求所有的同学都写了一篇论文,并使用随机算法打出了0-90之间的分数,分数可能不是整数。这里的随机是指,对于在[0,90]这个闭区间上的任何一对等长的区间,分数出现在其中的概率均是相同的。在期末的分数占比为百分之多少的时候,你的课程优秀率期望恰好在10%?保证所有同学的平时成绩都高于90分。
输入描述
输入第一行包含一个整数 n,保证n是10的倍数。
第二行包含 n 个整数,代表同学们的平时成绩。
输出描述
输出一行一个百分数,代表期末分数占比多少为合适。保留两位小数。
示例1
输入
10
99 99 99 99 99 99 99 99 99 99
输出
50.00%
说明
需要随机占比50%。
思路
设某一个人的平时成绩为a,期末随机成绩为b,x为期末成绩占比 ( a ⩾ 90 , 0 ⩽ b ⩽ 90 , 0 ⩽ x ⩽ 1 ) (a \geqslant 90,0 \leqslant b \leqslant 90,0 \leqslant x \leqslant 1) ( a ⩾ 90 , 0 ⩽ b ⩽ 90 , 0 ⩽ x ⩽ 1 ) 。
假设有一条线段,端点为(0,90),b的取值占线段的全部长度 L = 90 L = 90 L = 90 。
如果这个人的总成绩为优秀,那么有a ( 1 − x ) + b x ⩾ 90 a(1 - x) + bx \geqslant 90 a ( 1 − x ) + b x ⩾ 90 ,解得$b \geqslant \frac{{90 - (1 - x)a}}{x}$。
此时b占线段长度 $l = 90 - \frac{{90 - (1 - x)a}}{x} = \frac{{(a - 90)(1 - x)}}{x}$。
所以一个人得到优秀的概率为$P = \frac{l}{L} = \frac{{(a - 90)(1 - x)}}{{90x}}$。
这是典型的几何概型。
可以这样理解,每有1个人,就会有P人得到优秀,每个人得到优秀的概率相加就是0.1 × n 0.1 \times n 0.1 × n 。
于是得到方程:
$\sum\limits_{i = 1}^n {\frac{{({a_i} - 90)(1 - x)}}{{90x}}} = \frac{n}{{10}}$
解得: $x = \frac{{\sum\limits_{i = 1}^n {({a_i} - 90)} }}{{9n + \sum\limits_{i = 1}^n {({a_i} - 90)} }}$
接下来的事情就很好办了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream> using namespace std;int main () { ios::sync_with_stdio (false ); int n; cin>>n; int sum=0 ; int T=n; int a; while (T--) { cin>>a; a-=90 ; sum+=a; } double ans=(1.0 *sum)/(9 *n+sum)*100 ; printf ("%.2lf" ,ans); putchar ('%' ); return 0 ; }
H-坐火车
题目描述
牛牛是一名喜欢旅游的同学,在来到渡渡鸟王国时,坐上了颜色多样的火车。
牛牛同学在车上,车上有n个车厢,每一个车厢有一种颜色。
他想知道对于每一个正整数x ∈ [ 1 , n ] x∈[1, n] x ∈ [ 1 , n ] ,集合$\{ (i,x,j)|i < x < j,{l_x} \leqslant co{l_i} \leqslant {r_x}\}$中包含多少个元素。
换句话说,就是要求每一个车厢两边有多少对颜色相同的车厢,并且这一对车厢的颜色要在 l x l_x l x 到r x r_x r x 之间。其中c o l i col_i co l i 代表i i i 号车厢的颜色,l x , r x lx,r_x l x , r x 代表颜色的限制。
输入描述
第一行一个正整数n。
第二行n个三元组,每个三元组包括三个正整数$ (col_i, l_i, r_i)$,输入中没有括号,这 3n 个正整数之间均只用空格隔开,详见样例。
输出描述
输出一行 n 个非负整数代表答案。
示例1
输入
5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出
0 3 4 3 0
备注
1 ≤ n ≤ 5 ⋅ 1 0 5 1≤n≤5⋅10^5 1 ≤ n ≤ 5 ⋅ 1 0 5
1 ≤ c o l i , l i , r i ≤ 5 ⋅ 1 0 5 1 \le col_i,\ l_i,\ r_i \le 5 \cdot 10^5 1 ≤ co l i , l i , r i ≤ 5 ⋅ 1 0 5
思路
从左向右遍历,使用树状数组维护每种颜色的该车厢左右的对数即可。
如下一个颜色是c o l i col_i co l i ,应当先减去下一个颜色作为右边的匹配数,再加上当前颜色作为左边的匹配数,注意不要爆long long。
代码
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 #include <iostream> #include <algorithm> using namespace std;typedef long long ll;const int N=500009 ;struct node { ll l,r; ll col; }cabin[N]; ll suffix[N],prefix[N],ans[N]; ll lowbit (ll x) { return x&(-x); } ll n; void update (ll i,ll val) { while (i<=n) { ans[i]+=val; i+=lowbit (i); } } ll query (ll i) { ll res=0 ; while (i>0 ) { res+=ans[i]; i-=lowbit (i); } return res; } void solve () { cin>>n; int i; for (i=1 ;i<=n;i++) { cin>>cabin[i].col; cin>>cabin[i].l; cin>>cabin[i].r; suffix[cabin[i].col]++; } for (i=1 ;i<=n;i++) { suffix[cabin[i].col]--; update (cabin[i].col,-prefix[cabin[i].col]); cout<<query (cabin[i].r)-query (cabin[i].l-1 )<<' ' ; prefix[cabin[i].col]++; update (cabin[i].col,suffix[cabin[i].col]); } } int main () { ios::sync_with_stdio (false ); solve (); return 0 ; }
I-匹配星星
题目描述
天上有n颗星星,每颗星星有二维坐标( x i , y i ) (x_i, y_i) ( x i , y i ) ,还有一个属性值z i z_i z i ,若两颗星星A, B满足x A < x B x_A<x_B x A < x B 且y A < y B y_A <y_B y A < y B 且z A < z B z_A < z_B z A < z B ,则这两颗星星可以配成一对,每颗星星最多只能在一对之中,求最多能配成多少对星星。
输入描述
第一行一个正整数n,表示星星的个数。
接下来n行,每行 3 个整数x i , y i , z i x_i, y_i, z_i x i , y i , z i ,表示一颗星星。
输出描述
一行一个整数,表示答案。
示例1
输入
2
1 1 0
2 2 1
输出
1
示例2
输入
2
1 1 1
2 2 1
输出
0
思路
首先要让所有星星按照x x x 从小到大排序。
用multiset设置一个候选池pool,储存星星的坐标y y y ,用multiset的好处是使坐标y y y 有序,且是从小到大排列的。
然后做一次遍历(for i 1 to n),如果z i = 0 z_i=0 z i = 0 ,那么将这颗星星放入候选池;如果z i = 1 z_i=1 z i = 1 ,那么我们就要从pool中选取一颗星星与之配对。由于x x x 已经从小到大排序,所以放入pool的星星的坐标x x x 都比x i x_i x i 小;因为pool中y y y 从小到大排列,于是我们只要二分找到第一个比y i y_i y i 大的坐标y y y ,pool中前面的那几颗星星都可与之配对。
这样一种贪心的策略显然是可行的。
代码
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 #include <iostream> #include <set> #include <algorithm> using namespace std;void solve () { struct node { int x,y,z; bool operator < (const node &rhs) const { if (x==rhs.x) return z>rhs.z; else return x<rhs.x; } }star[100002 ]; int n; cin>>n; int i; for (i=1 ;i<=n;i++) cin>>star[i].x>>star[i].y>>star[i].z; sort (star+1 ,star+1 +n); multiset<int >pool; multiset<int >::iterator it; int ans=0 ; for (i=1 ;i<=n;i++) { if (star[i].z) { it=pool.lower_bound (star[i].y); if (it!=pool.begin ()) { pool.erase (--it); ans++; } } else { pool.insert (star[i].y); } } cout<<ans; } int main () { ios::sync_with_stdio (false ); solve (); return 0 ; }