这里记录的是这个账号的比赛情况。
ARC157
2023-2-25
Solved:4/6
2189->2216
C(Medium,1802)
给定一个XY矩阵，一条左上角到右下角的路径的分值定义为路径上连续两个Y的组数。求所有可能路径的分值的平方和。
Solution：经典DP。递推两个量，一个是到(i,j)所有路径的分值和\(f_{i,j}\)，一个是平方和\(dp_{i,j}\)。递推式为
\[f_{i,j}=f_{i-1,j}+f_{i,j-1}+C(i+j-3,i-2)+C(i+j-3,j-2) \]\[dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}+(2 \times f_{i,j-1}+C(i+j-3,i-2))+(2 \times f_{i-1,j}+C(i+j-3,j-2)) \]其中倒数第二项在\(a_{i,j}==a_{i-1,j}==Y\)是有效，倒数第一项在\(a_{i,j}==a_{i,j-1}==Y\)时有效。
D(Medium+,2435)
给定一个XY矩阵，用横线和竖线将矩阵分为若干块，使得每块内恰有2个Y。求方案数。
Solution：说到底是暴力。先求二维前缀和，然后枚举第一条横线，它以上的Y的数目是总数的约数。接着求出后面每条横线的可能位置。再枚举竖线，要求在每条横线的位置的值一定。最后求积就得到了这个横线位置的解数。细节很多。
AGC060
2022-12-25
Solved:3/6
Rank47!
2031->2189
A(Easy+,1345)
补全一个字符串，使得其任意一个子串中不存在一个字母出现次数超过一半。
Solution：容易分析出只需要对长为3的子串满足，然后DP。
B(Medium+,1996)
在 \(n \times m\) 的方格表中填入一些不超过 \(2^k-1\) 的数。考虑所有从左上角到右下角的最短路径，要求其中满足路径上数异或和为 \(0\) 的路径只有给定的 \(S\) 一条，问是否有解。
C(Hard,2680)
称一个长为 \(2^n-1\) 的排列 \(P\) 像堆，如果 \(P_i \lt P_{2i}\),且 \(P_i \lt P_{2i+1}\)。给定 \(a,b,u=2^a,v=2^{b+1}-1\)，在所有像堆的排列中任取一个，求 \(P_u \lt P_v\) 的概率。
组合计数还是好做
ABC264
2022-8-13
Solved:7/8
Rank79!
Unrated
E(Medium-,1229)
给定\(n+m\)个点的无向图，其中后\(m\)个点为源点。给定\(q\)次删边操作，求每次操作后与源点联通的非源点数。
Solution：其实是套路题。倒序处理，化删边为连边，并查集维护，合并时尽可能向后。
F(Medium+.1878)
给定01矩阵及翻转各行各列的代价，求使得从左上角到右下角有同色通路的最小代价，这里通路只能向右或向下。
Solution：考虑DP，用\(dp[i][j][p][q]\)表示从左上角到达\((i,j)\)的最小代价，且此时第\(i\)行反转了\(p\)次，第\(j\)列反转了\(q\)次。显然只用考虑\(p,q \in \{0,1\}\)。
每个位置可以从上方或左方转移而来，必须有两个位置相同才能转移。计算代价时只考虑所扩展的行（列）。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005;
int h,w,r[N],c[N],a[N][N];
char s[N];
ll dp[N][N][2][2];
int main(){
scanf("%d%d",&h,&w);
for(int i=1;i<=h;i++)scanf("%d",r+i);
for(int i=1;i<=w;i++)scanf("%d",c+i);
for(int i=1;i<=h;i++){
scanf("%s",s+1);
for(int j=1;j<=w;j++)
a[i][j]=s[j]-'0';
}
memset(dp,0x3f,sizeof(dp));
dp[1][1][0][0]=0;
dp[1][1][1][0]=r[1];
dp[1][1][1][1]=r[1]+c[1];
dp[1][1][0][1]=c[1];
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
for(int st=0;st<=15;st++){
int p1=st&1,p2=(st>>1)&1,q1=(st>>2)&1,q2=(st>>3)&1;
if(i!=1&&(a[i][j]^p2^q2)==(a[i-1][j]^p1^q1)&&q1==q2)
dp[i][j][p2][q2]=min(dp[i][j][p2][q2],
dp[i-1][j][p1][q1]+r[i]*p2);
if(j!=1&&(a[i][j]^p2^q2)==(a[i][j-1]^p1^q1)&&p1==p2)
dp[i][j][p2][q2]=min(dp[i][j][p2][q2],
dp[i][j-1][p1][q1]+c[j]*q2);
}
printf("%lld\n",min(min(dp[h][w][0][0],dp[h][w][0][1]),
min(dp[h][w][1][0],dp[h][w][1][1])));
return 0;
}
G(Medium,2348)
给出\(n\)个长度不超过\(3\)的字符串，每个字符串有一个代价。对于一个字符串，定义其价值为给出的字符串在其中出现的次数与代价的乘积之和。对所有字符串，求价值最大值，或判断不存在。
Solution：还是比较显然的吧。
直接建图，每个结点是一个长为\(2\)的字符串，在两结点AB与BC间连有向边，边权为C,BC,ABC的代价之和。另建一个源点，向每个结点AB连边，代价为A,B,AB的代价之和。
从源点出发跑单源最长路，若有正环就无解。SPFA没死。
（大不合理，F的DP显然比G的建图难想）
ARC145
2022-7-30
Solved:4/6
1973->2031
A(Medium-,596)
给定长为\(n\)的AB字符串，可以将相邻两个改为AB，问是否能将原字符串变为回文串。
Solution：分类讨论题还不难首先特讨\(n=2\)。然后：
若开头为B，可以将中间全部改为A，末尾改为B；
若开头不为B，结尾为B，无解；
若开头，结尾均为A，可以将第\(2\)个和第\(n-1\)个改为B，中间全为A。
B(Easy,767)
两人取石子，先手取\(A\)的正数倍，后手取\(B\)的整数倍，这里\(A,B\)给定。求\(1,2,...,n\)中使先手获胜的初始石子数的个数。
Solution：策略显然：先手往死里取。若\(A \le B\)，只要先手能取就必胜；否则，先手取完后少于\(B\)个即获胜。
C(Easy+,1697)
对于一个\(1,2,...,2n\)的排列，定义其分数为：将排列划分为两个等长的子序列，对应项乘积和的最大值。给定\(n\)，求使得分数取最大值的排列数。
Solution：调整法易得最大值在\(1 \times 2 + 3 \times 4 + ... + (2n-1)\times 2n\)时取到，只用考虑每一对数的位置。选定左侧，则右侧必须顺次排列,转化一下就是卡特兰数。故答案为\(\frac{(2n)!}{(n+1)!} \times 2^n\)。
D(Medium+,2297)
构造满足以下条件的集合：集合中含\(n\)个\([-10^7,10^7]\)的整数，其和为\(m\)，且不含等差子列。
Solution：FVMO牛逼！
MO原题：求证：可以找出\(1983\)个不超过\(10^5\)的正整数，其中不含等差子列。
原题证明：取三进制下只含数码\(0,1\)的数即可。
本题思路类似，前\(n-1\)个顺次取这样的数，最后一个大于前一个的两倍，然后使得总和模\(n\)与\(m\)同余，最后补上一个偏移量。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
typedef long long ll;
ll n,m,cnt,sum,ans[N],del;
bool check(ll x){
while(x){
if(x%3==2)return false;
x/=3;
}
return true;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;cnt<n-1;i++)
if(check(i)){ans[++cnt]=i;sum+=i;}
ll r=(m-sum)%n;
ans[n]=(ans[n-1]*3+n)/n*n+r;
del=(m-ans[n]-sum)/n;
for(int i=1;i<=n;i++)
printf("%lld\n",ans[i]+del);
return 0;
}
ABC260
2022-7-17
Solved:7/8
Rank98！
1908->1973
E(Medium-,1692)
给定\(n\)个二元组，值域为\([1,m]\)，求长度为\(k\)，包含每个二元组中至少一个数的区间数目，这里\(k\)需取遍\(1,...,m\)。
Solution:考虑每个左端点，求出使其满足条件的最小右端点，用双指针。双指针时有一个方法：将所有数塞到一个数组中，维护出现的二元组数目。
若\([l,r]\)可行，则\([l,t],r \le t \le m\)可行，从而差分。最后求一次前缀和。
F(Medium,1995)
给定一个二分图，求其中是否有长为\(4\)的环。特殊限制：右部点数\(t \le 3000\)。
Solution:对每个右部点，从它出发走两步，如果两次走到同一个点则得到解。若没有走到，则每次时间为\(O(t)\)，总时间不超过\(O(t^2)\)。
G(Medium+,2339)
给定一个\(n \times n\) 的OX矩阵和\(m\)，给出\(q\)个询问\((x,y)\)，求满足\(s \le x \le n,t \le y \le n,(x-s)+\frac{y-t}{2} \lt m\)且填O的点\((s,t)\)数目。
Solution:一个裸的模板题：二维斜向差分，和P8228类似。首先对斜率为\(\frac{1}{2}\)方向差分，对这个差分数组，再从横向和斜率\(\frac{1}{2}\)方向差分。对每个\(O\)转化一下，再求前缀和就可以了。（为什么又是差分）
说着不难，实际上还是有一些细节要处理的。
ABC258
2022-7-2
Solved:6/8
1864->1908
E(Medium-,1545)
给定周期为\(n\)的序列的一个周期，从第一个开始加和，和超过\(x\)就计一段。求第\(k\)段的长。
Solution:考虑从每个位置出发会到达哪里。用双指针。再由此建立段开头的周期即可。
G(Medium,1944)
给定一张图，求三角形数目。
Solution:枚举一条边，计算其两个端点所连点的集合之交的大小。用 bitset 。
ARC142
2022-6-19
Solved:3/6
1880->1864
B(Medium+,692)
构造 \(n \times n\) 的矩阵，填入从 \(1\) 开始的连续整数，使得对任意一格，其周围（八连通）比它大的个数和比它小的个数不相同。
Solution:首先，边界的格子有奇数个邻格，不用考虑。
其次，如果能保证每个格周围有至少 \(5\) 个格与其大小关系相同，就解决了题目。由此可以想到按照圈来填，外圈所填一定大于内圈。
如果 \(n\) 为奇数，直接让每一圈大小相间即可。如果 \(n\) 为偶数，先让角落处为该圈最大，然后让边角处连续，其它地方大小相间。倒数第二圈单独构造，可以完成。
题解的做法简单：按行考虑，每行大小交替，各行递减。
C(Medium,1347)
\(n\) 个点的树，可以询问除 \(1\) 和 \(2\) 之外任意两点间距离，要求用不超过 \(2n\) 次询问确定 \(1\) 和 \(2\) 的距离。
Solution:先找出所有与 \(1\) 相距 \(1\) 的点。若一个没有，则答案为 \(1\)。若至少两个，询问这两个与 \(2\) 的距离即可判断。
若恰有一个，询问这个与 \(2\) 的距离。若不为 \(2\)，则 \(1\) 为叶子结点，直接确定。否则，对 \(2\) 重复上述操作，假如也没有确定，询问两次得到的点的间距即可。
ABC256
2022-6-18
Solved:6/8
1839->1880
ABC251
2022-5-14
Solved:6/8
1816->1839
D(Easy+,1463)
构造长不超过\(300\)的数列，使得\(1\)到\(10^6\)中的整数都可以从该数列中取出不超过三个做和得到。
Solution:需要一点想法。我的做法是按照进制的思想，数列包含\(1,2,...,99\),\(100,200,...,9900\),\(10000,20000,...,990000\).
F(Easy+,1703)
求给出的图中两棵生成树，其一满足以\(1\)为根时，图中非树边的端点有祖先关系，另一恰好相反。
Solution：第一棵树最直接的情况是一条链，所以尝试构造链，贪心地连边。也就是直接dfs，看到未加入生成树的点就连边。
第二棵树最直接的情况是一个菊花，所以dfs时遇到一个点就把它所有的边都加入生成树。
ABC242
2022-3-5
Solved：7/8
Rank89！（第一次进前100）
1711->1816
D(Easy,1286)
给定字符串\(S\)，只包含\(A\),\(B\),\(C\)，一次变换将\(A\)变为\(BC\)，\(B\)变为\(CA\)，\(C\)变为\(AB\)。求\(t\)次变换后第\(l\)个位置的字符。多组询问，\(t\)，\(l\)在$ \ long \ long $范围内。
Solution：还是挺有意思的。
可以在模\(3\)意义下考虑。每一个位置变为它加\(1\)和它加\(2\)。二进制转一下就搞完了。
E(Easy,1365)
给定整数\(n\)及长为\(n\)的字符串\(S\)，求满足\(X \le S\)的回文串\(X\)个数。
Solution：按位考虑，前\([\dfrac{n+1}{2}]\)位直接贪心，然后特判前一半全部一样的情况。
F(Medium+,2268)
在\(n \times m\)的棋盘上放置\(b\)个黑車和\(w\)个白車，求使得黑白之间互不攻击的放法数。
Solution：先考虑黑棋，设\(k\)个黑棋占据\(i\)行\(j\)列的方案数为\(dp[k][i][j]\)。这里把\(k\)作为阶段进行递推。
状态转移方程为
\[dp[k][i][j]=\dfrac{1}{k}((dp[k-1][i-1][j-1]+dp[k-1][i-1][j]+dp[k-1][i][j-1]) \times i \times j+dp[k-1][i][j] \times (i \times j-k+1)) \]然后枚举黑棋占领的行列数，剩下的行列都可以放白棋。
预处理阶乘，阶乘逆元，逆元等。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=55,M=2505;
int n,m,b,w,fac[M],fac_inv[M],inv[M],dp[M][N][N],ans;
int power(int a,int b){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*c*a%mod;
a=1ll*a*a%mod;
}
return c;
}
int C(int n,int m){
if(n<m||n<0||m<0)return 0;
return 1ll*fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;
}
int main(){
fac[0]=1;
for(int i=1;i<=M-5;i++)fac[i]=1ll*i*fac[i-1]%mod;
for(int i=0;i<=M-5;i++)fac_inv[i]=power(fac[i],mod-2);
for(int i=1;i<=M-5;i++)inv[i]=power(i,mod-2);
scanf("%d%d%d%d",&n,&m,&b,&w);
dp[1][1][1]=1;
for(int k=2;k<=n*m;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
//if(i*j<=k)continue;
dp[k][i][j]=(1ll*dp[k-1][i-1][j-1]*i*j%mod+1ll*dp[k-1][i-1][j]*i*j%mod+
1ll*dp[k-1][i][j-1]*i*j%mod+1ll*dp[k-1][i][j]*(i*j-k+1)%mod)*inv[k]%mod;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=(ans+1ll*dp[b][i][j]*C(n,i)%mod*C(m,j)%mod*C((n-i)*(m-j),w)%mod)%mod;
printf("%d\n",ans);
return 0;
}
（闲话：该代码正好1024Byte）
G(Medium+,1828)
给出长为\(n\)的数组，求\([l,r]\)中的数能配成几对。多组询问。
Solution：没想出什么常规做法，于是写了莫队。
（其实是一开始把题目看成了P1494）
ABC240
2022-02-20
Solved:6/8
1691->1711
F(Easy+,1589)
以\(x_i\)个\(y_i\)的形式给出长为\(m\)的数列\(C\)，数列\(B\)满足\(B_i=\sum_{k=1}^{i}C_k\)，数列\(A\)满足\(A_i=\sum_{k=1}^{i}B_k\)，求\(A\)中的最大项。
Solution：注意到\(B\)的每一段是单调的，那么可以找出每一段中正负交界出的点，考虑这些位置的\(A\)值即可。
G(Hard,2462)
从\((0,0,0)\)出发，每一步沿坐标轴方向移动一个单位长度，求用\(n\)步走到\((x,y,z)\)的方案数。
Solution:（搬运题解）
一维的情况非常简单，但这是此后的基础。记\(n\)步走到\(x\)的方案数为\(f_1{(n,x)}\)。
二维需要一点想法：将\((x,y)\)变换为\((x+y,x-y)\)，那么移动就是从\((x,y)\)到\((x+1,y+1)\),\((x-1,y+1)\),\((x+1,y-1)\),\((x-1,y-1)\)，这时就可以将横纵分开考虑，方案数为\(f_2{(n,x,y)}=f_1{(n,x+y)}\times f_1{(n,x-y)}\)。
三维时，枚举一下\(z\)方向就可以了。
ABC237
2022-01-30
Solved:6/8
1669->1691
F(Medium-,1857)
求长为\(n\)，值域\([1,m]\)，\(LIS\)长为\(3\)的整数列数目。
Solution:把\(LIS\)问题\(O(nlogn)\)算法中的另一个数组记录在状态中，直接推就可以了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,dp[1005][12][12][12],ans;
int main(){
scanf("%d%d",&n,&m);
dp[0][m+1][m+1][m+1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m+1;j++)
for(int k=1;k<=m+1;k++)
for(int l=1;l<=m+1;l++){
if(j>k||k>l||j>l)continue;
if(j==k&&k!=m+1)continue;
if(k==l&&k!=m+1)continue;
for(int c=1;c<=m;c++){
if(c<=j)dp[i][c][k][l]=(dp[i][c][k][l]+dp[i-1][j][k][l])%mod;
else if(c<=k)dp[i][j][c][l]=(dp[i][j][c][l]+dp[i-1][j][k][l])%mod;
else if(c<=l)dp[i][j][k][c]=(dp[i][j][k][c]+dp[i-1][j][k][l])%mod;
}
}
for(int j=1;j<=m;j++)
for(int k=j+1;k<=m;k++)
for(int l=k+1;l<=m;l++){
ans=(ans+dp[n][j][k][l])%mod;
}
printf("%d\n",ans);
return 0;
}
ARC134
2022-01-29
Solved:3/6
1646->1669
ABC234
2022-01-08
Solved:6/8
1636->1646
F(Medium-,1596)
给定字符串\(S\)，求由\(S\)中字符的子集组成的字符串数。
Solution：用\(dp[i][j]\)表示用前\(i\)个字母组成长为\(j\)的字符串的方案数。
条件相当于是对每种字符使用次数做出了限制。
状态转移方程为
\[dp[i][j]=\sum_{k=0}^{min(cnt_i,j)}\frac{dp[i-1][j-k]}{k!} \]直接推就好了。
G(Hard-,2306)
给定一个数列\(a\)，将其分成若干段，求所有分法各段极差的积之和。
Solution:用\(dp[i]\)表示以\(i\)结尾的所有分法各段极差的积之和。
状态转移方程为
\[dp[i]=\sum_{j=0}^{i-1}dp[j] \times (max(j+1...i)-min(j+1...i)) \]这样会T飞起来。考虑一下怎么优化它。
大致思路如下：先把乘积式拆成两块，以最大值为例。\(j+1...i\)的最大值就是\(max(max(j+1...i-1),i)\)，加上最大值数组的单调性，可以使用一个栈去维护。每一次更新最大值序列时，该段的\(dp\)值所乘的系数加上同一个值，这样就可以用前缀和优化。那么就做到了线性复杂度。
这题的确是挺难的，赛时没做出来。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,mod=998244353,INF=1<<30;
struct rec{int l,r,val;};
int n,a[N],dp[N],s[N],sum,tmp,maxn,minn=INF;
stack<rec> MX,MN;
int main(){
scanf("%d",&n);
for(int i=2;i<=n+1;i++)scanf("%d",a+i);
maxn=minn=a[2];
s[1]=dp[1]=1;
for(int i=2;i<=n+1;i++){
maxn=max(maxn,a[i]);minn=min(minn,a[i]);
tmp=i-1;
while(!MX.empty()&&MX.top().val<=a[i]){
rec tt=MX.top();tmp=tt.l;
sum=(sum+1ll*(s[tt.r]-s[tt.l-1]+mod)%mod*(a[i]-tt.val))%mod;
MX.pop();
}
MX.push(rec{tmp,i-1,a[i]});
tmp=i-1;
while(!MN.empty()&&MN.top().val>=a[i]){
rec tt=MN.top();tmp=tt.l;
sum=(sum+1ll*(s[tt.r]-s[tt.l-1]+mod)%mod*(tt.val-a[i]))%mod;
MN.pop();
}
MN.push(rec{tmp,i-1,a[i]});
dp[i]=sum;
s[i]=(s[i-1]+dp[i])%mod;
}
printf("%d\n",dp[n+1]);
return 0;
}
ABC233
2021-12-25
Solved:5/8
1677->1636
AGC056
2021-12-04
Solved:1/6
1589->1677
ABC230
2021-12-03
Solved:6/8
1406->1589
F(Medium+,2113)
给定数列\(a\)，可以将相邻两项求和合并，求若干次操作后可能的结果数。
Solution：相当于在前缀和数列中删数。而前缀和数列与原数列是一一对应的。
于是就变成了只用求一个数列的不同子序列数。
使用动态规划，令\(dp[i]\)表示以第\(i\)个数开头的不同子序列数。
倒序扫描，遇到一个数时看一下它下一次在哪里出现，只用对两个位置之间的数在前面加前缀。
实时维护后缀和即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,mod=998244353;
ll n,a,s[N],dp[N],b[N];
map<ll,vector<ll> > M;
map<ll,ll> pos;
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a);
s[i]=s[i-1]+a;
if(i!=n)M[s[i]].push_back(i);
}
for(int i=1;i<n;i++)pos[s[i]]++;
b[n-1]=dp[n-1]=1;pos[s[n-1]]--;
for(int i=n-2;i>=1;i--){
int x=--pos[s[i]],y=n-1,f=1;
if(x+1!=M[s[i]].size())y=M[s[i]][x+1],f=0;
dp[i]=(b[i+1]-b[y+1]+f+mod)%mod;
b[i]=(b[i+1]+dp[i])%mod;
}
printf("%lld\n",(b[1]+1)%mod);
return 0;
}
（麻了，好神仙啊，我怎么想出来的）
ABC228
2021-11-20
Solved:4/8
1379->1406
ABC226
2021-11-07
Solved:6/8
1198->1379
F(Medium,2086)
一个\(1...n\)的排列\((p_1,p_2,...,p_n)\)的分数定义为：
开始时，第\(i\)个人拿着\(i\)号球。每一次操作，第\(i\)个人把手中的球传给第\(p_i\)个人。则分数就是所有人重新拿到自己的球的操作次数。
求\(1...n\)所有排列的分数的\(k\)次幂之和。
Solution：首先要明确所谓的“分数”。
对于一个排列\((p_1,p_2,...,p_n)\)，构建一张图，从\(i\)向\(p_i\)连边。最后图中会形成若干个环，所有环长的最小公倍数就是这个排列的分数。这一点通过感性理解不难发现。
此时就可以考虑将\(n\)分拆为若干个数代表环长。注意到\(n \le 50\)，所以可以执行一个dfs，从大到小分拆即可。
然后就是一些细节，比如平均分配，具体不细讲了。
G(Hard-,2373)
五种物品五种人，物品重量分1,2,3,4,5，人的力量分1,2,3,4,5,当人的力量不小于物品重量和时，人可以搬起这些物品。给定各种人数和物品数，问能否搬完。
Solution：（搬运题解）
贪心。先让人5搬物5，再让人4,5搬物4，然后让人3,4,5搬物3。接下来能搬2的人都再搬一个2。最后把1处理掉就可以了。
贪心的正确性证明比较麻烦，可以感性理解一下：1不用考虑，最后能放哪儿放哪儿；3,4,5每个人至多搬1个。于是就应该这么做。
还是挺需要想法的。
ABC225
2021-10-30
900->1198
Solved:5/8
E(Easy+,1678)
选择\(n\)个7中的一些放入坐标系内，要求从原点能看到所有选择的7。求最大数目。
Solution：就是区间合并，考虑每个7占用的斜率区间即可。
F(Hard,2612)
在\(n\)个字符串中选择\(k\)个首尾相连，求字典序最小的方案。
Solution：（搬运题解）
将给出的字符串记为\(S_1...S_n\)，按照\(S_i+S_j<=S_j+S_i\)排序。
然后进行DP：用dp[i][j]表示从\(S_i...S_n\)中选出j个的最小字典序。则状态转移方程为：
\[dp[i][j]=min(dp[i+1][j],dp[i+1][j-1]+S_i) \]此处省略一系列正确性证明。
ABC219
2021-09-18
944->900
Solved:3/8
ABC216
2021-08-29
317->944
Solved:7/8
F(Medium-,1541)
给定数列\(\{a_n\}\),\(\{b_n\}\)，求集合$S \subseteq {1,2,...,n} \(的个数，使得\)\max_{i \in S}{a_i} \ge \sum_{i \in S}{b_i}$。
Solution:先将\(a\)排序，从小到大枚举\(\max_{i \in S}{a_i}\)。设这是排序后第\(k\)个。
假设已经确定了这个值，那么问题变为在\(b_1,b_2,...,b_k\)中选出若干个，其和不超过\(\max_{i \in S}{a_i}\)。这只需要记忆化搜索就可以了。
G(Medium-,1963)
构造01数列，使得在给定区间内至少有给定数目的1，且1的个数最少。
Solution:对于每一个区间，将需要安放的1尽可能向后放，用贪心算法容易知道这是正确的。
详言之，先将所有区间以右端点为第一关键字排序，用树状数组维护01序列，依次扫描每个区间，算出它还需要几个1，全部放在最末尾即可。
ABC215
2021-08-21
24->317
Solved:4/8
ABC204
2021-06-06
0->24
Solved:2/6
标签：AtCoder,Medium,比赛,记录,int,Solution,Solved,...,dp From： https://www.cnblogs.com/by-chance/p/17365031.html