Problem A 华华教奕奕写几何
https://ac.nowcoder.com/acm/contest/894/A
题意：
题解：思维+数学
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#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-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
printf("%.3f\n",2*sqrt(n/PI));
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem B 华华送奕奕小礼物
https://ac.nowcoder.com/acm/contest/894/B
题意：
题解：前缀和+二分
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#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=1000+10;
const int M=1000000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p;
ll l,r,u,v;
ll ans,cnt,flag,temp,sum[2][N];
int a[N],b[N];
ll A[M];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d%lld%lld",&n,&m,&l,&r);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum[0][i]=sum[0][i-1]+a[i];
for(int i=1;i<=m;i++)scanf("%d",&b[i]),sum[1][i]=sum[1][i-1]+b[i];
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
A[++cnt]=sum[0][i]-sum[0][j];
}
}
sort(A+1,A+cnt+1);
for(int i=1;i<=m;i++){
for(int j=0;j<i;j++){
temp=sum[1][i]-sum[1][j];
ans+=(upper_bound(A+1,A+cnt+1,(double)r/temp)-lower_bound(A+1,A+cnt+1,(double)l/temp));
}
}
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem C 华华跟奕奕玩游戏
https://ac.nowcoder.com/acm/contest/894/C
题意：
C++版本一
题解：矩阵快速幂
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#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=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
ll q,p,l,r,u,v;
int cnt,flag,temp,sum;
int a,b;
char str;
struct node{};
ll POW(ll a,ll b,ll c){
ll res=1;
ll base=a%c;
while(b){
if(b&1)res=(res*base)%c;
base=(base*base)%c;
b>>=1;
}
return res;
}
struct Matrix{
int n;
Matrix(int nn = 1):n(nn){ memset(a,0,sizeof(a));};
long long a[N][N];
void print(){
for(int i = 0;i <= n; ++i)
for(int j= 0;j <= n; ++j)
printf("%lld%c",a[i][j]," \n"[j==n]);
}
Matrix operator*(const Matrix &b)const{
Matrix c(n);
for(int i = 0;i <= n; ++i){
for(int j = 0;j <= n; ++j){
for(int k = 0;k <= n; ++k){
c.a[i][j] += a[i][k] * b.a[k][j];
c.a[i][j] %= MOD;
}
}
}
//c.print();
return c;
}
};
Matrix ans,fac;
void MatrixPOW(ll k){
while(k){
if(k&1)ans=ans*fac;
fac=fac*fac;
k>>=1;
//ans.print();
}
}
void init(){
ans.n = fac.n = 2;
ans.a[0][0] = n;
ans.a[0][1] = (p*q)%MOD;
fac.a[0][0] = q;
fac.a[1][0] = 1;
fac.a[1][1] = 1;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
p=(a*POW(b,MOD-2,MOD))%MOD;
q=((n+m)*POW(n+m+1,MOD-2,MOD))%MOD;
init();
MatrixPOW(k);
cout<<ans.a[0][0]<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解：数学+数列
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#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=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
ll q,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a,b;
char str;
struct node{};
ll POW(ll a,ll b,ll c){
ll res=1;
ll base=a%c;
while(b){
if(b&1)res=(res*base)%c;
base=(base*base)%c;
b>>=1;
}
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
p=(a*POW(b,MOD-2,MOD))%MOD;
q=((n+m)*POW(n+m+1,MOD-2,MOD))%MOD;
ll qk=POW(q,k,MOD);
ll tmp=(q*POW((q-1+MOD)%MOD,MOD-2,MOD))%MOD;
tmp=(tmp*((qk-1+MOD)%MOD))%MOD;
ans=((n*qk)%MOD+(p*tmp)%MOD)%MOD;
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem D 华华陪奕奕打怪兽
https://ac.nowcoder.com/acm/contest/894/D
题意：
题解：
C++版本一
Problem E 华华和奕奕学物理
https://ac.nowcoder.com/acm/contest/894/E
题意：
若op==1,输入v,t,m,表示在t时刻从无穷高处以初速度v垂直向下抛出一个质量为m的小球。
若op==2,输入v,t。表示询问t时刻所有速度小于等于v的小球的动能之和是多少。
题解：树状数组+数学+物理
C++版本一题解：
若某一时刻a球比b球速度快，则a球始终比b球速度快。取T=300000。对于1操作 v1,t1,m1。可以算出V1=v1+g*(T-t1)。对于2操作，可以算出V2=v2+g*(T-t2)。则需要查询的小球即是满足V1<=V2的小球。然后根据公式m1*(v1+g*(t2-t1))^2,拆开，维护6个树状数组即可。
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#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=4000000+10;
const int M=100000+10;
const int T=300000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,g=10;
ll ans,cnt,flag,temp;
ll bit[8][N];
void add(ll b[],int i,ll C){
while(i<N){
b[i]=(b[i]+C)%MOD;
i+=i&-i;
}
}
ll sum(ll b[],int i){
ll ans=0;
while(i>0){
ans+=b[i];
i-=i&-i;
}
return ans%MOD;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
while(n--){
scanf("%d",&p);
if(p==1){
scanf("%d%d%d",&v,&t,&m);
int V=v+g*(T-t);
add(bit[1],V,1LL*m*v%MOD*v%MOD);
add(bit[2],V,1LL*m*g*g%MOD);
add(bit[3],V,1LL*m*g*g%MOD*t%MOD*t%MOD);
add(bit[4],V,1LL*2*m*g*g%MOD*t%MOD);
add(bit[5],V,1LL*2*m*v%MOD*g%MOD);
add(bit[6],V,1LL*2*m*v%MOD*g*t%MOD);
}else{
scanf("%d%d",&v,&t);
int V=min(v+g*(T-t),N-1);
ans=0;
ans+=sum(bit[1],V);
ans+=sum(bit[2],V)*t%MOD*t%MOD;
ans+=sum(bit[3],V);
ans-=sum(bit[4],V)*t%MOD;
ans+=sum(bit[5],V)*t%MOD;
ans-=sum(bit[6],V);
ans=(ans%MOD+MOD)%MOD;
printf("%lld\n",ans);
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem F 华华和奕奕的旅行
https://ac.nowcoder.com/acm/contest/894/F
题意：
题解：
C++版本一
京公网安备 11010502036488号