CF #639(div.2)

程序员文章站 2024-03-05 11:33:00

...

文章目录

A. Puzzle Pieces
B. Card Constructions
C. Hilbert's Hotel
D. Monopole Magnets
E. Quantifier Question
F. Résumé Review

A. Puzzle Pieces

题意：

CF #639(div.2)

给定如上这种图形，问能否用这种图形组成类似矩阵的图形

分析： 很直观的可以看出，单个图形有三个凸部和一个凹部，所以只能组成

$1 \times n$
$n \times 1$
$2 \times 2$

这三种形式的图形

代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,a,b;
	cin>>t;
	while(t--)
	{
		cin>>a>>b;
		if(a==1||b==1) cout<<"YES\n";
		else if(a==2&&b==2) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

B. Card Constructions

题意：

CF #639(div.2)

第一个图形由两张卡片组成，第二个图形由七张卡片组成，依次如上进行下去，现在给 n 张卡片，求最少可以组成多少个图形，要求图形尽量往高了选

分析： 观察一下可以发现第 m 个图形的卡片数即 $(3*\sum_{i=1}^{m}i)-m$ ，等价于 $n \times (n+1)/2 \times 3-m$ ，知道公式的话就可以二分了

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1E5+10;
ll a[N];
int m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	//打表稍微快些
	for(ll i=1;;i++)
	{
		a[i]=i*(i+1)/2*3-i;
		m=i;
		if(a[i]>1e9) break;
	}
	int t;
	ll n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		int ans=0,xb=m;
	    while(n>1)
	    {
	    	int xb=upper_bound(a+1,a+m+1,n)-a;
		    xb--;
		    if(xb) n-=a[xb],ans++;
		}
		cout<<ans<<'\n';
	}
}

C. Hilbert’s Hotel

题意： 0~n-1 共 n 个房间每个房间都有一个客人，现在给定长度为 n 的数组 a，把原第 k 个房间的客人移到第 $(k+a_k)~mod~n$ 个房间，问移动完所有的客人之后是否满足所有房间依旧只有一个客人

分析： 模拟

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2E5+10;
ll a[N];
bool vis[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++) cin>>a[i],vis[i]=0;
		int flag=0;
		for(int i=0;i<n;i++)
		{
			int nk=((i+a[i])%n+n)%n;
			if(vis[nk]) {flag=1;break;}
			vis[nk]=1;
		}
		if(flag) cout<<"NO\n";
		else cout<<"YES\n";
	}
}

D. Monopole Magnets

题意： $n \times m$ 的矩阵中只包含 ‘.’ 和 ‘#’ 两种元素，现在要求你在矩阵上摆 N 和 S 两种磁极，同一个点可以摆放多个，首先：

原则Ⅰ：若 N 和 S 处于同一列或者同一行，则 N 可以向 S 移动一个单位，S 的位置不可改变

在这个原则的基础上，你的摆放需要满足下列条件

矩阵中每行每列都至少有一个 S 磁极
若矩阵中某个点是 ‘#’ ，则矩阵中一定有 N 磁极可以通过原则Ⅰ到达这个点
若矩阵中某个点是’.’ ，则矩阵中所有的 N 磁极都无法到达这个点

问在满足上述所有条件的情况下是否有解，无解输出 -1，若有解则输出需要的最少的 N 磁极数量

分析： 题目有点绕，不过结合样例可以想到任意一行或者一列出现 ‘#’ 的话必须是连在一起的，否则的话讨论一下

若某一行两个 ‘#’ 之间有 ‘.’ ，则为了不违反条件3，这一行就不能有 S 磁极，但这样就违反了条件1，产生矛盾；反之为了满足条件1就无法同时满足条件3

所以此类情形无解

同时如果出现了全是 ‘.’ 的行则至少要有一列亦全为 ‘.’ 才行(反之亦然)，因为这一行至少要放一个 S 磁极，若放置在有 ‘#’ 的一列，则会违反条件3

无解的情况就可以判断出来了，有解的话需要最少的 N 磁极数量很简单，就是计算一下矩阵中有多少个连通块(通过上下左右移动)，你把所有 ‘#’ 都放置 S 磁极，那么一个连通块就只需要一个 N 磁极就可以移动到这个连通块的所有 '# ’ 区域了

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1000+10;
int n,m;
char s[N][N];
bool vis[N][N];
int r[]={1,-1,0,0},c[]={0,0,1,-1};
void dfs(int x,int y)
{
	vis[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int a=x+r[i],b=y+c[i];
		if(a<0||a>=n||b<0||b>=m) continue;
		if(vis[a][b]) continue;
		if(s[a][b]=='#') dfs(a,b);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i];
	int cnt=0;
	for(int i=0;i<n;i++)
	  for(int j=0;j<m;j++)
	    if(s[i][j]=='#')
	      cnt++;
    if(cnt==0) cout<<"0",exit(0);
    if((n==1||m==1)&&cnt!=n*m) cout<<"-1",exit(0); 
	int flag=0,kr=0,kc=0;
	for(int i=0;i<n;i++)
	{
		int xb=0;
		while(xb<m&&s[i][xb]=='.') xb++;
		if(xb==m) {kr++;continue;}
		while(xb<m&&s[i][xb]=='#') xb++;
		if(xb==m) continue;
		while(xb<m&&s[i][xb]=='.') xb++;
		if(xb<m) {flag=1;break;}
	} 
	if(flag) cout<<"-1",exit(0);
	
	for(int i=0;i<m;i++)
	{
		int xb=0;
		while(xb<n&&s[xb][i]=='.') xb++;
		if(xb==n) {kc++;continue;}
		while(xb<n&&s[xb][i]=='#') xb++;
		if(xb==n) continue;
		while(xb<n&&s[xb][i]=='.') xb++;
		if(xb<n) {flag=1;break;}
	} 
	if(flag) cout<<"-1",exit(0); 
	if(!kr&&kc || kr&&!kc) cout<<"-1",exit(0);  
	
	int ans=0;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	  if(s[i][j]=='#'&&!vis[i][j])
	  	dfs(i,j),ans++;  //统计连通块数量
	cout<<ans;
}

E. Quantifier Question

题意： 现在有 n 个数需要满足 m 个条件

CF #639(div.2)

给出所有的 $(j_i,k_i)$ ，现在你需要为所有的 $x_i$ 设置量词 $\forall$ 或 $\exists$ ，使得存在这样的数组 x， m 个条件都得到满足，判断顺序需要按照数组 x 的下标，例如：若下标 $(j_i,k_i)$ 在之前的判断都未曾出现过，则 $min(j_i,k_i)$ 在前， $max(j_i,k_i)$ 在后 (所以前者可以为 $\forall$ 或 $\exists$ ，后者只能为 $\exists$ )

问在满足条件的情况下，最多可以出现多少个全称量词 $\forall$ ，并给出具体方案

分析： 题目挺绕，把所有 $(x_{j_i},x_{k_i})$ 看成一条有向边构图，不难想出如果图中存在环则无解，判断顺序需要按照数组下标，所以我们第一个肯定是找点 1，它的量词肯定可以设成全称量词 $\forall$ ，那么接下来，对于点 1 能影响的所有点，我们只能设成存在量词 $\exists$ ，它能影响的所有点即从点1按正方向能到达的所有点和按反方向能到达的所有点，所以从点 1 走一遍正图和反图就可以了。

然后推广到整个图，就是，从小到大遍历所有没有访问过的点，把这个点标记为全称量词，然后沿此点正图反图dfs两遍，所有走过的点标记为已访问

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2E5+10;
vector<int>e[N],E[N];
int n,m,in[N];
queue<int>q;
bool tp()  //拓扑判环
{
	int cnt=0;
	for(int i=1;i<=n;i++)
	    if(in[i]==0) q.push(i);
	while(!q.empty())
	{
		int u=q.front(); q.pop(); cnt++;
		for(auto v:e[u])
		{
			in[v]--;
			if(in[v]==0) q.push(v);
		}
	}
	if(cnt==n) return true;
	return false;
}
int ANS[N];
bool vis1[N],vis2[N];

void dfs1(int u)
{
	vis1[u]=1;
	for(auto v:e[u])
	{
		if(vis1[v]) continue;
		
		dfs1(v);
	}
}

void dfs2(int u)
{
	vis2[u]=1;
	for(auto v:E[u])
	{
		if(vis2[v]) continue;	
		dfs2(v);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int u,v; cin>>u>>v;
		e[u].push_back(v);  //正图
		E[v].push_back(u);  //反图
		in[v]++;
	}
    if(!tp()) cout<<"-1",exit(0);
    
    int ans=0;
    for(int i=1;i<=n;i++)
    {
    	if(!vis1[i]&&!vis2[i])
		{
		    ans++;
			ANS[i]=1;	
		}
		if(!vis1[i]) dfs1(i);
		if(!vis2[i]) dfs2(i);
	}
	
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++)
        if(ANS[i]) cout<<'A';
        else cout<<'E';
}

F. Résumé Review

题意： 给定大小为 n 的数组 a 和一个整数 k，现在要求你构造大小亦为 n 的数组 b ，满足下列条件

$b_i<=a_i$
$\sum_{i=1}^{n}b_i=k$
满足条件1,2 的情况下使得 $f=\sum_{i=1}^{n}b_i \times (a_i-b_i^2)$ 最大

求具体方案

分析： 对于某一个 $b_i$ 和 $a_i$ ， $b_i$ 增加 1 的贡献是
$\bigtriangleup value=b_i \times (a_i-b_i^2)-(b_i-1) \times (a_i-(b_i-1)^2)=a_i-3 \times b_i^2+3 \times b_i-1$
可以看出，贡献从 1 开始是单调递减的，所以我们可以二分贡献值的下界，找到每个 $a_i$ 对应最大的 $b_i$ ，并累加判断是不是小于 k

ll check(double m)
{
	for(int i=0;i<n;i++) 
	    if(a[i]-m-1<=0) b[i]=0;
	    else b[i]=min(a[i],(ll)(sqrt((a[i]-m-1)/3)));
	ll res=0;
	for(int i=0;i<n;i++) res+=b[i];
	return res; 
}	

ll l=-INF,r=INF;
while(r-l>1)
{
    ll mid=(l+r)>>1;
    if(check(mid)<=k) r=mid;
    else l=mid+1;
}

然后如果 $\sum_{i=1}^{n}b_i<k$ ，那么就一个优先队列维护补充剩余的就可以了

for(int i=0;i<n;i++)
	    if(b[i]<a[i]) 
	        que.push(P(f(b[i]+1,i),i));
	while(k--)
	{
		P p=que.top(); que.pop();
		b[p.sd]++;
		if(b[p.sd]<a[p.sd]) que.push(P(f(b[p.sd]+1,p.sd),p.sd));
	}

完整代码：

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define sd second
#define ll long long
#define P pair<ll,int>
const int N = 1E5+10;
const ll INF = 4E18;

int n;
ll k,a[N],b[N];

ll check(double m)
{
	for(int i=0;i<n;i++) 
	    if(a[i]-m-1<=0) b[i]=0;
	    else b[i]=min(a[i],(ll)(sqrt((a[i]-m-1)/3)));
	ll res=0;
	for(int i=0;i<n;i++) res+=b[i];
	return res; 
}

ll f(ll b,ll xb)
{
	return a[xb]-1-3*b*b+3*b;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
	ll l=-INF,r=INF;
	while(r-l>1)
    {
    	ll mid=(l+r)>>1;
    	if(check(mid)<=k) r=mid;
    	else l=mid+1;
	}
	check(r);
	for(int i=0;i<n;i++) k-=b[i];
	priority_queue<P>que;
	for(int i=0;i<n;i++)
	    if(b[i]<a[i]) 
	        que.push(P(f(b[i]+1,i),i));
	while(k--)
	{
		P p=que.top(); que.pop();
		b[p.sd]++;
		if(b[p.sd]<a[p.sd]) que.push(P(f(b[p.sd]+1,p.sd),p.sd));
	}
	for(int i=0;i<n;i++) cout<<b[i]<<' ';
}

CF #639(div.2)

文章目录

A. Puzzle Pieces

B. Card Constructions

C. Hilbert’s Hotel

D. Monopole Magnets

E. Quantifier Question

F. Résumé Review

CF #639(div.2)

CF #627(div.3)

【洛谷_CF261D】Maxim and Increasing Subsequence

CF838C（博弈+FWT子集卷积+多项式ln、exp）

CF-Round #630-div2-D题

CF-Round #633-div2-E题&div1C

CF-Round #633-div2-D题&div1C

CF-Round #631-div2-D题&div1B题

题解 CF1391D 【505】

CF 896C - Willem, Chtholly and Seniorious （珂朵莉树）