「周练」Codeforces Round #530 (Div. 2)
比赛网址链接：Codeforces Round #530 (Div. 2)
A. Snowball (模拟)题意
一个重量为 www 的雪球从高度 hhh 滚下，每下降一单位，重量的增加量为当前高度，过程有两个石头，雪球经过石头重量的减少量为石头的重量，问雪球到达地面时的重量
思路
按照题意模拟即可，注意过程重量不会减成负值
代码
#include
#include
#include
#include
#include
#include
#define ft first
#define sd second
#define nul string::npos
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=2e5+7;
const int inf=0x3f3f3f3f;
int w,h,u1,u2,d1,d2;
int main()
{
cin>>w>>h>>u1>>d1>>u2>>d2;
int pos=h,nw=w;
while(pos){
nw+=pos;
if(pos==d1){
nw-=u1;
nw=max(nw,0);
}
else if(pos==d2){
nw-=u2;
nw=max(nw,0);
}
pos--;
}
cout<<nw<<'\n';
return 0;
}
B. Squares and Segments (数学)
题意
给一个数 nnn，找出两个数，使得它们的乘积不小于 nnn，要求最小化这两个数的和
思路
开始读错题了，以为要用这 nnn 个小正方形组成一个矩形，后来发现不是，那就好办了，最小化两个数的和，肯定这两个数要比较接近，那就不断增大两个数，知道它们的乘积不小于 nnn 即可
代码
#include
#include
#include
#include
#include
#include
#define ft first
#define sd second
#define nul string::npos
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=2e5+7;
const ll inf=1e15;
ll n;
int main()
{
cin>>n;
ll sum=n+1;
ll l=1,r=1;
while(l*rr)r++;
else l++;
}
cout<<l+r<<'\n';
return 0;
}
C. Postcard (贪心)
题意
一个字符串里有小写字母、∗*∗ 符号、??? 符号，这两种符号都可以将它们前方的字母删除、保留，不同的是 ∗*∗ 符号还可以无穷多次复制其前面的字母，问这个串能否构造出一个长度为 kkk 的串
思路
首先考虑不存在的情况，那就只有两种情况，一是字符串里没有 ∗*∗ 符号，但 kkk 太大，二是 kkk 太小，能删的全删也构造不出长度为 kkk 的。
之后就分类讨论就好，根据原串我们统计的信息，如果 kkk 比较大，那就确定好要复制的字母和个数，剩下的字母都保留即可，如果 kkk 比较小，那就确定要删除的字母个数，先删够，剩下的字母都保留即可
代码
#include
#include
#include
#include
#include
#include
#define ft first
#define sd second
#define nul string::npos
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=2e5+7;
const ll inf=1e15;
string s,ans;
int f1,f2,id=-1;
int n,sum[5];//sum[0]有意义的?和*个数、sum[1]无意义的*和?个数、sum[2]字母个数
int main()
{
cin>>s>>n;
int len=s.length();
for(int i=0;i=0&&(s[i-1]>='a'&&s[i-1]=0&&(s[i-1]>='a'&&s[i-1]sum[2]&&!f2)||(n=sum[3]){//太多的情况
ans="";
int ln=n-sum[2];
for(int i=0;i='a'&&s[i]<='z')ans+=s[i];
}
for(int i=1;i<=ln;i++)ans+=s[id-1];
for(int i=id+1;i='a'&&s[i]<='z')ans+=s[i];
}
cout<<ans<<'\n';return 0;
}
int sc=sum[2]-n;
for(int i=0;i='a'&&s[i]<='z'){
if(i+1<len&&(s[i+1]=='*'||s[i+1]=='?')){
if(sc){
sc--;
}
else ans+=s[i];
i++;
}
else {
ans+=s[i];
}
}
else continue;
}
cout<<ans<<'\n';
return 0;
}
D. Sum in the tree (dfs+贪心)
题意
现在有一棵树，根为 111，iii 号结点的权值为 aia_iai，sis_isi 为 iii 号结点到根路径上的总权值，现在只知道深度为奇数的结点的 sis_isi 值，让你推出 所有结点的 aia_iai 值，要求它们的 aia_iai 总和最小
思路
我们会发现一个规律就是，给越靠近根的结点赋值越大，它们的子孙赋值就越小，那么 aia_iai 总和就会越小，所以我们要想办法把靠近根的结点赋上尽可能大的值，离根越远的赋尽可能小的值
对于 −1-1−1 的情况肯定就是对于某一个结点，存在一个子孙结点的 sis_isi 值比其本身的要小，因为 aia_iai 非负，所以从根到叶子的路径 sis_isi 值肯定不会递减。然后我们尝试还原深度为偶数的每个点的 sis_isi 值。
根据前面的分析，很容易得出 su=min(sv)(v是u的儿子)s_u=min(s_v)(v是u的儿子)su=min(sv)(v是u的儿子)，也就是儿子共享的部分，这部分给父亲，让父亲赋更大的值，如果叶子所在层也为偶数层的话其 aia_iai 值显然赋 0 最优，所以其 sis_isi 的值应和父亲的相同，知道了所有结点的 sis_isi 值，aia_iai 就很好求了
代码
#include
#define ft first
#define sd second
#define pb push_back
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
int n,flag=0;
ll a[maxn],s[maxn];
int dep[maxn];
vector g[maxn];
ll dfs(int u,int fa,ll ma){//ma为父亲的s[]值
dep[u]=dep[fa]+1;
ll qq=inf;
if(s[u]!=-1){
if(s[u]<ma)flag=1;
else ma=s[u];
}
for(auto v: g[u]){
if(v==fa)continue;
qq=min(dfs(v,u,ma),qq);
}
if(s[u]==-1&&qq!=inf)s[u]=qq;//是否为叶子
if(s[u]==-1&&qq==inf)s[u]=ma;
return s[u];
}
void _dfs(int u,int fa,ll ma){
a[u]=s[u]-ma;
ma=s[u];
for(auto v: g[u]){
if(v==fa)continue;
_dfs(v,u,ma);
}
}
int main()
{
scanf("%d",&n);
for(int u=2,v;u<=n;u++){
scanf("%d",&v);
g[u].pb(v);
g[v].pb(u);
}
for(int i=1;i<=n;i++)scanf("%lld",&s[i]);
dfs(1,0,0);
if(flag){
puts("-1");return 0;
}
_dfs(1,0,0);
ll sum=0;
for(int i=1;i<=n;i++){
sum+=a[i];
}
cout<<sum<<'\n';
return 0;
}
E. Nice table (找规律+模拟)
题意
一个 n×mn×mn×m 矩阵，要求最小的修改次数使得矩阵的所有 2×22×22×2 的子矩阵都包含 A,T,G,CA,T,G,CA,T,G,C 四个字母
思路
找规律会发现有两种情况：
1.每行都是两个固定字符交替组成，且相邻两行的字符交集为空
例如：
2.每列都由两个固定字符交替组成，且相邻两列的字符交集为空
例如：
那就枚举交替的行或列，找出替换最小的那组
代码
#include
#define ft first
#define sd second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=3e5+7;
const double inf=1e18;
int n,m,hid,lid;
string s[maxn];
char str[6][2]={{'A','T'},{'A','C'},{'A','G'},{'C','T'},{'T','G'},{'C','G'}};
int h[6][maxn][2],hsum[6];
int l[6][maxn][2],lsum[6];
string ans[maxn];
void solve(int op,int id){
if(!op){//行
for(int i=0;i<n;i++){
if(h[id][i][0]!=-1){
for(int j=0;j<m;j++){
printf("%c",str[(i&1)?5-id:id][j&1]);
}
}
else {
for(int j=0;j<m;j++){
printf("%c",str[(i&1)?5-id:id][!(j&1)]);
}
}
printf("\n");
}
return;
}
for(int i=0;i<m;i++){//列
if(l[id][i][0]!=-1){
for(int j=0;j<n;j++){
ans[j]+=str[(i&1)?5-id:id][j&1];
}
}
else {
for(int j=0;j<n;j++){
ans[j]+=str[(i&1)?5-id:id][!(j&1)];
}
}
}
for(int i=0;i<n;i++)cout<<ans[i]<>n>>m;
for(int i=0;i>s[i];
memset(h,-1,sizeof(h));
memset(l,-1,sizeof(l));
for(int i=0;i<6;i++){//枚举行
int sum=0;
for(int j=0;j<n;j++){
int a=0,b=0;
for(int k=0;k=b)h[i][j][1]=b,sum+=b;//逆序
else h[i][j][0]=a,sum+=a;//正序
}
hsum[i]=sum;
if(hsum[hid]>hsum[i])hid=i;//保留最优解下标
}
for(int i=0;i<6;i++){//枚举列
int sum=0;
for(int j=0;j<m;j++){
int a=0,b=0;
for(int k=0;k=b)l[i][j][1]=b,sum+=b;//逆序
else l[i][j][0]=a,sum+=a;//正序
}
lsum[i]=sum;
if(lsum[lid]>lsum[i])lid=i;//保留最优解下标
}
if(hsum[hid]<lsum[lid])solve(0,hid);//行
else solve(1,lid);//列
return 0;
}
F. Cookies (待补)
题意
思路
代码
二. 二分练习
A. Aggressive cows (最大化最小值)
题目链接
POJ 2456
题意
xxx 坐标轴有 nnn 个牛舍，现在给 mmm 头牛分配牛舍，问怎样分配使得任意两头牛的距离最大化
思路
二分一下任意两头牛的最小距离，从前往后贪心的填即可
代码
#include
#include
#include
#include
#include
#define ft first
#define sd second
#define nul string::npos
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=2e5+7;
const int inf=0x3f3f3f3f;
int t,n,c;
int a[maxn];
bool judge(int x){
int pos=a[0];
int co=1;
for(int i=1;i<n;i++){
if(a[i]-pos=c;
}
int main()
{
cin>>n>>c;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
int l=0,r=inf,ans=1;
while(l>1;
if(judge(m)){
l=m+1;ans=m;
}
else r=m-1;
}
cout<<ans<<'\n';
return 0;
}
B. String Game (二分下标)
题目链接
CodeForces - 779D
题意
一个字符串 sss，现在有一个删除序列，问按照这个删除序列执行，最多执行几次，原序列仍有 ttt 字符串的子序列
思路
二分这个删除序列的下标，看以这个下标为终点对 sss 串进行删除，剩下的串能否找出一个子序列为 ttt
代码
#include
#include
#include
#include
#include
#include
#define ft first
#define sd second
#define nul string::npos
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=2e5+7;
const int inf=0x3f3f3f3f;
int n,c,len1,len2;
int a[maxn];
bool vis[maxn];
string s,t;
bool judge(int m){
ms(vis,0);
int len=min(m,len1);
for(int i=1;i<=len;i++){
vis[a[i]]=1;
}
string no="";
for(int i=0;i<len1;i++){
if(!vis[i+1]){
no+=s[i];
}
}
len=no.length();
int l=0;
for(int i=0;i>s>>t;
len1=s.length();
len2=t.length();
for(int i=1;i<=len1;i++)scanf("%d",&a[i]);
int l=0,r=len1+1,ans=0;
while(l>1;
if(judge(m)){
l=m+1,ans=m;
}
else r=m-1;
}
ans=min(ans,len1);
cout<<ans<<'\n';
return 0;
}
C. Delivering Carcinogen (二分+计算几何)
题目链接
CodeForces - 199E
题意
有一颗行星 PPP 围绕一颗恒星 DDD 以恒定速度 vpv_pvp 逆时针旋转，绕行半径为 RRR，现在有一艘飞船(初始位置给出)要去 行星 PPP 上，且要求任何时刻都不能处在 以恒星 DDD 为中心，半径为 rrr 的范围内，让你求到达行星 PPP 的最短时间
思路
对于一个确定时间 ttt，行星的位置确定，飞船到达行星的时间取决于其运行路线，如果以最短路线前往 PPP，花费时间为 t1t_1t1，只要 t1t_1t1 不大于 ttt，就一定可以到达 PPP，所以可以对时间二分，来寻找最短时间。
对于确定的时间 ttt，现在有几个问题需要解决：
给出行星的初始坐标，经过时间 ttt 后的具体坐标 确定行星的位置后，飞船的最短距离的确定与计算(1) 对于前者，确定其逆时针旋转多少度即可
推导过程如下：
设原向量 p1p_1p1 坐标 (x1,y1)(x_1,y_1)(x1,y1)，长度为 RRR ，与 xxx 轴夹角为 AAA，逆时针旋转 BBB 角度后的坐标为 (x2,y2)(x_2,y_2)(x2,y2)，则有：
x2=Rcos(A+B)x_2=Rcos(A+B)x2=Rcos(A+B)
=Rcos(A)cos(B)−Rsin(A)sin(B)=Rcos(A)cos(B)-Rsin(A)sin(B)=Rcos(A)cos(B)−Rsin(A)sin(B)
=x1cos(B)−y1sin(B)=x_1cos(B)-y_1sin(B)=x1cos(B)−y1sin(B)
y2y_2y2 同理：
y2=Rsin(A+B)y_2=Rsin(A+B)y2=Rsin(A+B)
=Rsin(A)cos(B)+Rcos(A)sin(B)=Rsin(A)cos(B)+Rcos(A)sin(B)=Rsin(A)cos(B)+Rcos(A)sin(B)
=y1cos(B)+x1sin(B)=y_1cos(B)+x_1sin(B)=y1cos(B)+x1sin(B)
(2) 对于后者，比较麻烦。要先确定是否可以直线到达，或者是中间需要绕着走，这取决于 飞船与行星的距离 和 两者关于内圆的切线段长度和 谁大谁小
直线走的话就直接拿两点距离除以飞船速度可得最短时间，如果需要绕行的话，需要计算中间那段绕内圆的弧长，弧度的计算是先计算 飞船与行星关于原点的夹角 ，可根据余弦定理来求(飞船 行星和原点组成一个三角形，知道三边可求任意夹角)，然后计算 飞船与切点关于圆心的夹角 和 行星与切点关于圆心的夹角，这个很好求。然后求得的大角减去两个小角即为我们要的那段弧的弧度，乘上半径即为距离。
代码
#include
#define ft first
#define sd second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair P;
const int maxn=2e5+7;
const double inf=1e18;
const double eps=1e-8;
const double pi=acos(-1.0);
double xp,yp,vp,x,y,v,r;
double tp,R;
bool c(double t){
double a=(t-(int)(t/tp)*tp)*pi*2/tp;//行星在t时刻需要逆时针旋转的角度
double nxp=xp*cos(a)-yp*sin(a);//行星的x坐标
double nyp=yp*cos(a)+xp*sin(a);//行星的y坐标
double T=0.0;//飞船沿最短路走花费总时长
double dis1=sqrt(x*x+y*y-r*r);//飞船与内圆的切线长度
double dis2=sqrt(nxp*nxp+nyp*nyp-r*r);//星球与内圆的切线长度
double dis3=sqrt(x*x+y*y);//飞船到原点的距离
double dis4=sqrt(nxp*nxp+nyp*nyp);//行星到原点的距离 就是 R
double dis=sqrt((x-nxp)*(x-nxp)+(y-nyp)*(y-nyp));//飞船与行星的距离
if(dis1+dis2>=dis)T=dis/v;//不需要绕行
else {//需要绕行
//余弦定理求大角
double angle=acos((dis3*dis3+dis4*dis4-dis*dis)/(dis3*dis4*2));
double angle1=atan(dis1/r);//飞船的小角
double angle2=atan(dis2/r);//行星的小角
angle-=angle1+angle2;
T=(dis1+dis2+angle*r)/v;
}
return T>xp>>yp>>vp>>x>>y>>v>>r;
R=sqrt(xp*xp+yp*yp);
tp=pi*R*2.0/vp;//行星周期
double l=0.0,r=inf,ans=0;
for(int i=1;i<=100;i++){
double m=(l+r)/2.0;
if(c(m)){
r=m;ans=m;
}
else l=m;
}
printf("%.10f\n",ans);
return 0;
}
作者：ぺ晨曦若梦ぺ
