首页 > 其他分享 >KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

时间:2024-04-02 23:44:33浏览次数:19  
标签:AtCoder 200 int get Contest ans mod define

题目链接https://atcoder.jp/contests/abc200
A - Century
简单的abs(n-1)/100+1即可
B - 200th ABC-200
按题意写代码

点击查看代码
void solve(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        if(n%200==0)n/=200;
        else n=n*1000+200;
    }
    cout<<n;

}
C - Ringo's Favorite Numbers 2 用MAP来存储 对于每个%200的数相加 规律为这个数如果相减的值%200为0 那么他们%200的值必定相等
点击查看代码
void solve(){
    int n,k;cin>>n;
    map<int,int>mp;
    vector<int>a(n);
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];a[i]%=200;
        sum+=mp[a[i]];
        mp[a[i]]++;
    }
    cout<<sum;
}
D-Happy Birthday! 2 枚举子集 假设每个数都不相等那么如果超过8个数 将会有2^8=256种情况 根据鸽巢原理必定有解
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
//const int mod=998244353;
//int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
//int inv(int x){return qpw(x,mod-2);}
const int maxn=1e6+10;
int dp[200];
unordered_map<int,vector<int>>mp;
void print(vector<int>v){
    cout<<v.size()<<" ";
    for(auto t:v)cout<<t<<" ";
    cout<<'\n';
}
void solve(){
    int n;cin>>n;vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    n=min(n,8ll);
    for(int i=1;i<(1<<n);i++){
        int sum=0;
        vector<int>ans;
        for(int k=0;k<n;k++){
            if(i>>k&1)sum+=a[k],ans.pb(k+1);
        }
        if(mp[sum%200].size()){cout<<"Yes\n";print(mp[sum%200]),print(ans);return;}
        else mp[sum%200]=ans;
    }
    cout<<"No\n";
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}

补: E - Patisserie ABC 2 首先枚举取值情况 以s为例子 每个s都有s-1的空 根据高中所学的组合数学中的插排法可知存在C(s-1,2)种不同的情况即为(s-1)*(s-2)/2; 但是i j k的范围有限制 那么通过容斥定律进行容斥 我们使用隔板法求出每个情况的子集数 定义为int get(x) return (x-1)*(x-2)/2; 将i j k的情况进行分类讨论 方案一为有一个元素的值大于n 那么我们将一个n提出 然后在剩下的元素中进行隔板法 最后再将提出的n加回 又因为有三个元素所以*3 为get(s-n)*3 方案二为有两个元素的值大于n 同理可得 这次有ij ik jk 三种情况 为get(s-2*n)*3 方案三为有三个元素的值大于n 这次仅有一种情况那么得出为get(s-3*n) 根据容斥定律结果为t=get(s)-get(s-n)*3+get(s-2*n)*3-get(s-3*n) 对于k如果k>t那么对k-=t; 如果k<t那么就找到了所对应的s 接下来枚举i="" 对于每个i寻找它所对应的j的上下界="" 其中下界为宁外一个数取最大值即为max(s-n-i,1ll)="" 上界为另外一个数取最小即为min(s-n-1,n)="" 可取个数即为两数相减加一="" code:="" <details=""> 点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
//const int mod=998244353;
//int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
//int inv(int x){return qpw(x,mod-2);}
int get(int x){return x<=2?0:(x-1)*(x-2)/2;}
void solve(){
    int n,k;cin>>n>>k;
    for(int s=3;s<=n*3;s++){
        int t=get(s)-get(s-n)*3+get(s-2*n)*3-get(s-3*n);
        if(k>t){k-=t;continue;}
        for(int i=1;i<=n;i++){
            int mij=max(s-i-n,1ll),maj=min(s-i-1,n);
            if(mij>maj)continue;
            int num=maj-mij+1;
            if(k>num){k-=num;continue;}
            int j=mij+k-1;
            cout<<i<<" "<<j<<" "<<s-i-j;
            return;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}

标签:AtCoder,200,int,get,Contest,ans,mod,define
From: https://www.cnblogs.com/archer233/p/18111741

相关文章

  • Notes-02年Fan-2002-Analysis of guided resonances in photonic crystal slabs-BIC的
    Notes-02年Fan-2002-Analysisofguidedresonancesinphotoniccrystalslabs目录Notes-02年Fan-2002-Analysisofguidedresonancesinphotoniccrystalslabs共振的含义就是:在光锥内,发光、辐射。引言guidedmodeguidedmoderesonance--Similartotheguidedmode,a......
  • 用C语言输出100到200以内的所有素数 (只能被本身或则1整除的数)
    代码如下#include<stdio.h>intmain(){//输出100到200以内的所有素数(只能被本身或则1整除的数)   inti=0,j=0;   printf("100到200以内的所有素数为:");   for(i=100;i<=200;i++)   {         for(j=2;j<i;j++)  ......
  • P2036 [COCI2008-2009 #2] PERKET
    题目链接:本题显然考查\(\rmDFS\),但需注意是否恢复现场和参数设置的细节。#include<cstdio>#include<algorithm>constintN=15;structEdge{ intsour; intsweet;}e[N];boolst[N];//判断每个位置的数有没有被考虑过ints=1,t;//分别代表总的酸度和甜度......
  • AtCoder Beginner Contest 346 G
    #G-Alone(atcoder.jp)ABC346这一场来说相对比较简单,F是一个细节比较多的二分,G也算是一个比较板子的题。简单说一下G题的思路。其实比较容易想到用两个数组维护第i个数\(a_i\)在第i位之前出现的位置,以及第i个数在第i位之后出现的位置。那么当前位的能够满足的......
  • POI2005 KOS-Dicing
    网络流#二分考虑二分答案,用\(Dinic\)来\(check\)具体来说,就是对每一个人限制流量,然后检查能不能把所有场全部流满#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineullunsignedlonglong#defineALL(a)(a).begin(),(a).end()#definepb......
  • Poi2002滑雪者命名
    网络流#有源汇上下界费用流#最小点覆盖最小点覆盖问题这里可以直接有源汇上下界费用流//Author:xiaruize#ifndefONLINE_JUDGE#definedebug(x)cerr<<"OnLine:"<<__LINE__<<#x<<"="<<x<<endlboolstart_of_memory_use;#else#defi......
  • [ABC347] AtCoder Beginner Contest 347 题解
    [ABC347]AtCoderBeginnerContest347题解A模拟。BSA模板,把所有子串丢进哈希表里即可。C逆天题,这个分讨并不显然。考虑计算所有天数到今天的偏移量,然后如果最远的和最近的天数的距离\(\leA\)肯定可以,否则可以把所有天向右平移一段距离,然后使得最远的天到达第二周的......
  • The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jina
    The2023ICPCAsiaJinanRegionalContest(The2ndUniversalCup.Stage17:Jinan)D.LargestDigit题意:给定两个范围la,ra,lb,rb,求在两个范围内选任意两个数相加,求最大的数位思路:暴力枚举即可,遇到9跳出循环voidsolve(){llla,ra,lb,rb;cin>>la>>r......
  • foobar2000 v2.1.3 汉化版(x64 暂缺)
    foobar2000v2.1.3汉化版-----------------------【软件截图】----------------------     -----------------------【软件介绍】----------------------foobar2000是一个Windows平台下的高级音频播放器.包含完全支持unicode及支持播放增益的高级标签功能.特......
  • P1024 [NOIP2001 提高组] 一元三次方程求解
    题目描述有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在 −100 至 100 之间),且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后......