19点02分时发现比赛开始了，在纠结要不要打，如果打的话就亏了(狗头
过了一个小时上去看看，还是打了打hhh
除了G题没怎么看过。。
先放代码，之后再补题解和简单的题意hhh
A dd爱科学1.0
每次可以选择一个字符修改为另一个字符，使得最终字符串呈递增排序。
动态规划
对于当前字符si，dp当前字符变为A~Z需要的最小花费
int n,dp[30],mi[30]; char s[maxn]; void solve() { sd(n); sc(s+1); rep(i,1,n) { rep(j,0,25) { if(j!=s[i]-'A')dp[j]=mi[j]+1; else dp[j]=mi[j]; if(!j)mi[j]=dp[j]; else mi[j]=min(mi[j-1],dp[j]); } } pd(mi[25]); }
B dd爱探险
/* 状压dp嚯 */ int n,p[20][20]; int sum[maxn][20][4],ans; void solve() { memset(sum,INF,sizeof sum); sd(n); rep(i,1,n)rep(j,1,n)sd(p[i][j]); rep(i,1,n)sum[(1<<(i-1))][i][0]=0; rep(i,1,(1<<n)-1) { rep(j,1,n)//准备去往的下一个点 { if(!(i&(1<<(j-1))))continue; rep(k,1,n)//前一个点 { if(!(i&(1<<(k-1)))||k==j)continue; sum[i][j][0]=min(sum[i][j][0],sum[i^(1<<(j-1))][k][0]+p[k][j]); sum[i][j][1]=min(sum[i][j][1],sum[i^(1<<(j-1))][k][0]); sum[i][j][1]=min(sum[i][j][1],sum[i^(1<<(j-1))][k][1]+p[k][j]); sum[i][j][2]=min(sum[i][j][2],sum[i^(1<<(j-1))][k][0]+p[k][j]*2); sum[i][j][2]=min(sum[i][j][2],sum[i^(1<<(j-1))][k][2]+p[k][j]); sum[i][j][3]=min(sum[i][j][3],sum[i^(1<<(j-1))][k][3]+p[k][j]); sum[i][j][3]=min(sum[i][j][3],sum[i^(1<<(j-1))][k][2]); sum[i][j][3]=min(sum[i][j][3],sum[i^(1<<(j-1))][k][1]+p[k][j]*2); } } } ans=1e9; rep(i,1,n)ans=min(ans,sum[(1<<n)-1][i][3]); pd(ans); }
C dd爱科学2.0
int n,dp[30],mi[30]; char s[maxn]; void solve() { sd(n); sc(s+1); rep(i,1,n) { rep(j,0,25) { dp[j]=mi[j]+abs(s[i]-'A'-j); if(!j)mi[j]=dp[j]; else mi[j]=min(mi[j-1],dp[j]); } } pd(mi[25]); }
D dd爱矩阵
给一个n*n矩阵，从每行选一个数，共n^n种结果，要求输出前n大的和。
(输出结果得从大到小排序。。。
对于第i行，从前i-1行得到的前n大和求和，每次只要求n大的和。
int n,a[maxn][maxn]; int sum[maxn]; priority_queue<int,deque<int>,greater<int> >pq; void solve() { sd(n); rep(i,1,n)rep(j,1,n)sd(a[i][j]); rep(i,1,n)sum[i]=a[1][i]; sort(sum+1,sum+1+n); rep(i,2,n) { sort(a[i]+1,a[i]+1+n); dep(j,n,1)dep(k,n,1) { if(pq.size()>=n&&sum[j]+a[i][k]<pq.top())break; pq.push(sum[j]+a[i][k]); while(pq.size()>n)pq.pop(); } rep(j,1,n)sum[j]=pq.top(),pq.pop(); } dep(i,n,1)pdk(sum[i]); puts(""); }
E dd爱旋转
第一种操作的结果：矩阵上下翻转，左右翻转。
第二种操作的结果：矩阵上下翻转。
int n,a[maxn][maxn]; int cnt1,cnt2; void solve() { sd(n); rep(i,1,n)rep(j,1,n)sd(a[i][j]); int q; sd(q); while(q--) { int x; sd(x); if(x==1)cnt1^=1,cnt2^=1; else cnt2^=1; } if(cnt1) { rep(i,1,n) { rep(j,1,n/2)swap(a[i][j],a[i][n-j+1]); } } if(cnt2) { dep(i,n,1) { rep(j,1,n)pdk(a[i][j]); puts(""); } } else { rep(i,1,n) { rep(j,1,n)pdk(a[i][j]); puts(""); } } }
F dd爱框框
给一个长度为n的数组，要求找到最小的区间[l,r]，区间内的和大于等于x，输出最小的l和r。
二分长度
int n,x,a[maxn]; int ansl,ansr; bool check(int len) { ll sum=0; rep(i,1,len)sum+=a[i]; if(sum>=x) { ansl=1;ansr=len; return 1; } rep(i,len+1,n) { sum-=a[i-len]; sum+=a[i]; if(sum>=x) { ansl=i-len+1; ansr=i; return 1; } } return 0; } void solve() { sdd(n,x); rep(i,1,n)sd(a[i]); int l=1,r=n; while(l<=r) { int mid=(l+r)>>1; if(check(mid))r=mid-1; else l=mid+1; } pdd(ansl,ansr); }
H dd爱整齐
k有限序列：
k=3时：...abbbabbbabbba...
每k+1个一队
/* 一开始还以为k没给呢qwq */ int n,k,c,mi,M[maxn],cnt[maxn]; ll sum[maxn],ans,SUM; void solve() { mi=2e9; ans=1e18; sdd(n,k);k++; rep(i,0,k)M[i]=2e9; rep(i,1,n) { sd(c); SUM+=c; mi=min(mi,c); sum[i%k]+=c; M[i%k]=min(M[i%k],c); cnt[i%k]++; } rep(i,0,k-1) { ll tmp=(SUM-sum[i])-1ll*mi*(n-cnt[i]); tmp+=sum[i]-1ll*M[i]*cnt[i]; ans=min(ans,tmp); } plld(ans); }
(好感动！还是第一次看到推荐！