头像

Snowandraw.




离线:21小时前


最近来访(265)
用户头像
谁说打代码不秃头
用户头像
ycycyc
用户头像
小飞龙
用户头像
尒猫不秀
用户头像
山海皆可平
用户头像
SuFame_Acwing_Only
用户头像
用户头像
Arthur_5
用户头像
焱_0
用户头像
wuzgnm
用户头像
ShallowHawk
用户头像
用户头像
Rain丶bow
用户头像
Peter_5
用户头像
我是fw
用户头像
starky
用户头像
sourlf
用户头像
挑战关注全acwing的人
用户头像
SayonaraGzm
用户头像
填海难....填心更难


Codeforces Global Round 17 A B C

A. Anti Light’s Cell Guessing

题意大概就是你最少查询几个点,使得任意隐藏的位置一定能通过回馈的哈密顿距离确定。有三种情况$1:只有一行一列时,那么不用查询,那么答案也就是0$$2:行或列中有一个是1,那么我们也可以通过查询临界点来确定任意的隐藏位置,答案是1$ $3:行或列都大于1,那么答案是2,我们可以通过查询同一侧的两个底角来确定任意隐藏点$
在这里插入图片描述

  • 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#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 lowbit(x) (x&-x)
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 pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        if(a==1&&b==1){
            cout<<0<<endl;
        }
        else if(a==1||b==1){
            cout<<1<<endl;
        }
        else cout<<2<<endl;
    }

    return 0;
}

B. Kalindrome Array

很容易想到的是双指针,之前CF有一场出现过字符暴力双指针。但是这题不能直接裸暴力,复杂度会高达$1e10$的级别,然后加上一点思维,容易发现我们通过双指针的移动,直至左指针与右指针指向的数不同,当然如果$i>=j$我们可以直接返回,因为已经满足回文,否则记录左指针指的数和右指针指的数然后分别操作一遍,然后判断最终能不能构造成回文。

  • 参考代码
#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#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 lowbit(x) (x&-x)
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 pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        int st=1,end=n;
        while(a[st]==a[end]){
            st++,end--;
        }
        if(st>=end){
            cout<<"YES"<<endl;
            continue;
        }
        int x1=a[st],x2=a[end];
        int st1=st,end1=end;//复制一下当前的st和end,因为我们还要进行第二次操作。
        bool success=false;
        while(st1<end1){
            if(a[st1]==a[end1])st1++,end1--;
            else if(a[st1]==x1)st1++;
            else if(a[end1]==x1)end1--;
            else break;
            if(st1>=end1)success=true;
        }
        st1=st,end1=end;
        while(st1<end1){
            if(a[st1]==a[end1])st1++,end1--;
            else if(a[st1]==x2)st1++;
            else if(a[end1]==x2)end1--;
            else break;
            if(st1>=end1)success=true;
        }
        if(success)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

C. Keshi Is Throwing a Party

这道题是一个二分检验的题目,没学过的同学推荐看一下acwing中有的最佳牛围栏这一道题,加上检验中有贪心的思想。

  • 参考代码
#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#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 lowbit(x) (x&-x)
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 pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int n;
struct{
    int a,b,c;
}nodes[N];
bool check(int x){
    int num=0;
    int l=0,r=x-1;//l表示左边有多少poorer,r表示右边有多少richer,一开始初始化第一个人那么左边为0,右边为x-1。
    for(int i=1;i<=n;i++){
        int b=nodes[i].b,c=nodes[i].c;
        if(l<=b&&r<=c){num++;l++,r--;}//如果当前人可取我们才进行num++,以及l和r的更新。
    }
    if(num>=x)return true;//如果num>=x说明我能够取到不低于x的人数。
    return false;
}
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            nodes[i].a=i;
            cin>>nodes[i].c>>nodes[i].b;//b放poorer,c放richer。
        }
        int l=1,r=n;//人数在1~n中检验
        while(l<r){
            int mid=l+r+1>>1;
            if(check(mid))l=mid;//如果当前人数满足,那么我们将区间延后。
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    unordered_map<int,int>S;
    while(t--){
        char x;
        int y;
        cin>>x>>y;
        if(x=='I'){
            S[y]++;
        }
        else{
            if(S[y])cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e5+10;
int a[N];
int son[N*31][2],idx;
void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int j=x>>i&1;
        if(!son[p][j])son[p][j]=++idx;
        p=son[p][j];
    }
}
int search(int x){
    int p=0;
    int res=0;
    for(int i=30;i>=0;i--){
        int j=x>>i&1;
        if(son[p][!j]){
            res=(res<<1)+1;
            p=son[p][!j];
        }
        else{
            res<<=1;
            p=son[p][j];
        }
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    int res=-2e9;
    for(int i=1;i<=n;i++){
        res=max(res,search(a[i]));
    }
    cout<<res<<endl;
    return 0;
}



现在回过头看y总代码觉得好复杂,其实直接记录第一个区间,并且如果后面的数$l$>当前记录的最大右支点直接加一即可。然后更新一下最大右支点,最后就可以输出区间的数量了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Ne{
    int l,r;
    bool operator<(const Ne &W)const {
        return l<W.l;
    }
}nodes[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>nodes[i].l>>nodes[i].r;
    }
    sort(nodes,nodes+n);
    int res=1;
    int MA=nodes[0].r;
    for(int i=1;i<n;i++){
        if(nodes[i].l<=MA){
            MA=max(MA,nodes[i].r);
        }
        else{
            MA=nodes[i].r;
            res++;
        }
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1081. 度的数量

#include<bits/stdc++.h>
using namespace std;
int n,m,k,b;
const int N=35;
int f[N][N];
void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(i==j)f[i][j]=1;
            else f[i][j]=f[i-1][j]+f[i-1][j-1];
        }
    }
}
int dp(int x){
    if(x==0)return 0;
    int step=0;//存当前1的个数
    int res=0;
    vector<int>S;
    while(x){
        S.push_back(x%b);
        x/=b;
    }
    for(int i=S.size()-1;i>=0;i--){//从大到小枚举
        int num=S[i];
        if(num){//如果有1
            res+=f[i][k-step];//加上他是0的情况。
            if(num>1){//如果是2那么可以全出来了,因为2>1&&2>0;
                if(k-step-1>=0)res+=f[i][k-step-1];//除了他本身剩下的数求组合数
                break;
            }
            else{
                step++;
                if(step>k)break;//如果step已经满了,说明当前数是1的位置已经在之前组合数宏计算过了,后面的也是一样的,所以
            }//可以直接break;
        }
        if(!i&&step==k)res++;//一个比较难理解的点,因为每个数我们求的都是假设他是0,剩余数的组合数,那么这个条件主要是针对
    }//的是全是0和1的数,最后还要加上他本身。
    return res;
}
int main(){
    cin>>n>>m>>k>>b;
    init();//预处理组合数
    cout<<dp(m)-dp(n-1)<<endl;//前缀和思想
    return 0;
}


活动打卡代码 AcWing 1077. 皇宫看守

#include<bits/stdc++.h>
using namespace std;
int t;
const int N=1510;
int idx,e[N],ne[N],h[N];
int w[N];
bool st[N];
int root;
int f[N][3];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    f[u][1]=1e9;
    f[u][0]=0;
    f[u][2]=w[u];
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][0]+=min(f[j][1],f[j][2]);
        f[u][2]+=min({f[j][0],f[j][1],f[j][2]});
    }
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        f[u][1]=min(f[u][1],f[u][0]+f[j][2]-min(f[j][1],f[j][2]));
    }
}
int main(){
    cin>>t;
    memset(h,-1,sizeof h);
    for(int i=1;i<=t;i++){
        int id,val;
        cin>>id>>val;
        int n;
        cin>>n;
        w[id]=val;
        while(n--){
            int x;
            cin>>x;
            add(id,x);
            st[x]=true;
        }
    }
    for(int i=1;i<=t;i++){
        if(!st[i]){
            root=i;
            break;
        }
    }
    dfs(root);
    cout<<min(f[root][1],f[root][2])<<endl;
    return 0;
}


活动打卡代码 AcWing 323. 战略游戏

#include<bits/stdc++.h>
using namespace std;
const int N=1510;
int idx,e[N],ne[N],h[N];
bool is_root[N];
int root;
int f[N][N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    f[u][1]=1;
    f[u][0]=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][1]+=min(f[j][0],f[j][1]);
        f[u][0]+=f[j][1];
    }
}
int main(){
    int n;
    while(cin>>n){
        memset(h,-1,sizeof h),idx=0;
        memset(is_root,0,sizeof is_root);
        for(int i=1;i<=n;i++){
            int a,b,c;
            scanf("%d:(%d)",&a,&c);
            while(c--){
                cin>>b;
                add(a,b);
                is_root[b]=true;
            }
        }
        for(int i=0;i<n;i++){
            if(!is_root[i]){
                root=i;
                break;
            }
        }
        dfs(root);
        cout<<min(f[root][0],f[root][1])<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1074. 二叉苹果树

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#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 lowbit(x) (x&-x)
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 pair<int,int>PII;
typedef pair<int,string>PIS;
int n,m;
const int N=110,M=N<<1;
int idx,e[M],ne[M],h[N],w[M];
int f[N][N];
void dfs(int u,int fa){
    for(int i=h[u];i!=-1;i=ne[i]){
        int uu=e[i];
        if(uu==fa)continue;
        dfs(uu,u);
        for(int j=m;j>=0;j--){
            for(int k=0;k<=j-1;k++){
                f[u][j]=max(f[u][j],f[u][j-1-k]+f[uu][k]+w[i]);
            }
        }
    }
}
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
signed main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    cout<<f[1][m]<<endl;
    return 0;
}


活动打卡代码 AcWing 1075. 数字转换

  • $Time:23:18$
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int sum[N];
int idx,e[N],ne[N],h[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int res;
int d1[N],d2[N];
void dfs(int u){
    if(d1[u])return ;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        dfs(j);
        if(d1[j]+1>d1[u]){
            d2[u]=d1[u];
            d1[u]=d1[j]+1;
        }
        else if(d1[j]+1>d2[u]){
            d2[u]=d1[j]+1;
        }
    }
    res=max(res,d1[u]+d2[u]);
}
int main(){
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
        for(int j=2;j<=n/i;j++){
            sum[i*j]+=i;
        }
    for(int i=2;i<=n;i++){
        if(sum[i]<i)add(sum[i],i);
    }
    for(int i=1;i<=n;i++){
        dfs(i);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1073. 树的中心

  • $Time:2021/11/13$ $3:03$

    $LCA倍增模型$

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=N<<1;
int idx,e[M],ne[M],h[N],w[M];
int d1[N],d2[N],p1[N];
int up[N];
const int INF=0x3f3f3f3f;
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs2(int u,int fa){
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        if(j==p1[u]){
            up[j]=max(up[u],d2[u])+w[i];//有路径压缩思想
        }
        else{
            up[j]=max(up[u],d1[u])+w[i];
        }
        dfs2(j,u);
    }
}
int dfs1(int u,int fa){
    d1[u]=d2[u]=-INF;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        int d=dfs1(j,u)+w[i];
        if(d>d1[u]){
            d2[u]=d1[u];
            d1[u]=d;
            p1[u]=j;
        }
        else if(d>d2[u]){
            d2[u]=d;
        }
    }
    if(d1[u]==-INF){
        d1[u]=d2[u]=0;
    }
    return d1[u];
}
int main(){
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs1(1,-1);
    dfs2(1,-1);
    int res=INF;
    for(int i=1;i<=n;i++){
        res=min(res,max(d1[i],up[i]));
    }
    cout<<res<<endl;
    return 0;
}