当前位置： 首页 > news >正文

Codeforces Round #653 (Div. 3)（A-E1）

news 来源：原创 2024/5/3 23:10:08

A - Required Remainder（签到）

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,x,y;
    cin>>t;
    while(t--){
        cin>>x>>y>>n;
        int p=n%x;
        if(p>y) cout<<n-(p-y)<<endl;
        else if(p<y) cout<<n-(p+x-y)<<endl;
        else cout<<n<<endl;
    }
    return 0;
}

B - Multiply by 2, divide by 6（质因数分解）

写了质因数分解的板子，实际上就是看是不是质因数只有2和3，这基础上3的指数是否大于等于2的指数

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long double ld;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const LL INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;


struct BigIntegerFactor{
    const static int maxm = 1e6+16;
    LL prime[maxm],p[maxm],fac[maxm],sz,cnt;     //多组输入注意初始化cnt = 0
    inline LL mul(LL a,LL b,LL mod){             //WA了尝试改为__int128或慢速乘
        if(mod <= 1000000000) return a * b % mod;
        return (a*b-(LL)((long double)a/mod*b+1e-8)*mod+mod)%mod;
    }
    void init(int maxn){    //传入的参数不能超过maxm,一般取1e5即可
        int tot = 0; sz = maxn-1;
        for(int i = 1;i <= sz; ++i) p[i] = i;
        for(int i = 2;i <= sz; ++i){
            if(p[i] == i) prime[tot++] = i;
            for(int j = 0;j<tot&&1ll*i*prime[j]<=sz; ++j){
                p[i*prime[j]] = prime[j];
                if(i%prime[j] == 0) break;
            }
        }
    }
    LL powl(LL a,LL x,LL mod){
        LL res = 1LL;
        while(x){
            if(x&1) res = mul(res,a,mod);
            a = mul(a,a,mod);
            x >>= 1;
        }
        return res;
    }
    bool check(LL a,LL n){                       //二次探测原理检验n
        LL t = 0,u = n-1;
        while(!(u&1)) t++,u >>= 1;
        LL x = powl(a,u,n),xx = 0;
        while(t--){
            xx = mul(x,x,n);
            if(xx==1 && x!=1 && x!=n-1) return false;
            x = xx;
        }
        return xx == 1;
    }
    bool miller(LL n,int k){   //一般k取20即可
        if(n == 2) return true;
        if(n < 2 || !(n&1)) return false;
        if(n <= sz) return p[n] == n;
        for(int i = 0;i <= k; ++i){               //测试k次
            if(!check(rand()%(n-1)+1,n)) return false;
        }
        return true;
    }
    inline LL gcd(LL a,LL b){
        return b == 0 ? a : gcd(b,a%b);
    }
    inline LL Abs(LL x){
        return x < 0 ? -x : x;
    }
    LL Pollard_rho(LL n){                  //基于路径倍增的Pollard_Rho算法
        LL s = 0,t = 0,c = rand()%(n-1)+1,v = 1,ed = 1;
        while(1){
            for(int i = 1; i <= ed; ++i){
                t = (mul(t,t,n) + c) % n; v = mul(v,Abs(t-s),n);
                if(i % 127 == 0){
                    LL d = gcd(v,n);
                    if(d > 1) return d;
                }
            }
            LL d = gcd(v,n); if(d > 1) return d;
            s = t; v = 1; ed <<= 1;
        }
    }
    void getfactor(LL n){                          //得到所有的质因子(可能有重复的)
        if(n <= sz){
            while(n != 1) fac[cnt++] = p[n],n /= p[n];
            return;
        }
        if(miller(n,6)) fac[cnt++] = n;
        else{
            LL d = n; while(d >= n) d = Pollard_rho(n);
            getfactor(d); getfactor(n/d);
        }
    }
    int solve(LL x){  //每次使用更改这个函数得出结果即可，这里是打印每个质因数以及对应数量
        cnt=0;
        getfactor(x);
        int res[2]={0};
        for(int i = 0;i < cnt; ++i){
            if(fac[i]!=2 && fac[i]!=3) return -1;
            res[fac[i]-2]++;
        }
        if(res[0]==res[1]) return res[0];
        if(res[0]>res[1]) return -1;
        else return res[1]+res[1]-res[0];
    }
}Q;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    Q.init(100000);
    int n,t;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<Q.solve(n)<<endl;
    }
    return 0;
}

C - Move Brackets（签到）

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

stack<char> st;
string s;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        cin>>s;
        while(!st.empty()) st.pop();
        int ans=0;
        for(int i=0;i<n;i++){
            if(s[i]=='('){
                st.push(s[i]);
            }else{
                if(st.size())
                    st.pop();
                else ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

D - Zero Remainder Array（思维）

我们发现只需考虑最大的数有多少个，因为相同的数每次都要经过 k k k的周期才能修改成功，那么只需找到最大的， m a p map map即可

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[maxn];
map<int,int> mp;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,k;
    cin>>t;
    while(t--){
        cin>>n>>k;
        int minn=inf;
        mp.clear();
        for(int i=0,x;i<n;i++){
            cin>>x;
            a[i]=k-x%k;
            if(a[i]<k) mp[a[i]]++;
        }
        int maxx=0,cnt=0;
        for(auto i: mp){
            if(i.se>cnt){
                cnt=i.se,maxx=i.fi;
            }else if(i.se==cnt){
                maxx=max(maxx,i.fi);
            }
        }
        if(cnt==0){
            cout<<0<<endl;
            continue;
        }
        //cout<<maxx<<" "<<cnt<<endl;
        ll ans=0;
        ans=maxx+1LL*(cnt-1)*k+1;
        cout<<ans<<endl;
    }
    return 0;
}

E1 - Reading Books (easy version)（简单分类）

将只有一个人喜欢读的两本书合并为两个人都喜欢的一本书，然后考虑所有"1-1"情况，排序贪心选即可

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

vector<int> ab,a,b;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    int A=0,B=0;
    for(int i=0,x,y,z;i<n;i++){
        cin>>x>>y>>z;
        if(y&z){
            ab.push_back(x);
            A++,B++;
        }else if((!y)&z){
            b.push_back(x);
            B++;
        }else if(y&(!z)){
            a.push_back(x);
            A++;
        }
    }
    if(A<k || B<k){
        cout<<"-1"<<endl;
        return 0;
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int cnt;
    for(cnt=0;cnt<a.size() && cnt<b.size();cnt++){
        ab.push_back(a[cnt]+b[cnt]);
    }
    sort(ab.begin(),ab.end());
    int ansA=0,ansB=0;
    if(ab.size()>=k){
        ll ans=0;
        for(int i=0;i<k;i++)
            ans+=ab[i];
        cout<<ans<<endl;
    }else cout<<"-1"<<endl;
    return 0;
}

相关文章：

  • Linux hdparm命令使用方法
  • UVA - 11582 Colossal Fibonacci Numbers!（找循环节）
  • UVA - 12169 Disgruntled Judge（枚举+扩展欧几里得）
  • ASM管理命令和操作笔记
  • UVA - 10791 Minimum Sum LCM（质因数分解）
  • 删除ASM残留信息方法和重建步骤
  • UVA - 12716 GCD XOR（找规律+枚举技巧）
  • Oracle 修改归档模式
  • UVA - 1635 Irrelevant Elements（质因数分解）
  • spfile和pifle的一点浅浅的认识
  • 欧拉函数
  • UVA - 1636 Headshot（条件概率）
  • Oracle RAC日常基本维护命令
  • UVA - 11181 Probability|Given（条件概率+状压dfs）
  • UVA - 1637 Double Patience（全概率+记忆化搜索）
  • 《Javascript高级程序设计 (第三版)》第五章 引用类型
  • 【个人向】《HTTP图解》阅后小结
  • CSS盒模型深入
  • extjs4学习之配置
  • github指令
  • javascript面向对象之创建对象
  • JS变量作用域
  • Laravel Telescope：优雅的应用调试工具
  • LeetCode刷题——29. Divide Two Integers（Part 1靠自己）
  • nginx 负载服务器优化
  • Promise面试题2实现异步串行执行
  • Sass Day-01
  • SpringBoot几种定时任务的实现方式
  • vue-router的history模式发布配置
  • 解析带emoji和链接的聊天系统消息
  • 精彩代码 vue.js
  • 问:在指定的JSON数据中（最外层是数组）根据指定条件拿到匹配到的结果
  • 阿里云重庆大学大数据训练营落地分享
  • 蚂蚁金服CTO程立：真正的技术革命才刚刚开始
  • ​ 无限可能性的探索：Amazon Lightsail轻量应用服务器引领数字化时代创新发展
  • ​​​​​​​Installing ROS on the Raspberry Pi
  • #laravel 通过手动安装依赖PHPExcel#
  • （3）STL算法之搜索
  • （4）事件处理——（7）简单事件（Simple events）
  • （动手学习深度学习）第13章 计算机视觉---微调
  • （十七）Flask之大型项目目录结构示例【二扣蓝图】
  • (数位dp) 算法竞赛入门到进阶 书本题集
  • （五）MySQL的备份及恢复
  • (转)Linux NTP配置详解 (Network Time Protocol)
  • .\OBJ\test1.axf: Error: L6230W: Ignoring --entry command. Cannot find argumen 'Reset_Handler'
  • .apk文件，IIS不支持下载解决
  • .bat批处理（六）：替换字符串中匹配的子串
  • .NET BackgroundWorker
  • .NET MVC第五章、模型绑定获取表单数据
  • .NET/C# 利用 Walterlv.WeakEvents 高性能地中转一个自定义的弱事件（可让任意 CLR 事件成为弱事件）
  • .net获取当前url各种属性(文件名、参数、域名 等)的方法
  • .sh 的运行
  • @DependsOn：解析 Spring 中的依赖关系之艺术
  • @RequestBody与@ModelAttribute
  • @SuppressWarnings注解