2021杭电多校第三场
MorphLing
7月 30, 2021
03. Forgiving Matching
题意：给出长度为n的原串S和模式串T，串由’1’,’2’,…,’9’和通配符’*’构成，问对于$k\in[0,n-1]$，S的子串中满足失配位置小于等于k的子串个数
用FFT/NTT卷积计算字符匹配数。单独考虑每个字符，如字符’1’，将S和T串根据位置上是否为’1’转化为一个0/1串，若$s[i]=t[j]=1$，则开始位置在$i-j+1$的子串匹配数+1，用数组$cnt[i]$记录开始位置在$i$的子串的匹配数，有$cnt[i]=\sum\limits_{j=1}^ns[j]t[j-i+1]$。
将T串反置为T’，即$t[j-i+1]=t’[n-(j-i+1)+1]=t’[n-j+i]$，就有$cnt[i]=\sum\limits_{j=1}^ns[j]t’[n-j+i]$，发现这个东西就可以用卷积计算了。$cnt[i]$的结果在卷积之后$n+i$的位置。
还需要注意的是通配符的处理，可以用一个容斥计算通配符的影响，将每个位置的结果直接加上两个串同通配符的总数，然后减去两个通配符相匹配的情况，两个通配符相匹配的情况计算方法同上。
04. Game on Plane
签到，计算每种斜率的直线条数，然后从条数从小的开始轮着取即可
需要注意double精度问题，如果精度要求在$1e-9$左右可能需要使用long double，并且注意eps也要设置小于题目要求的最小精度单位
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define per(x,y,z) for (int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;
int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(int a, int b) { return 1ll * a * b % MOD; }
int bin(int x, int p) {
int res = 1;
for (int b = x; p; p >>= 1, b = mul(b, b))
if (p & 1) res = mul(res, b);
return res;
}
const int maxn=1111111;
const long double pi=3.1415926535897932384626433832795,eps=1e-18;
const long double special = -1e20;
int T, n;
long double slope(int x_0, int x_1, int y_0, int y_1) {
if (x_0 == x_1) return special;
return (long double)(y_1 - y_0) / (x_1 - x_0);
}
struct Line {
int x[2], y[2];
bool operator < (Line &L) const {
return slope(x[0], x[1], y[0], y[1]) < slope(L.x[0], L.x[1], L.y[0], L.y[1]);
}
}l[N];
bool equ(long double x, long double y) {
return fabs(x - y) <= eps;
}
long double slo[N];
int tot, cnt[N];
void solve() {
scanf("%d", &n);
tot = 0;
for (int i = 1; i <= n; i++) {
int x[2], y[2];
cnt[i] = 0;
scanf("%d %d %d %d", &l[i].x[0], &l[i].y[0], &l[i].x[1], &l[i].y[1]);
}
sort(l + 1, l + 1 + n);
for (int i = 1; i <= n; i++) {
slo[i] = slope(l[i].x[0], l[i].x[1], l[i].y[0], l[i].y[1]);
}
for (int i = 1; i <= n; i++) {
if (i == 1 || !equ(slo[i - 1], slo[i])) tot++;
cnt[tot]++;
}
sort(cnt + 1, cnt + 1 + tot);
int l = 1, ans = 0;
while(l <= tot) {
bool fi = 1;
for (int i = l; i <= tot; i++) {
cnt[i]--;
if (!cnt[i]) l++;
if (fi) fi = 0;
else ans++;
printf("%d\n", ans);
}
}
}
int main() {
scanf("%d", &T);
while(T--) {
solve();
}
return 0;
}
09. Rise in Price
题意：随机给一个矩阵，每个格子有$a,b$两个属性，求一条从$(1,1)$到$(n,m)$的路径，使得路径上$\sum a\times \sum b$最大
ZRC&LYF解：
首先感受到退火对这道题貌似很不稳定，貌似局部爬山的峰都很小，比较难找到正确的峰。考虑A*。估值随便按局部最优解估，更重要的是如何剪枝。LYF想出了可以预处理当前点到终点的a+b的和的最大值，剪枝时利用这个最大值求出一个从当前状态走到终点时的答案的上界，与当前答案比较。跑得飞快。
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define per(x,y,z) for (int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;
int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(int a, int b) { return 1ll * a * b % MOD; }
int bin(int x, int p) {
int res = 1;
for (int b = x; p; p >>= 1, b = mul(b, b))
if (p & 1) res = mul(res, b);
return res;
}
const int maxn=111;
const double pi=3.1415926535897932384626433832795,eps=1e-14;
int T,n,a[maxn][maxn],b[maxn][maxn];
LL maxa[maxn][maxn],maxb[maxn][maxn],maxapb[maxn][maxn];
LL nowa,nowb,ans;
LL value(int x,int y)
{
return (nowa+maxapb[x][y]/2)*(nowb+maxapb[x][y]/2);
}
bool cango(int x,int y)
{
if ((nowa+maxa[x][y])*(nowb+maxb[x][y])<=ans) return false;
if ((min(nowa,nowb)+maxapb[x][y])<max(nowa,nowb))
{if ((min(nowa,nowb)+maxapb[x][y])*max(nowa,nowb)<=ans) return false;}
else
{
LL temp=nowa+nowb+maxapb[x][y],sum;
if (temp&1) sum=(temp>>1)*((temp>>1)+1);
else sum=(temp>>1)*(temp>>1);
if (sum<=ans) return false;
}
return true;
}
void dfs(int x,int y)
{
nowa+=a[x][y];nowb+=b[x][y];
if (x==n&&y==n)
{
ans=max(ans,nowa*nowb);
goto ending;
}
if (x+1>n) {if (cango(x,y+1)) dfs(x,y+1);}
else if (y+1>n) {if (cango(x+1,y)) dfs(x+1,y);}
else if (value(x+1,y)>value(x,y+1))
{
if (cango(x+1,y)) dfs(x+1,y);
if (cango(x,y+1)) dfs(x,y+1);
}
else
{
if (cango(x,y+1)) dfs(x,y+1);
if (cango(x+1,y)) dfs(x+1,y);
}
ending:;
nowa-=a[x][y];nowb-=b[x][y];
return;
}
int main()
{
cin>>T;
while (T--)
{
ans=0;
memset(maxa,0,sizeof(maxa));
memset(maxb,0,sizeof(maxb));
memset(maxapb,0,sizeof(maxapb));
cin>>n;
rep(i,1,n) rep(j,1,n) cin>>a[i][j];
rep(i,1,n) rep(j,1,n) cin>>b[i][j];
per(i,n,1) per(j,n,1)
{
maxa[i][j]=max(maxa[i+1][j],maxa[i][j+1])+a[i][j];
maxb[i][j]=max(maxb[i+1][j],maxb[i][j+1])+b[i][j];
maxapb[i][j]=max(maxapb[i+1][j],maxapb[i][j+1])+a[i][j]+b[i][j];
}
dfs(1,1);
cout<<ans<<endl;
}
return 0;
}
10. Road Discount
题意：给出一张无向图，每条边有两种权值（打折前和打折后），问恰好选择k条边打折时，最小生成树的最小权值为多少
wqs二分的经典题。令$f(x)$为k=x时对应的答案，通过（各种方法）发现，$(x,f(x))$是一个凸函数，也就是说斜率具有单调性，且在$f(x)$无法简单求出的情况下，$f(x)-kx$的最优解（最小/最大值）却可以用某些简单（复杂度低）的方式快速求得，那么就符合wqs二分的条件。
对于这道题，首先可以发现解在几何上满足凸函数性质，并且当我们将所有折扣边减去k后跑一次最小生成树，可以神奇的发现这个最小生成树的权值就是$f(x)-kx$的最小值。接下来只要枚举斜率k，找到斜率为k时最少和最多用多少条折扣边，再用把得到最小生成树的权值加上kx，可以反推出$f(x)$为多少
具体先不展开说了，贴一个博客:关于WQS二分算法以及其一个细节证明
这题还有两个trick，一个是先单独对折扣边和非折扣边跑两次最小生成树，然后接下来只需要考虑这两颗生成树中的这些边，将边集大小降为$O(n)$级别。（考虑kruskal算法过程，单独对某一类边跑mst时，不在最小生成树中的边在访问时一定已联通，那么两类边一起跑mst时这些边对应的两个点一定也已经联通了），二是由于边权范围是$[1,1000]$，不需要$O(n\log n)$对边排序，而是像桶一样开1000个数组，分别记录权值不同的边即可。
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 1e3 + 5;
int T, n, m;
struct Edge {
int f, t, v, type;
};
vector<Edge> W[N], B[N];
vector<Edge> E[N][2];
int res, ans[N];
int fa[N];
int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }
void init() {
for (int i = 1; i <= 1000; i++) {
W[i].clear(); B[i].clear();
E[i][0].clear();
E[i][1].clear();
}
}
void getEdgeW() {
for (int i = 1; i <= n; i++) fa[i] = i;
int cnt = 0;
for (int i = 1; i <= 1000; i++) {
for (auto x : W[i]) {
int u = getfa(x.f), v = getfa(x.t);
if (u == v) continue;
fa[u] = v;
E[x.v][0].push_back({x.f, x.t, x.v, 0});
cnt++;
if (cnt == n - 1) break;
}
if (cnt == n - 1) break;
}
}
void getEdgeB() {
for (int i = 1; i <= n; i++) fa[i] = i;
int cnt = 0;
for (int i = 1; i <= 1000; i++) {
for (auto x : B[i]) {
int u = getfa(x.f), v = getfa(x.t);
if (u == v) continue;
fa[u] = v;
E[x.v][1].push_back({x.f, x.t, x.v, 1});
cnt++;
if (cnt == n - 1) break;
}
if (cnt == n - 1) break;
}
}
int getAns1(int c) {
for (int i = 1; i <= n; i++) fa[i] = i;
int cnt = 0;
int edgenum = 0;
for (int i = -2000; i <= 2000; i++) {
if (i >= 1 && i <= 1000) {
for (auto x : E[i][0]) {
if (edgenum == n - 1) break;
int u = getfa(x.f), v = getfa(x.t);
if (u == v) continue;
fa[u] = v;
res += x.v + (x.type == 1 ? -c : 0);
cnt += x.type;
edgenum++;
}
}
if (i + c >= 1 && i + c <= 1000) {
for (auto x : E[i + c][1]) {
if (edgenum == n - 1) break;
int u = getfa(x.f), v = getfa(x.t);
if (u == v) continue;
fa[u] = v;
res += x.v - c;
cnt += x.type;
edgenum++;
}
}
if (edgenum == n - 1) break;
}
return cnt;
}
int getAns2(int c) {
for (int i = 1; i <= n; i++) fa[i] = i;
int cnt = 0;
int edgenum = 0;
for (int i = -2000; i <= 2000; i++) {
if (i + c >= 1 && i + c <= 1000) {
for (auto x : E[i + c][1]) {
if (edgenum == n - 1) break;
int u = getfa(x.f), v = getfa(x.t);
if (u == v) continue;
fa[u] = v;
cnt += x.type;
edgenum++;
}
}
if (i >= 1 && i <= 1000) {
for (auto x : E[i][0]) {
if (edgenum == n - 1) break;
int u = getfa(x.f), v = getfa(x.t);
if (u == v) continue;
fa[u] = v;
cnt += x.type;
edgenum++;
}
}
if (edgenum == n - 1) break;
}
return cnt;
}
void solve() {
scanf("%d %d", &n, &m);
init();
for (int i = 1; i <= m; i++) {
int u, v, w1, w2; scanf("%d %d %d %d", &u, &v, &w1, &w2);
W[w1].push_back({u, v, w1});
B[w2].push_back({u, v, w2});
}
getEdgeW(); getEdgeB();
memset(ans, 0x3f, sizeof(ans));
for (int c = -1000; c <= 1000; c++) {
res = 0;
int L = getAns1(c);
int R = getAns2(c);
for (int j = L; j <= R; j++) ans[j] = res + c * j;
}
for (int i = 0; i <= n - 1; i++) printf("%d\n", ans[i]);
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}