比赛概况：
50+100+0+70
T1：ans%mod，挂50分
先枚举点，再枚举出边数，复杂度为边数的两倍
T2:100分
最水的一题，但老师觉得最难？？？？、
直接离线，树状数组维护就行了
#include<bits/stdc++.h>
using namespace std;
long long n,Q,a[200005],t[200005],tree[200005],top=1,ans[200005],ls;
struct xw
{
long long l,r,id;
}q[200005];
int cmp(xw A,xw B)
{
return A.r<B.r;
}
long long lowbit(int xx)
{
return xx&(-xx);
}
void add(int x,int sum)
{
while(x<=n)
{
tree[x]+=sum;
x=x+lowbit(x);
}
return ;
}
long long work(int x)
{
if(x==0) return 0;
ls=0;
while(x>0)
{
ls+=tree[x];
x-=lowbit(x);
}
return ls;
}
int main()
{
freopen("liyue.in","r",stdin);
freopen("liyue.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
cin>>Q;
for(int i=1;i<=Q;i++)
{
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+Q+1,cmp);
top=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j*j<=2*n;j++)
{
if(j*j-a[i]>=1)
{
if(t[j*j-a[i]]!=0)
{
add(t[j*j-a[i]],1);
}
}
}
t[a[i]]=i;
if(q[top].r==i)
{
ans[q[top].id]+=work(q[top].r)-work(q[top].l-1);
while(q[top+1].r==i&&top+1<=Q)
{
top++;
ans[q[top].id]+=work(q[top].r)-work(q[top].l-1);
}
top++;
if(top>Q) break;
}
}
for(int i=1;i<=Q;i++)
{
printf("%lld\n",ans[i]);
}
return 0;
}
T3
对于每一个环，通电时间就是环上最小边和次小边与第三小边取min
不在环上的边就直接取min就好了
### （死在不会判环）
qr大佬的代码用了tarjan判环，思路大概是一个环上的点low值相等（除了dfn最小的点），都为dfn最小的点
#include<bits/stdc++.h>
using namespace std;
long long w[4000005],u[4000005],v[4000005],head[1000005],nex[4000005],cnt=1,n,m,aa,bb,cc,num,dfn[1000005],low[1000005];
long long col,vis[1000005],ck[4000005],flag,lls,ans=99999999999;
vector<long long> G[1000005];
void add(int xx,int yy,int zz)
{
cnt++;
u[cnt]=xx;
v[cnt]=yy;
w[cnt]=zz;
nex[cnt]=head[u[cnt]];
head[u[cnt]]=cnt;
}
void tarj(int x,int ff)
{
num++;
dfn[x]=low[x]=num;
for(int i=head[x];i!=0;i=nex[i])
{
int to=v[i];
if(dfn[to]==0)
{
tarj(to,i);
low[x]=min(low[x],low[to]);
}
else
{
if(i!=(ff^1))
{
low[x]=min(low[x],dfn[to]);
}
}
}
}
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i!=0;i=nex[i])
{
int to=v[i];
if(ck[i]==1) continue;
if(!(low[to]==flag||dfn[to]==flag)) continue;
G[col].push_back(w[i]);
ck[i]=ck[i^1]=1;
dfs(to);
}
}
int main()
{
freopen("inazuma.in","r",stdin);
freopen("inazuma.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&aa,&bb,&cc);
add(aa,bb,cc);
add(bb,aa,cc);
}
tarj(1,0);
for(int i=1;i<=n;i++)
{
flag=low[i];
col++;
dfs(i);
}
for(int i=1;i<=col;i++)
{
if(G[i].size()==0) continue;
sort(G[i].begin(),G[i].end());
lls=G[i][0]+G[i][1];
if(G[i].size()>2)
{
lls=min(lls,G[i][2]);
}
ans=min(ans,lls);
}
for(int i=2;i<=cnt;i++)
{
if(ck[i]==0)
{
ans=min(ans,w[i]);
}
}
cout<<ans;
return 0;
}
T4
高斯消元拿70，剩下不知道怎么拿了，貌似有0的数据会被卡
#include<bits/stdc++.h>
using namespace std;
long long T,ls,flag,fflag;
double a[5][5],li=0,sum;
double dabs(double aa)
{
if(aa<li) return -aa;
else return aa;
}
int main()
{
freopen("sumeru.in","r",stdin);
freopen("sumeru.out","w",stdout);
cin>>T;
while(T--)
{
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
scanf("%lld",&ls);
a[i][j]=ls;
}
}
for(int i=1;i<=3;i++)
{
scanf("%lld",&ls);
a[4][i]=ls;
}
for(int i=1;i<=3;i++)
{
if(dabs(a[i][i])>li)
{
for(int j=i+1;j<=3;j++)
{
sum=a[i][j]*1.000/a[i][i]*1.0000;
if(dabs(a[i][j])<=li) continue;
for(int h=i+1;h<=4;h++)
{
a[h][j]=a[h][j]-sum*a[h][i];
}
}
}
else
{
flag=0;
for(int j=i+1;j<=3;j++)
{
if(dabs(a[i][j])>li)
{
flag=1;
for(int h=1;h<=4;h++) swap(a[h][i],a[h][j]);
}
}
if(flag==0) continue;
else
{
for(int j=i+1;j<=3;j++)
{
sum=a[i][j]*1.000/a[i][i]*1.0000;
if(dabs(a[i][j])<=li) continue;
for(int h=i+1;h<=4;h++)
{
a[h][j]=a[h][j]-sum*a[h][i];
}
}
}
}
}
fflag=1;
for(int i=3;i>=1;i--)
{
if((a[i][i]<-li&&a[4][i]>li)||(a[i][i]>li&&a[4][i]<-li))
{
printf("NO\n");
fflag=0;
break;
}
if(dabs(a[i][i])<=li&&dabs(a[4][i])>li)
{
printf("NO\n");
fflag=0;
break;
}
if(dabs(a[i][i])<=li&&dabs(a[4][i])<=li)
{
printf("YES\n");
fflag=0;
break;
}
if(dabs(a[i][i])>li&&dabs(a[4][i])<=li)
{
continue;
}
for(int j=i-1;j>=1;j--)
{
sum=a[i][j]*1.000/a[i][i]*1.0000;
a[4][j]=a[4][j]-sum*a[4][i];
}
}
if(fflag==1)
{
printf("YES\n");
}
}
return 0;
}