夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

Atcoder杂题选讲第三轮

2021-01-28 16 min read # 题目集合 # 计数题 # 费用流 # 构造

AT3945 [ARC092D] Two Faced Edges

有向图没有边双,考虑翻转一条边的影响

原图中u,v不是同一个强联通分量中的

原图存在不经过这条边的u−>vu->v的一条路径

  1. 在这个条件下,原图存在v−>uv->u的一条路径

那么答案不变....等等好像不可能?

  1. 在这个条件下,原图不存在v−>uv->u的一条路径

那么一旦翻转,就存在u->v和v->u的路径了,u,v就会成为一个强联通分量的,所以答案会减少

不存在不经过的u−>vu->v路径

因为本来就不在一个连通分量中,所以答案不会变

原图中u,v在一个强联通分量里面

  1. 原图存在不经过这条边的u−>vu->v的路径

那么无论v−>uv->u,答案都不会变

  1. 原图不存在不经过这条边的u−>vu->v的路径

翻转之后,由于u−>vu->v只有这么一条边,所以答案会变大

综上,我们如果

u,v不是一个连通块,且存在u−>vu->v不经过这条边的路径

答案减少

u,v在一个连通块,不存在不经过u−>vu->v

答案增加

怎么做这两个呢?

其实都是相当于判断这条边是不是必经边

不存在不经过u−>vu->v的路径,相当于u−>vu->v

判断必经边的方法,就是我们先从x出发dfs,然后得到每个点到达时x出边的标号

然后把x的出边翻转再看看这个出边标号是不是一样的就知道答案了

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int MAXN = 2e5 + 7;
const int MAXT = 1e3 + 7;
int n, m;
vector<int> v[MAXN], g[MAXN];
struct rec {
	int x, y;
} e[MAXN];
int mp[MAXT][MAXT];
inline void ct(int x, int y, int z) {
	v[x].pb(y);
	g[x].pb(z);
}
int vis1[MAXN], vis2[MAXN], ans[MAXN];
inline void dfs1(int x, int e) {
	if(vis1[x])return;
	vis1[x] = e;
	for(int i = 0; i < v[x].size(); ++i) {
		dfs1(v[x][i], e);
	}
	return;
}
inline void dfs2(int x, int e) {
	if(vis2[x])return;
	vis2[x] = e;
	for(int i = 0; i < v[x].size(); ++i) {
		dfs2(v[x][i], e);
	}
	return;
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		ct(x, y, i);
		e[i].x = x;
		e[i].y = y;
	}
	for(int u = 1; u <= n; ++u) {
		dfs1(u, u);
		for(int j = 1; j <= n; ++j) {
			if(vis1[j]) {
				mp[u][j] = 1;
				vis1[j] = 0;
			}
		}
	}
	for(int u = 1; u <= n; ++u) {
		vis1[u] = 1;
		vis2[u] = 1;
		for(int i = 0; i < v[u].size(); ++i) {
			dfs1(v[u][i], g[u][i]);
		}
		for(int i = v[u].size() - 1; i >= 0; --i) {
			dfs2(v[u][i], g[u][i]);
		}
		for(int i = 0; i < v[u].size(); ++i) {
			int to = v[u][i], id = g[u][i];
			if((vis1[to] != vis2[to]) || (vis1[to] != id || vis2[to] != id)) {
				ans[id]++;//满足这个条件
			}
			if(mp[to][u]) {
				ans[id]++;
			}
		}
		for(int i = 1; i <= n; ++i)vis1[i] = vis2[i] = 0;
	}
	for(int i = 1; i <= m; ++i) {
		if(ans[i] == 1)puts("diff");
		else puts("same");
	}
	return 0;
}

AT3955 [AGC023D] Go Home

考虑1,n两个位置,如果pn>p1p_n>p_1,那么无论如何在最后都会向n走,1就会想尽可能向n走,所以删掉1,然后把人数加到那个方向即可,然后删掉1递归

当1,n同侧,做完了

统计答案可看code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
int n, L, R;
long long a[MAXN], b[MAXN], s;
long long ans = 0;
inline void solve(int l, int r, int g) {
	if(a[l] >= s && a[r] >= s) {
		ans += a[r] - s;
		return;
	}
	if(a[l] <= s && a[r] <= s) {
		ans += s - a[l];
		return;
	}
	if(b[l] >= b[r]) {
		if(g != 0)
			ans += a[r] - a[l];
		b[l] += b[r];
		solve(l, r - 1, 0);
	} else {
		if(g != 1)
			ans += a[r] - a[l];
		b[r] += b[l];
		solve(l + 1, r, 1);
	}
	return;
}

int main() {
	scanf("%d%lld", &n, &s);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &a[i], &b[i]);
		if(a[i] > s && a[i] <= s)R = i;
	}
	L = R - 1;
	while(a[L] == s)--L;
	solve(1, n, -1);
	printf("%lld\n", ans);
	return 0;
}

AT2672 [AGC018C] Coins

最后还是爬过来做AGC

首先如果只有两个硬币我有个错误的贪心想法就是A-B然后选取这个值最大的前x个

这个在X=0X=0还真是对的

正确是建模网络流,左边一排点,然后右边两个点,每个点有个流量限制x,y,然后左边的点向右边连接边,表示选择a的cost和选择b的cost,费用流即可

本题也可以做一歩转换变成这样子,就是直接每个点减去c,变为选择a得到a-c,选择b得到b-c,然后提前拿到所有c的总和

现在的问题难在时间复杂度不对

首先第一种做法是模拟费用流,就是考虑每次增广带来的影响是什么,无疑只有几种情况:

  1. 选择x
  2. 选择y
  3. 选择x,然后让某一个x的放弃(达到了上界弹掉他)
  4. 选择y,然后让某一个y的放弃

模拟费用流嘛,就是模拟增广的过程:选择一个最大权的放入,如果我能够顶替掉权值最小的那个,那么就顶替,然后他去找另一边的有没有,然后如果另一边也有再继续找下去

这个路径的总长可以用几个类别表示出来,要么选择x的变成y,选y变为z,选z变为x.这样循环一周,要么选择x的变成y,选y的变为z

一共有5种情况,我们每次取出这样子的变换的最大值执行即可

当最大值变为<0<0结束

当然我们也可以使用第一种做法的延续

排序后,枚举一个分界点,我们一定是在这个分界点左边选出最大的A个和右边选出最大的右边最优,因为但凡交换两边选择的位置,都会导致某一边选择的其实不够优秀(交换回来一定更优)

于是我们也能转换回来,就做完了

//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define pa pair<ll,ll>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
inline ll lowbit(ll x){return x&(-x);}
ll n,X,Y,Z;
ll a[N],b[N],c[N];
ll vis[N],ans;
priority_queue<pa,vector<pa>,less<pa> >q1,q2,q3,q4,q5,q6;
inline void add(ll x)
{
	q1.push(mp(b[x]-a[x],x));//x->y
	q2.push(mp(c[x]-b[x],x));//y->z
	q3.push(mp(a[x]-c[x],x));//z->x
	
	q4.push(mp(c[x]-a[x],x));//x->z
	q5.push(mp(b[x]-c[x],x));//z->y
	q6.push(mp(a[x]-b[x],x));//y->x
}
int main()
{
	//ios::sync_with_stdio(false);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	X=read(),Y=read(),Z=read();n=X+Y+Z;
	FOR(i,1,n)a[i]=read(),b[i]=read(),c[i]=read();
	FOR(i,1,X)vis[i]=1,ans+=a[i];
	FOR(i,X+1,X+Y)vis[i]=2,ans+=b[i];
	FOR(i,X+Y+1,X+Y+Z)vis[i]=3,ans+=c[i];
	FOR(i,1,n)add(i);
	while(true)
	{
		while(!q1.empty()&&vis[q1.top().sd]!=1)q1.pop();
		while(!q2.empty()&&vis[q2.top().sd]!=2)q2.pop();
		while(!q3.empty()&&vis[q3.top().sd]!=3)q3.pop();
		
		while(!q4.empty()&&vis[q4.top().sd]!=1)q4.pop();
		while(!q5.empty()&&vis[q5.top().sd]!=3)q5.pop();
		while(!q6.empty()&&vis[q6.top().sd]!=2)q6.pop();//反悔贪心在每次取值时弹出不合法状态往往更好写 
		
		ll v1=(q1.empty()?-inf:q1.top().fr),v2=(q2.empty()?-inf:q2.top().fr),v3=(q3.empty()?-inf:q3.top().fr);
		ll v4=(q4.empty()?-inf:q4.top().fr),v5=(q5.empty()?-inf:q5.top().fr),v6=(q6.empty()?-inf:q6.top().fr);
		ll maxn=0,t=0;
		if(v1+v2+v3>maxn)maxn=v1+v2+v3,t=1;//情况1
		if(v4+v5+v6>maxn)maxn=v4+v5+v6,t=2;//情况2
		if(v1+v6>maxn)maxn=v1+v6,t=3;//情况3
		if(v2+v5>maxn)maxn=v2+v5,t=4;//情况4
		if(v3+v4>maxn)maxn=v3+v4,t=5;//情况5
		if(!maxn)break;ans+=maxn;
		if(t==1)
		{
			ll x=q1.top().sd,y=q2.top().sd,z=q3.top().sd;
			vis[x]=2,vis[y]=3,vis[z]=1;
			add(x);add(y);add(z);
		}
		if(t==2)
		{
			ll x=q4.top().sd,y=q5.top().sd,z=q6.top().sd;
			vis[x]=3;vis[y]=2;vis[z]=1;
			add(x);add(y);add(z);
		}
		if(t==3)
		{
			ll x=q1.top().sd,y=q6.top().sd;
			vis[x]=2;vis[y]=1;
			add(x);add(y);
		}
		if(t==4)
		{
			ll x=q2.top().sd,y=q5.top().sd;
			vis[x]=3;vis[y]=2;
			add(x);add(y);
		}
		if(t==5)
		{
			ll x=q3.top().sd,y=q4.top().sd;
			vis[x]=1;vis[y]=3;
			add(x);add(y);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
//gl

其中弹出不合法操作是很重要的,相当于我们给每个元素重新更新信息,但是并不需要特判,只需要把原来信息不符合的删掉即可!lessless是大根堆比较算子

AT2043 [AGC004C] AND Grid

我竟然个给出一种构造方式,不可思议啊

我们首先利用题目给出的条件,第一张图使用最上面一行和最下面一行连通,第二张图利用最左边一列和最右边一列来连通,也就是说只要一个点和上下左右连通,他就在两张图中成为交点了

然后我们要注意到一个很关键的点,四个对角一定没有用,因为我们只需要使用2~n-1的位置就能让方格内部都连通了

然后考虑怎么让中间的点连通,我们取最左上角的一个点,然后用它画出一条横竖交叉的线,左右连通的信息代表和当前状态的左右连通了,然后上下连通代表和当前状态的上下连通了!于是发现我们只需要交换了行列连通性质就能递归到子问题

但是此时感觉上可以,如果我们一个画出的线上有多个点,又萎住了QAQ,因为我们一定要保证边界上没有点!

于是我们又能构造出另一种毒瘤的策略,只要存在点他向左直走向上直走没有其他点,我们就能把这个点和左边连通然后另一张图和上面连通,然后减少问题规模!

这样你会发现可能我们连通后还是自闭了,因为不能保证每个点向左向上都是和某张图连通....

题解给出了很不错的构造方法,令人叹为观止

####.   ....#
#....   .####
####.   ....#
#....   .####
####.   ....#

然后如果在中间某些位置有#对应点亮即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int n, m;
char s[MAXN][MAXN];
int a[MAXN][MAXN], b[MAXN][MAXN];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s[i] + 1);
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(i & 1) {
				if(j != m)
					a[i][j] = 1;
				else b[i][j] = 1;
			} else {
				if(j != 1)
					b[i][j] = 1;
				else a[i][j] = 1;
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(s[i][j] == '#') {
				if(i & 1)b[i][j] = 1;
				else a[i][j] = 1;
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			printf("%c", a[i][j] == 1 ? '#' : '.');
		}
		puts("");
	}
	puts("");
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			printf("%c", b[i][j] == 1 ? '#' : '.');
		}
		puts("");
	}
	return 0;
}

AT2293 [AGC009D] Uninity

题目相当于问最小化点分树上最大深度

给每个点分配一个标签label,表示这个点是第几级别树的树根

点分树深度不会超过log,所以可以状压深度的信息

显然对于两个级别相同的点,他们之间一定要有一个级别高于他们的点

然后考虑对于一个点u子树内两个点v,他们都存在一个级别w,那么u的级别至少是w

所以这好像告诉我们,u的深度是所有这样限制下的|,然后这个|值的第一个不为1的位置

不妨定义ban[u]ban[u]表示u子树内还有哪些深度没有完成匹配,然后好像就是banvban_v按位或和的第一个为0的位置

注意叶子也是可以的

所以我们还要统计一个任意两个儿子&起来的值的或,不难发现这个值告诉了我们最严限制,所以这个限制的前导零部分也是我们可以存在的答案位置

于是O(log)枚举每一位判断是否合法即可

Powered by Gridea RSS