526互联

CF957 Codeforces Round 472 (rated, Div. 2, based on VK Cup 2018 Round 2)

发布时间 2023-09-27 22:20:24作者: Zhou_JK

CF957A Tritonic Iridescence

如果原序列中有两个相同的字符，显然不合法。

如果开头或者结尾为 ?，或者有两个连续的 ?，或者一个 ? 两边的字符不同显然合法。

否则一定不合法。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int n;
char s[N];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		if(s[i]!='?'&&s[i]==s[i-1])
		{
			printf("No");
			return 0;
		}
	if(s[1]=='?'||s[n]=='?')
	{
		printf("Yes");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='?'&&s[i-1]=='?')
		{
			printf("Yes");
			return 0;
		}
		if(s[i]=='?'&&s[i-1]==s[i+1])
		{
			printf("Yes");
			return 0;
		}
	}
	printf("No");	
	return 0;
}

CF957B Mystical Mosaic

枚举 # 所在的列，将这列上有 # 的行拿出来，这些行的字符必须相同，否则就不合法。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=55;
int n,m;
string s[N];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>s[i];
	for(int j=0;j<m;j++)
	{
		vector<string>pos;
		for(int i=0;i<n;i++)
			if(s[i][j]=='#') pos.emplace_back(s[i]);
		for(size_t i=1;i<pos.size();i++)
			if(pos[i]!=pos[i-1])
			{
				printf("No");
				return 0;
			}
	}
	printf("Yes");
	return 0;
}

CF957C Three-level Laser

对于确定的 \(i\)，我们要使 \(\frac{E_k-E_j}{E_k-E_i}=1-\frac{E_j-E_i}{E_k-E_i}\) 最大，我们要使 \(E_k\) 尽可能大，\(E_j\) 尽可能接近 \(E_i\)。那么就可以枚举 \(i\)，双指针扫一扫即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m;
int a[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	double ans=-1;
	for(int i=1,k=1;i<=n;i++)
	{
		int j=i+1;
		while(k+1<=n&&a[k+1]-a[i]<=m) k++;
		if(i<j&&j<k) ans=max(ans,(double)(a[k]-a[j])/(a[k]-a[i]));
	}
	printf("%.10lf",ans);
	return 0;
}

CF957D Riverside Curio

令 \(a_i\) 表示第 \(i\) 天总共画了多少条线。则 \(a_i\) 需要满足的条件为：

  • 对于 \(1\leq i\leq n\)，\(a_i\ge m_i+1\)；
  • 对于 \(1\le i \le n-1\)，\(a_{i+1}-1\le a_i\le a_{i+1}\)。

然后问题变成了最少用多少次操作使得 \(a\) 满足上述限制，这个从前往后扫一遍然后在从后往前扫一遍就好了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n;
int m[N];
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&m[i]);
	for(int i=1;i<=n;i++)
		a[i]=m[i]+1;
	for(int i=1;i<=n;i++)
		if(a[i]<a[i-1]) a[i]=a[i-1];
	for(int i=n;i>=1;i--)
		if(a[i]<a[i+1]-1) a[i]=a[i+1]-1;
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=a[i]-m[i]-1;
	printf("%lld",ans);
	return 0;
}

CF957E Contact ATC

令 \(tx_i\) 表示风速为 \(w\) 需要的时间，\(ty_i\) 表示风速为 \(-w\) 需要的时间。则对于点对 \((i,j)\)，它们能够相遇的条件为 \((tx_i-tx_j)(ty_i-ty_j)\le 0\)。直接算好像有点难算，考虑计算不合法的方案数即为 \((tx_i-tx_j)(ty_i-ty_j)< 0\) 的方案数，这个相当于一个二维偏序问题。

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
int n,w;
int x[N],v[N];
pair<double,double>p[N];
int tx[N],ty[N];
struct BIT
{
	int C[N];
	int lowbit(int x)
	{
		return x&-x;
	}
	void add(int x,int y)
	{
		for(int i=x;i<=n;i+=lowbit(i))
			C[i]+=y;
		return;
	}
	int getsum(int x)
	{
		int res=0;
		for(int i=x;i>0;i-=lowbit(i))
			res+=C[i];
		return res;
	}
}T;
vector<int>pos[N];
int main()
{
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&v[i]);
	for(int i=1;i<=n;i++)
		p[i]={(double)-x[i]/(v[i]+w),(double)-x[i]/(v[i]-w)};
	sort(p+1,p+n+1);
	static double b[N];
	int tot=0;
	for(int i=1;i<=n;i++)
		b[++tot]=p[i].second;
	sort(b+1,b+tot+1);
	tot=unique(b+1,b+tot+1)-b-1;
	for(int i=1;i<=n;i++)
		ty[i]=lower_bound(b+1,b+tot+1,p[i].second)-b;
	tot=0;
	for(int i=1;i<=n;i++)
		b[++tot]=p[i].first;
	sort(b+1,b+tot+1);
	tot=unique(b+1,b+tot+1)-b-1;
	for(int i=1;i<=n;i++)
		tx[i]=lower_bound(b+1,b+tot+1,p[i].first)-b;
	for(int i=1;i<=n;i++)
		pos[tx[i]].emplace_back(ty[i]);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int y:pos[i])
			ans+=T.getsum(y-1);
		for(int y:pos[i])
			T.add(y,1);
	}
	printf("%lld",1LL*n*(n-1)/2-ans);
	return 0;
}