首页 > 其他分享 >Codeforces Global Round 27

Codeforces Global Round 27

时间:2024-10-29 22:58:07浏览次数:1  
标签:27 return int lowbit ll Global Codeforces long include

Codeforces Global Round 27 总结

A

将红色的位置 \((r,c)\) 移走,分为三块来考虑,蓝色的块移动 \(m-c\),黄色的块移动 \(m*(n-r)\),绿色的块移动 \((m-1)*(n-r)\)。

img

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1;
ll n,m,r,c;
void solve()
{
    cin>>n>>m>>r>>c;
    cout<<m-c+m*(n-r)+(m-1)*(n-r)<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B

首先 \(n\) 为 \(1\) 到 \(5\) 时,直接输出样例。到 \(n>5\) 的时候,\(n\) 为奇数就是 \(36366\) 每次在前面加上 \(33\),否则就是 \(3366\) 每次在前面加上 \(33\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1;
int n;
void solve()
{
    cin>>n;
    if(n==1||n==3) cout<<-1<<'\n';
    else if(n==2) cout<<66<<'\n';
    else 
    {
        if(n&1)
        {
            for(int i=1;i<=n-5;i+=2) cout<<33;
            cout<<36366<<'\n';
        }
        else 
        {
            for(int i=1;i<=n-4;i+=2) cout<<33;
            cout<<3366<<'\n';
        }
    }
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C

构造题,观察到 \(5 \le n\),不妨就考虑最后几位,因为可以保证最后几位受到的影响最小,思路是先考虑或出来最大,再考虑与上某个数不会影响或的数。

  • \(n\) 为奇数,最后一次运算是按位与,所以 \(k \le n\),且 \(n\) 必须在最后一位,前面按位或的结果要保留 \(n\) 有的所有位,不妨就只保证等于 \(n\)。将 \(n\) 拆开,用最后一位 \(1\),也就是 \(lowbit(n)\) 和 \(n-lowbit(n)\) 相或得到 \(n\),然后要保证 \(lowbit(n)\) 不被影响,可以与上 \(lowbit(n)\) 加上一位小的 \(1\),这样的话可以确定最后四位:

\[lowbit(n),lowbit(n)+lowbit(n)==1 ? 2 : 1,n-lowbit(n),n \]

  • \(n\) 为偶数,最后一次运算是按位或,所以可以填充所有位 \(k \le 2^t-1\),\(t\) 表示 \(n\) 的二进制下的位数。
    • 考虑特殊情况 \(n=2^{t-1}\),这样的话最高位就只能是 \(n\) 来给,所以不妨让最后一位为 \(n\),然后前面的结果就是要为 \(n-1\),但显然直接或上 \(n-1\) 的话不可能保住它,所以将 \(n-1\) 再拆开成 \(1\) 和 \(n-2\),用 \(3\) 保住 \(1\),用 \(n-1\) 保住 \(n-2\),这样的话就能确定最后五位:

    \[1,3,n-2,n-1,n \]

    • 否则,用 \(n\) 的最高位 \(2^{t-1}\),和 \(2^{t-1}-1\) 拼凑成 \(2^t-1\)。所以确定最后三位:

    \[2^{t-1},n,2^{t-1}-1 \]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int ans[N],v[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) ans[i]=0,v[i]=i;
    int a,b,c,d=0,e=0;
    
    if(n&1)
    {
        a=n&-n;
        cout<<n<<'\n';
        if(a==1) b=3;
        else b=a+1;
        c=n-a,d=n;
        ans[n]=d,ans[n-1]=c,ans[n-2]=b,ans[n-3]=a;
    }
    else 
    {
        int t=1;
        while(t<=n) t<<=1;
        cout<<t-1<<'\n';
        if(n!=t/2)
        {
            a=t/2,b=n,c=t/2-1;
            ans[n]=c,ans[n-1]=b,ans[n-2]=a;
        }
        else 
        {
            a=1,b=3,c=n-2,d=n-1,e=n;
            ans[n]=e,ans[n-1]=d,ans[n-2]=c,ans[n-3]=b,ans[n-4]=a;
        }
    }
    v[a]=v[b]=v[c]=v[d]=v[e]=0;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(ans[i]) continue;
        while(!v[cnt]) cnt++;
        ans[i]=v[cnt++];
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    cout<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D

结论比较好猜,就是尽可能将 \(2\) 都乘到最大的数上,但是有一个问题,前面的数不能乘后面的 \(2\),就是说原本后面的数更小,但是可以乘上更多的 \(2\)。

因此将 \(a_i\) 的 \(2\) 拆出来统计个数,用一个单调栈维护,栈内单调递减,每次加入一个数,如果栈顶的元素小于这个数,就把栈顶的 \(2\) 全部给新加入的数。注意这里的新数大小是要目前有的 \(2\) 的。注意乘上以后会爆 long long。细节看代码吧。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5,mod=1e9+7;
int n;
ll a[N],v[N],b[N];
int st[N];
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1) ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return ret;
}
ll count(ll &x)
{
    if(!x) return 0;
    int ret=0;
    while(x%2==0) x/=2,ret++;
    return ret;
}
ll restore(ll x,ll y)
{
    while(y)
    {
        x<<=1;
        if(x>mod) return mod;
        y--;
    }
    return x;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],v[i]=count(a[i]);
    int tot=0;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+a[i]*qpow(2,v[i])%mod)%mod;
        while(tot&&a[b[tot]]<restore(a[i],v[i]))
        {
            ans=(ans-a[b[tot]]*qpow(2,v[b[tot]])%mod+mod)%mod;
            ans=(ans+a[b[tot]])%mod;
            ans=(ans-a[i]*qpow(2,v[i])%mod+a[i]*qpow(2,v[i]+v[b[tot]])%mod+mod)%mod;
            v[i]+=v[b[tot]];
            tot--;
        }
        b[++tot]=i;
        cout<<ans<<' ';
    }
    cout<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

标签:27,return,int,lowbit,ll,Global,Codeforces,long,include
From: https://www.cnblogs.com/zhouruoheng/p/18512768

相关文章

  • 2024.10.14 Codeforces Round 978 (Div. 2)
    比赛链接Solved:4/7Upsolved:5/7Rank:447(rated343)D2.Asesino(HardVersion)题意:有n个人,除了一个卧底以外,其他人或者只会说真话,或者只会说谎,且他们知道彼此的身份。卧底只会说谎,但其他人都认为他只会说真话。现在你可以进行若干次询问,每次询问形如问第i个人第j个人是什么......
  • .NET周刊【10月第4期 2024-10-27】
    国内文章C#实现信创国产Linux麦克风摄像头推流(源码,银河麒麟、统信UOS)https://www.cnblogs.com/shawshank/p/18494362随着国际形势变化,软件信创国产化迫在眉睫。本文介绍如何在国产操作系统上实现RTMP推流,包括摄像头和麦克风数据采集、编码、推送至流媒体服务器等。使用.NETCor......
  • 9.27
    原型模式原型模式(PrototypePattern)是用于创建重复的对象,同时又能保证性能。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式之一。这种模式是实现了一个原型接口,该接口用于创建当前对象的克隆。当直接创建对象的代价比较大时,则采用这种模式。例如,一个对象需要......
  • 10.27 多表
    已知2张基本表:部门表:dept(部门号,部门名称);员工表emp(员工号,员工姓名,年龄,入职时间,收入,部门号)1:dept表中有4条记录:部门号(dept1)部门名称(dept_name)101财务102销售103IT技术104行政2:emp表中有6条记录:员工号员工姓名年龄入职时间收入部门号对应字段名称为:(sidna......
  • Educational Codeforces Round 171 (Rated for Div. 2) 题解(A-C)
    EducationalCodeforcesRound171(RatedforDiv.2)题解(A-C)这场ABC全都犯病了(悲伤)目录EducationalCodeforcesRound171(RatedforDiv.2)题解(A-C)目录A.PerpendicularSegmentsB.BlackCellsC.ActionFiguresA.PerpendicularSegments大意给你一个......
  • [CodeForces] CF520 题解
    A.Pangram【题目大意】给定一个字符串,询问是否所有英文字符(a到z)都在这个字符串中出现过,不区分大小写。【解题思路】开个桶记录字符是否出现过,最后遍历桶,如果发现有一个没出现就输出NO,否则就输出YES。注意不区分大小写!B.TwoButtons【题目大意】给定两个正整数\(n\)......
  • Educational Codeforces Round 163 (Rated for Div. 2) - VP记录
    Preface这次难度感觉挺平均的,前面的题不水,后面的题也不毒瘤(可能是因为我做的不够后面)A.SpecialCharacters开局构造题。因为特殊字符一定是成对出现的(包括两边的,可以分类讨论思考一下),所以只有\(n\)为偶数的时候才有解。然后直接以AABBAABB...的格式输够\(n\)个就行了......
  • CodeForces
    CodeForces做题记录CodeforcesGlobalRound27ASliding当\((r,c)\)被取走时:\(\foralli\in[r+1,n],(i,1)\)会移动到\([i-1,m]\),曼哈顿距离为\(m\)。\(\foralli\in[r+1,n],j\in[2,m],(i,j)\)会移动到\((i,j-1)\),曼哈顿距离为\(1\)。\(......
  • Educational Codeforces Round 171 (Rated for Div. 2)题解记录
    比赛链接:https://codeforces.com/contest/2026A.PerpendicularSegments题目说了必定有答案,直接对角线即可#include<iostream>#include<queue>#include<map>#include<set>#include<vector>#include<algorithm>#include<deque>#include<......
  • Educational Codeforces Round 171 (Rated for Div. 2)
    目录写在前面A签到B暴力C反悔贪心D枚举,分块,推式子E网络流,最大权闭合子图F写在最后写在前面比赛地址:https://codeforces.com/contest/2026。因为太困了决定睡大觉,于是赛时unratedregister只写了DE。然而十一点半上床还是失眠到一点半睡的太搞了呃呃A签到B暴力限......