Comet OJ CCPC－Wannafly Comet OJ 夏季欢乐赛（2019）
Preface
在一個月黑風高的夜晚我這個蒟蒻正躊躇著打什么比賽好
是繼續做一場AGC，還是去刷一場CF
然后，一道金光閃過（滑稽），我們的紅太陽bzt給我指明了方向：
你太菜了，我知道有一場很水的比賽，你快來做吧
然后我就點進比賽，看到了排行榜上Minamoto旁大大的AK二字，不禁心生敬意
同時對于它一人狂得兩題一血，身穿兩條小裙子的事跡有不免心生敬佩
然后我就開始了刷水之旅（被水題狂虐）
以下題目按照編號順序排列（怎么感覺在說廢話）
A 完全k叉樹
一眼發現可以處理出這棵樹的深度和最后一層的節點數，然后分類討論路徑的拼法即可
要注意細節，同時還有\(k=1\)的情況要特判
#include<cstdio> using namespace std; int t,n,k; int main() {for (scanf("%d",&t);t;--t){scanf("%d%d",&k,&n); int dep=0; long long cur=1,lst=1;if (k==1) { printf("%d\n",n-1); continue; }if (n==1) { puts("0"); continue; }while (cur<n) ++dep,cur=cur+(lst*=k);cur-=lst; int left=n-cur;if (left>(lst/k)) printf("%d\n",dep<<1); else printf("%d\n",(dep<<1)-1);}return 0; }B 距離產生美
比A題簡單，發現原序列的數據范圍是\(10^5\)，\(k\le 10^9\)，所以我們要修改就直接改到\(10^{18}\)即可
隨便DP一下即可
#include<cstdio> #include<iostream> #include<algorithm> #define RI register int using namespace std; const int N=100005; int n,k,a[N],f[N][2]; int main() {RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i){scanf("%d",&a[i]); if (abs(a[i]-a[i-1])>=k)f[i][0]=min(f[i-1][0],f[i-1][1]); else f[i][0]=f[i-1][1];f[i][1]=min(f[i-1][0],f[i-1][1])+1;}return printf("%d",min(f[n][0],f[n][1])),0; }C 烤面包片
首先我們肯定容易發現，對于\(x! \operatorname{mod} y\)，若\(x>=y\)值一定為\(0\)
然后我們掏出計算器一算就發現\(4!!\)已經大到天上去了（好吧也就\(10^{24}\)級別）
所以我們要考慮的只有\(n=0,1,2,3\)的情況，注意下細節即可（PS：\(0!=1\)）
#include<cstdio> #define RI register int using namespace std; int n,mod; int main() {scanf("%d%d",&n,&mod); if (n==0||n==1||n==2) return printf("%d",(n?n:1)%mod),0;if (n>3) return puts("0"),0; int ret=1;for (RI i=1;i<=720;++i) ret=1LL*ret*i%mod; return printf("%d",ret),0; }D 茶顏悅色
首先我們轉化問題，把一個點化為一個矩形，表示若把正方形的某個定點放置在這個矩形內能覆蓋到這個點
所以現在問題就變成了平面矩形覆蓋次數最多的點，直接掃描線+樹狀數組即可
#include<cstdio> #include<iostream> #include<algorithm> #define RI register int #define CI const int& using namespace std; const int N=400005; struct line {int x,y1,y2,tp;inline line(CI X=0,CI Y1=0,CI Y2=0,CI Tp=0){x=X; y1=Y1; y2=Y2; tp=Tp;}friend inline bool operator < (const line& A,const line& B){return A.x<B.x;} }l[N]; int n,k,x,y,rst[N],num,ans; class Segment_Tree {private:struct segment{int mx,tag;}node[N<<2];#define M(x) node[x].mx#define T(x) node[x].tag#define TN CI now=1,CI l=1,CI r=numinline void apply(CI now,CI mv){M(now)+=mv; T(now)+=mv;}inline void pushup(CI now){M(now)=max(M(now<<1),M(now<<1|1));}inline void pushdown(CI now){if (T(now)) apply(now<<1,T(now)),apply(now<<1|1,T(now)),T(now)=0;}public:inline void modify(CI beg,CI end,CI mv,TN){if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);if (beg<=mid) modify(beg,end,mv,now<<1,l,mid);if (end>mid) modify(beg,end,mv,now<<1|1,mid+1,r); pushup(now);}inline int query(void){return M(1);}#undef M#undef T#undef TN }SEG; inline int find(CI x) {return lower_bound(rst+1,rst+num+1,x)-rst; } int main() {RI i,j,k; for (scanf("%d%d",&n,&k),i=1;i<=n;++i){scanf("%d%d",&x,&y); x<<=1; y<<=1; rst[i]=y-k; rst[n+i]=y+k;l[i]=line(x-k,y-k,y+k,1); l[n+i]=line(x+k+1,y-k,y+k,-1);}sort(rst+1,rst+(n<<1)+1); num=unique(rst+1,rst+(n<<1)+1)-rst-1;for (i=1;i<=(n<<1);++i) l[i].y1=find(l[i].y1),l[i].y2=find(l[i].y2);for (sort(l+1,l+(n<<1)+1),i=1;i<=(n<<1);i=j+1){for (j=i;j<(n<<1)&&l[j+1].x==l[i].x;++j);for (k=i;k<=j;++k) SEG.modify(l[k].y1,l[k].y2,l[k].tp);ans=max(ans,SEG.query());}return printf("%d",ans),0; }E 飛行棋
有點套路的期望題。首先我們考慮倒推，即用\(f_i\)表示距離終點\(i\)步時的期望步數
顯然\(f_0=0\)，然后我們考慮對于\(f_i(i\in [1,k])\)，它們的答案是什么
發現對于它們任何一個位置，直接走到終點的概率就是\(\frac{1}{k}\)，否則就會落入另一個狀態
而我們發現這些狀態的問題和原問題等價，我們可以很容易地從概率推出它們的期望都是\(k\)
PS：如果你不想觀察出這個結論的話你也可以大力列出方程然后高斯消元
然后我們發現接下來的轉移由于沒有走到終點再走回的這樣一個過程，轉移就比較單一，即為\(f_i=\frac{1}{k}\cdot \sum_{j=i-k}^{i-1} f_j+1\)，我們可以容易的使用矩陣快速冪來優化復雜度到\(O(k^3\cdot\log n)\)
#include<cstdio> #include<cstring> #define RI register int #define CI const int& using namespace std; const int N=25,mod=1e9+7; long long d,k; int invk; inline void inc(int& x,CI y) {if ((x+=y)>=mod) x-=mod; } inline int quick_pow(int x,int p=mod-2,int mul=1) {for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul; } struct Matrix {int mat[N][N],n,m;inline Matrix(CI N=0,CI M=0){n=N; m=M; memset(mat,0,sizeof(mat));}inline int* operator [] (CI x) { return mat[x]; }friend inline Matrix operator * (Matrix A,Matrix B){Matrix C(A.n,B.m); for (RI i=0;i<C.n;++i)for (RI j=0;j<C.m;++j) for (RI k=0;k<A.m;++k)inc(C[i][j],1LL*A[i][k]*B[k][j]%mod); return C;}friend inline Matrix operator ^ (Matrix A,long long p){Matrix T(A.n,A.m); for (RI i=0;i<A.n;++i) T[i][i]=1;for (;p;p>>=1,A=A*A) if (p&1) T=T*A; return T;} }; int main() {scanf("%lld%lld",&d,&k); Matrix S(k+1,1),P(k+1,k+1);RI i; for (invk=quick_pow(k%mod),i=0;i<k;++i) S[i][0]=k; S[k][0]=1;for (i=0;i<k-1;++i) P[i][i+1]=1; for (i=0;i<k;++i) P[k-1][i]=invk;P[k-1][k]=P[k][k]=1; P=P^(d-k); S=P*S; return printf("%d",S[k-1][0]),0; }F 三元組
我們考慮把\(\min,\max\)去掉，那么我們強制\(a_i+a_j\)是\(\min\)，這樣題目就變成求\(2\cdot(a_i+a_j)\le b_i+b_j\)的\(c_i\cdot c_j\)的和
把式子拆開并移項就得到了\((2\cdot a_i-b_i)+(2\cdot a_j-b_j)\le 0\)，這個我們記\(2\cdot a_i-b_i\)為\(d_i\)，然后把\(d_i\)排序后two points掃一下用前（后）綴和算答案即可
若\(b_i+b_j\)是\(\min\)的話就交換所有\(a_i,b_i\)再做一次即可
#include<cstdio> #include<algorithm> #include<iostream> #define RI register int #define CI const int& using namespace std; const int N=100005,mod=1e9+7; struct data {int a,b,c,v;friend inline bool operator < (const data& A,const data& B){return A.v<B.v;} }p[N]; int n,suf[N],ans; inline void inc(int& x,CI y) {if ((x+=y)>=mod) x-=mod; } inline int calc(int ret=0) {RI i,j; for (i=1;i<=n;++i) p[i].v=p[i].b-2*p[i].a;for (sort(p+1,p+n+1),i=n;i;--i) suf[i]=suf[i+1],inc(suf[i],p[i].c);for (i=n,j=1;i;--i){while (j<=n&&p[i].v+p[j].v<0) ++j;if (j<=n) inc(ret,1LL*p[i].c*suf[max(i,j)]%mod);}return ret; } int main() {RI i; for (scanf("%d",&n),i=1;i<=n;++i)scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);for (ans=calc(),i=1;i<=n;++i) swap(p[i].a,p[i].b);return inc(ans,calc()),printf("%d",ans),0; }G 籃球校賽
律師函警告（不是）
首先我們很容易發現我們對于\(5\)個位置每個位置挑出前\(5\)的隊員然后最優解一定在它們之中（否則要它有什么用？）
然后還愣著干什么，直接\(O(5^5)\)甚至\(O(2^{25})\)大暴力就過了啊
#include<cstdio> #include<iostream> #include<algorithm> #define RI register int #define CI const int& using namespace std; const int N=100005; struct data {int val,id,tp;friend inline bool operator < (const data& A,const data& B){return A.val>B.val;} }a[5][N],t[30]; int n,cnt; long long ans; bool cs[N]; inline void DFS(CI nw=1,CI ct=0,CI st=0,const long long& sum=0) {if (nw>cnt) { if (ct==5) ans=max(ans,sum); return; }if (!cs[t[nw].id]&&!((st>>t[nw].tp)&1))cs[t[nw].id]=1,DFS(nw+1,ct+1,st|(1<<t[nw].tp),sum+t[nw].val),cs[t[nw].id]=0; DFS(nw+1,ct,st,sum); } int main() {RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)for (j=0;j<5;++j) scanf("%d",&a[j][i].val),a[j][i].id=i,a[j][i].tp=j;for (i=0;i<5;++i) for (sort(a[i]+1,a[i]+n+1),j=1;j<=5;++j) t[++cnt]=a[i][j];return DFS(),printf("%lld",ans),0; }H 分配學號
首先容易發現最后修改的學號序列在排序后是唯一的，只不過有些人可以被改動到的數字不一樣
我們考慮先掃一遍求出目標序列，然后將原序列和目標序列都排序，然后two points維護下每個數能從多少個數變過來，然后乘起來就好了
#include<cstdio> #include<algorithm> #define RI register int using namespace std; const int N=100005,mod=1e9+7; int n,ans=1; long long a[N],tar[N]; int main() {RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);for (sort(a+1,a+n+1),i=1;i<=n;++i)if (a[i]<=tar[i-1]) tar[i]=tar[i-1]+1; else tar[i]=a[i];for (sort(tar+1,tar+n+1),i=j=1;i<=n;++i){while (j<=n&&a[j]<=tar[i]) ++j;ans=1LL*ans*(j-i)%mod;}return printf("%d",ans),0; }I Gree的心房
整場比賽最水的題，容易發現最少步數一定是\(n+m-2\)，所以判斷\(k\)和它的關系即可
注意起點和終點不能被占用了以及計算剩下多少個無用位置時要開long long
#include<cstdio> using namespace std; int n,m,k; int main() {scanf("%d%d%d",&n,&m,&k); long long left=1LL*n*m-(n+m-1);if (k>left) puts("-1"); else printf("%d",n+m-2); return 0; }Postscript
當我做完這場比賽，看著自己每道題都WA上三四遍的提交，再看著現場AK并拿兩題一血的bzt，我流下了蒟蒻的淚水
轉載于:https://www.cnblogs.com/cjjsb/p/11379643.html
總結
以上是生活随笔為你收集整理的Comet OJ CCPC－Wannafly Comet OJ 夏季欢乐赛（2019）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 增加FiroFox3对迅雷的支持
- 下一篇： python人脸识别代码实现