Codeforces Round #618 (Div. 2)
题目链接:
https://codeforces.com/contest/1300
A. Non-zero
有手就行
B. Assigning to Classes
从小到大排序，然后(ans=b[n+1]-b[n])
C. Anu Has a Function
题解
首先变形一下：(f(x,y)=(x|y)-y=x-(x&y))
所以其实越变越小。我们按二进制位看，第一个数为(a_i),对于第(k位(代表2^{k-1}))如果(exists a_j,使得 a_j&(1<<k)==1), 则(ans)这一位为0。所以我们可以从最高位开始找。如果这一位只有一个数为1，那么这个数就是第一个数。后面的数顺序不影响结果。
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int INF=1e9+7;
const int N=300050;
int a[N],num[N],b[N];
void work(){
int n,ans=0,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
for(int j=0;j<30;j++){
if ((a[i]>>j)&1){num[j]++;b[j]=i;}
}
}
for(int i=29;i>=0;i--){
if (num[i]==1){
swap(a[1],a[b[i]]);
break;
}
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("aa.in","r",stdin);
#endif
work();
}
D. Aerodynamic
题解:
没怎么做过几何题，连题目都没看懂，直接跳了。后来一点点查字典，看懂了题目，然而还是不会做。看了题解，感觉自己也想不出来。
就判断他是不是中心对称，如果不是中心对称，那答案就是"NO"。因为对于T，我们让(0,0)任何时候都在图形内，若((x,y))在图形内，((x ightarrow 0,y ightarrow0),则(0 ightarrow -x,0 ightarrow -y)),也就是((x,y)和(-x,-y)同时存在于T内)
我没接下来证明所有中心对称图形答案是"YES"。因为(x,y)和(-x,-y)同时存在于T，所以(2x,2y)也一定存在于T。也就是实际上就是原凸多边形所有边增长了一倍。
如果知道结论，题目就变成了怎么判断凸多边形是不是中心对称。我们只需要把每个点的对点连线的交点是否在一个点上。其实就是对角线的交点啦。假如n个点
a[i]的对点就是a[i+n/2]，如果n为奇数那肯定不是的。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
struct Point{
int x,y;
ll operator *(Point &b){
ll ans=1LL*x*b.y-1LL*y*b.x;
return ans;
}
};
struct Convex{
int num=0;
Point p[N];
void add(int x,int y){
p[++num]={x,y};
}
bool isCentralSymmetry(){
if (num%2)return 0;
int x,y;
x=p[1].x+p[1+num/2].x;
y=p[1].y+p[1+num/2].y;
for(int i=1;i<=num/2;i++){
if (p[i].x+p[i+num/2].x!=x || p[i].y+p[i+num/2].y!=y)
return 0;
}
return 1;
}
ll getArea(){
ll ans=0;
p[0]=p[num];
for(int i=1;i<=num;i++)
ans+=p[i-1]*p[i];
ans/=2;
return ans;
}
}C;
int main(){
int n,x,y;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&x,&y);
C.add(x,y);
}
if (!C.isCentralSymmetry()){
printf("NO
");
return 0;
}
printf("YES
");
}
E. Water Balance
题解
这个倒水可以倒很多次。我们不妨想什么情况下需要倒水和什么情况下不用倒水。
如果第i桶水比前面的水少，那么肯定就要从前面往这杯水倒。也就是倒完水之后水的体积是单调不减的。那我们就可以用一个单调队列来维护。单调队列单调不减，如果当前水比前面水体积小，就往前倒，直到不满足条件。
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,double> pid;
const int INF=1e9+7;
const int N=1000050;
const double eps=1e-7;
int n;
double a[N];
void work(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
deque<pid>Q;
for(int i=1;i<=n;i++){
double val=a[i];
int num=1;
while(!Q.empty() && val<Q.back().se){
val=(val*num+Q.back().fi*Q.back().se)/(double)(num+Q.back().fi);
num+=Q.back().fi;
Q.pop_back();
}
Q.push_back({num,val});
}
for(pid u:Q){
for(int i=1;i<=u.fi;i++)printf("%.10lf
",u.se);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("aa.in","r",stdin);
#endif
work();
}