Result

AC: 3/10, J A F
Rank: 359/890
Upsolved: 1/7, E

J. Fraction Comparision

直接交叉相乘会爆ll，比赛时__int128暴过去了
实际上，化成带分数比较就好了
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
#include<bits/stdc++.h>
usingnamespacestd;
usingll=longlong;
#define debug(x) cout<<#x<<' '<<x<<endl
//
intmain()
{
  ll x,a,y,b;
  while(cin>>x>>a>>y>>b) {
    ll ans=0;
    if(x/a==y/b) {
      x=x%a,y=y%b;
      ans=x*b-y*a;
    } else{
      ans=x/a-y/b;
    }
   
    if(ans>0) {
      puts(">");
    } elseif(ans==0) {
      puts("=");
    } else{
      puts("<");
    }
  }
  return0;
}

A. Equivalent Prefixes

单调栈处理出每个元素作为最小值的左端点
从左往右扫一遍，对应元素左端点不相同则跳出
可以证明，某个位置的右端点不同不影响结论
min(rightA[i], rightB[i])+1处的leftA和leftB一定不同

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
#include<bits/stdc++.h>
usingnamespacestd;
usingll=longlong;
#define debug(x) cout<<#x<<' '<<x<<endl
//
constintMAXN=(int)1e5+10;
inta[MAXN],b[MAXN];
intla[MAXN],lb[MAXN];
//
voidinit(intnum[],intl[]intn);
//
intmain()
{
  intn;
  while(cin>>n) {
    for(inti=1;i<=n;i++) {
      scanf("%d",a+i);
    }
    for(inti=1;i<=n;i++) {
      scanf("%d",b+i);
    }
    init(a,la,n);
    init(b,lb,n);
 
    intans=1;
    for(inti=1;i<=n;i++) {
      if(la[i]!=lb[i]) {
        break;
      }
      ans=i;
    }
    printf("%d\n",ans);
  }
  return0;
}
 
voidinit(intnum[],intl[],intn)
{
  stack<int> s;
  for(inti=1;i<=n;i++) {
    while(!s.empty() && num[i]<num[s.top()]) {
      s.pop();
    }
    if(s.empty()) {
      l[i]=1;
    } else{
      l[i]=s.top()+1;
    }
    s.push(i);
  }
}

F. Random Point in Triangle

显然是个多重积分，但是我不会求（摊手）
考虑到答案一定是个整数，蒙特卡洛跑一下找规律
发现答案是面积的22倍，玄学选手实锤
顺便学会了三角形面积计算公式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
usingnamespacestd;
usingll=longlong;
#define debug(x) cout<<#x<<' '<<x<<endl
//
intmain()
{
  ll x1,y1,x2,y2,x3,y3;
  while(cin>>x1>>y1>>x2>>y2>>x3>>y3) {
    ll ans=abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)*11;
    printf("%lld\n",ans);
  }
  return0;
}

E. ABBA

贪心一下，前n个A作为AB的A，答案是最优的
如果作为BA的A，显然可以从后面随便抓个A来匹配B
同样的，前m个B一定是BA的B
dp[i][j]表示用了i个A，j个B的方案数，枚举下一个位置放A或B
  1. i<n，直接放A，dp[i+1][j]+=dp[i][j]
  2. i>=n，确保A能匹配BA的B，即出现在所有B后面，给了的小于需要的，i-n<min(j,m)
  3. j<m，直接放B，dp[i][j+1]+=dp[i][j]
  4. j>=m，确保B能匹配AB的A，即出现在所有A后面，给了的小于需要的，j-m<min(i,n)
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
#include<bits/stdc++.h>
usingnamespacestd;
usingll=longlong;
#define debug(x) cout<<#x<<' '<<x<<endl
//
constll mod=(ll)1e9+7;
constintMAXN=(int)2e3+10;
ll dp[MAXN][MAXN];
//
intmain()
{
  intn,m;
  while(cin>>n>>m) {
    for(inti=0;i<=n+m;i++) {
      for(intj=0;j<=n+m;j++) {
        dp[i][j]=0;
      }
    }
 
    dp[0][0]=1;
    for(inti=0;i<=n+m;i++) {
      for(intj=0;j<=n+m;j++) {
        if(i<n || i-n<min(j,m)) {
          dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
        }
        if(j<m || j-m<min(i,n)) {
          dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
        }
      }
    }
 
    printf("%lld\n",dp[n+m][n+m]);
  }
  return0;
}