本文的目的是介绍CodeforcesRound#576(Div.2)B-WaterLily的详细情况，我们将通过专业的研究、有关数据的分析等多种方式，同时也不会遗漏关于CodeforceRound57
本文的目的是介绍Codeforces Round #576 (Div. 2) B - Water Lily的详细情况，我们将通过专业的研究、有关数据的分析等多种方式，同时也不会遗漏关于Codeforce Round 578 Div. 2 A. Hotelier、Codeforces Round #257 (Div. 2)、Codeforces Round #257 (Div. 2) 题解、Codeforces Round #557 (Div. 2)的知识。
本文目录一览：- Codeforces Round #576 (Div. 2) B - Water Lily
- Codeforce Round 578 Div. 2 A. Hotelier
- Codeforces Round #257 (Div. 2)
- Codeforces Round #257 (Div. 2) 题解
- Codeforces Round #557 (Div. 2)
Codeforces Round #576 (Div. 2) B - Water Lily
Codeforces Round #576 (Div. 2)
B - Water Lily
While sailing on a boat, Inessa noticed a beautiful water lily flower above the lake''s surface. She came closer and it turned out that the lily was exactly H centimeters above the water surface. Inessa grabbed the flower and sailed the distance of L centimeters. Exactly at this point the flower touched the water surface.
Suppose that the lily grows at some point A on the lake bottom, and its stem is always a straight segment with one endpoint at point A. Also suppose that initially the flower was exactly above the point A, i.e. its stem was vertical. Can you determine the depth of the lake at point A?
Input
The only line contains two integers H and L (1≤H<L≤10^6).
Output
Print a single number — the depth of the lake at point A. The absolute or relative error should not exceed 10^−6.
Formally, let your answer be A, and the jury''s answer be B. Your answer is accepted if and only if |A−B|max(1,|B|)≤10^−6.
Examples
input
1 2
output
1.5000000000000
input
3 5
output
2.6666666666667
思路：几何数学题，看图我们可以列出方程 
，
化简之后得 
，由此得解
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<cstring>
5 #include<map>
6 #include<set>
7 #include<vector>
8 #include<algorithm>
9 #include<queue>
10 #include<unordered_map>
11 #include<list>
12 using namespace std;
13 #define ll long long
14 const int mod=1e9+7;
15 const int inf=1e9+7;
16
17 const int maxn=1e5+5;
18
19 int main()
20 {
21 //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
22
23 double H,L;
24
25 while(cin>>H>>L)
26 {
27 double x=(L*L-H*H)/(2*H);
28 printf("%.10f\n",x);
29 }
30
31 return 0;
32 }
Codeforce Round 578 Div. 2 A. Hotelier
A. Hotelier
Problem
Amugae has a hotel consisting of $10$ rooms. The rooms are numbered from $0$ to $9$ from left to right.
The hotel has two entrances — one from the left end, and another from the right end. When a customer arrives to the hotel through the left entrance, they are assigned to an empty room closest to the left entrance. Similarly, when a customer arrives at the hotel through the right entrance, they are assigned to an empty room closest to the right entrance.
One day, Amugae lost the room assignment list. Thankfully Amugae''s memory is perfect, and he remembers all of the customers: when a customer arrived, from which entrance, and when they left the hotel. Initially the hotel was empty. Write a program that recovers the room assignment list from Amugae''s memory.
Input
The first line consists of an integer $n (1 \leq n \leq 105)$, the number of events in Amugae''s memory.
The second line consists of a string of length $n$ describing the events in chronological order. Each character represents:
''L'': A customer arrives from the left entrance. ''R'': A customer arrives from the right entrance. ''0'', ''1'', ..., ''9'': The customer in room x (0, 1, ..., 9 respectively) leaves.
It is guaranteed that there is at least one empty room when a customer arrives, and there is a customer in the room $x$ when $x (0, 1, ..., 9)$is given. Also, all the rooms are initially empty.
Output
In the only line, output the hotel room''s assignment status, from room $0$ to room $9$. Represent an empty room as ''0'', and an occupied room as ''1'', without spaces.
Examples
input
8 LLRL1RL1
output
1010000011
input
9 L0L0LLRR9
output
1100000010
Note
In the first example, hotel room''s assignment status after each action is as follows.
·First of all, all rooms are empty. Assignment status is 0000000000. ·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000. ·L: one more customer from the left entrance. Assignment status is 1100000000. ·R: one more customer from the right entrance. Assignment status is 1100000001. ·L: one more customer from the left entrance. Assignment status is 1110000001. ·1: the customer in room 1 leaves. Assignment status is 1010000001. ·R: one more customer from the right entrance. Assignment status is 1010000011. ·L: one more customer from the left entrance. Assignment status is 1110000011. ·1: the customer in room 1 leaves. Assignment status is 1010000011.
So after all, hotel room''s final assignment status is 1010000011.
In the second example, hotel room''s assignment status after each action is as follows.
·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000. ·0: the customer in room 0 leaves. Assignment status is 0000000000. ·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000 again. ·0: the customer in room 0 leaves. Assignment status is 0000000000. ·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000. ·L: one more customer from the left entrance. Assignment status is 1100000000. ·R: one more customer from the right entrance. Assignment status is 1100000001. ·R: one more customer from the right entrance. Assignment status is 1100000011. ·9: the customer in room 9 leaves. Assignment status is 1100000010.
So after all, hotel room''s final assignment status is 1100000010.
想法
暴力出奇迹
The Code Of My Program
/*********************
*@Author: ChenShou *
*@Language: C++11 *
*********************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
inline ll read(){
long long x=0,f=1;
char ch=getchar();
while(ch<''0''||ch>''9''){
if(ch==''-'')
f=-1;
ch=getchar();
}
while(ch>=''0''&&ch<=''9''){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n;
int room [15]={0};
char op[100005];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
//}
n=read();
scanf("%s",op);
for(int i=0;i<n;i++){
if(op[i]==''L''){
for(int j=0;j<=9;j++){
if(!room[j]){
room[j]=1;
break;
}
}
}else
if(op[i]==''R''){
for(int j=9;j>=0;j--){
if(!room[j]){
room[j]=1;
break;
}
}
}
else {
int now=op[i]-''0'';
room[now]=0;
}
}
for(int i=0;i<10;i++){
printf("%d",room[i]);
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Fuck You !" << endl;
return 0;
}
Codeforces Round #257 (Div. 2)
Codeforces Round #257 (Div. 2)
https://codeforces.com/contest/450/
A
模拟
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,mid,rt<<1 4 #define rson mid+1,r,rt<<1|1 5 #define sqr(x) ((x)*(x)) 6 #define pb push_back 7 #define eb emplace_back 8 #define maxn 100005 9 #define eps 1e-8 10 #define pi acos(-1.0) 11 #define rep(k,i,j) for(int k=i;k<j;k++) 12 typedef long long ll; 13 typedef pair<int,int> pii; 14 typedef pair<long long,int>pli; 15 typedef pair<int,char> pic; 16 typedef pair<pair<int,string>,pii> ppp; 17 typedef unsigned long long ull; 18 const long long MOD=1e9+7; 19 /*#ifndef ONLINE_JUDGE 20 freopen("1.txt","r",stdin); 21 #endif */ 22 23 int n,m; 24 int a[105]; 25 26 int main(){ 27 #ifndef ONLINE_JUDGE 28 // freopen("1.txt",stdin); 29 #endif 30 cin>>n>>m; 31 for(int i=0;i<n;i++){ 32 cin>>a[i]; 33 } 34 int pos=0; 35 int i=0; 36 int co=0; 37 while(1){ 38 if(a[i]>0){ 39 pos=i; 40 a[i]-=min(m,a[i]); 41 co=0; 42 } 43 else { 44 co++; 45 } 46 i=(i+1)%n; 47 if(co==n) break; 48 } 49 cout<<pos+1<<endl; 50 51 }
B
矩阵快速幂
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,pii> ppp; 17 typedef unsigned long long ull; 18 const long long mod=1e9+7; 19 /*#ifndef ONLINE_JUDGE 20 freopen("1.txt",stdin); 21 #endif */ 22 ll n,m,k; 23 struct sair{ 24 ll a[3][3]; 25 sair(){ 26 a[0][0]=0,a[0][1]=0; 27 a[1][0]=0,a[1][1]=0; 28 } 29 friend sair operator*(const sair&a,const sair &b){ 30 sair ans; 31 for(int i=0;i<2;i++){ 32 for(int j=0;j<2;j++){ 33 for(int k=0;k<2;k++){ 34 ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j]%mod+mod)%mod; 35 } 36 } 37 } 38 return ans; 39 } 40 }; 41 42 sair pow_mul(sair a){ 43 k-=2; 44 sair base; 45 base.a[0][0]=1,base.a[0][1]=0; 46 base.a[1][0]=0,base.a[1][1]=1; 47 while(k){ 48 if(k&1) 49 base=base*a; 50 k>>=1; 51 a=a*a; 52 } 53 return base; 54 } 55 56 int main(){ 57 #ifndef ONLINE_JUDGE 58 // freopen("1.txt",stdin); 59 #endif 60 cin>>n>>m>>k; 61 sair a; 62 a.a[0][0]=(m+mod)%mod,a.a[0][1]=0; 63 a.a[1][0]=(n+mod)%mod,a.a[1][1]=0; 64 if(k==1) cout<<a.a[1][0]<<endl; 65 else if(k==2) cout<<a.a[0][0]<<endl; 66 else { 67 sair base; 68 base.a[0][0]=1,base.a[0][1]=-1; 69 base.a[1][0]=1,base.a[1][1]=0; 70 sair tmp=pow_mul(base); 71 base=tmP*a; 72 cout<<(base.a[0][0]+mod)%mod<<endl; 73 } 74 75 }
C
找规律
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,stdin); 21 #endif */ 22 23 int main(){ 24 #ifndef ONLINE_JUDGE 25 // freopen("1.txt",stdin); 26 #endif 27 ll n,k; 28 cin>>n>>m>>k; 29 ll tmp=(n-1)+(m-1); 30 if(n-1==0) tmp=m-1; 31 if(m-1==0) tmp=n-1; 32 if(n-1==0&&m-1==0) tmp=0; 33 if(tmp<k) cout<<-1<<endl; 34 else{ 35 ll ans=0; 36 if(k>=n)ans=max(ans,m/(k-n+2)); 37 if(k>=m)ans=max(ans,n/(k-m+2)); 38 if(k<n)ans=max(ans,m*(n/(k+1))); 39 if(k<m)ans=max(ans,n*(m/(k+1))); 40 cout<<ans<<endl; 41 } 42 43 }
