2019牛客ACM暑期多校第一场
太菜了 就过了一道题。
A-Equivalent Prefixes
题目描述
Two arrays u and v each with m distinct elements are called equivalent if and only if RMQ(u,l,r)=RMQ(v,l,r)RMQ(u,l,r)=RMQ(v,l,r) for all 1≤l≤r≤m1≤l≤r≤m
where RMQ(w,l,r)RMQ(w,l,r) denotes the index of the minimum element among wl,wl+1,…,wrwl,wl+1,…,wr.
Since the array contains distinct elements, the definition of minimum is unambiguous.
Bobo has two arrays a and b each with n distinct elements. Find the maximum number p≤np≤n where {a1,a2,…,ap}{a1,a2,…,ap} and {b1,b2,…,bp}{b1,b2,…,bp} are equivalent.
输入描述:
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains an integer n.
The second line contains n integers a1,a2,…,ana1,a2,…,an.
The third line contains n integers b1,b2,…,bnb1,b2,…,bn.
* 1≤n≤1051≤n≤105
* 1≤ai,bi≤n1≤ai,bi≤n
* {a1,a2,…,an}{a1,a2,…,an} are distinct.
* {b1,b2,…,bn}{b1,b2,…,bn} are distinct.
* The sum of n does not exceed 5×1055×105.
输出描述:
For each test case, print an integer which denotes the result.
示例1
输入
复制
2
1 2
2 1
3
2 1 3
3 1 2
5
3 1 5 2 4
5 2 4 3 1
输出
复制
1
3
4
一开始读错题了 wa了好多次 发现了之后本以为n^2过不了就没试 。看了别人的代码才知道
承认下面的代码有点问题。但能过
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
for(int i=0; i<n; i++)
scanf("%d",&b[i]);
int cnt=n-1;
for(int i=0; i<=cnt; i++)
{
for(int j=i+1; j<=cnt; j++)
{
int f=0;
if(a[i]>a[j])
f++;
if(b[i]>b[j])
f++;
if(f==1)
{
cnt=j-1;
break;
}
if(f==2)
break;
}
}
cout<<cnt+1<<'\n';
}
return 0;
}用单调栈做的人挺多的
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
const int INF=1e9;
ll a[maxn],b[maxn];
stack<ll >s1,s2;
int main()
{
ll n;
while(~scanf("%lld",&n))
{
while(!s1.empty())
s1.pop();
while(!s2.empty())
s2.pop();
for(int i=1; i<=n; i++)
scanf("%lld",&a[i]);
for(int i=1; i<=n; i++)
scanf("%lld",&b[i]);
s1.push(a[1]);
s2.push(b[1]);
int i;
for(i=2; i<=n; i++)
{
while(!s1.empty()&&a[i]<s1.top())//递减的单调栈
s1.pop();
s1.push(a[i]);
while(!s2.empty()&&b[i]<s2.top())
s2.pop();
s2.push(b[i]);
if(s1.size()!=s2.size())
break;
}
printf("%d\n",i-1);
}
return 0;
}
F-Random Point in Triangle
题目描述
Bobo has a triangle ABC with A(x1,y1),B(x2,y2)A(x1,y1),B(x2,y2) and C(x3,y3)C(x3,y3). Picking a point P uniformly in triangle ABC, he wants to know the expectation value E=max{SPAB,SPBC,SPCA}E=max{SPAB,SPBC,SPCA} where SXYZSXYZ denotes the area of triangle XYZ.
Print the value of 36×E36×E. It can be proved that it is always an integer.
输入描述:
The input consists of several test cases and is terminated by end-of-file.
Each test case contains six integers x1,y1,x2,y2,x3,y3x1,y1,x2,y2,x3,y3.
* |x1|,|y1|,|x2|,|y2|,|x3|,|y3|≤108|x1|,|y1|,|x2|,|y2|,|x3|,|y3|≤108
* There are at most 105105 test cases.
输出描述:
For each test case, print an integer which denotes the result.
示例1
输入
复制
0 0 1 1 2 2
0 0 0 0 1 1
0 0 0 0 0 0
输出
复制
0
0
0
首先普及一下三角形面积公式
1.S=(1/2)*a*b*sinC
2.S=(1/2)*|(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)| ///来源于叉乘
3.S=sqrt(p*(p-a)*(p-b)*(p-c)) p=(1/2)(a+b+c) ///海伦公式
4.略
大佬用二重积分推出来的比值 选正三角形为特例
期望E=（11/2）*S
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long x1,x2,x3,y1,y2,y3;
while(scanf("%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF)
{
long long s=x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2;
cout<<abs(s*11)<<'\n';
}
return 0;
}
J-Fraction Comparision
题目描述
Bobo has two fractions xaxa and ybyb. He wants to compare them. Find the result.
输入描述:
The input consists of several test cases and is terminated by end-of-file.
Each test case contains four integers x, a, y, b.
* 0≤x,y≤10180≤x,y≤1018
* 1≤a,b≤1091≤a,b≤109
* There are at most 105105 test cases.
输出描述:
For each test case, print `=` if xa=ybxa=yb. Print `<` if xa<ybxa<yb. Print `>` otherwise.
示例1
输入
复制
1 2 1 1
1 1 1 2
1 1 1 1
输出
复制
<
>
=
唯一过了的题qaq
感悟：python java真是好东西
python：
while True:
try:
x,a,y,b=map(int,input().split())
if x*b>y*a:
print(">")
elif x*b<y*a:
print("<")
else:
print("=")
except:
break
Java（偷来的一块代码）：
import java.io.*;
import java.math.*;
import java.util.*;
import java.math.*;
public class Main
{
public static void main( String []args)
{
Scanner cin = new Scanner(System.in);
BigInteger a,b,c,d,e,f;
while(cin.hasNext())
{
a = cin.nextBigInteger();
b = cin.nextBigInteger();
c = cin.nextBigInteger();
d = cin.nextBigInteger();
e = b.multiply(c);
f = a.multiply(d);
if(e.compareTo(f) == 0)
System.out.println("=");
else if(e.compareTo(f) > 0)
System.out.println('<');
else
System.out.println('>');
}
}
}
E-ABBA
题目描述
Bobo has a string of length 2(n + m) which consists of characters `A` and `B`. The string also has a fascinating property: it can be decomposed into (n + m) subsequences of length 2, and among the (n + m) subsequences n of them are `AB` while other m of them are `BA`.
Given n and m, find the number of possible strings modulo (109+7)(109+7).
输入描述:
The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.
* 0≤n,m≤1030≤n,m≤103
* There are at most 2019 test cases, and at most 20 of them has max{n,m}>50max{n,m}>50.
输出描述:
For each test case, print an integer which denotes the result.
示例1
输入
复制
1 2
1000 1000
0 0
输出
复制
13
436240410
1
dp
记得开long long
dp[i][j]是添加到i个A j个B时的方案数。
i<=n时 A可以随意添。i>n时 前面有多余的B时可以添 即i<=n+j
j<=m时 B可以随意添。j>m时 前面有多余的A时可以添 即j<m+i
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
const int MOD=1e9+7;
long long dp[N][N];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<=n+m;i++)
{
for(int j=0;j<=n+m;j++)
dp[i][j]=0;
}
dp[0][0]=1;
for(int i=0;i<=n+m;i++)
{
for(int j=0;j<=n+m;j++)
{
if(i<n+j)
dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
if(j<m+i)
dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD;
}
}
cout<<dp[n+m][n+m]<<'\n';
}
return 0;
}
暂时补了这么多。抽空继续。
