首页 > 其他分享 >8.11模拟赛小结

8.11模拟赛小结

时间：2023-08-12 23:11:59浏览次数：37  
标签：int 8.11 memset low 字符串 now 小结 id 模拟

前言

最无语的一集

T1 数对 原题

给定整数 \(L,R\ (L\ \le\ R)\)，请计算满足以下条件的整数对 \((x,y)\) 的数量：

  • \(L\ \le\ x,y\ \le\ R\)
  • 设 \(g\) 是 \(x,y\) 的最大公约数，则满足以下条件：
    • \(g\ \neq\ 1\) 且 \(\frac{x}{g}\ \neq\ 1\) 且 \(\frac{y}{g}\ \neq\ 1\)

很简单的容斥 考虑原问题拆分成

\(S(m,m)-S(n-1,m)-S(n,m-1)+S(n-1,n-1)\)

其中\(S(n,m)\)函数表示 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(g…)\)

考虑\(S\)函数求法 考虑容斥

先钦定满足： \(g=1\)

非常容易 一个莫比乌斯反演搞定

然后是：\(x=g\) 这个也很简单 只需要枚举 \(g\) 然后算一下即可

\(y=g\) 同理可得

然后看一下钦定满足 \(g=1,x=g\) 很明显 \(x=1\) y能取任意数

看一下钦定满足 \(x=g,y=g\) 很明显 \(x=y\) \(x,y\)能取 \(min(n,m)\)

最后看一下满足三个条件 很明显只有 \(x=y=1\)的情况

容斥即可

时间复杂度\(O(n)\)

ps:\(l=1\)需要特判

Code

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int isp[N],mu[N];
int P[N],l;
int n,m;
ll ans;
void init(int n)
{
	mu[1]=isp[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!isp[i])
		{
			P[++l]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=l&&i*P[j]<=n;j++)
		{
			isp[i*P[j]]=1;
			if(i%P[j]==0)
			{
				mu[i*P[j]]=0;
				break;
			}
			mu[i*P[j]]=-mu[i];
		}
	}
}
ll solve(int n,int m)
{
	ll sum=1ll*n*m;
	for(int i=1;i<=n;i++)
		sum-=1ll*(n/i)*(m/i)*mu[i];
	//task1
	for(int i=1;i<=n;i++)
		sum-=(m/i);
	//task1
	for(int i=1;i<=m;i++)
		sum-=(n/i);
	//task1
	sum=sum+n+m+min(n,m); //task2
	sum--;//task 3
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	if(n==1) n++;
	init(m);
	printf("%lld",solve(m,m)-solve(m,n-1)-solve(n-1,m)+solve(n-1,n-1));
	return 0;
}

T2 小偷和警察 原题

简要题意：给你一个无向图 给出 \(q\) 个问题 每次问你如果删掉一条点或边后 \(A\) 点是否还能到 \(B\) 点

思考：
考虑缩点

在一个点双中的点就不要管它了 问题就在两个点双 这个问题考虑缩点成树

我们知道 强连通分量中缩点可以将图缩成一个 DAG 变双中找桥也可以缩成一棵树 那么点双的缩点方法是什么？就是圆方树

什么是原方树呢？

考虑一个点双 点双里面所有的圆点连向一个方点 那么只有割点连了多个点双 这样子能保证连通性而且最终一定是一棵树

边怎么搞？找桥！一个桥就是连接多个割点的边

那么怎么找？实际上 我们建的那个方点实际上就代表的一条桥

为什么？因为这是当前割点连向下一个点双的媒介 如果判断出这是桥 这个方点就代表桥了！

然后现在问题就转化成 在路线 \(A\space \to \space B\) 中 是否存在点\(C\)

然后 LCA 分类讨论太麻烦了 我们选择直接大力树剖判断就可以了

Code

#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define M 1000005 
using namespace std;
int n,m,g;
vector <int> G[N],E[N];
int col[N],colcnt,id[N],low[N],cnt;
int q[N],l;
int dep[N],fa[N],size[N],Son[N];
int top[N];
map <pair<int,int>,int> mp;
void tarjan(int x,int fa)
{
	id[x]=low[x]=++cnt;
	q[++l]=x;
	int child=0;
	for(int i=0;i<G[x].size();i++)
	{
		int to=G[x][i];
		if(to==fa) continue;
		if(!id[to]) 
		{
			tarjan(to,x);
			low[x]=min(low[to],low[x]);
			if(low[to]>=id[x]) 
			{
				colcnt++;
				if(low[to]>id[x]) mp[make_pair(x,to)]=mp[make_pair(to,x)]=colcnt;
				while(q[l+1]!=to) 
				{
					int o=q[l--];
					E[o].push_back(colcnt);
					E[colcnt].push_back(o);
				}
				E[x].push_back(colcnt);
				E[colcnt].push_back(x);
			}
			child++;
		}
		else low[x]=min(low[x],id[to]);
	}
}
void dfs1(int now,int f)
{
	dep[now]=dep[f]+1;
	fa[now]=f;
	size[now]=1;
	int maxx=0;
	for(int i=0;i<E[now].size();i++)
	{
		int son=E[now][i];
		if(son==f) continue;
		dfs1(son,now);
		size[now]+=size[son];
		if(size[son]>maxx) maxx=size[son],Son[now]=son;
	}
}
void dfs2(int now,int topf)
{
	top[now]=topf;
	if(!Son[now]) return;
	dfs2(Son[now],topf);
	for(int i=0;i<E[now].size();i++)
	{
		int son=E[now][i];
		if(son==fa[now]||son==Son[now]) continue;
		dfs2(son,son);
	}
}
bool lca(int a,int b,int c)
{
	bool p=0;
	while(top[a]!=top[b])
	{
		if(dep[top[a]]<dep[top[b]]) swap(a,b);
		if(top[a]==top[c]&&dep[c]<=dep[a]) p=1;
		a=fa[top[a]];
	}
	if(dep[a]<dep[b]) swap(a,b);
	if(top[a]==top[c]&&dep[c]>=dep[b]&&dep[c]<=dep[a]) p=1;
	return p;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	colcnt=n;
	
	tarjan(1,0);
	dfs1(1,0);
	dfs2(1,1);
	scanf("%d",&g);
	while(g--)
	{
		int opr;
		int a,b,c,d;
		scanf("%d%d%d%d",&opr,&a,&b,&c);
		if(opr==1)
		{
			scanf("%d",&d);
			int e=mp[make_pair(c,d)];
			if(e==0) 
			{
				printf("yes\n");
				continue;
			}
			c=e;
		}
		if(lca(a,b,c)) printf("no\n");
		else printf("yes\n");
	}
	return 0;
}

T3 无线网络 原题

题意给你一个有向无环图 有一个总父亲 你要给每个点定一个父亲 使得所有点儿子数的最大值最小 输出 字典序最小的方案 方案要保证联通性 总父亲的儿子数不算

思考：

想一下 如果每个点都有一个父亲 只有总结点没有父亲 那么图肯定是保证联通的 因为这就是一棵树 所以 一个点和他的祖父没有关系 所以只需考虑父亲

所以 我们可以把原图抽象成一个二分图 考虑网络流模型

我们设一个原点 \(S\) 连接着左边 \(n\) 个点 流量为1

中间如果有一条有向边 就把左边的点连向右边的对应点 流量为1

还有一些能直接流向总父亲的 直接连一条流向 \(T\) 的边

还有一个汇点 \(T\) 连接着右边\(n\)个点 流量为 \(K\)

我们发现 其实 \(K\) 就是最大儿子数

所以只要跑一遍网络流 如果汇点的值为 \(N\) 那么就存在合法方案

所以可以二分答案

然后是怎么枚举最小字典序

其实每个边暴力枚举父亲即可 记得割掉其他边 特别注意与 \(T\) 相连的边 跑\(N^2\)次网络流 能过

分析一下时间复杂度:\(O(n^2m\log n+n^4m)\)

Code:

#include<bits/stdc++.h>
#define ll long long
#define N 105
using namespace std;
int n,s,t;
char c[N][N];
int tot=2,head[N*2];
struct edge{
	int to,next,w;
}e[N*N*8];
void add(int u,int v,int w)
{
	e[tot]=(edge){v,head[u],w};
	head[u]=tot++;
}
int q[N],l,r;
int pre[N],dis[N];
bool bfs()
{
	fill(dis,dis+1+t+1,-1);
	l=r=0;
	pre[s]=head[s];
	dis[s]=0;
	q[++r]=s;
	while(l<r)
	{
		int x=q[++l];
		for(int i=head[x];i;i=e[i].next)
		{
			int to=e[i].to;
			if(e[i].w&&dis[to]==-1)
			{
				dis[to]=dis[x]+1;
				pre[to]=head[to];
				q[++r]=to;
				if(to==t) return 1;
			}
		}
	}
	return 0;
}
int dfs(int now,int sum)
{
	if(now==t) return sum;
	int cnt=0,k;
	for(int i=pre[now];i&&sum;i=e[i].next)
	{
		pre[now]=i;
		int to=e[i].to;
		if(e[i].w&&dis[to]==dis[now]+1)
		{
			k=dfs(to,min(sum,e[i].w));
			if(k==0) dis[to]=2e9;
			e[i].w-=k;
			e[i^1].w+=k;
			sum-=k;
			cnt+=k; 
		}
	}
	return cnt;
}
int Dinic()
{
	int sum=0;
	while(bfs()) sum+=dfs(s,2e9);
	return sum;
}
int fa[N];
bool check(int k)
{
	fill(head,head+1+t+1,0);
	tot=2;
	for(int i=1;i<=n;i++)
		if(c[0][i]=='Y'&&!fa[i]) 
			add(i,t,1),add(t,i,0);
	for(int i=1;i<=n;i++)
		add(s,i,1),add(i,s,0),
		add(i+n,t,k),add(t,i+n,0);
	for(int i=1;i<=n;i++)
	{
		if(fa[i])
		{
			add(i,fa[i],1);
			add(fa[i],i,0);
			continue;
		}
		for(int j=1;j<=n;j++)
			if(c[i][j]=='Y') add(i,j+n,1),add(j+n,i,0);
	}
	return Dinic()==n;
}
int main()
{
	scanf("%d",&n);
	t=2*n+1;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cin>>c[i][j];
	}
    for(int i=1;i<=n;i++)
		cin>>c[0][i];
	int l=0,r=n+1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	if(r>n)
	{
		printf("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		bool p=0;
		for(int j=1;j<=n;j++)
		{
			if(c[i][j]=='N') continue;
			fa[i]=j+n;
			if(check(r+1))
			{
				p=1;
				break;
			}
		}
		if(!p) fa[i]=t;
		printf("%d ",fa[i]-n-1);
	}
	return 0;
}

T4 游戏设计

找不到原题(((

贴一下题目：

你是游戏设计师，你要设计所有长度为K的字符串，每个字符是‘A’或‘B’或‘C’或‘D’，显然共有4^K个不同的字符串，你要给每个字符串都分配一种颜色，不同的字符串可以分配相同的颜色，颜色分配过程是由你来决定的。

奶牛Bessie是这个游戏的玩家，首先Bessie会输入一个长度是K的字符串S（每个字符也是‘A’或‘B’或‘C’或‘D’），然后Bessie每一步操作是如下两种选择之一：

  • 1、 交换当前字符串S的相邻的两个字符。注意，第一个字符和最后一个字符不算相邻，即S不能看成一个环。

  • 2、如果当前字符串S含有子串b[i]，那么可以把该子串替换成字符串c[i]。其中b数组和c数组都是字符串数组，作为输入数据给出来的。

如果Bessie能够通过上面的操作，使得从字符串S出发，通过若干次操作之后，能够变成字符串T（T和S是不同的字符串），且字符串T和字符串S是相同颜色的，那么Bessie就会胜利了。

作为游戏设计师的你，你的目的是想让Bessie永远都不可能胜利，也就是说无论Bessie输入的字符串S是什么，都不可能胜利。

显然，这与你对4^K个不同的字符串如何分配颜色是非常重要的。现在的问题是，你至少需要多少种不同的颜色，才能使得Bessie永远不可能胜利。

简要题意：

有一个字符串 每次可以将这个字符串的一个子串变成另一个子串 然后每次变换后不能变成相同颜色 然后字符串可以随意排列 求最少的颜色方案数

思考：

注意到可以随便排列 因此原来的字符串已经不重要了 记一个数组 \(id_{a,b,c,d}\) 表示状态即可

因为 \(a+b+c+d=n\) 所以可以去掉一维 记\(id_{a,b,c}\) 即可

然后思考一下 什么是变成另一个子串？实际上不就是一个状态变换：

\[id_{a,b,c,d}\to id_{a-a1+a2,b-b1+b2,c-c1+c2,d-d1+d2}\space (a>a1,b>b1,c>c1,d>d1) \]

状态转移有什么用呢 如果是无环的直接 \(dp\) 即可 但是有可能有环

所以我们可以直接抽象出一个图 然后转移就是连边

那么这个图里面怎么跑出最少的颜色呢？总不可能每过一个点就染色吧？

实际上可以这样想：因为一个点到另一个点必须有不同颜色 但是到了访问过的点就无需再次染色

什么情况下会有访问过的点呢？一个点能经过另一条有向边回来

诶？这不就是强连通分量吗？

然后就可以缩点成一个 DAG

DAG 就能跑拓补啦！

答案就是经过点值最大的路径

好像遗漏了一个点：怎么求点值？

先求原点值 其实就是这个问题：

  • 给你 \(a\) 个 \(A\), \(b\) 个 \(B\), \(c\) 个 \(C\), \(d\) 个 \(D\),有多少中不同的排列顺序？

那么也非常容易求，就是\(C(a+b+c+d,a)\times C(b+c+d,b)\times C(c+d,c)\times C(d,d)\)

很容易理解 因为 \(A\) 的排列顺序没有区别 所以只要想怎么放就行

一个强连通分量的价值就是它的点权和 然后就可以 dp 了

为什么卡了这么久没过？还不是因为初始化不彻底就 WA 的离谱

Code

#include<bits/stdc++.h>
#define ll long long
#define N 65
using namespace std;
int g;
int m,n,c;
ll C[N][N];
string s;
int s1[N][4],s2[N][4];
ll f[N*N*N],w[N*N*N],ans;
int head[N*N*N],tot=1;
int dfn[N*N*N],col[N*N*N],low[N*N*N],cnt,colcnt;
int q[N*N*N],l,r;
int in[N*N*N],ids,id[N][N][N];
pair<int,int> E[N*N*N*N];
struct edge{
	int fr,to,next;
}e[N*N*N*N];
void add(int u,int v)
{
	e[tot]=(edge){u,v,head[u]};
	head[u]=tot++;
}
void tarjan(int x)
{
	low[x]=dfn[x]=++cnt;
	q[++r]=x;
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(col[to]) continue;
		if(!dfn[to]) tarjan(to);
		low[x]=min(low[x],low[to]);
	}
	if(low[x]==dfn[x])
	{
		colcnt++;
		while(q[r+1]!=x)
			col[q[r--]]=colcnt;
	}
}
void init()
{
	ids=cnt=colcnt=ans=l=r=0;
	tot=1;
	memset(s1,0,sizeof(s1));
	memset(s2,0,sizeof(s2));
	memset(id,0,sizeof(id));
	memset(f,0,sizeof(f));
	memset(w,0,sizeof(w));
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(col,0,sizeof(col));
	memset(q,0,sizeof(q));
	memset(in,0,sizeof(in));
}
void Sort()
{
	l=r=0;
	for(int i=1;i<=colcnt;i++)
		if(in[i]==0) q[++r]=i;
	while(l<r)
	{
		int x=q[++l];
		f[x]=max(w[x],f[x]);
		for(int i=head[x];i;i=e[i].next)
		{
			int to=e[i].to;
			in[to]--;
			if(in[to]==0) q[++r]=to;
			f[to]=max(f[to],f[x]+w[to]);
		}
		ans=max(ans,f[x]);
	}
}
int main()
{
	C[0][0]=1;
	for(int i=1;i<=40;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	scanf("%d",&g);
	while(g--)
	{
		scanf("%d%d",&n,&m);
		c=(n+1)*(n+1)*(n+1)+5;
		init(); 
		for(int i=1;i<=m;i++)
		{
			cin>>s;
			for(int j=0;j<s.size();j++)
				s1[i][s[j]-'A']++;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>s;
			for(int j=0;j<s.size();j++)
				s2[i][s[j]-'A']++;
		}
		for(int i=0;i<=n;i++)
		for(int j=0;j<=n-i;j++)
		for(int k=0;k<=n-i-j;k++)
		{
			id[i][j][k]=++ids;
			f[ids]=C[n][i]*C[n-i][j]*C[n-i-j][k];
		}
		for(int i=0;i<=n;i++)
		for(int j=0;j<=n-i;j++)
		for(int k=0;k<=n-i-j;k++)
		{
			int now=id[i][j][k];
			for(int l=1;l<=m;l++)
			if(i>=s1[l][0]&&j>=s1[l][1]&&k>=s1[l][2]&&n-i-j-k>=s1[l][3])
			{
				int to=id[i-s1[l][0]+s2[l][0]][j-s1[l][1]+s2[l][1]][k-s1[l][2]+s2[l][2]];
				E[tot]=make_pair(now,to);
				add(now,to);
			}
		}	
		for(int i=1;i<=ids;i++)
			if(!dfn[i]) tarjan(i);
		for(int i=1;i<=ids;i++)
			w[col[i]]+=f[i];
		int tots=tot;
		tot=1;
		fill(head+1,head+1+ids+1,0);
		fill(f+1,f+1+c+ids,-1);
		for(int i=1;i<tots;i++)
		{
			int u=e[i].fr,v=e[i].to;
			if(col[u]!=col[v])
				add(col[u],col[v]),in[col[v]]++;
		}
			
		Sort();
		printf("%lld\n",ans);
	}
	return 0;
}

标签：int,8.11,memset,low,字符串,now,小结,id,模拟
From： https://www.cnblogs.com/g1ove/p/17625811.html

相关文章

  • 交换机M-LAG知识小结
    M-LAG（MultichassisLinkAggregationGroup）即跨设备链路聚合组，是一种实现跨设备链路聚合的机制，将一台设备与另外两台设备进行跨设备链路聚合，从而把链路可靠性从单板级提高到了设备级，组成双活系统M-LAG的作用：1、增加带宽：将成员交换机的多条物理链路配置成一个聚合组，提高交换机的上行......
  • 8.7-8.11读后感
    这个星期对于大数据的学习，由于hbase一直弄不对，不知道为什么一直报错，连接都没有问题，不管是用服务端hbaseshell命令还是用JavaApi连接，都能链接成功，但是一到使用命令，查看命名空间，创建表格那些，就开始报错，这个星期一直再弄这个，也没什么太大的进展，另外就是我们的物联网比赛进入了分区......
  • 【考后总结】8 月 CSP-S 模拟赛 4
    CSP模拟19ItstartedoffsowellTheysaidwemadeaperfectpairIclothedmyselfinyourgloryandyourloveHowIlovedyouHowIcriedTheyearsofcareandloyaltyWerenothingbutashamitseemsTheyearsbeliewelivedthelieIloveyou'......
  • CSP模拟-19
    前言emm.....考场其实想到T2正解的思路了，但是不会优化，导致有些拉胯少了50分。还有就是说数学题我是真不行，向上次\(fengwu\)的筛我不会，这会最简单的容斥想这么老半天学这么老半天都不会，着实是有些废物了。T1十年之约一道很简单的数学题QAQ，但我就是不会，我真服了。首先对于\(......
  • Linux磁盘故障,模拟故障及解决思路方法
    每个分区起始位置都有一个inod表索引节点表(类似于目录表)每一个文件都对应一个编号称为索引节点，如果这个空间文件数太多了，记满了，就说明索引节点表耗尽。故障1 该分区不能正常读写或者说只能读不能写了但是又没有满，就代表文件系统有问题，文件系统有问题需要进行修复命令：故障2：索引......
  • 8.11 格路计数与乐子题
    邮戳拉力赛好题啊！写了一个错误的解，但仍未知道错在哪里。容易发现路径一定是：向上走，到一个点后向下走，走到一个点后再向上走，以此类推。往下走时，可以自由选择是下行时盖章还是上行时盖章，这也是一直往上走不最优的理由。从\(0\)向上走到\(n+1\)的路径长度可以最后再加，不用考虑......
  • 2023.8.11
    今天早上起来，还是和往常一样打球，还有几天就离开了，只能假期回来再和兄弟们一起玩了，下午回家有些无聊了，问兄弟们还来不来，他们答应我出来打几个小时，太好了，终于不用在家里待着了，下午打到56点钟就回家了，爸妈还没回来，赶紧把饭蒸好，舒服了，晚上有些累了，躺着突然就睡着了，半夜起来写下这些，明......
  • 8.11话闲——记一次“下雨”（内含传统艺能）
    气象局刚一发黄色预警，很快啊，教育局就发通知停一切教学活动了......
  • 2023.8.11 模拟赛
    A询问\(L\lei,j\leR\),其中\(\gcd(i,j)\not=1,i,j\)的对数。莫反先求出\(gcd(i,j)\not=1\)的对数，然后再直接调和级数暴力删去\(i,j\)是倍数的对数即可。BP4334[COI2007]Policija考虑建立圆方树。圆方树是怎么样的呢？圆方树是对于每个点双，都建立一个方点，然后......
  • 2023.8.11 周五：保留小数点后几位
    1#include<iostream>2#include<iomanip>3intmain()4{5intn;6cin>>n;7doublePI=3.14159265358979;8cout<<setprecision(n)<<fixed<<PI<<endl;9return0;10}1......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99