CF1909A
一眼秒之题，我们发现就是四个方向选三个方向，若是存在一个点它的方向恰好在（0，0）点的另外一个方向，则一定不成立
枚举4个方向，发现有点在这个方向，显然选除这个点之外的三个方向的方案就不可行
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int t,n;
int x[N],y[N];
bool c1(){
for(int i=1;i<=n;i++){
if(x[i]<0) return 0;
}
return 1;
}
bool c2(){
for(int i=1;i<=n;i++){
if(x[i]>0) return 0;
}
return 1;
}
bool c3(){
for(int i=1;i<=n;i++){
if(y[i]<0) return 0;
}
return 1;
}
bool c4(){
for(int i=1;i<=n;i++){
if(y[i]>0) return 0;
}
return 1;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
if(c1()||c2()||c3()||c4()) printf("YES\n");
else printf("NO\n");
}
}
CF1909B
看似普及-，实则封神
我们先想到若这些数有奇数也有偶数k直接等于2即可
然而若不是呢？
判断一个数的奇偶只需要看它的二进制最低位是0/1就行
若一个数列全是奇或偶那么必然二进制第一位上全是1或全是0
但是其必然会出现在二进制的某一位上1/0两种都存在
若一个数模上一个 \(2^k\) 那么在2进制下只有 1~k+1位上数是有效的
所以我们只需要找到在二进制表示的数列中，找到最低的一位满足这一位存在0/1即可
这显然可以字典树做，但这道题普及-所以我们暴力枚举 \(2^i\) 即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,inf=1e18;
int t,n;
int a[N];
bool check(int mod){
set<int>st;
for(int i=1;i<=n;i++){
int z=a[i]%mod;
st.insert(z);
}
if(st.size()!=2) return 0;
return 1;
}
signed main(){
scanf("%lld",&t);
while(t--){
int ans=inf;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int j=0;j<=63;j++){
int mod=(1ll<<j);
if(check(mod)){
printf("%lld\n",mod);
break;
}
}
}
}
CF19909C
小恶心贪心题
显然我们是要求出来一个降序序列 \(r_i-l_i\) 使得其每一位乘上升序排序的 \(c_i\) 得出来的结果最小
考虑如何构造出对应的 \(l_i\) 和 \(r_i\) 呢？
我们先将 \(l,r\) 序列排好序，然后考虑以下两种组合情况
所以我们只需要让在 \(l_i<r_i\) 这个限制范围内使得 \(l_i\) 尽量接近 \(r_i\)，我们可以用栈来解决这个问题
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,cnt,t;
int l[N],r[N],c[N],s[N],ans[N];
bool cmp(int x,int y){
return x>y;
}
signed main(){
scanf("%lld",&t);
while(t--){
cnt=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&l[i]);
}
for(int i=1;i<=n;i++){
scanf("%lld",&r[i]);
}
for(int i=1;i<=n;i++){
scanf("%lld",&c[i]);
}
sort(c+1,c+1+n);
sort(l+1,l+1+n);
sort(r+1,r+1+n);
for(int i=1,j=1;i<=n;i++){
while(l[j]<r[i]&&j<=n){
s[++cnt]=l[j];
j++;
}
// printf("%lld %lld\n",r[i],s[cnt]);
ans[i]=r[i]-s[cnt--];
}
sort(ans+1,ans+1+n,cmp);
int tot=0;
for(int i=1;i<=n;i++){
tot+=ans[i]*c[i];
}
printf("%lld\n",tot);
}
}