[赛后总结]G2022 Regular Contest 05总结

智商不足，一做AGC的题目就自闭…

赛时

T1-普及T1难度，10min切掉。
T2-感觉难度跨度好大…
想了一堆贪心方法，然后一个一个的被hack了…
连均值不等式都考虑过了…但是好像只能最大化$\sum a_i^2$而不是$\sum a_i$。
T3-连暴力分都是假的…考虑过倒着$O(n^4)$dp…但是怎么试都有问题…
回到T2-重新捋了一遍思路，猜测答案是有单调性的…写了一半发现时间来不及了…于是赶紧换成暴力…然后就自闭了…

赛后总结

T2大概最终已经知道做法了吧…感觉这题的关键就在处理技巧上面。
T3神仙dp…说实话我觉得这种题当考试用确实没什么意义…部分分是假的，正解也基本没
这场的得分确实很难看，因为我平时考试习惯了最后30min再写骗分…然后就很容易写挂…
以后还是要改一下策略。

题解

T1-长寿面(noodle) / AGC034B ABC

略

T2-印作业(homework) / AGC034C Tests

题目描述

对于所有数据，满足$1\le n\le 10^5,1\le x\le 10,0\le d_i\le x,1\le l_i\le r_i\le n$。

题解

我认为这题最关键的一点就在于我们的将物品的最大权值看成p[i].b*p[i].l+(x-p[i].b)*p[i].r而不是x*p[i].r，这样我们就可以轻松的将最大权和最小权的情况结合起来考虑，就可以直接二分了。

Other

这题真没什么细节，就不多说了…
鬼知道像他们一样用错误的方法贪心可以直接拿65。我还是忘了这次考试是OI赛制的本质…

吃山楂(hardest) / AGC012F Prefix Median

题目描述

对于所有数据，满足 $1\le n\le 50$，$1\le a_i\le 2n?1$。

题解

神仙dp题。
typ(e)学长已经吧做法讲的够详细了，我就不多说了。
传送门

实现

T1-noodle

int main(){
    freopen("noodle.in","r",stdin);freopen("noodle.out","w",stdout);scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++){
    if(s[i]=='A')cntA++;else if(s[i]=='B'&&s[i+1]=='C')ans+=cntA,i=i+1;else cntA=0;}printf("%lld",ans);
}

T2-homework

/*Lower_Rating*/
/*Ex*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 100000
#define eps 1e-10
#define INF 10000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}int n;LL x;
LL D,ans,sum[MAXN+5];
struct node{
    LL b,l,r,h;
}p[MAXN+5];
bool cmp(node s1,node s2){
    return s1.h>s2.h;
}LL calc(int i,LL pv){
    if(pv<=p[i].b)return pv*p[i].l;return p[i].b*p[i].l+(pv-p[i].b)*p[i].r;
}bool check(LL v){
    LL res=0,rm=v%x,cnt=v/x;if(cnt>=n)return sum[n];for(int i=1;i<=n;i++){
    if(i<=cnt)res=max(res,calc(i,rm)+sum[cnt+1]-p[i].h);else res=max(res,calc(i,rm)+sum[cnt]);}return res>=D;
}int main(){
    freopen("homework.in","r",stdin);freopen("homework.out","w",stdout);n=read(),x=read();for(int i=1;i<=n;i++){
    p[i]=(node){
    read(),read(),read(),0};p[i].h=p[i].b*p[i].l+(x-p[i].b)*p[i].r;D+=p[i].b*p[i].l;}sort(p+1,p+n+1,cmp);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+p[i].h;LL l=0,r=INF;while(l<=r){
    LL mid=(l+r)>>1;if(check(mid))r=mid-1,ans=mid;else l=mid+1;}printf("%lld",ans);
}

T3-hardest

/*Lower_Rating*/
/*Ex*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 100
#define eps 1e-10
#define INF 2147483647
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}int n;
int a[MAXN+5],p[MAXN+5],ans;
int dp[(MAXN>>1)+5][MAXN+5][MAXN+5];int main(){
    //freopen("hardest.in","r",stdin);//freopen("hardest.out","w",stdout);n=read();for(int i=1;i<=2*n-1;i++)a[i]=read();sort(a+1,a+2*n);dp[n][1][0]=1;for(int i=n-1;i>=1;i--){
    int al=(a[i]!=a[i+1]),ar=(a[2*n-i]!=a[2*n-i-1]);for(int l=0;l<=2*n-1;l++)for(int r=0;l+r<=2*n-1;r++)if(dp[i+1][l][r]){
    for(int dl=1;dl<=l+al;dl++){
    int pl=l+al-dl+1,pr=r+ar+(dl>1);dp[i][pl][pr]=add(dp[i][pl][pr],dp[i+1][l][r]);}for(int dr=1;dr<=r+ar;dr++){
    int pl=l+al+1,pr=r+ar-dr;dp[i][pl][pr]=add(dp[i][pl][pr],dp[i+1][l][r]);}}}for(int l=0;l<=2*n-1;l++)for(int r=0;l+r<=2*n-1;r++)ans=add(ans,dp[1][l][r]);printf("%d",ans);
}