啊啊苏夏啊
Result
AC: 3/10, J A F
Rank: 359/890
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倍，玄学选手实锤
顺便学会了三角形面积计算公式
发现答案是面积的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
- i<n，直接放A，dp[i+1][j]+=dp[i][j]
- i>=n，确保A能匹配BA的B，即出现在所有B后面，给了的小于需要的，i-n<min(j,m)
- j<m，直接放B，dp[i][j+1]+=dp[i][j]
- 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; } |
