2019牛客暑期多校訓練營（第一場）
A-Equivalent Prefixes
（單調棧，思維，笛卡爾樹）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int ans1[maxn],ans2[maxn];
int val1[maxn],val2[maxn];
struct node
{
int val,index;
};
int main()
{
int n,i;
stack<node> s;
while(cin>>n)
{
for(i=1;i<=n;i++)
cin>>val1[i];
for(i=1;i<=n;i++)
cin>>val2[i];
val1[0]=val2[0]=-1;
for(i=n;i>=0;i--)
{
while(!s.empty()&&s.top().val>val1[i])
{
ans1[s.top().index]=i;
s.pop();
}
s.push(node{val1[i],i});
}
for(i=n;i>=0;i--)
{
while(!s.empty()&&s.top().val>val2[i])
{
ans2[s.top().index]=i;
s.pop();
}
s.push(node{val2[i],i});
}
for(i=1;i<=n;i++)
{
if(ans1[i]!=ans2[i])
break;
}
cout<<i-1<<endl;
}
return 0;
}
B-Integration
（數學積分推導，分式分解技巧，快速幂，逆元）
寫這道題首先要知道 部分分式分解 這個技巧：
假定 p 1 p_1 p1, p 2 p_2 p2,… p n p_n pn均為實數，且無重根，例如，考慮如下的變換式求其逆變換：
F ( s ) = A ( s ) ( s − p 1 ) ( s − p 2 ) ( s − p 3 ) F(s)=\frac{A(s)}{(s-p_1)(s-p_2)(s-p_3)} F(s)=(s−p1)(s−p2)(s−p3)A(s)
式子中分母多項式的階次高于分子多項式的階次。這時 F ( s ) F(s) F(s)可以分解為以下形式：
F ( s ) = K 1 ( s − p 1 ) + K 2 ( s − p 2 ) + K 3 ( s − p 3 ) F(s)=\frac{K_1}{(s-p_1)}+\frac{K_2}{(s-p_2)}+\frac{K_3}{(s-p_3)} F(s)=(s−p1)K1+(s−p2)K2+(s−p3)K3
其中 K i = ( s − p i ) F ( s ) ∣ （ s = p i ) K_i=(s-p_i)F(s)|（s=p_i) Ki=(s−pi)F(s)∣（s=pi)
知道這個結論後，開開始看原題的那個式子： 1 π ∫ 1 ∞ 1 ∏ i = 1 n ( a i 2 + x 2 ) d x \frac{1}{\pi}\int_1^\infty\frac{1}{\prod_{i=1}^{n}(a^2_i+x^2)}dx π1∫1∞∏i=1n(ai2+x2)1dx
先考慮 1 ∏ i = 1 n ( a i 2 + x 2 ) \frac{1}{\prod_{i=1}^{n}(a^2_i+x^2)} ∏i=1n(ai2+x2)1，我們可以用上面的公式進行變換，得到：
∑ i = 1 n C i ( a i 2 + x 2 ) \sum_{i=1}^n\frac{C_i}{(a^2_i+x^2)} ∑i=1n(ai2+x2)Ci 其中 C i = 1 ∏ i ! = j ( a j 2 − a i 2 ) C_i=\frac{1}{\prod_{i!=j}^{}(a^2_j-a^2_i)} Ci=∏i!=j(aj2−ai2)1
是以原式： 1 π ∫ 1 ∞ 1 ∏ i = 1 n ( a i 2 + x 2 ) d x = ∑ 1 n C i 2 a i π \frac{1}{\pi}\int_1^\infty\frac{1}{\prod_{i=1}^{n}(a^2_i+x^2)}dx=\sum_1^n\frac{C_i}{2a_i}\pi π1∫1∞∏i=1n(ai2+x2)1dx=∑1n2aiCiπ
是以暴力就完事了。
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e3+5;
const int Mod = 1e9+7;
int a[N];
inline int qpow(int a,int b){
a%=Mod;
int res = 1;
while(b){
if(b&1) res = res*a%Mod;
a = a*a%Mod;
b>>=1;
}
return res;
}
inline int inv(int x){
return qpow(x,Mod-2);
}
int32_t main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i];
}
int ans = 0;
for(int i=0;i<n;i++){
int p = 1;
for(int j=0;j<n;j++){
if(i==j) continue;
p = p*((a[j]*a[j]-a[i]*a[i])%Mod)%Mod;
}
p = 2*a[i]*p%Mod;
p = inv(p);
ans = (ans+Mod+p)%Mod;
}
cout<<ans<<endl;
}
return 0;
}
C- Euclidean Distance
照着唯神的思路寫的，沒用分數類，導緻最後細節太多還是沒處理好。
放一個正解，沒用标解中的拉格朗日乘數法。
(數學推導)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10000;
int m,n;
struct frac
{
ll p,q;
frac(){}
frac(ll _p,ll _q)
{
if(_p<0&&_q<0) _p=-_p,_q=-_q;
else
if(_q<0) _q=-_q,_p=-_p;
//cout<<"ce "<<_p<< " "<<_q<<endl;
p=_p/__gcd(abs(_p),abs(_q));
q=_q/__gcd(abs(_p),abs(_q));
//cout<<"ce "<<p<< " "<<q<<endl;
}
bool operator < (const frac &x) const
{
return p*x.q<q*x.p;
}
bool operator <= (const frac &x) const
{
return p*x.q<=q*x.p;
}
bool operator == (const frac &x) const
{
return p==x.p&&q==x.q;
}
frac operator + (const frac &x)
{
return frac(p*x.q+q*x.p,q*x.q);
}
frac operator * (const frac &x)
{
return frac(p*x.p,q*x.q);
}
frac operator / (const frac &x)
{
return frac(p*x.q,q*x.p);
}
frac operator - (const frac &x)
{
return frac(p*x.q-q*x.p,q*x.q);
}
}a[maxn+5];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
a[i]=frac(x,m);
}
sort(a+1,a+n+1);
//for(int i=1;i<=n;++i) cout<<a[i].p<<" "<<a[i].q<<endl;
frac now(1,1);
frac left(1,1);
frac pos(0,0);
for(int i=n-1;i>=1;--i)
if((a[i+1]-a[i])*now<=left) left=left-(a[i+1]-a[i])*now,now.p+=1;
else
{
pos=a[i+1]-left/now;
break;
}
// cout<<"left : "<<left.p<<" "<<left.q<<endl;
//cout<<now.p<<endl;
if(pos.p==0&&pos.q==0)
{
// assert(now.p==n);
//a[1]-left/now
//cout<<"ok"<<endl;
pos=a[1]-left/now;
//cout<<pos.p<<" "<<pos.q<<endl;
}
frac ans(0,1);
for(int i=1;i+now.p<=n;++i) ans=ans+a[i]*a[i];
ans=ans+now*pos*pos;
if(ans.p==0) printf("0\n");
else if(ans.q==1) printf("%lld\n",ans.p);
else printf("%lld/%lld\n",ans.p,ans.q);
}
return 0;
}
F-Random Point in Triangle
(數學推導，期望)
選三個中點，連接配接中線，利用中心的性質即可得出，具體推倒不算特别簡單，還需要再畫輔助線，代換等數學推導。
其實最簡單的方法就是猜性質，我們畫一個特例的等邊三角形來算，這樣節省了許多不必要的計算。
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int x1,x2,x3,y1,y2,y3;
while(cin>>x1>>y1>>x2>>y2>>x3>>y3){
int s = (x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)*11;
cout<<abs(s)<<endl;
}
return 0;
}
J-Fraction Comparision
(簽到題)
C++:
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int x,a,y,b;
while(scanf("%lld%lld%lld%lld",&x,&a,&y,&b)!=EOF){
long long int i,o;
i=x/a;
o=y/b;
if(i>o)printf(">\n");
else if(i<o) printf("<\n");
else {
x=x%a*b;y=y%b*a;
if(x>y)printf(">\n");
else if(x<y) printf("<\n");
else printf("=\n");
}
}
return 0;
}
python：
import sys
for line in sys.stdin:
a,b,c,d = map(int,line.split(' '))
if a*d>b*c:
print('>')
elif a*d==b*c:
print('=')
elif a*d<b*c:
print('<')
![POJ 1284 Primitive Roots (歐拉函數&原根定理)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)