这次惨烈的炸了个精光（只有20），然后对我的OI想法造成了巨大的转折。
（以上有点作，其实我只是再也不用vector存图了而已（用邻接表））
难度很不均匀，而且题型很狗（还有结论题？？？）
T1 坑人结论题，想出来100，没有就爆零
我和这道题杠了一个半小时，然后他们猥琐地告诉我结论——要么四边形要么不可能
反正我也不会证（雾）
找正方形的话枚举两个点，剩下的快排+二分或者hash。
可能是我的hash太丑了，被卡了
CODE
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=,seed=,mod=;
LL x[N],y[N],n,i,j,t;
bool flag,f[mod+];
inline void read(LL &x)
{
x=; char ch=getchar(); LL flag=;
while (ch<''||ch>'') { if (ch=='-') flag=-; ch=getchar(); }
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
x*=flag;
}
inline LL hash(LL a,LL b)
{
LL res=;
if (a<) a=-a*;
if (b<) b=-b*;
while (a!=-) res=((res+a%)*seed)%mod,a=a?a/:-;
while (b!=-) res=((res+b%)*seed)%mod,b=b?b/:-;
return res;
}
int main()
{
freopen("geometry.in","r",stdin); freopen("geometry.out","w",stdout);
read(t);
while (t--)
{
read(n);
memset(f,,sizeof(f)); flag=;
for (i=;i<=n;++i)
read(x[i]),read(y[i]),f[hash(x[i],y[i])]=;
for (i=;i<n;++i)
if (flag)
for (j=i+;j<=n;++j)
{
if (f[hash(x[i]+y[j]-y[i],x[i]+y[i]-x[j])]&&f[hash(x[j]+y[j]-y[i],x[i]+y[j]-x[j])]) { puts(""); flag=; break; }
if (f[hash(x[i]-y[j]+y[i],-x[i]+y[i]+x[j])]&&f[hash(x[j]-y[j]+y[i],-x[i]+y[j]+x[j])]) { puts(""); flag=; break; }
}
if (flag) puts("-1");
}
return ;
}
T2 超难，难度已经高于NOIP一等（标算应该是容斥DP），弃坑
只会20分暴力：
枚举全排列（用STL），然后暴力判断是否可行。
然后我试图打表找规律，又浪费了一个小时。
20分CODE
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=,mod=1e9+;
int a[N],n,t,k,i,tot,ans;
inline int next(int a,int b)
{
if (abs(a-b)<=) return ;
if (a==&&b==n) return ;
if (a==n&&b==) return ;
return ;
}
int main()
{
freopen("counting.in","r",stdin); freopen("counting.out","w",stdout);
scanf("%d%d",&n,&k);
for (i=;i<=n;++i)
a[i]=i;
do
{
tot=;
for (i=;i<=n;++i)
if (next(a[i],i)) tot++;
if (tot>=k) ans++;
if (ans==mod) ans=;
} while (next_permutation(a+,a+n+));
printf("%d\n",ans);
return ;
}
T3 SB题，一道链表题（像我这种连邻接表都不会的人SB地敲了vector然后全部爆内存）
一个类似邻接表的东西，只是多了一个end[]来表示结尾的元素以方便连接
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
int a[N],head[N],end[N],next[N],i,j,n,m,q,x,y;
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline void write(int x)
{
if(x/) write(x/);
putchar(x%+'');
}
int main()
{
freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout);
read(n); read(m); read(q);
memset(head,-,sizeof(head));
memset(end,-,sizeof(end));
memset(next,-,sizeof(next));
for (i=;i<=n;++i)
{
read(a[i]);
if (head[a[i]]==-) head[a[i]]=end[a[i]]=i; else end[a[i]]=next[end[a[i]]]=i;
}
while (q--)
{
read(x); read(y);
if (head[x]==-||x==y) continue;
if (end[y]==-) head[y]=head[x]; else next[end[y]]=head[x];
end[y]=end[x];
head[x]=end[x]=-;
}
for (i=;i<=m;++i)
for (j=head[i];j!=-;j=next[j])
a[j]=i;
for (i=;i<=n;++i)
write(a[i]),putchar(' ');
return ;
}