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