题解直通车：集美大学第9届校赛【出题人题解】 - 知乎 (zhihu.com)
补题补知识：
1.多边形叉积用来算多边形的面积的两倍
H-面积_集美大学第九届程序设计竞赛（同步赛） (nowcoder.com)
#include <bits/stdc++.h> using namespace std; int main() { long long x[6], y[6]; for(int i=1; i<=5; ++i) cin>>x[i]>>y[i]; x[0]=x[5]; y[0]=y[5]; long long res=0; for(int i=1; i<=5; ++i) res += x[i]*y[i-1] - x[i-1]*y[i]; cout<<abs(res); return 0; }
2.F-区间_集美大学第九届程序设计竞赛（同步赛） (nowcoder.com)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; struct { ll l,r; }tr[N]; int n; void solve() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&tr[i].l,&tr[i].r); ll res=0; for(int B=59;B>=0;B--) { bool f=true; for(int i=1;i<=n;i++) if(~tr[i].r>>B&1) { f=false; break; } if(f) { res+=1ll<<B; for(int i=1;i<=n;i++) if(~tr[i].l>>B&1) tr[i].l=0; } else { for(int i=1;i<=n;i++) if((tr[i].r>>B&1)&&(~tr[i].l>>B&1)) tr[i].l=tr[i].r=(1ll<<B)-1; } } printf("%lld\n",res); } int main() { int T=1; while(T--) solve(); return 0; }
3.I-逛孙厝的贝贝_集美大学第九届程序设计竞赛（同步赛） (nowcoder.com)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=310,M=90010,mod=1e9+7,K=1e7+10; int n,m,k; int w[N]; int Sum,sum[M]; int f[N][M]; int fac[K],inv[K]; int qmi(int a,int k,int p) { int res=1; while(k) { if(k&1) res=(ll)res*a%p; a=(ll)a*a%p; k>>=1; } return res; } void init(int n) { fac[0]=1; for(int i=1;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod; inv[n]=qmi(fac[n],mod-2,mod); for(int i=n;i;i--) inv[i-1]=(ll)inv[i]*i%mod; } int C(int a,int b) { if(a<b) return 0; return (ll)fac[a]*inv[b]%mod*inv[a-b]%mod; } void solve() { init(1e7); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) scanf("%d",&w[i]),Sum+=w[i]; f[0][0]=1; for(int i=1;i<=m;i++) { sum[0]=0; for(int j=0;j<=Sum;j++) sum[j+1]=(sum[j]+f[i-1][j])%mod; for(int j=0;j<=Sum;j++) f[i][j]=(sum[j+1]-sum[max(0,j-w[i])]+mod)%mod; } if(n==m) { printf("%d\n",f[m][k]); return; } int ans=0; for(int i=0;i<=Sum;i++) ans=(ans+(ll)f[m][i]*C(k-i+n-m-1,n-m-1)%mod)%mod; printf("%d\n",ans); } int main() { int T=1; while(T--) solve(); return 0; }
3.L-序列_集美大学第九届程序设计竞赛（同步赛） (nowcoder.com)
#include<bits/stdc++.h> using namespace std; #define lowbit(x) x&-x typedef long long ll; const int N=1e5+10; int tr[N]; int n,a[N]; int l[N],r[N]; void add(int x) { for(int i=x;i<=n;i+=lowbit(i)) tr[i]++; } int sum(int x) { int res=0; for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } void solve() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) l[i]=i-1-sum(a[i]),add(a[i]); memset(tr,0,sizeof tr); for(int i=n;i;i--) r[i]=n-i-sum(a[i]),add(a[i]); int res=0; for(int i=1;i<=n;i++) res+=min(l[i],r[i]); printf("%d\n",res); } int main() { int T=1; while(T--) solve(); return 0; }
4.M-循环节_集美大学第九届程序设计竞赛（同步赛） (nowcoder.com)
比赛时代码：
思路：看看当前l能不能更新到1的位置，r能不能更新到n的位置假如可以并且这个区间长度可以被整除说明这个区间是可以作为循环戒更新S串的
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,ne[N]; char p[N]; int l[N],r[N]; int main() { scanf("%d%d%s",&n,&m,p+1); for(int i=2,j=0;i<=n;i++) { while(j&&p[i]!=p[j+1]) j=ne[j]; if(p[i]==p[j+1]) j++; ne[i]=j; } int t=n; r[t]=n; while(ne[t]!=0) t=ne[t],r[t]=n; l[1]=1; for(int i=2;i<=n;i++) { int j=ne[i]; l[i]=l[j]; } int a,b; while(m--) { scanf("%d%d",&a,&b); a++,b++; if(l[a]==1&&r[b]==n&&n%(b-a+1)==0) puts("YES"); else puts("NO"); } return 0; }
题解：
这是一个kmp经典应用，len=n−next[n]即是最短循环节的长度
一个字符串是否是原串的循环节，取决于这个串的左右端点取模len都需要等于0，并且r−l+1整除n
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int ne[N]; char s[N]; int n,m; void solve() { scanf("%d%d",&n,&m); scanf("%s",s+1); for(int i=2,j=0;i<=n;i++) { while(j&&s[i]!=s[j+1]) j=ne[j]; if(s[i]==s[j+1]) j++; ne[i]=j; } int len=n-ne[n]; if(!ne[n]) len=n; int l,r; while(m--) { scanf("%d%d",&l,&r); l++,r++; if(l==1&&r==n) puts("YES"); else { if((l-1)%len==0&&r%len==0&&n%(r-l+1)==0) puts("YES"); else puts("NO"); } } } int main() { int T=1; while(T--) solve(); return 0; }
