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;
}