练习记录-cf-div2-A-D

标签：std const int ll 练习 cf long sum div2

上课的时候抓紧时间写的，状态不好，c也没过，估计换个环境也很难想吧

A Likes

题意 点赞， a<0 表示取消赞 a>0表示增加赞，a数组乱序 输出如何排让赞数价值最多

分别记录大于0和小于0的个数f[1] f[0]

输出如下代码

 

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;

int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    int f[2]={0};
int n;cin>>n;
for(int i=0;i<n;i++){
    int a;cin>>a;
    if(a<0) f[1]++;
    else f[0]++;
}
for(int i=1;i<=f[0];i++){
    cout<<i<<" ";
}
for(int i=f[0]-1;i>=f[0]-f[1];i--){
    cout<<i<<" ";
}
cout<<"\n";
int k1=min(f[0],f[1]);
int k2=max(f[0]-k1,f[1]-k1);
for(int i=1;i<=k1;i++){
    cout<<"1 0 ";
}
for(int i=1;i<=k2;i++){
    cout<<i<<" ";
}
cout<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--) 
    solve();
}

View Code

B Settlement of Guinea Pigs

 

1表示买了一只猪 2表示找医生鉴定猪的性别

一个房子可以放两个性别相同的猪 问至少要多少个房子

在鉴别性别前 每只猪都要单独的房子 

检测到2时 我将模拟鉴别的过程 最坏的情况就是 当一个性别刚好可以塞进屋子（n%2==0）时，又来了这个性别的 最后 输出个数的最大值（有可能是中间遇到的）

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
int n;cin>>n;
int f[2]={0};
    int ans=0,sum=0,res=0;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a==2) {
            while(sum){
                if(f[0]%2==1) f[1]++;
                else f[0]++;
                sum--;
            }
            ans=(int)(ceil(f[0]*1.0/2))+(int)(ceil(f[1]*1.0/2));
        }
        else {
            sum++,ans++;
        }
        res=max(res,ans);
    }
    cout<<res<<"\n";
}
int main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

c The Very Beautiful Blanket

构造一个矩阵，n*m，使得里面每个4*4的矩阵都满足对角线异或和相等

这题是补的 看的jiangly大佬的思路 直接按照ij的序号填充矩阵 

只看j的时候 直接输出j就可以让每四个异或等于0 

因此i也同理 为了让i不影响j i往前多移动几位即可（>200）

很聪明很聪明 反正我没想到orz

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    ll n,m;cin>>n>>m;
    cout<<n*m<<"\n";
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cout<<(i<<21)+j<<" ";
        }
        cout<<"\n";
    }
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

 

D  Buying gifts

一开始题目没看清 应该是 要进入每一家商店 选择给a买或者给b买 求最小的礼物最贵价值差

补的 看了排序的思路 按照a来排，这样枚举a的时候前面的价格不影响a的最大价格

b的价格 首先必须取后面的，当然 如果后面的很小，比如说此时a=10，但是后面最大的b的价格是7，前面的b存在9和10，那么此时前面的有作用

后面的最大值用前缀和处理 前面的放进set使用lower_bound，如果不是在首尾就取再取一个前面的，防止出现从小的数字逼近的情况

但是注意，只有前面取的值>后面最大值才能生效 因此我写的是abs(a[i]-max(a1,sum[i+1])

就解决了问题

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 1e6+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long
struct node{
    int a,b;
}N[MAXN];
int sum[MAXN];
bool bj(node a,node b){
    return a.a<b.a;
}
void solve(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>N[i].a>>N[i].b;
    }
    sort(N,N+n,bj);
    sum[n]=inf*-1;
    for(int i=n-1;i>=0;i--){
        sum[i]=max(N[i].b,sum[i+1]);
    }
    set<int>sz;
    int ans=inf;
    for(int i=0;i<n;i++){ //枚举买到第几个 
    if(i==0){
        ans=min(ans,abs(N[i].a-sum[i+1]));
    }
    else{
        auto it=sz.lower_bound(N[i].a);
        int a1,a2;
        if(it!=sz.end()){
             a1=*it;
            if(it!=sz.begin()) a2=*(--it);
            else a2=a1;
        }
        
        else{
            a1=a2=*(--it);
         }
        ans=min({ans,abs(N[i].a-max(a1,sum[i+1])),abs(N[i].a-max(a2,sum[i+1])),abs(N[i].a-sum[i+1])});
    }
    sz.insert(N[i].b);
    }
    cout<<ans<<"\n";
}
signed main(){
    close;
    int t;cin>>t;
    while(t--) 
    solve();
}

View Code

 

标签：std,const,int,ll,练习,cf,long,sum,div2
From： https://www.cnblogs.com/xishuiw/p/17205549.html