## 练习赛95B

$$S=\frac{1}{2}|(x_i-x_k)(y_j-y_k)-(x_j-x_k)(y_i-y_k)|$$

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

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
vector<int> node[N];
typedef long long ll;
ll x;scanf("%lld",&x);return x;
}
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(){
for(int i=1;i<=n;i++)node[i].clear();
for(int i=1;i<n;i++){
}
dfs(1,0,1);
cout<<res*(res+1)/2<<"\n";
}
int main(){
while(T--)solve();
}

## 小白月赛F

#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';
}
}