Codeforces Round #339 (Div. 2) （已更新A，B，C，D）
因为明晚又有cf了，所以顺手摸了场出题人 _kun_ 以前出的一场，然后我发现
这个problem setter
好duliu啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
场内他俩亲自出的题，基本全是hack题啊…………
明晚是不可能打的, 这被几都不可能打的……..
好了，让我们转回cf round 339
A. Link/Cut Tree
这题vp….wa了4发，最后是java摸过去的…….看了眼原榜，这题好惨烈啊……
import java.util.*;
public class __
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
long left=in.nextLong(),right=in.nextLong();
long base=in.nextLong();
List<Long>answer=new ArrayList<>();
for(long power=1;power<=right;)
{
if(left<=power) answer.add(power);
if(power<=right/base) power*=base;
else break;
}
if(answer.isEmpty()) answer.add(-1L);
for(long power : answer) System.out.print(power + " ");
System.out.println();
}
}
B. Gena’s Code
模拟就完事了(不过不知道为什么这题被hack的也蛮多的)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int cal(string s)
{
int cnt=0;
if(s[0]!='1')
{
if(s[0]=='0') return -2;
else return -1;
}
for(int i=1; i<s.length(); i++)
{
if(s[i]!='0') return -1;
cnt++;
}
return cnt;
}
int main()
{
int n;
scanf("%d",&n);
string s;
string ss="1";
ll cnt=0;
int flag=0;
for(int i=0; i<n; i++)
{
cin>>s;
if(flag==1) continue;
int op=cal(s);
if(op==-1)
{
ss=s;
continue;
}
if(op==-2)
{
printf("0\n");
flag=1;
}
cnt+=op;
}
if(!flag)
{
cout<<ss;
for(int i=0; i<cnt; i++) cout<<'0';
}
}
C. Peter and Snow Blower
多边形绕点旋转所覆盖的最大面积，掏出板子，然后ac
要注意的就是最远点肯定是多边形角上的点，最近点还可能在边上.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-8;
int cmp(double x)
{
if(fabs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
const double pi=acos(-1.0);
inline double sqr(double x)
{
return x*x;
}
struct point
{
double x,y;
point() {};
point(double a,double b):x(a),y(b) {};
void input()
{
scanf("%lf%lf",&x,&y);
}
friend point operator + (const point &a,const point &b)
{
return point(a.x+b.x,a.y+b.y);
}
friend point operator - (const point &a,const point &b)
{
return point(a.x-b.x,a.y-b.y);
}
friend bool operator == (const point &a,const point &b)
{
return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
}
friend point operator * (const point &a,const double &b)
{
return point(a.x*b,a.y*b);
}
friend point operator * (const double &a,const point &b)
{
return point(a*b.x,a*b.y);
}
friend point operator / (const point &a,const double &b)
{
return point(a.x/b,a.y/b);
}
double norm()
{
return sqrt(sqr(x)+sqr(y));
}
};
struct Line
{
point s;
point e;
Line(point a, point b)
{
s=a;
e=b;
}
Line() { }
};
double det(const point &a,const point &b)
{
return a.x*b.y-a.x*b.y;
}
double dot(const point &a,const point &b)
{
return a.x*b.x+a.y*b.y;
}
double dis(const point &a,const point &b)
{
return (a-b).norm();
}
point rotate_point(const point &p,double A)
{
double tx=p.x,ty=p.y;
return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}
int dcmp(double k)
{
return k<-eps?-1:k>eps?1:0;
}
double cross(const point &a,const point &b)
{
return a.x*b.y-a.y*b.x;
}
double abs(const point &o)
{
return sqrt(dot(o,o));
}
double mysqrt(double n)
{
return sqrt(max(0.0,n));
}
double dotmultiply(point p1,point p2,point p0)
{
return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y));
}
double relation(point p,Line l)
{
Line tl;
tl.s=l.s;
tl.e=p;
return dotmultiply(tl.e,l.e,l.s)/(dis(l.s,l.e)*dis(l.s,l.e));
}
point perpendicular(point p,Line l)
{
double r=relation(p,l);
point tp;
tp.x=l.s.x+r*(l.e.x-l.s.x);
tp.y=l.s.y+r*(l.e.y-l.s.y);
return tp;
}
double ptolinesegdist(point p,Line l,point &np)
{
double r=relation(p,l);
if(r<0)
{
np=l.s;
return dis(p,l.s);
}
if(r>1)
{
np=l.e;
return dis(p,l.e);
}
np=perpendicular(p,l);
return dis(p,np);
}
int n;
point P[100005];
int main()
{
point p;;
scanf("%d",&n);
p.input();
for(int i=1; i<=n; i++) P[i].input();
P[n+1]=P[1];
double Max=0;
double Min=1e10;
point p0;
for(int i=1; i<=n; i++)
{
Max=max(Max,dis(P[i],p));
Line l=Line(P[i],P[i+1]);
Min=min(Min,ptolinesegdist(p,l,p0));
}
printf("%.10f\n",(Max*Max-Min*Min)*pi);
}
D. Skills
暴力遍历+二分
duliu压了一下行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll pre[maxn],fi[maxn];
pair<ll,ll>a[maxn];
ll cal(ll l,ll r,ll goal)
{
return l>r?0:goal*(r-l+1)-(pre[r]-pre[l-1]);
}
bool check(ll x,ll n,ll m)
{
ll num=0;
for (ll l=1,r=n,mid; l<=r; mid=(l+r)>>1,a[mid].first<x?num=mid,l=mid+1:r=mid-1);
return cal(1,num,x)<=m;
}
int main()
{
ll n,A,cf,cm,m;
scanf("%lld%lld%lld%lld%lld",&n,&A,&cf,&cm,&m);
for(ll i=1; i<=n; i++) scanf("%lld",&a[i].first),a[i].second=i;
sort(a+1,a+n+1);
for(int i=1; i<=n; i++) pre[i]=a[i].first+pre[i-1];
ll ans=0,ansk=0,ansst=0;
for(int i=0;i<=n;i++)
{
ll lef=m-cal(n-i+1,n,A);
if(lef<0) break;
ll st=0;
for(ll l=0,r=A,mid; l<=r; mid=(l+r)>>1,check(mid,n-i,lef)?st=mid,l=mid+1:r=mid-1);
ll t=i*cf+st*cm;
if(t>ans) ans=t,ansk=i,ansst=st;
}
printf("%lld\n",ans);
for(int i=1; i<=n; i++) fi[a[i].second]=i>n-ansk?A:max(ansst,a[i].first);
for(int i=1; i<=n; i++) printf("%lld ",fi[i]);
printf("\n");
}
发表评论