2020-07-15发表2021-08-28更新ICPC/CCPC / Contests / 其他31 分钟读完 (大约4645个字)

2020牛客暑期多校训练营（第二场）

收获

一定要注意 corner cases
$40000$ 的数据量考虑一下 bitset
平面图最小割 $\implies$ 对偶图最短路
区间 $[L,R]$ 及其移动可以尝试看成点 $(L,R)$ 及其移动

A All with Pairs

把所有后缀的 $\text{hash}$ 值都存下来，枚举每一个字符串的前缀，设 $cnt_i$ 表示与 $s[1…i]$ 相同的后缀数量。但是我们发现同一个串可能会给不同的 $cnt_i$ 有贡献，例如给出两个 $aba$，那么考虑其中一个 $aba$ 时，另一个 $aba$ 的后缀 $a$ 会给 $cnt_1$ 贡献，后缀 $aba$ 会给 $cnt_3$ 贡献，我们只想要保留对 $i$ 最大的 $cnt_i$ 的贡献。假设一个字符串对 $cnt_i,cnt_j$ 均有贡献，其中 $j<i$，这意味着长度为 $j$ 的后缀是长度为 $i$ 的后缀的公共前后缀。联想到 $\textbf{KMP}$ 算法的 $\text{next}$ 数组，只需要 $cnt_{\text{next[i]}}-=cnt_i$ 即可消除重复贡献的情况。

A.cpp >folded

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
#define pb(x) emplace_back(x)

const int LEN = 1000005;

ULL base = 233, power[LEN] = {1};
void Hash(vector<ULL> &h, char s[]){
    int len = (int)strlen(s+1);
    h[1] = s[1];
    for(int i = 2; i <= len; i++)
        h[i] = h[i-1] * base + s[i];
}
ULL getSubstring(vector<ULL> &h, int l, int r){ // get hash value of s[l...r]
    return h[r] - h[l-1] * power[r - l + 1];
}

void getFail(vector<int> &fail, char t[], int lent){
    int i = 1, j = 0;
    fail[1] = 0;
    while(i <= lent){
        if(!j || t[i] == t[j])  fail[++i] = ++j;
        else    j = fail[j];
    }
}

const LL MOD = 998244353;
const int N = 100005;

int n, len[N], cnt[LEN];
char s[LEN];
LL ans;
vector<ULL> H[N];
vector<int> fail[N];
map<ULL, int> m;

int main(){
	for(int i = 1; i <= 1000000; i++)
		power[i] = power[i-1] * base;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%s", s+1); len[i] = strlen(s+1);
		H[i].resize(len[i]+5); Hash(H[i], s);
		for(int j = 1; j <= len[i]; j++)
			m[getSubstring(H[i], j, len[i])]++;
		fail[i].resize(len[i]+5); getFail(fail[i], s, len[i]);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= len[i]; j++){
			cnt[j] = m[getSubstring(H[i], 1, j)];
			cnt[fail[i][j+1]-1] -= cnt[j];
		}
		for(int j = 1; j <= len[i]; j++){
			(ans += 1ll * cnt[j] * j % MOD * j % MOD) %= MOD;
			cnt[j] = 0;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

B Boundary

比赛时因为没考虑 corner cases 而贡献了 7 发罚时，吸取了惨烈的教训。

枚举点，与原点构成一条弦，根据圆周角定理，和这两个点在同一个圆上的所有点的圆周点相同或互补，于是我们可以把其他点的圆周角算出来（右侧的角用 $\pi$ 减掉，相当于把点全放到左侧去），统计相同角的个数即可。

一定注意 $n=1$ 以及 $n=2$ 但是共线等 corner cases！

复杂度：$O(n^2\lg n)$

B.cpp >folded

#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-14;
const double PI = 4 * atan2(1, 1);
const int N = 2005;
inline int sgn(double x){
    if(fabs(x) < eps)	return 0;
    else if(x > 0)	return 1;
    else	return -1;
}
inline int cmp(double x, double y){ return sgn(x-y); }

//------------------------------------ Vector & Point ------------------------------------//
struct Vector{
    double x, y;
    Vector() {}
    Vector(double x, double y):x(x), y(y){}
    void read(){ scanf("%lf%lf", &x, &y); }
};
typedef Vector Point;
Vector operator + (Vector A, Vector B){ return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B){ return Vector(A.x - B.x, A.y - B.y); }
bool operator < (const Vector &A, const Vector &B){
    return cmp(A.x, B.x) == 0 ? cmp(A.y, B.y) < 0 : cmp(A.x, B.x) < 0;
}
// dot product
double operator * (Vector A, Vector B){ return A.x * B.x + A.y * B.y; }
// cross product
double operator ^ (Vector A, Vector B){ return A.x * B.y - A.y * B.x; }
// angle between two vectors, in [0,PI]
double Angle(Vector A, Vector B){ return atan2(fabs(A ^ B), A * B); }

//------------------------------------------------------------------------------//



int n, ans = 1;
Point p[N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)	p[i].read();
    for(int i = 1; i <= n; i++){
    	vector<double> a;
    	for(int j = 1; j <= n; j++){
    		if(j == i)	continue;
    		if(sgn(p[i] ^ p[j]) == 0)	continue;
    		Vector v1 = p[i] - p[j], v2 = Point(0, 0) - p[j];
    		double ang = Angle(v1, v2);
    		if(sgn(p[i] ^ p[j]) < 0)	ang = PI - ang;
    		a.push_back(ang);
    	}
    	sort(a.begin(), a.end());
    	int sz = a.size();
    	int res = 0;
    	for(int k = 0; k < sz; k++){
    		int j = k;
    		while(j+1 < sz && cmp(a[j+1], a[k]) == 0)	j++;
    		res = max(res, j - k + 1);
    		k = j;
    	}
    	ans = max(ans, res + 1);
    }
    printf("%d\n", ans);
    return 0;
}

C Cover the Tree

链的形式显然是从一个叶子到另一个叶子，所以答案至少是 $\left\lceil\frac{s}{2}\right\rceil$.

解法看上去很神奇：选取一个非叶子节点作为根进行 $dfs$，得到叶子节点的 $dfs$ 序，连接第 $i$ 和第 $\frac{s}{2}+i$ 个叶子节点即可（$i\leq\frac{s}{2}$）。

这是可以证明的：假设这条边“覆盖”着 $[l,r]$ 的叶子，如果 $l>\frac{s}{2}$，那么它一定被 $l-\frac{s}{2}\to l$ 的链覆盖；如果 $r\leq\frac{s}{2}$，那么它一定被 $r\to r+\frac{s}{2}$ 覆盖；否则，它一定被 $1\to1+\frac{s}{2}$ 或者 $\frac{s}{2}\to s$ 覆盖。

C.cpp >folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, deg[N], rt;
vi edge[N];

vi leaf;
void dfs(int x, int f){
	if(deg[x] == 1)	leaf.pb(x);
	for(auto &to : edge[x]){
		if(to == f)	continue;
		dfs(to, x);
	}
}

int main(){
	read(n);
	for(int i = 1; i < n; i++){
		int u, v; read(u, v);
		edge[u].pb(v), edge[v].pb(u);
		deg[u]++, deg[v]++;
	}
	if(n == 1)	return puts("0"), 0;
	if(n == 2)	return puts("1"), puts("1 2"), 0;
	for(rt = 1; rt <= n; rt++) if(deg[rt] != 1) break;
	dfs(rt, 0);
	int sz = leaf.size();
	printf("%d\n", (sz + 1) / 2);
	for(int i = 0; i < sz / 2; i++)
		printf("%d %d\n", leaf[i], leaf[i + sz / 2]);
	if(sz & 1)	printf("%d %d\n", leaf[sz-1], leaf[0]);
	return 0;
}

D Duration

签到题，把两个时间换算成秒，相减取绝对值即可。

D.cpp >folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int h, m, s;

int main(){
	scanf("%d:%d:%d", &h, &m, &s);
	int a = h * 3600 + m * 60 + s;
	scanf("%d:%d:%d", &h, &m, &s);
	int b = h * 3600 + m * 60 + s;
	printf("%d", abs(a - b));
	return 0;
}

F Fake Maxpooling

注意 $k$ 是固定的，一个 $k\times k$ 子矩阵在平移的时候可以用单调队列搞定。预处理的时候也用单调队列。

另外，直接算 $A$ 数组是 $O(nm\lg n)$ 的，实测用递归 $\gcd$ 会 $\text{TLE}$，循环 $\gcd$ 可过。不过用下面这种方式计算 $A$ 数组是 $O(nm)$ 的（出题人的方式）：

>folded

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(!GCD[i][j])
            for(int k = 1; k * i <= n && k * j <= m; k++)
                GCD[k * i][k * j] = k,  A[k * i][k * j] = i * j * k;

其实就是记忆化。

复杂度：$O(nm)$

F.cpp >folded

#include<bits/stdc++.h>
 
using namespace std;
 
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
 
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
 
int gcd(int a, int b){
    int r = a % b;
    while(r)    a = b, b = r, r = a % b;
    return b;
}
 
const int N = 5005;
 
int n, m, k, g[N][N], p[N][N];
queue<pii> q;
 
void _push(int val, int pos){
    while(!q.empty() && q.front().first <= val)  q.pop();
    q.push(mp(val, pos));
}
 
int main(){
    read(n, m, k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            g[i][j] = i / gcd(i, j) * j;
    for(int j = 1; j <= m; j++){
        while(!q.empty())   q.pop();
        for(int i = 1; i <= k; i++)  _push(g[i][j], i);
        p[1][j] = q.front().first;
        for(int i = 2; i <= n - k + 1; i++){
            _push(g[i+k-1][j], i+k-1);
            while(q.front().second < i)  q.pop();
            p[i][j] = q.front().first;
        }
    }
    LL ans = 0;
    for(int i = 1; i <= n - k + 1; i++){
        while(!q.empty())   q.pop();
        for(int j = 1; j <= k; j++)  _push(p[i][j], j);
        ans += q.front().first;
        for(int j = 2; j <= m - k + 1; j++){
            _push(p[i][j+k-1], j+k-1);
            while(q.front().second < j)  q.pop();
            ans += q.front().first;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

G Greater and Greater

$40000$ 的数据量要联想到 bitset。

首先对每个 $A_i$ 求一个长度为 $m$ 的 bitset $S_i$，其中 $S_i[j]$ 表示 $A_i$ 能否干掉 $B_j$。例如：样例中 $A=\{1,4,2,8,5,7\},\,B=\{2,3,3\}$，以 $A_3=2$ 为例，它的 $S_3=100$，因为 $2$ 可以干掉 $B_1$，但不能干掉 $B_2,B_3$。

为了计算所有的 $S_i$，注意到，如果把 $A$ 数组排序，那么后一个数字的 bitset 是在前一个数字的 bitset 的基础上，把某些 $0$ 改成 $1$ 得到的，因此，$S_i$ 最多有 $m$ 种。我在代码中把具有相同的 bitset 的 $A_i$ 都映射到同一个 bitset 上，这样保证时间复杂度和空间复杂度都是 $O\left(\frac{m^2}{32}\right)$. （否则会爆空间）

随后设 $n$ 个长度为 $m$ 的 bitset $cur_i$，其中 $cur_i[j]$ 表示从 $A_i$ 开始的连续 $m-j+1$ 个数能否干掉 $B$ 的后 $m-j+1$ 个数（为什么是 $m-j+1$ 这个奇怪的数字，其实是为了后面的式子简便）。仍以样例为例：$cur_2=001$，因为 $\{4,2,8\}$ 不能干掉 $\{2,3,3\}$，$\{4,2\}$ 不能干掉 $\{3,3\}$，$\{4\}$ 可以干掉 $\{3\}$；同理，$cur_3=100$ 等等。

为了计算 $cur_i$，我们寻找递推式。以 $cur_2$ 为例，$cur_2[1]$ 可以看作是比较 $\{2,8\}$ 和 $\{3,3\}$ 后再比较 $\{4\}$ 和 $\{2\}$，也即是 $cur_2[1]=cur_3[2]\text{ & }S_2[1]$；$cur_2[2]$ 可以看作是比较 $\{2\}$ 和 $\{3\}$ 后比较 $\{4\}$ 和 $\{2\}$，也即是 $cur_2[2]=cur_3[3]\text{ & }S_2[2]$；$cur_2[3]$ 可以看作是比较 $\{4\}$ 和 $\{2\}$，为了统一递推式，不妨设 $cur_3[4]=1$，那么就有 $cur_2[3]=cur_3[4]\text{ & }S_2[3]$。综上，我们可以归纳出 $cur_i$ 的递推式：$cur_i=((cur_{i+1}\text{>>}1)\text{ & }S_i)\text{ | }I_{m+1}$，其中 $I_{m+1}$ 表示仅第 $m+1$ 位置 $1$ 的 bitset。

答案就是统计有多少个 $cur_i$ 的 $cur_i[1]=1$。

G.cpp >folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 150005;

int n, m, ans, func[N], id;
struct Node{
	int val, pos;
}a[N];
struct Nodeb{
	int val, pos;
	bool operator < (const Nodeb &A) const{
		return val == A.val ? pos < A.pos : val < A.val;
	}
}b[N];
bitset<40002> s[40002], cur;

int main(){
	read(n, m);
	for(int i = 1; i <= n; i++)	read(a[i].val), a[i].pos = i;
	for(int i = 1; i <= m; i++)	read(b[i].val), b[i].pos = i;
	sort(a+1, a+n+1, [&](const Node &A, const Node &B){ return A.val < B.val; });
	sort(b+1, b+m+1, [&](const Nodeb &A, const Nodeb &B){ return A.val < B.val; });
	for(int i = 1, j = 1; i <= n; i++){
		int jj = upper_bound(b+1, b+m+1, (Nodeb){a[i].val, 100000000}) - b;
		if(j == jj){
			func[a[i].pos] = id;
			continue;
		}
		id++; s[id] = s[id-1]; func[a[i].pos] = id;
		for(int k = j; k < jj; k++)	s[id].set(b[k].pos);
		j = jj;
	}
	sort(a+1, a+n+1, [&](const Node &A, const Node &B){ return A.pos < B.pos; });
	cur.set(m+1);
	for(int i = n; i >= 1; i--){
		cur = ((cur >> 1) & s[func[i]]);
		cur.set(m+1);
		ans += cur.test(1);
	}
	printf("%d\n", ans);
	return 0;
}

H Happy Triangle

对于一个询问，分类讨论：

若 $x$ 是最大边，则寻找 $x$ 的前驱 $p$（非严格）和它的前驱的前驱 $pp$（非严格），若 $p+pp>x$，那么可形成三角形；
若 $x$ 是中间边，则寻找 $x$ 的前驱 $p$ （非严格）和它的后继 $q$（非严格），若 $p+x>q$，那么可形成三角形；
若 $x$ 是最小边，则为了形成三角形，我们需要找到 $b>a>x$ 且 $b-a<x$ 的一对数 $a,b$，即需要在大于 $x$ 的数值中找到相邻的最小差值 $d$，如果 $d<x$，那么可以形成三角形。

为了完成上述操作，我是离线之后上值域线段树，值域线段树叶子节点内存储该数与其非严格前驱的差值，非叶子节点维护子树的最小差值。

值得注意的一点是，这里的差值是非严格前驱，所以在添加或删除一个数之后，要数一数还剩多少个数，然后分类讨论修改这个差值。

附：值域线段树找严格前驱和后继的代码：

>folded

LL getPre(int id, int pos){
	if(tr[id].size == 0)	return -INF;
	if(tr[id].l == tr[id].r)	return tr[id].l == pos ? -INF : tr[id].l;
	if(pos <= mid){ LL t = getPre(lid, pos); return t == pos ? -INF : t; }
	else{
		LL t = getPre(rid, pos);
		if(t == -INF)	t = getPre(lid, pos);
		return t == pos ? -INF : t;
	}
}
LL getSuc(int id, int pos){
	if(tr[id].size == 0)	return INF;
	if(tr[id].l == tr[id].r)	return tr[id].l == pos ? INF : tr[id].l;
	if(pos > mid){ LL t = getSuc(rid, pos); return t == pos ? INF : t; }
	else{
		LL t = getSuc(lid, pos);
		if(t == INF)	t = getSuc(rid, pos);
		return t == pos ? INF : t;
	}
}

H.cpp >folded

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL INF = 1e14;
const int N = 200005;

struct segTree{
	int l, r, cnt, size;
	LL mndiff;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
#define len(id) (tr[id].r - tr[id].l + 1)
inline void pushup(int id){
	tr[id].mndiff = min(tr[lid].mndiff, tr[rid].mndiff);
	tr[id].size = tr[lid].size + tr[rid].size;
}
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].mndiff = INF;
	tr[id].cnt = tr[id].size = 0;
	if(tr[id].l == tr[id].r)	return;
	build(lid, l, mid), build(rid, mid+1, r);
	pushup(id);
}
int add_del(int id, int pos, int val){
	// val == 1(add) or -1(delete) or 0(query for cnt)
	// return how many elements left in pos
	if(tr[id].l == tr[id].r){
		tr[id].cnt += val;
		tr[id].size += val;
		return tr[id].cnt;
	}
	if(pos <= mid)	return add_del(lid, pos, val);
	else	return add_del(rid, pos, val);
	pushup(id);
}
void modify(int id, int pos, LL val){
	if(tr[id].l == tr[id].r){
		tr[id].mndiff = val;
		return;
	}
	if(pos <= mid)	modify(lid, pos, val);
	else	modify(rid, pos, val);
	pushup(id);
}
LL getPre(int id, int pos){
	if(tr[id].size == 0)	return -INF;
	if(tr[id].l == tr[id].r)	return tr[id].l == pos ? -INF : tr[id].l;
	if(pos <= mid){ LL t = getPre(lid, pos); return t == pos ? -INF : t; }
	else{
		LL t = getPre(rid, pos);
		if(t == -INF)	t = getPre(lid, pos);
		return t == pos ? -INF : t;
	}
}
LL getSuc(int id, int pos){
	if(tr[id].size == 0)	return INF;
	if(tr[id].l == tr[id].r)	return tr[id].l == pos ? INF : tr[id].l;
	if(pos > mid){ LL t = getSuc(rid, pos); return t == pos ? INF : t; }
	else{
		LL t = getSuc(lid, pos);
		if(t == INF)	t = getSuc(rid, pos);
		return t == pos ? INF : t;
	}
}
LL query(int id, int l, int r){
	if(tr[id].l == l && tr[id].r == r)	return tr[id].mndiff;
	if(r <= mid)	return query(lid, l, r);
	else if(l > mid)	return query(rid, l, r);
	else	return min(query(lid, l, mid), query(rid, mid+1, r));
}

int q, op[N], x[N], t[N];
map<LL, LL> func;

int main(){
	// freopen("data.in", "r", stdin);
	// freopen("H.out", "w", stdout);
	func[-INF] = -INF, func[INF] = INF;
	scanf("%d", &q);
	for(int i = 1; i <= q; i++){
		scanf("%d%d", &op[i], &x[i]);
		t[++t[0]] = x[i];
	}
	sort(t+1, t+t[0]+1);
	int len = unique(t+1, t+t[0]+1) - (t+1), mx = 0;
	for(int i = 1; i <= q; i++){
		int tmp = lower_bound(t+1, t+len+1, x[i]) - t;
		func[tmp] = x[i], x[i] = tmp, mx = max(mx, tmp);
	}
	mx++;
	build(1, 1, mx);
	for(int i = 1; i <= q; i++){
		if(op[i] == 1){
			int cnt = add_del(1, x[i], 1);
			LL pre = getPre(1, x[i]), suc = getSuc(1, x[i]);
			if(cnt == 1){
				if(suc != INF && add_del(1, suc, 0) == 1)
					modify(1, suc, func[suc] - func[x[i]]);
				modify(1, x[i], func[x[i]] - func[pre]);
			}
			else if(cnt >= 2)	modify(1, x[i], 0);
		}
		else if(op[i] == 2){
			int cnt = add_del(1, x[i], -1);
			LL pre = getPre(1, x[i]), suc = getSuc(1, x[i]);
			if(cnt == 0){
				modify(1, x[i], INF);
				if(suc != INF && add_del(1, suc, 0) == 1)
					modify(1, suc, func[suc] - func[pre]);
			}
			else if(cnt == 1)	modify(1, x[i], func[x[i]] - func[pre]);
		}
		else{
			int cnt = add_del(1, x[i], 0);
			if(cnt >= 2){ puts("Yes"); continue; }
			LL pre = -INF, ppre = -INF;
			if(cnt == 1)	pre = x[i], ppre = getPre(1, x[i]);
			else{
				pre = getPre(1, x[i]);
				if(pre == -INF)	ppre = -INF;
				else{
					if(add_del(1, pre, 0) >= 2)	ppre = pre;
					else	ppre = getPre(1, pre);
				}
			}
			if(func[pre] + func[ppre] > func[x[i]]){ puts("Yes"); continue; }

			LL suc = getSuc(1, x[i]);
			if(func[pre] + func[x[i]] > func[suc]){ puts("Yes"); continue; }
			
			puts(query(1, x[i] + 1, mx) < func[x[i]] ? "Yes" : "No");
		}
	}
	return 0;
}

I Interval

把区间 $[l,r]$ 看成直角坐标下的点 $(l,r)$，则原题转化成了网格图的最小割问题，等价于最大流问题。

然而这个图的大小显然不适合跑网络流，但是受到“狼抓兔子”的启发，我们可以把平面图的最小割问题转化为其对偶图的最短路问题，于是 $\textbf{dijkstra}$ 搞定。

I.cpp >folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 300005;
const LL INF = 1e16;

struct Edge{
    int nxt, to;
    LL dis;
}edge[5000005];
int head[N], edgeNum;
void addEdge(int from, int to, LL dis){
    edge[++edgeNum].nxt = head[from];
    edge[edgeNum].to = to;
    edge[edgeNum].dis = dis;
    head[from] = edgeNum;
}

struct Node{
    LL dis; int num;
    bool operator < (const Node &a) const{
        return a.dis < dis;
    }
};
LL dis[N];
bool inS[N];
void dijkstra(int s, int n){
    priority_queue<Node> q;
    for(int i = 1; i <= n; i++)	dis[i] = INF;
    dis[s] = 0;
    q.push( (Node){0, s} );
    while(!q.empty()){
        Node cur = q.top();
        q.pop();
        if(inS[cur.num])	continue;
        inS[cur.num] = 1;
        for(int i = head[cur.num]; i; i = edge[i].nxt){
            if((LL)dis[edge[i].to] > (LL)dis[cur.num] + edge[i].dis){
                dis[edge[i].to] = dis[cur.num] + edge[i].dis;
                q.push( (Node){dis[edge[i].to], edge[i].to} );
            }
        }
    }
}

int n, m;
bool b[505][505];

inline int get(int x, int y){
	return (x - 1) * (n - 1) + y;
}

int main(){
	read(n, m);
	int st = n * n + 1, ed = n * n + 2;
	for(int i = 1; i <= m; i++){
		int l, r, c; char dir[2];
		scanf("%d%d%s%d", &l, &r, dir, &c);
		if(dir[0] == 'L'){
			if(r == n)	addEdge(get(l, r-1), ed, c), addEdge(ed, get(l, r-1), c);
			else	addEdge(get(l, r-1), get(l, r), c), addEdge(get(l, r), get(l, r-1), c);
		}
		else{
			if(l == 1)	addEdge(st, get(l, r-1), c), addEdge(get(l, r-1), st, c);
			else	addEdge(get(l-1, r-1), get(l, r-1), c), addEdge(get(l, r-1), get(l-1, r-1), c);
		}
	}
	dijkstra(st, n * n + 2);
	if(dis[ed] == INF)	puts("-1");
	else	printf("%lld\n", dis[ed]);
	return 0;
}

J Just Shuffle

比赛时思路方向是对的，后续没想出来，有所收获。

我们可以根据 $A$ 数组将原排列拆成一个个环，而我们只需要在每个环上转动 $1$ 次就行了。设第 $i$ 个环大小为 $r_i$，我们想要寻找的 $P$ 排列是按照上述规则转动 $x_i$ 次后的一个映射，即按照 $P$ 转 $1$ 次等价于转 $x_i$ 次。那么按照 $P$ 转 $k$ 次等价于转了 $kx_i$ 次，我们希望 $kx_i\bmod r_i=1$，即 $kx_i\equiv1\pmod {r_i}$，也即 $x_i\equiv k^{-1}\pmod {r_i}$，所以求求逆元，那么 $P$ 映射就是 $A$ 映射转 $x_i$ 次的结果，这道题就搞定了。

J.cpp >folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int exgcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

const int N = 100005;

int n, k, a[N], ans[N];

bool vis[N];

int main(){
	read(n, k);
	for(int i = 1; i <= n; i++)	read(a[i]);
	for(int i = 1; i <= n; i++){
		if(vis[i])	continue;
		vi org, _org;
		int now = i;
		while(!vis[now]){
			vis[now] = true;
			org.pb(now);
			_org.pb(now);
			now = a[now];
		}
		int ri = _org.size();
		int x, y; exgcd(k, ri, x, y);
		((x %= ri) += ri) %= ri;
		while(x--) for(auto &t : _org) t = a[t];
		for(int i = 0; i < ri; i++)	ans[org[i]] = _org[i];
	}
	for(int i = 1; i <= n; i++)	printf("%d ", ans[i]); puts("");
	return 0;
}

K Keyboard Free

大佬博客

固定 $A$ 点后，答案不变。现在让 $B$ 点和 $C$ 点在圆上运动。

假设 $B$ 点固定住，此时可知如图所示的角 $\alpha$ 和 $O$ 到直线 $AB$ 的距离 $h$，那么 $C$ 到直线 $AB$ 的期望距离为：

$\begin{align} \bar d&=\frac{\int_\alpha^{\pi-\alpha}(r_3\sin\theta-h)\mathrm d\theta+2\int_0^\alpha(h-r_3\sin\theta)\mathrm d\theta+\int_0^\pi(h+r_3\sin\theta)\mathrm d\theta}{2\pi}\\&=\frac{2r_3\cos\alpha-h(\pi-2\alpha)+2h\alpha+2r_3\cos\alpha-2r_3+h\pi+2r_3}{2\pi}\\&=\frac{2r_3\cos\alpha+2h\alpha}{\pi} \end{align}$

于是。三角形期望面积为：

$\bar S=\frac{\bar d\cdot\left|AB\right|}{2}=\frac{(r_3\cos\alpha+h\alpha)\left|AB\right|}{\pi}$

取 $1000$ 个 $B$ 即可。

K.cpp >folded

#include<bits/stdc++.h>

using namespace std;

const double PI = acos(-1);

int main(){
	int T; for(scanf("%d", &T); T; T--){
		double r1, r2, r3;
		scanf("%lf%lf%lf", &r1, &r2, &r3);
		if(r1 > r2)	swap(r1, r2);
		if(r2 > r3)	swap(r2, r3);
		if(r1 > r3)	swap(r1, r3);
		double res = 0;
		for(int i = 1; i <= 1000; i++){
			double phi = 2 * PI / 1000.0 * i - PI / 10000;
			double AB = sqrt(r1 * r1 + r2 * r2 - 2 * r1 * r2 * cos(phi));
			double h = r1 * r2 * sin(phi) / AB;
			double alpha = asin(h / r3);
			res += (r3 * cos(alpha) + alpha * h) / PI * AB;
		}
		printf("%.1f\n", res / 1000.0);
	}
	return 0;
}

2020牛客暑期多校训练营（第二场）

http://xyfjason.github.io/blog-xcpc/2020/07/15/2020牛客暑期多校训练营（第二场）/

作者

xyfJASON

发布于

2020-07-15

更新于

2021-08-28

许可协议

#Nowcoder

2020牛客暑期多校训练营（第二场）

收获

A All with Pairs

B Boundary

C Cover the Tree

D Duration

F Fake Maxpooling

G Greater and Greater

H Happy Triangle

I Interval

J Just Shuffle

K Keyboard Free

作者

发布于

更新于

许可协议

评论

分类

最新文章

标签