牛客练习赛95过了两个题，rank165/1153，成功的把练习赛做成了百度之星。小白月赛过了4个题，rank215/1709，找回点做题的感觉了，手速还是不行，一些基本的建表建树，STL用法，都是变搜边用，对边界数据也不是很敏感。总归是再向好的地方发展。

练习赛95B

由叉积计算面积的公式
$$
S=\frac{1}{2}|(x_i-x_k)(y_j-y_k)-(x_j-x_k)(y_i-y_k)|
$$
可以发现面积是否为整数只与$i,j,k$三个点的$x,y$坐标的奇偶性有关，并且由于问的是非整数，可以忽略三点共线等情况（这些情况面积是整数$0$, 不会计入答案）

TZOJ 2519 Regetni(N个点求三角形面积为整数总数)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point
{
    ll p,q,c;
    bool operator<(const point &d)const{
        if(p<d.p)return true;
        else if(p==d.p)
        {
            if(q<d.q)return true;
            else if(q==d.q)
            {
                if(c<d.c)return true;
            }
        }
        return false;
    }
};
set<point>v;
void cs()
{
    pair<ll,ll>po[4];
    po[0]={2,2};
    po[1]={2,1};
    po[2]={1,2};
    po[3]={1,1};
    for(int p=0;p<4;p++)
        for(int q=0;q<4;q++)
            for(int c=0;c<4;c++)
            {
                ll x1,x2,x3,y1,y2,y3;
                x1=po[p].first;y1=po[p].second;
                x2=po[q].first;y2=po[q].second;
                x3=po[c].first;y3=po[c].second;
                if((x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1)%2==0)
                {
                    ll d[4];
                    d[0]=p;
                    d[1]=q;
                    d[2]=c;
                    sort(d,d+3);
                    v.insert({d[0],d[1],d[2]});
                }
            }
}
long long C(ll n,ll m)
{
    if(m>n)return 0;
    long long sum=1;
    for(ll i=1;i<=m;i++)
        sum=sum*(n-i+1)/i;
    return sum;
}
int main()
{
    cs();
    ll t,n,ca=1;
    ll d[4]={0};
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        if(x%2==0&&y%2==0)d[0]++;
        if(x%2==0&&y%2!=0)d[1]++;
        if(x%2!=0&&y%2==0)d[2]++;
        if(x%2!=0&&y%2!=0)d[3]++;
    }
    long long sum=0;
    for(auto x:v)
    {
        ll p=x.p;
        ll q=x.q;
        ll c=x.c;
        //printf("%d %d %d\n",p,q,c);
        ll f[4]={0};
        f[p]++;f[q]++;f[c]++;
        sum+=C(d[0],f[0])*C(d[1],f[1])*C(d[2],f[2])*C(d[3],f[3]);
    }
    printf("%lld\n",C(n,3)-sum);
    //printf("Scenario #%d:\n%lld\n\n",ca++,sum);
    //system("pause");
    return 0;
}

小白月赛E

本题要求树上有多少个起点和终点均为黑点的路径。

答案显然是 $C_{cnt}^2$其中cnt是黑点的数量。

至于黑点数量怎么求，按照二分图染色的方式dfs一下即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
vector<int> node[N];
typedef long long ll;
ll read(){
    ll x;scanf("%lld",&x);return x;
}
void add(int a,int b){
    node[a].push_back(b);
    node[b].push_back(a);
}
ll res;
void dfs(int u,int v,int h){
    if(h==1)res++;
    for(int x:node[u])if(x!=v)dfs(x,u,h^1);
}
void solve(){
    int n=read();res=0;
    for(int i=1;i<=n;i++)node[i].clear();
    for(int i=1;i<n;i++){
        int a=read(),b=read();
        add(a,b);
    }
    dfs(1,0,1);
    cout<<res*(res+1)/2<<"\n";
}
int main(){
    int T=read();
    while(T--)solve();
}

小白月赛F

知识点：树，贪心

思路：

显然，如果最长链不超过所有点数的一半，那么所有的点都可以成为重心。

如果最长链超过了sum的一半，那么重心一定落在最长链上。求出有效的左右端点位置即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
long long a[101010];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m,i,j,k,t,_=1;
    cin>>_;
    while(_--){
        cin>>n;
        long long sum=0,ma=0,res=0;
        for(i=0;i<n;i++)cin>>a[i],sum+=a[i],ma=max(ma,a[i]);
        //sort(a,a+n);
        long long yu=sum-ma;
        //如果一个最大值不超过其他点的总和，那么所有点全部都可以是重心
        if(ma<=yu){cout<<sum<<'\n';continue;}
        //否则只计算最长链，找到中间合法部分（小+余≥大）
        long long l=(ma-yu+1)/2,r=ma+1-l;
        cout<<r-l+1<<'\n';
    }
}