首页 > 其他分享 >【题解】AtCoder Beginner Contest 318（D - Ex）

【题解】AtCoder Beginner Contest 318（D - Ex）

时间：2023-09-03 09:22:14浏览次数：40  
标签：AtCoder 318 int 题解 sum leq 顶点 now ldots

赛时过了 A-G，Ex 仿佛猜到了结论但是完全不懂多项式科技，就炸了。
大家好像都秒了 A,B,C 就不写了。

D.General Weighted Max Matching

题目描述：

给你一个加权无向完全图，图中有 \(N\) 个顶点，编号从 \(1\) 到 \(N\)。连接顶点 \(i\) 和 \(j\) 的 \((i < j)\)的权重为\(D_{i,j}\)。

在以下条件下选择若干条边时，请找出所选边的最大可能总权重。

  • 所选边的端点是成对不同的。

\(2\leq N\leq 16\)
\(1\leq D_{i,j} \leq 10^9\)
所有输入值均为整数。

题目分析：

一眼看过去这是一般图的最大权独立集，根本没啥多项式做法。
所以就直接爆搜的就好了，也就是对于每一个点找它匹配的点，需要注意的是可以有点不匹配边。
这样的复杂度就是 \(O(N!!)\) 显然可以过。

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20;
int n,match[N],d[N][N],ans,sum;
void dfs(int now){
	if(now == n + 1){
		ans = max(ans,sum);
		return;
	}
	if(match[now]){
		dfs(now+1);
		return;
	}
	for(int i=now+1; i<=n; i++){
		if(match[i])	continue;
		match[now] = i,match[i] = now;
		sum += d[now][i];
		dfs(now+1);
		match[now] = match[i] = 0;
		sum -= d[now][i];
	}
	dfs(now+1);
}
signed main(){
	scanf("%lld",&n);
	for(int i=1; i<=n; i++){
		for(int j=i+1; j<=n; j++){
			scanf("%lld",&d[i][j]);
		}
	}
	dfs(1);
	printf("%lld\n",ans);
	return 0;
}

E.Sandwiches

题目描述：

给你一个长度为 \(N\) 的正整数序列：\(A=(A_1,A_2,\ldots,A_N)\).求满足下列所有条件的正整数三元组 \((i,j,k)\)的个数：

  • \(1\leq i < j < k\leq N\),
  • \(A_i = A_k\),
  • \(A_i \neq A_j\).

\(3 \le N \le 3 \times 10^5\)
\(1 \le A_i \le N\)

题目分析：

看上去我们可以考虑枚举 \(i,k\) 然后看看有多少符合条件的 \(j\)。
不妨假设 \(s_i\) 表示前 \(i\) 个数中有多少个等于 \(A_i\) 的数。
可以发现答案其实就是：

\[\sum_{i=1}^n \sum_{k=i+1}^n [A_i = A_k] (k - i - 1) - (s_k - s_i - 1) \]

可以对于每一个 \(A_i\) 开一个桶维护位置，这样我们直接在每一个桶内维护就好了，这样 \(A_i = A_k\) 的限制就无了：

\[\begin{aligned} &\sum_{i=1}^{len} \sum_{k=i+1}^{len}(k - i - 1) - (s_k - s_i - 1) \\ &= \sum_{i=1}^{len} \sum_{k=i+1}^{len}k - i - s_k + s_i \\ &= \sum_{i=1}^{len} (s_i - i + \sum_{k=i+1}^{len}k - s_k) \end{aligned} \]

考虑每一个 \(s_i - i\) 会有 \(n - (i + 1)\) 个 \(k\) 使得 \(i\) 可以产生这个贡献，所以这一部分对答案的贡献就是：\(\sum_{i=1}^{len} (s_i-i) \times (n - i - 1)\)
考虑每一个 \(k - s_k\) 会有 \(k-1\) 个 \(i\) 使得 \(k\) 可以产生这个贡献，所以这一部分对答案的贡献就是：\(\sum_{k=1}^{len} (k - s_k) \times (k - 1)\)
两部分求和就好。

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
int a[N];
vector<int> v[N];
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	for(int i=1; i<=n; i++){
		v[a[i]].push_back(i);
	}
	int ans = 0;
	for(int i=1; i<=n; i++){
		int len = v[i].size();
		for(int j=0; j<v[i].size(); j++){
			ans += -v[i][j] * (len - (j + 1));
			ans += v[i][j] * j;
			ans += j * (len - (j + 1));
			ans += -j * j;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

F.Octopus

题目描述：

在一条数线上有一个章鱼形机器人和 \(N\)个宝物。第 \(i\)个宝物 \((1\leq i\leq N)\)位于坐标 \(X_i\)处。
机器人有一个头和\(N\)条腿，\(i\)条腿\((1\leq i\leq N)\)的长度为\(L_i\)。

求满足如下要求的整数 \(k\) 的个数：

  • 将头部置于坐标 \(k\)处。
  • 依次对 \(i=1,2,\ldots,N\)重复以下步骤：如果在距离头部 \(L_i\)的距离内，即在满足 \(k-L_i\leq x\leq k+L_i\)的坐标 \(x\)处，有一件宝物尚未被抓取，则选择其中一件宝物并抓取。

\(1 \leq N\leq 200\)
\(-10^{18} \leq X_1 < X_2 < \cdots < X_N\leq 10^{18}\)
\(1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}\)

题目分析：

首先考虑若给定 \(k\) 给怎么判断是否合法。
一个显然的贪心就是按与 \(k\) 的距离将宝藏排序，然后让第 \(i\) 长的腿去抓第 \(i\) 远的宝藏，若抓不到则无解。

类似扫描线的思想，我们会发现如果对于区间 \(k \in [l,r]\) 任何一条腿都没有恰好碰到某一个宝藏，则这一段的数是否可以作为 \(k\) 的结果是一样的，因为感性理解既然不存在其恰好碰到某一个宝藏的情况，也就是不存在某一个腿原来可以覆盖宝藏 \(i\) 但是现在不能覆盖了，或者原本不能覆盖了现在可以覆盖的情况，因为若出现这种情况必然存在恰好碰到这样的分界点。

所以可以直接钦定某一条腿碰到某一个宝藏，这样可以得到 \(O(n^2)\) 个 \(k\)，并且它们将区间分成了 \(O(n^2)\) 段。
只需要对于每一个段里随便选一个数判断一下即可，然后再对于选出的 \(O(n^2)\) 个 \(k\) 判断一下即可。

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,tot,a[N],b[N],x[N],l[N],c[N];
bool chk(int k){
	for(int i=1; i<=n; i++)	a[i] = abs(x[i] - k);
	for(int i=1; i<=n; i++)	b[i] = l[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for(int i=1; i<=n; i++){
		if(a[i] > b[i])	return false;
	}
	return true;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld",&x[i]);
	for(int i=1; i<=n; i++)	scanf("%lld",&l[i]);
	for(int j=1; j<=n; j++){
		for(int i=1; i<=n; i++){
			int k = x[i] + l[j];
			c[++tot] = k;
			k = x[i] - l[j];
			c[++tot] = k;
		}
	}
	sort(c+1,c+tot+1);
	tot = unique(c+1,c+tot+1) - c - 1;
	int ans = 0;
	for(int i=1; i<tot; i++){
		if(c[i] == c[i+1])	continue;
		if(chk(c[i]+1))	ans += c[i+1] - c[i] - 1;
	}
	for(int i=1; i<=tot; i++)	if(chk(c[i]))	++ans;
	printf("%lld\n",ans);
	return 0;
}

G.Typical Path Problem

题目描述：

问题陈述

给你一个简单连通的无向图\(G\)，它有\(N\)个顶点和\(M\)条边。 \(G\)的顶点和边分别编号为顶点\(1\)、顶点\(2\)、\(\ldots\)、顶点\(N\)和边\(1\)、边\(2\)、\(\ldots\)、边\(M\)，边\(i\)\((1\leq i\leq M)\)连接顶点\(U_i\)和\(V_i\)。

在\(G\)上还有不同的顶点\(A,B,C\)。请判断是否有一条简单路径通过顶点\(B\)连接顶点\(A\)和\(C\)。

什么是简单连通无向图？
当\(G\)是简单且连通的无向图时，图\(G\)被称为简单连通的无向图。
当 \(G\) 的边没有方向时，图 \(G\) 称为无向图。
当 \(G\)不包含重边和自环时，图 \(G\)是简单的。
当人们可以通过边在\(G\)的所有顶点之间移动时，图\(G\)是连通的。

什么是通过顶点\(Z\)的简单路径？
对于图\(G\)上的顶点\(X\)和\(Y\)，连接\(X\)和\(Y\)的简单路径是一系列不同的顶点\((v_1,v_2,\ldots,v_k)\)，使得\(v_1=X\) \(v_k=Y\)，并且对于满足\(1\leq i\leq k-1\)的每一个整数\(i\)，在\(G\)上有一条边连接顶点\(v_i\)和\(v_{i+1}\)。
当有一条 \(i\)\((2\leq i\leq k-1)\)满足 \(v_i=Z\)时，称一条简单路径 \((v_1,v_2,\ldots,v_k)\)经过顶点 \(Z\) \((2\leq i\leq k-1)\)满足 \(v_i=Z\)。

\(3 \le N \le 2\times 10^5，M \le 2 \times 10^5\)

题目分析：

（官解竟然是网络流，充分说明科技的重要性，感觉震撼）
路径(必须)经过某个点的问题，显然想到圆方树，因为圆方树完美地保留了原图的必经性。
这个意思就是说圆方树路径上的圆点为两点路径的必经点，路径上的方点下的圆点就是两点路径的可经过的点。
所以只需要建出圆方树然后判断 \(A,C\) 路径上的圆点或方点下的圆点是否含有 \(B\) 即可。

代码：

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
const int _ = 2e6 + 5;

int A,B,C,n, m, q, tp;
int cnt_node, cntn;
bool flag;
int dfn[_], low[_];
int dep[_], top[_], siz[_], hson[_], fa[_];
stack<int> s;

struct Graph
{
    int tot, head[_], nxt[_ << 1], to[_ << 1];
    void add(int u, int v)
    {
        nxt[++tot] = head[u];
        to[tot] = v;
        head[u] = tot;
        nxt[++tot] = head[v];
        to[tot] = u;
        head[v] = tot;
    }
} G, T;

void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt_node;
    s.push(u);
    for (int i = G.head[u], v; i; i = G.nxt[i])
    {
        v = G.to[i];
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u])
            {
                T.add(++cntn, u);
                while (1)
                {
                    int now = s.top();
                    s.pop();
                    T.add(cntn, now);
                    if (now == v)
                        break;
                }
            }
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

void dfs1(int u, int d = 1)
{
    siz[u] = 1;
    dep[u] = d;
    for (int i = T.head[u], v; i; i = T.nxt[i])
    {
        v = T.to[i];
        if (dep[v])
            continue;
        fa[v] = u;
        dfs1(v, d + 1);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}

void chk(int now){
	if(now <= n && now == B)	flag = true;
	else{
		for(int i=T.head[now]; i; i=T.nxt[i]){
			int to = T.to[i];
			if(to == B)	flag = true;
		}
	}
}

signed main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d",&A,&B,&C);
    cntn = n;
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d",&u,&v);
        G.add(u, v);
    }
    tarjan(1);
    dfs1(1);
    flag = false;
    while(A != C){
    	if(dep[A] < dep[C])	swap(A,C);
		chk(A);
		A = fa[A];
	}
	chk(A);
	if(flag)	printf("Yes\n");
	else	printf("No\n");
    return 0;
}

Ex.Count Strong Test Cases

题目描述：

Snuke 遇到了以下问题。

给你\((1,2,\ldots,N)\)的排列组合\(P=(P_1,P_2,\ldots,P_N)\)和\(Q=(Q_1,Q_2,\ldots,Q_N)\)。让我们如下建立一个有 \(N\) 个顶点和 \(N\) 条边的图。

  • 依次为\(i=1,2,\ldots,N\)，画一条权重为\(Q_i\)的边，双向连接顶点\(i\)和\(P_i\)。

当删除一定数量的边以消除图中的循环时，求删除的边的总重量的最小值。

爱丽丝和鲍勃提出了以下解决方案。

爱丽丝： 初始化答案为\(0\)。对于按此顺序排列的 \(i=1,2,\ldots,N\)，如果连接顶点 \(i\)和 \(P_i\)的边包含在一个循环中，则删除该边并将其权重添加到答案中。

鲍勃： 将答案初始化为 \(0\)。对于按此顺序排列的\(i=N,N-1,\ldots,1\)，如果连接顶点\(i\)和\(P_i\)的边包含在一个循环中，则删除该边并将其权重添加到答案中。

Snuke 意识到他们的解法都不正确，他想知道他们的解法都没有给出正确答案的输入数。

在 \((N!)^2\) 个可能的输入中，求爱丽丝和鲍勃的解都没有给出正确答案的输入个数（模为 \(998244353\)）。

题目分析：

（这个大概就是 Atcoder 网站上的解法）
考虑答案可以容斥转化为所有的概率 - 两个全部正确的概率 - 恰好一个正确的概率。

首先若对于一个环最小的 \(i\) 满足 \(i \to P_i\) 在环上不为这个环的最小值，则 Alice 会寄掉。
如果对于一个环最大的 \(i\) 满足 \(i \to P_i\) 在环上不为这个环的最小值，则 Bob 会寄掉。

两个全部正确的概率，设为 \(f_n\)
而因为权值一定是一个排列，也就是不存在相等的情况，所以只要环不为自环则必然会至少寄一个，则显然 \(f_n = \frac{1}{n!}\)

恰好一个正确的概率，设为 \(g_n\)
这个计算就可以考虑枚举 \(n\) 所在环的大小设为 \(i\)，则就有如下的式子：

\[g_n = \dfrac{\sum_{i=1}^n \frac{2}{i} \times f_{n-i} + \frac{1}{i} \times g_{n-i}}{n} \]

上面的这个首先要知道一个定理就是：长度为 \(n\) 的置换，点 \(n\) 所在环的长度在 \([1,n]\) 概率相等，所以上文的 \(\frac{2}{i}\) 的含义其实就是最小值在下标最大的/最小的位置，而后面的 \(\frac{1}{i}\) 相当于我们已经在 \(g_{n-i}\) 确定了谁寄，为了保证另一个不寄最小值只能在这一个位置。
对于 \(g\) 前面这一坨就是卷积，后面这一坨是半在线卷积，都是可以做的。

我们的答案显然就是 \((1 - f_n - g_n) \times (n!)^2\)，然后就做完了。

标签：AtCoder,318,int,题解,sum,leq,顶点,now,ldots
From： https://www.cnblogs.com/linyihdfj/p/17674541.html

相关文章

  • P4198 楼房重建题解
    传送门一眼数据结构。考虑线段树，记录该区间能看到最多的建筑数量\(ans_{wz}\)以及看到区间中最大的斜率（或者说，该区间内最后看到的建筑）\(xl_{wz}\)。很明显，假如我现在的修改操作是\((x,y)\)，那么会改变\(\log_n\)个节点，即包含\(x\)的节点，考虑如何修改他们的\(ans\)和\(......
  • AT_abc318_e 题解
    AT_abc318_eSandwiches题解Links洛谷AtCoderDescription给定一个长度为\(n\)的序列\(a\)，找到满足以下条件的三元组\((a,b,c)\)的数量。\(i<j<k\)；\(a_{i}=a_{k}\)；\(a_{i}\neqa_{j}\)。数据范围：\(1\leqn\leq3\times10^{5}\)，\(1\leqa_{i}\leqn......
  • AtCoder Beginner Contest 318
    A-FullMoonProblemStatementTakahashilikesfullmoons.Lettodaybeday\(1\).Thefirstdayonoraftertodayonwhichhecanseeafullmoonisday\(M\).Afterthat,hecanseeafullmoonevery\(P\)days,thatis,onday\(M+P\),day\(......
  • ABC318
    T1：FullMoon模拟代码实现n,m,p=map(int,input().split())ans=0i=mwhilei<=n:ans+=1i+=pprint(ans)或者答案是\(\lfloor\frac{n+(p-m)}{p}\rfloor\)T2：Overlappingsheets模拟代码实现#include<bits/stdc++.h>#definerep(i,n)f......
  • ABC317题解报告
    我直接从第三题开始讲了。T3把数组\(A\)从大到小排序。然后从前往后把前\(q\)个数加起来，然后判断这\(q\)个数的和与\(d\)的大小关系，如果大了就变成\(d\)。然后有些细节就看代码吧。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintm......
  • 龙芯平台Hadoop集群搭建问题解决
    这几天一直在困扰我pycurl版本和本机的版本不符合他连接又连接的自己自带的版本与系统不相同低级也会报错 https://blog.csdn.net/u010910682/article/details/89496550/?ops_request_misc=&request_id=&biz_id=102&utm_term=pycurl7.45.2%20%E6%90%AD%E9%85%8Dlibcurl%E6%......
  • 【题解】NOIP2021
    咕咕咕的东西总是要补的。A.报数题目描述：报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是\(7\)的倍数，或十进制表示中含有数字\(7\)，就必须跳过这个数，否则就输掉了游戏。在一个风和日丽的下午，刚刚结束SPC20nn比赛的小r和......
  • 【题解】Luogu[P7706] 「Wdsr-2.7」文文的摄影布置
    Link一道很有意思的线段树题。第一步分析，我们要求最大的\(a_i+a_k-\min{(b_j)}\)，事实上我们可以直接省去这个\(\min\)因为要最大化这个东西，选出来的\(b_j\)必然是最小的，所以原题转化为给定\(l,r\)求\(\max{(a_i-b_j+a_k)}\)其中\(i<j<k\)。第二步分析，我们发现这是一......
  • 【题解】Educational Codeforces Round 153（CF1860）
    每次打都想感叹一句，Educational名不虚传。A.NotaSubstring题目描述：有\(t\)组数据，对于每一组数据，你需要判断能否构造一个只由左右括号组成且长度为已经给定字符串的\(2\)倍且已经给定的字符串不是子串的合法字符串。注：合法的字符串是左右括号能完全匹配的字符串。如果能，......
  • 【题解】Luogu-P2482 SDOI2010 猪国杀
    写了\(358\)行，\(11.94\mathrm{KB}\)，有这么几个地方写挂了：反猪决斗一定选主猪。游戏结束判定是主猪死亡或全部反猪死亡。决斗可能被反杀，之后不能再出牌。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intn,m;charCh[3];queue<char>Deck;in......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99