T1 思路： 前置知识：对于一个四边形，三边之和一定大于第四边。 设sx为每一边的上限，i，j为两边 因为由题意可得：任意一边都大于等于1且为整数（k为正整数） 所以可以有如下几个不等式： 1.n-i-j-k>=1 k<=sx 可以得出： k<=n-i-j-1 k<=sx 所以k的范围为k<=min(n-i-j-1,sx) 2.k>=1 n-i-j-k<=sx 可以得出: k>=1 k>=n-sx-i-j 所以k的范围为k>=max(n-sx-i-j,1) 综上，max(n-sx-i-j,1)<=k<=min(n-i-j-1,sx) 代码:
#include<bits/stdc++.h> using namespace std; int main(){ freopen("wood.in","r",stdin); freopen("wood.out","w",stdout); int n; long long ans=0; cin>>n; int sx; if(n%2==0) sx=n/2-1; else sx=n/2; for(int i=1;i<=sx;i++) for(int j=1;j<=min(sx,n-i-2);j++) ans+=(min(sx,n-i-j-1)-max(n-sx-i-j,1)+1); cout<<ans; return 0; }T2 线段树模板： 代码:
#include <bits/stdc++.h> using namespace std; const int maxn=100000+10; int a[4*maxn],n,m,x,y,z; void update(int h,int l,int r,int s,int t){ if(l>t||r<s) return; if(l==r&&l>=s&&r<=t){ a[h]=1-a[h]; return; } int mid=(l+r)>>1; update(h<<1,l,mid,s,t); update(h<<1|1,mid+1,r,s,t); a[h]=a[h<<1]+a[h<<1|1]; } int query(int h,int l,int r,int s,int t){ if(l>t||r<s) return 0; if(s<=l&&r<=t) return a[h]; int mid=(l+r)>>1; return query(h<<1,l,mid,s,t)+query(h<<1|1,mid+1,r,s,t); } int main(){ freopen("party.in","r",stdin); freopen("party.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); if(x==0) update(1,1,n,y,z); else printf("%d\n",query(1,1,n,y,z)); } return 0; }T3:WA 算法：不加路径压缩的并查集or可持久化并查集 思路：可以采取一种染色的方法： 1.将一个结点染上任意一种颜色 2.搜索出每一个与它相连的点 3.判断这几个点，并将其染上同一颜色（如果这几个点中有些点相连，就不符合二分图的定义了） 代码：
#include <bits/stdc++.h> using namespace std; const int maxn=1e4+10,maxm=2e6+10,inf=1e9; int fa[maxn<<1],from[maxm],to[maxm],fron[maxm]; bool can[maxm]; int n,m,e,last; inline int find(int x){//找父亲结点 if(fa[x]==x) return x; return fa[x]; } inline void add(int x,int y){//加边 int fx=find(x),fy=find(y); if(fx==fy){ from[++e]=inf; to[e]=inf; return; } fa[fx]=fy; from[++e]=fx; to[e]=fy; } inline void del(){//删边 if(from[e]==inf&&to[e]==inf){ e--; return; } int x=from[e]; int y=to[e]; fa[x]=x; e--; } int main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n<<1;i++) fa[i]=i;//初始化->每个结点的父亲是它自己 for(int i=1;i<=m;i++){ int op,x,y; scanf("%d",&op); if(op==1){ scanf("%d%d",&x,&y); fron[i]=last; if(find(x)==find(y)||find(x+n)==find(y+n)|| can[last]) can[i] = true;//染色-判断是否为二分图 else{ add(x,y+n);add(x+n,y); } last=i; if(can[i]) printf("NO\n"); else printf("YES\n"); } if(op == 2){//删边 if(!can[last]) del(),del(); last=fron[last]; if(can[last]) printf("NO\n"); else printf("YES\n"); } } return 0; }反思：1.努力学习&熟练各种算法 2.尝试不同思路
