前言：
论读假题得来的\(80~pts\)
\(T1：\) 雷暴（storm）
思路：
据说是\(J\)组难度，几乎全切。记录下来每种颜色出现的最上/下/左/右，然后作差平方就好了
代码：
$code$
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+5,M=1e5+5,inf=1e5;
int n,m,k,a,lmin[M],lmax[M],rmin[M],rmax[M],s,t;
int main(){
// freopen("storm.in","r",stdin);
// freopen("storm.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m>>k;for(int i=1;i<=k;i++) lmin[i]=rmin[i]=inf;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a;lmin[a]=min(lmin[a],j),lmax[a]=max(lmax[a],j);//最左/右rmin[a]=min(rmin[a],i),rmax[a]=max(rmax[a],i);//最上/下}}for(int i=1;i<=k;i++){t=max(lmax[i]-lmin[i],rmax[i]-rmin[i])+1;//作差求边长s=t*t;//求面积cout<<s<<'\n';//输出答案}return 0;
}
\(T2：\) 神力 (god)
思路：
除了我几乎都想到了\(dp\)做法，但是很显然，正着推的\(dp\)有点假，因为它会算重，因为如果第三\(i\)步到了\(j\)，那么在第\(k\)（\(k>i\)）步到\(j\)的概率就不应该再计入了。因此我们可以倒过来\(dp\)。设\(dp_{i,j}\)表示经过后\(i\)个操作走到了距离原点为\(j\)的概率。此时唯一受影响的就是\(j=0\)的情况，强制令\(dp_{i,0}=1\)即可。
代码：
code
#include<iostream>
#define int long long
using namespace std;
const int N=5200,mod=1e9+7;
int n,p,q,a[N],f[N][N<<1];
inline int qpow(int x,int y){int res=1;while(y){if(y&1) res=(res*x)%mod;x=(x*x)%mod;y>>=1;}return res;
}//快速幂
signed main(){
// freopen("god.in","r",stdin);
// freopen("god.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>p;p=p*qpow(100,mod-2)%mod;q=(1-p+mod)%mod;//分数取模 for(int i=1;i<=n;i++) cin>>a[i];f[n+1][n+1]=1;for(int i=n;i>=1;i--){//倒推 for(int j=1;j<=(n<<1)+1;j++) f[i][j]=(f[i+1][j]*p+f[i+1][j-a[i]]*q)%mod;//很显然的递推式 f[i][n+1]=1;//强制为 1 }for(int i=1;i<=(n<<1)+1;i++) cout<<f[1][i]<<" ";//输出答案 return 0;
}
\(T3：\) 之缘千里（fate）
思路：
一道如果读真题我不一定会做，但是读假题得\(80~pts\)的题。
我们可以将这题看做是左括号的位置与\(1,3,5,7,...,2n-1\)的位置匹配。遍历\(2n\)个位置，看当点位置对应的会面那个位置能否作为左括号，若能，则从可以匹配的空缺位置中找到最小的两个匹配（满足题目字典序最小的要求）。
代码：
code
#include<iostream>
#include<set>
using namespace std;
const int N=2e6+5;
int n,x,fir[N],sec[N];bool flag[N];set<int> s;
int main(){
// freopen("fate.in","r",stdin);
// freopen("fate.out","w",stdout);ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=(n<<1);i++){cin>>x;if(fir[x]) sec[fir[x]]=i;//第二次出现的位置 else fir[x]=i;//第一次出现的位置 }for(int i=1;i<=(n<<1);i+=2) s.insert(i);//{1,3,5,7,...2*n-1}for(int i=1;i<=(n<<1);i++){if(sec[i]&&s.size()&&*s.rbegin()>=sec[i]){//有后面对应的数字&&还有位置填&&最后的空位在后面对应数字的后面（长难句，寄几分析去叭） s.erase(s.lower_bound(sec[i]));//把后面的那个位置占了 if(*s.rbegin()>=i) s.erase(s.lower_bound(i));//把现在这个位置占了 else{//前后位置不匹配 cout<<":(";//赛时题面里给的两个符号里面有空格啊啊啊 return 0;}flag[i]=flag[sec[i]]=1;//标注一下 }}if(s.size()){cout<<":(";return 0;}//没能完全匹配上 for(int i=1;i<=(n<<1);i++) //输出答案 if(flag[i]) cout<<"(";else cout<<")";return 0;
}
\(T4：\) 怒气冲天（ rectangle）
思路：
借鉴的一位学长的，学长安康，学长您吉祥，学长您别生气
其实我要写的好像跟学长的也会是差不多的（毕竟是借鉴的【逃】），那就不写了？？？我觉得思路还是挺好懂的，就是代码实现可能困难了些，应该粘个代码就行了吧（其实也是粘学长的，微微动了一点点）
$code$
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int maxn=4e5+5;
int n,lsh[maxn],tot,cnt,d[maxn],ans,res;
struct node{int x,y1,y2,typ,id;node(int x=0,int y1=0,int y2=0,int typ=0,int id=0):x(x),y1(y1),y2(y2),typ(typ),id(id){}bool operator<(const node &b)const{return (x<b.x)||(x==b.x&&typ<b.typ);}
}a[maxn];
struct BIT{int tr[maxn];void add(int p,int v){for(;p<=tot;p+=lowbit(p)) tr[p]+=v;}int query(int p){int res=0;for(;p;p-=lowbit(p)) res+=tr[p];return res;}
};
struct DS{BIT L,R;void add(int l,int r,int v){L.add(l,v),R.add(r,v);}int query(int l,int r){return L.query(r)-R.query(l-1);}
}D1,D2,D3;
//树状数组维护扫描线 struct seg{int ll,rr,sum;seg(int ll=0,int rr=0,int sum=0):ll(ll),rr(rr),sum(sum){}seg operator+(const seg &x)const{return seg(ll+x.ll,rr+x.rr,sum+x.sum+rr*x.ll);}
};
struct STR{#define ll(id) tr[id].ll#define rr(id) tr[id].rr#define sum(id) tr[id].sum seg tr[maxn<<2];void pushup(int id){tr[id]=tr[lid]+tr[rid];}void addl(int id,int l,int r,int p,int v){if(l==r){ll(id)+=v;return ;}int mid=(l+r)>>1;if(p<=mid) addl(lid,l,mid,p,v);else addl(rid,mid+1,r,p,v);pushup(id);}void addr(int id,int l,int r,int p,int v){if(l==r){rr(id)+=v;return ;}int mid=(l+r)>>1;if(p<=mid) addr(lid,l,mid,p,v);else addr(rid,mid+1,r,p,v);pushup(id);}seg query(int id,int L,int R,int l,int r){if(L>=l&&R<=r) return tr[id];int mid=(L+R)>>1;if(r<=mid) return query(lid,L,mid,l,r);if(l>mid) return query(rid,mid+1,R,l,r);return query(lid,L,mid,l,r)+query(rid,mid+1,R,l,r);}
}S;
//线段树 signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1,x1,x2,y1,y2;i<=n;i++){cin>>x1>>x2>>y1>>y2;lsh[++tot]=y1,lsh[++tot]=y2;a[++cnt]=node(x1,y1,y2,0,i);a[++cnt]=node(x2,y1,y2,1,i);}sort(lsh+1,lsh+tot+1);tot=unique(lsh+1,lsh+tot+1)-lsh-1;for(int i=1;i<=cnt;i++){a[i].y1=lower_bound(lsh+1,lsh+tot+1,a[i].y1)-lsh;a[i].y2=lower_bound(lsh+1,lsh+tot+1,a[i].y2)-lsh;}sort(a+1,a+cnt+1);ans=n*(n-1)*(n-2)/6;for(int i=1,l,r,typ,id;i<=cnt;i++){l=a[i].y1,r=a[i].y2,typ=a[i].typ,id=a[i].id;if(typ){D2.add(l,r,1);d[id]+=D1.query(l,r)-1;S.addl(1,1,tot,l,-1);S.addr(1,1,tot,r,-1);D3.add(l,r,-1);}else{D1.add(l,r,1);d[id]-=D2.query(l,r);int tmp=D3.query(l,r);ans-=tmp*(tmp-1)/2-S.query(1,1,tot,l,r).sum;S.addl(1,1,tot,l,1);S.addr(1,1,tot,r,1);D3.add(l,r,1);}}for(int i=1;i<=n;i++) res+=(n-2)*d[i]-d[i]*(d[i]-1);cout<<ans-res/2;return 0;
}
