F

博弈，A和B轮流操作，不能操作者输。双方都想对方输，所以都会做出最优选择。

• 1.删除图G中的一条边
• 2.删除不成环的连通分量

给定n个点，m条边，没有自环、重边。

连通分量：无向图的极大联通子图；

观察左边这个图，如果A一来就删除整个连通分量，A直接赢了，如果按一条边一条边，一个点一个删最后结果还是一样的，所以删除连通分量的效果其实和删除点、边效果是一样的，所以只需要考虑删除边的情况。所以我们只需要考虑点和边的个数一共有多少个就行了，奇数一定就是A赢，偶数B赢。

右边的图就是样例，无论你是删除这个连通分量，还是删除这条边，最后结果是一样的。

总结：
操作1会使边数减1，操作2会使边减少k条，点数减少k-1个，两种操作都会使点、边的数量减少奇数个，所以我们只需判断一开始点、边数量之和是奇数还是偶数。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y;

    for(int i=0;i<m;i++){
        cin>>x>>y;
    }
    if((n-m)&1)puts("Alice");
    else puts("Bob");

}

I

给你一个全排列序列;你可以给加1或加0，求有最少有多少对
满足。

思路：

这个关系式就是求逆序对的数量，跟这题 一样求逆序数，有三种方法，线段树，树状数组，归并排序。
这题要求最小，加1是可以减少逆序对的数量的。怎么加才能更少，可以发现，比当前数大1的数如果在当前数的前面就需要加1；如样例应该变成：.

代码：

//树状数组写的
#include<bits/stdc++.h>
using namespace std;
int c[200020],st[200020],a[200020];
int n;
void add(int x){
    for(;x<=n;x+=x&-x) c[x]++;
}
int get(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}
int main(){
    cin>>n;
    //long long ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(st[a[i]+1]==1) st[a[i]]=0,a[i]++;
        else st[a[i]]=1;
    }
    long long ans=0;
    for(int i=1;i<=n;i++){

        ans += get(n)-get(a[i]);
        add(a[i]);
    }
    cout<<ans<<endl;
    return 0;
}

陈卓的归并排序：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int a[maxn],slb[maxn]={0};
long long ans=0,tmp[maxn];
void merge(int l,int mid,int r)
{
    int x=l,y=mid+1,pos=0;
    while(x<=mid&&y<=r){
        if(a[x]>a[y]){
            tmp[pos++]=a[y++];
            ans+=(mid-x+1);
        }
        else tmp[pos++]=a[x++];
    }
    while(x<=mid)tmp[pos++]=a[x++];
    while(y<=r)tmp[pos++]=a[y++];
    for(int i=r;i>=l;i--)a[i]=tmp[--pos];
}
void merge_sort(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    merge(l,mid,r);
}
int main()
{
    int n,cou=0;cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(slb[a[i]+1]==1)++cou;
        else slb[a[i]]=1;
    }
    merge_sort(1,n);
    printf("%lld",ans-cou);
}

J

跟这题类似，二分
Best Cow Fences
不过这个是一维的，这一次的这个是二维的，那二维怎么转化成一维。

所以只需要二分两次加起来就可以了。

Best Cow Fences题解

#include <bits/stdc++.h>
using namespace std;
#define bug(x) cerr<<#x<<" : "<<x<<endl;
#define x first
#define y second
typedef long long ll;
const int N=2e5+10; 
double a[N],b[N];
double s[N];//前缀和数组
int n,f;

bool chk(double mid){
    //如果你用两重循环去chk的话会超时，具有单调性，我们就可以想到用双指针 
    /*for (int i = 1; i <= n-f+1; i++) {
        for (int j = i + f - 1; j <= n; j++) {
            if (s[j]-s[i-1]>=mid*(j-i+1))return 1;//s[]数组为每个位置奶牛数量的前缀和数组。
        }
    }
    return 0;*/
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i]-mid;//减mid的前缀和数组 ， 
    }
    double minx=2000;
    for(int i=0,j=f;j<=n;i++,j++){
        minx=min(s[i],minx);
        if(s[j]-minx>=0) return 1;//大于0说明符合 
    }
    return 0;
}

int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    double l=0,r=2000;
    while(r-l>1e-5){//浮点数二分 
        double mid=(l+r)/2;
        if(chk(mid)) l=mid;
        else r=mid;
    }
    printf("%ld\n",(int)r*1000);
}

今天这题范围要大一些，需要开long double ;

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
long double a[N],b[N];
long double find(int x,int n,long double a[]){
   long double minn=10000000,maxn=-1;
    for(int i=0;i<n;i++){
        minn=min(a[i],minn);
        maxn=max(a[i],maxn);
    }
   long double l=minn,r=maxn;
    while(r-l>10e-8){
       long double c[100005];
        c[0]=0;
       long double mid=(r+l)/2;
        for(int i=0;i<n;i++){
            c[i+1]=c[i]+a[i]-mid;
        }
        long double p=0,m=-1;
        for(int i=x;i<=n;i++){
            m=max(m,c[i]-p);
            p=min(p,c[i-x+1]);
        }
        if(m>0)
        l=mid;
        else
        r=mid;
    }
    return l;
}
int main() {
    int n, m,x,y;
    cin>>n>>m>>x>>y;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int j=0;j<m;j++) cin>>b[j];
    long double ans1,ans2;
    ans1=find(x,n,a);
    ans2=find(y,m,b);
    printf("%.10Lf\n",ans1+ans2);
}