牛客练习赛3

题目链接： https://www.nowcoder.com/acm/contest/13#question

A.反蝴蝶效应

#include
#include
#include
using namespace std;
const int maxn=100005;
int n;
int a[maxn];
int main(){
    cin>>n;
    int ans=0;
 for(int i=1;i<=n;i++){
     scanf("%d",&a[i]);
       ans=max(a[i]+i-1,ans);
 
     }
    cout<

B.贝伦卡斯泰露
dfs暴力搜索，加几个优化


首先判断相同的数是否出现偶数次


记录每个数的总出现次数，若在某一个集合出现偶数次则跳出


若对于两个集合已经选择的数已经不是对应相等则跳出



#include
#include
#include
#include
#include
using namespace std;
vector g1;
vector g2;
int read(){
    char ch;
    int x=0,f=1;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a[45],num[45],num1[45],num2[45];
int n;
bool dfs(int x){
    int z=min(g1.size(),g2.size());
    if(x==n+1){
        if(z!=n/2)
            return false;
        for(int i=0;in/2||g2.size()>n/2)
        return false;
 
    for(int i=0;i

C 不会。。。
D.生物课程
首先只能有n-1条边，其次判断每个点所连接的点数，注意点较少时的特判

#include
#include
#include
using namespace std;
const int maxn=100005;
int n,m;
int num[maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x!=y){
            num[x]++;
            num[y]++;
        }
    }
    if(m!=n-1){
        cout<<"NotValid"<=5&&num[n]==4&&num[n-1]=4&&num[n]==3&&num[n-1]

E.绝对半径2051
首先将相同的数的下标记录到同一个vector里，再二分答案，对于每个容器里的数判断是否满足

#include
#include
#include
#include
using namespace std;
const int maxn=100005;
  int z=0;
struct P{
int x,i;
}p[maxn];
int vis[maxn];
int n,k;
vector g[maxn];
int a[maxn];
 
 
int read(){
    char ch;
    int x=0,f=1;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
bool cmp(P a,P b){
    if(a.x!=b.x)
        return a.xk+x)
                continue;
            return true;
        }
    return false;
}
int main(){
 
    n=read();
    k=read();
    for(int i=1;i<=n;i++){
        p[i].x=read();
        a[i]=p[i].x;
        p[i].i=i;
    }
    if(n==0){
        printf("0\n");
        return 0;
    }
    sort(p+1,p+1+n,cmp);
 
    for(int i=1;i<=n;i++){
        if(p[i].x!=p[i-1].x){
            z++;
            //vis[p[i].i]=z;
        }
        vis[p[i].i]=z;
        g[z].push_back(p[i].i);
       // cout<

F.监视任务
先将所有的区间按照右端点进行排序，根据贪心的思想，每次用树状数组求(l[i],r[i])区间的和，若大于等于k[i]，则不需操作，否则从r[i]开始向左进行操作，将不是1的全部改为1，直至区间和为k[i]

#include
#include
#include
#include
#include
using namespace std;
const int maxm=1000005;
const int maxn=500005;
int bit[maxn],vis[maxn];
int n,m;
struct P{
 int l,r,z;
}p[maxm];
int sum(int x){
    int s=0;
    while(x>0){
        s+=bit[x];
        x-=(x&-x);
    }
    return s;
}
void add(int x){
    while(x<=n){
        bit[x]+=1;
        x+=(x&-x);
    }
}
int read(){
    char ch;
    int x=0,f=1;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool cmp(P a,P b){
    if(a.r!=b.r)
        return a.r=p[i].z)
            continue;   // cout<=p[i].l&&k>0;j--){
            if(!vis[j]){
                vis[j]=1;
                k--;
                add(j);
            }
        }
    }
    printf("%d\n",sum(n));
}