测试成果
100+100+50+10=260
还行吧（虽然 T2 做法很迷惑）
A 惊鸿 (grace)
题面大意
给定一个 \(n\) 行 \(m\) 列的仅包含小写字母的矩阵 \(A\)。求从 \((1, 1)\) 到 \((n, m)\) 只向下或向右走，且路径上的所有字符按照顺序排列可以构成一个回文串的路径条数。答案对 \(993244853\) 取模。 \(1\le n,m \le 500\)
题解
直接 dp 就完了呀，我们可以从两端开始匹配字母
记 \(f_{i,j,t}\) 表示当前走了 \(t\) 步，匹配到的最后一个点的行数分别为 \(i,j\)
注意到列数可以用 \(t,i,j\) 表示
然后转移就很容易啦
具体看代码 空间有点紧开了个滚动数组（
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 505, P = 993244853;
int n,m;
char s[N][N];
int f[N][N][3]; //滚动数组
int main()
{
scanf("%d%d",&n,&m); int sts=((n+m-1)>>1)-1; //前后需要走的步数
for(int i=1; i<=n; i++) scanf("%s",s[i]+1);
f[1][n][0]=(s[1][1]==s[n][m]);
int cr=1;
for(int t=1; t<=sts; t++,cr^=1)
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) f[i][j][cr]=0; //开滚动记得清空
for(int i=1; i<=min(n,1+t); i++)
for(int j=max(i,n-t); j<=n; j++)
{
int yi=t-i+2; int yj=n+m-t-j;
if(yi>yj or s[i][yi]!=s[j][yj]) continue;
ll res=0;
if(i>1 and j<n) res+=f[i-1][j+1][cr^1];
if(yi>1 and j<n) res+=f[i][j+1][cr^1];
if(i>1 and yj<m) res+=f[i-1][j][cr^1];
if(yi>1 and yj<m) res+=f[i][j][cr^1];
f[i][j][cr]=res%P;
}
}
cr^=1; //注意最后一次 dp 的时候 cr 多异或了一次 1 （因为这个调了一会
if((n+m-1)&1) // 处理答案要分奇偶
{
int ans=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
int yi=sts-i+2,yj=n+m-sts-j;
if(j-i==1 and yj-yi==1) ans=(ans+((ll)f[i][j][cr]<<1))%P;
//这边方案数记得乘 2
else if(j-i==2 or yj-yi==2) ans=(ans+f[i][j][cr])%P;
}
printf("%d\n",ans);
}
else
{
int ans=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
int yi=sts-i+2,yj=n+m-sts-j;
if((j-i)+(yj-yi)==1) ans=(ans+f[i][j][cr])%P;
}
printf("%d\n",ans);
}
return 0;
}
B 长夜 (story)
题面大意
给定一张 \(n\) 个点的有向图，每个点都有且仅有一条出边，初始时 \(i\) 号点的出边连向 \(a_i\) 号点。你每次可以选择一个点 \(i\)，改变它的出边所连向的点，并花费 \(c_i\) 的代价。求使得这张图强连通的最小总代价。对于所有测试数据，保证 \(2 \le n \le 10 ^ 5\)，\(1 \le a_i \le n\)，\(a_i \ne i\)，\(1 \le c_i \le 10 ^ 9\)。
题解
我这题做法很玄学，不知道怎么过去的
首先你注意到每个点有且仅有一条出边，那就是一个内向基环树森林.
因为最终的图还是一棵基环树，所以要使得图强联通，就要让他变成一个环
我们先把每一个基环树做成一个环，再合并起来.
如果一个基环树内已经有过改变，合并不需要代价，因为你可以把这条边直接改到环上
所以你只需要考虑一下有几棵基环树开始就是环.
然后对于每一棵基环树内部，考虑它的每一个节点，如果入度大于 1，我们就要删去这些边，只保留一条边.
贪心地选，只要让这条保留的边是最大的就好了.
然后要注意一个特判，如果环上的边没有删去，那就不可能还是一个环.
所以你加入亿点点特判就好了
具体见代码
好像好写的做法就是每次枚举删的边，然后这个时候选取每个点入度的最大值，这个用增量法优化一下就好了（
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5, inf = 1e9+114514;
int n,a[N],c[N];
int col[N],ncol;
int p[N],np,deg[N];
int in_r[N],rp[N],nr;
int mnir;
ll res;
vector<int> h[N];
void dfs_col(int u, int c)
{
p[++np]=u; col[u]=c;
if(col[a[u]]==0) dfs_col(a[u],c);
for(int v:h[u]) if(col[v]==0) dfs_col(v,c);
}
void tpst()
{
queue<int> q;
for(int i=1; i<=np; i++) deg[p[i]]=h[p[i]].size();
for(int i=1; i<=np; i++) if(deg[p[i]]==0) q.push(p[i]);
while(!q.empty())
{
int u=q.front(); q.pop();
deg[a[u]]--; if(deg[a[u]]==0) q.push(a[u]);
}
for(int i=1; i<=np; i++) if(deg[p[i]]>0) rp[++nr]=p[i],in_r[p[i]]=1;
}
void work()
{
int flag=0; ll sum=0,d=mnir; // d 表示如果一定要删环上的一条边，最小多少，初始化显然是环上最小边
for(int i=1; i<=np; i++)
if(h[p[i]].size()>1)
{
int mxv=0; ll res1=0,res2=0; // mxv表示最大的边的起点
for(int v:h[p[i]]) if(c[v]>c[mxv] or (c[v]==c[mxv] and !in_r[v] and in_r[mxv])) mxv=v; //找 mxv，注意要优先选非环上边
for(int v:h[p[i]]) if(v!=mxv) { res1+=c[v]; if(in_r[v]) flag=1; } //res1 表示直接贪心做, flag 表示当前有没有删过环
sum+=res1; mxv=0; int vld=0; // vld 表示求 d 的时候有没有删到环，如果没有删到就说明这时候做的是树边，是假的不能更新 d
for(int v:h[p[i]]) if(!in_r[v] and c[v]>c[mxv]) mxv=v; //求 d 要找一遍环，枚举是哪个点删环，要保证 mxv 不在环上
for(int v:h[p[i]]) if(v!=mxv) { res2+=c[v]; if(in_r[v]) vld=1; }
if(vld) d=min(d,res2-res1);
}
if(flag) res+=sum;
else res+=sum+d;
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d%d",&a[i],&c[i]),h[a[i]].push_back(i); // 反边
int flag=0;
for(int i=1; i<=n; i++)
if(!col[i])
{
np=nr=0;
dfs_col(i,++ncol); //找连通块
tpst(); //拓扑找环
mnir=inf; for(int i=1; i<=nr; i++) mnir=min(mnir,c[rp[i]]); // 找环里最小边
if(nr==np) res+=mnir,flag=1; //如果本来就是环，加入答案
else work();
}
if(ncol==1 and flag) res-=mnir; //如果整个图只有一个环，要特判
printf("%lld\n",res);
return 0;
}
总之很玄学
C 苍穹 (universe)
题面大意
给定一个长度为 \(n\) 的正整数序列，其中有些位置为空，另一些位置已经填好了数字。
你需要删去序列中的一个位置（可以是空的位置，也可以不是），然后在剩余的位置中填入数字，满足：所有数字均为 \([1, n]\) 之间的正整数，且两两不同。保证原序列已经填入的数字满足该条件。
求填入数字后字典序最小的序列。 \(n\le 2\times 10^5\)
题解
怎么又是这种一堆细节的分讨题
总之我还没补完
\(O(n^2)\)暴力
当然是枚举删去的点然后直接贪心填，找字典序最小的，
这甚至有 \(50\sim 55\) 分
正解
首先考虑如果删的数是 \(0\)，一定是对原序列没有影响的，直接贪心把零填上，遇到第一个 \(a_i>a_{i+1}\) 的时候删去 \(i\) 这个位置一定是最优的
然后如果删掉序列里非 \(0\) 的数，可以考虑从头到尾贪心.
如果第一个 \(0\) 前面出现了 \(a_i>a_{i+1}\) ，删去 \(i\) 一定是最优的，删去别的数一定更劣
如果没有，说明 \(0\) 前面是一个单增序列，这时候我们有三种做法
- 删去单增序列最后一个
- 直接贪心填 \(0\)
- 在序列后面删除最小的元素，再把它填到 \(0\) 上
考虑什么时候取这三种情况
记直接贪心填的数为 \(cur\) ，单增序列末尾为 \(peak\) ，\(0\) 后面最小的元素为 \(min\)
那么当 \(cur<peak\) 显然直接 删去单增序列最后一个
当 \(cur>peak\) 的时候，如果 \(min<cur\) ，在序列后面删除最小的元素，再把它填到 \(0\) 上
否则如果 \(min>cur\) 直接贪心填 \(0\)，然后继续往下找下一个 \(0\) 贪心
序列后面最小的元素可以用 set 维护
具体见代码
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+5;
int T,n,a[N],vt[N<<1],b[N],res[N];
void init()
{
scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++) res[i]=n;
}
int tmp[N];
void D(int x) // 贪心做
{
int tp=0,cur=1;
while(vt[cur] and cur!=a[x]) cur++;
for(int i=1; i<=n; i++)
{
if(i==x) continue;
if(a[i]) tmp[++tp]=a[i];
else { tmp[++tp]=cur++; while(vt[cur] and cur!=a[x]) cur++; }
}
int flag=0;
for(int i=1; i<n; i++)
{
if(tmp[i]>res[i]) return ;
else if(tmp[i]<res[i]) { flag=1; break; }
}
if(flag) for(int i=1; i<n; i++) res[i]=tmp[i];
}
void work() // 分讨
{
for(int i=1; i<=n; i++) vt[i]=0;
for(int i=1; i<=n; i++) vt[a[i]]=1;
int cur=1; while(vt[cur]) cur++;
int flag=0;
for(int i=1; i<=n; i++)
{
if(a[i]==0)
{
b[i]=cur++; while(vt[cur]) cur++;
}
else b[i]=a[i];
if(i>1 and b[i]<b[i-1]) { flag=1; D(i-1); break; }
}
if(!flag) D(n);
map<int,int> mp;
for(int i=1; i<=n; i++) if(a[i]) mp.insert({a[i],i});
int L=1;
cur=1; while(vt[cur]) cur++;
for(int i=1; i<=n; i++)
{
if(a[i]==0)
{
for(int j=L+1; j<i; j++) if(a[j]<a[j-1]) { D(j-1); return ; }
int peak=((L==i)?0:a[i-1]); auto mn=*mp.begin();
if(cur<peak) { D(i-1); return; }
else if(mn.first<cur) { D(mn.second); return; }
else { cur++; while(vt[cur]) cur++; }
L=i+1;
}
else mp.erase(a[i]);
}
}
int main()
{
scanf("%d",&T);
while(T--) { init(); work(); for(int i=1; i<n; i++) printf("%d ",res[i]); puts(""); }
return 0;
}
D 浮光 (history)
题面大意
在一个有障碍点的 \(n\) 行 \(m\) 列的网格图中，用 \((x,y)\) 来表示第 \(x\) 行第 \(y\) 列的格子。
如果该网格图中的回路满足：不经过任何一个障碍点且回路不自交，则我们称该回路为合法的简单回路。
有 \(q\) 次询问，每次询问有多少条合法的简单回路经过了 \((x,y)\) 与 \((x+1,y)\) 之间的边。答案对 \(10 ^ 9 + 7\) 取模。
对于所有测试数据，保证 \(1 \le n \le 1000\)，\(1 \le m \le 6\)，\(0 \le k \le 100\)，\(1 \le q \le 10 ^ 4\)。
题解
插头 dp
红日学长说是板子题，没见过也应该会
但我不会
等学了插头 dp 再来补吧
标签：11,le,15,int,题解,mxv,序列,删去,贪心 From： https://www.cnblogs.com/copper-carbonate/p/16896602.html