ZAFU寒假个人赛2022.01.22 A~H 题解

ZAFU寒假个人赛2022.01.22 A~H 题解 ZAFU寒假个人赛2022.01.22 A~H 题解 A - Weird Function(AtCoder - abc234_a)

思路： 直接调用函数即可，签到。

参考代码：

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
int f(int x){
    return x*x+2*x+3;
}
signed main(){
    int n;
    cin>>n;
    cout< 
B - typo(AtCoder - abc221_b) 
 
 
思路： 只需要交换相邻判断，
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         )
        
       
       
        O(n)
       
      
     O(n)扫一遍就好了。
 
 
参考代码： 
#include
#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
signed main(){
    string a,b;
    cin>>a>>b;
    bool st=false;
    if(a==b){cout<<"Yes"<C. Helpful Maths(CodeForces - 339A) 
 
 
思路： 用一个
     
      
       
        
         v
        
        
         e
        
        
         c
        
        
         t
        
        
         o
        
        
         r
        
       
       
        vector
       
      
     vector存所有数，
     
      
       
        
         s
        
        
         o
        
        
         r
        
        
         t
        
       
       
        sort
       
      
     sort输出即可。
 
 
参考代码： 
#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
signed main(){
    string s;
    cin>>s;
    vectorS;
    for(int i=0;i 
D. Berland Crossword(CodeForces - 1494B ) 
 
 
思路： 一道思维题，我们需要将所有
     
      
       
        
         N
        
        
         o
        
       
       
        No
       
      
     No的情况排除，然后输出
     
      
       
        
         Y
        
        
         e
        
        
         s
        
       
       
        Yes
       
      
     Yes的情况。显然当方位上黑点数
     
      
       
        
         =
        
        
         =
        
       
       
        ==
       
      
     ==
     
      
       
        
         n
        
       
       
        n
       
      
     n时，该方位对应的两侧黑点数至少为
     
      
       
        
         1
        
       
       
        1
       
      
     1，在角落上面。或者相对的两个方位上的黑点数都是
     
      
       
        
         =
        
        
         =
        
        
         n
        
       
       
        ==n
       
      
     ==n时，那么他们俩夹着的两侧黑点数必须都要至少两个，用来填充角落必须的黑点。最后进行第三种判定，如果一侧黑点数
     
      
       
        
         >
        
       
       
        >
       
      
     >
     
      
       
        
         n
        
       
       
        n
       
      
     n
     
      
       
        
         −
        
       
       
        -
       
      
     −
     
      
       
        
         2
        
       
       
        2
       
      
     2，说明其至少有个黑点落在左边或者右边的角上。同样是统计两侧夹两侧，统计一下相对两侧的边上黑点数至少落在角落上的数量是多少，同时判断是否该对相对边所夹的两个边上黑点数满足其最小要求即可。剩余情况全是满足。
 
 
参考代码： 
#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=110;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,u,r,d,l;
        cin>>n>>u>>r>>d>>l;
        if(u==n){
            if(l==0||r==0){
                cout<<"NO"<=n-1)x+=u-n+2;
        if(d>=n-1)x+=d-n+2;
        if(x>l+r){
            cout<<"NO"<=n-1)x+=l-n+2;
        if(r>=n-1)x+=r-n+2;
        if(x>u+d){
            cout<<"NO"< 
E - Select Mul(AtCoder - abc221_c) 
 
 
思路： 一道贪心，显然越大的数尽可能在前面对双方相乘整体的贡献越大。从
     
      
       
        
         9
        
       
       
        9
       
      
     9~
     
      
       
        
         0
        
       
       
        0
       
      
     0的数从高位平分给两边，但是错误了。
     
      
       
        
         h
        
        
         a
        
        
         c
        
        
         k
        
       
       
        hack
       
      
     hack数据：4320
     
      
       
        
         −
        
       
       
        -
       
      
     −>
     
      
       
        
         42
        
        
         ∗
        
        
         30
        
        
         <
        
        
         40
        
        
         ∗
        
        
         32
        
       
       
        42 * 30<40 * 32
       
      
     42∗30<40∗32。正解就是，每次分配进行判断，核心代码：
 
 
int getlen(int a){
    int x=0;
    while(a){
        a/=10;
        x++;
    }
    return x;
}
if((a*10+i)*b>=(b*10+i)*a&&getlen(a)<=getlen(b))a=a*10+i;
else b=b*10+i;
 
 
 
最后将
     
      
       
        
         a
        
       
       
        a
       
      
     a和
     
      
       
        
         b
        
       
       
        b
       
      
     b相乘即可。
 
 
参考代码： 
#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
int sum[15];
int getlen(int a){
    int x=0;
    while(a){
        a/=10;
        x++;
    }
    return x;
}
signed main(){
    int n;
    cin>>n;
    int cnt=0;
    while(n){
        int x=n%10;
        sum[x]++;
        n/=10;
        cnt++;
    }
    int a=0;
    int b=0;
    for(int i=9;i>=0;i--){
        while(sum[i]){
            sum[i]--;
            if((a*10+i)*b>=(b*10+i)*a&&getlen(a)<=getlen(b))a=a*10+i;
            else b=b*10+i;
        }
    }
    cout< 
F - Colorful Candies(AtCoder - abc210_c) 
 
 
思路： 双指针扫描，滑动窗口模型。数据范围
     
      
       
        
         1
        
        
         e
        
        
         9
        
       
       
        1e9
       
      
     1e9无法直接暴力，需要通过
     
      
       
        
         h
        
        
         a
        
        
         s
        
        
         h
        
       
       
        hash
       
      
     hash将大数离散成新的编号然后
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         )
        
       
       
        O(n)
       
      
     O(n)扫描。
 
 
参考代码： 
#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=3e5+10;
int a[N];
int sum[N];
signed main(){
    int n,k;
    cin>>n>>k;
    unordered_mapS;
    for(int i=1;i<=n;i++)cin>>a[i];
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(S[a[i]]==0){
            S[a[i]]=++cnt;
            a[i]=S[a[i]];
        }
        else{
            a[i]=S[a[i]];
        }
    }
    int MA=0;
    for(int i=1;i<=k;i++){
        if(sum[a[i]]==0)MA++;
        sum[a[i]]++;
    }
    int res=MA;
    for(int i=k+1;i<=n;i++){
        if(sum[a[i]]==0)res++;
        sum[a[i]]++;
        sum[a[i-k]]--;
        if(sum[a[i-k]]==0)res--;
        MA=max(MA,res);
    }
    cout< 
G - online games(AtCoder - abc221_d) 
 
 
思路： 离散+差分。这里可以使用
     
      
       
        
         m
        
        
         a
        
        
         p
        
       
       
        map
       
      
     map内的自动排序映射功能直接 *** 作。还有一个很强的功能，只要 *** 作过的数据，都会在
     
      
       
        
         m
        
        
         a
        
        
         p
        
       
       
        map
       
      
     map中有过记录，可以使用
     
      
       
        
         a
        
        
         u
        
        
         t
        
        
         o
        
       
       
        auto
       
      
     auto进行遍历。
 
 
参考代码： 
#include
using namespace std;
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
mapmp;
const int N=2e5+10;
int cnt[N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        mp[a]++;
        mp[a+b]--;
    }
    int pre=-1;
    int sum=0;
    for(auto x:mp){
        if(pre!=-1){
            cnt[sum]+=x.first-pre;
        }
        sum+=x.second;
        pre=x.first;
    }
    for(int i=1;i<=n;i++){
        if((i-1))cout<<' ';
        cout< 
H - Coprime 2(AtCoder - abc215_d) 
 
 
思路： 小数学，我的做法是将已有的数全部筛出质因数，然后
     
      
       
        
         u
        
        
         n
        
        
         i
        
        
         q
        
        
         u
        
        
         e
        
       
       
        unique
       
      
     unique一遍。然后取出容器中所有的数跑一便。复杂度
     
      
       
        
         O
        
        
         (
        
        
         m
        
        
         l
        
        
         o
        
        
         g
        
        
         m
        
        
         )
        
       
       
        O(mlogm)
       
      
     O(mlogm)。最后没打上
     
      
       
        
         t
        
        
         r
        
        
         u
        
        
         e
        
       
       
        true
       
      
     true标记的说明与原数组中所有数互质，升序输出即可。
 
 
参考代码： 
#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=2e5+10;
int a[N];
int primes[N],cnt;
vectorS;
bool st[N];
void get_divisors(int n){
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            S.push_back(n/i);
            if(i!=n/i){
                S.push_back(i);
            }
        }
    }
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        get_divisors(a[i]);
    }
    sort(S.begin(),S.end());
    S.erase(unique(S.begin(),S.end()),S.end());
    for(auto x:S){
        if(x==1)continue;
        st[x]=true;
        for(int i=x;i<=m;i+=x){
            st[i]=true;
        }
    }
    int sum=0;
    for(int i=1;i<=m;i++)if(!st[i])sum++;
    cout<
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5711118.html