A. 辣雞(ljh)

打暴搜，然后$TLE75$，

丑陋的考試$75$分代碼：

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<map> #define int long long #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) #define abs(x) ((x)<0?(-1*(x)):(x)) #define Maxn 100050 #define Reg register using namespace std; bool vis[Maxn]; int totx1,totx2,toty1,toty2; int n,sum=0,X1[Maxn],X2[Maxn],Y1[Maxn],Y2[Maxn]; map<int,int> XX1,XX2,YY1,YY2; vector<vector<int> >Xs1(Maxn),Xs2(Maxn),Ys1(Maxn),Ys2(Maxn); signed main() { // freopen("text.in","r",stdin); // freopen("text2.out","w",stdout);scanf("%lld",&n);for(Reg int i=1;i<=n;++i){scanf("%lld%lld%lld%lld",&X1[i],&Y1[i],&X2[i],&Y2[i]);if(!XX1[X1[i]]) XX1[X1[i]]=++totx1;if(!XX2[X2[i]]) XX2[X2[i]]=++totx2;if(!YY1[Y1[i]]) YY1[Y1[i]]=++toty1;if(!YY2[Y2[i]]) YY2[Y2[i]]=++toty2;Xs1[XX1[X1[i]]].push_back(i);Xs2[XX2[X2[i]]].push_back(i);Ys1[YY1[Y1[i]]].push_back(i);Ys2[YY2[Y2[i]]].push_back(i);}sum=0;for(Reg int i=1,x;i<=n;++i){x=2*((X2[i]-X1[i]+1)*(Y2[i]-Y1[i]+1)-(X2[i]-X1[i]+1)-(Y2[i]-Y1[i]+1)+1);if(XX2[X1[i]-1]){int p=XX2[X1[i]-1];for(Reg int k=0;k<Xs2[p].size();++k){int j=Xs2[p][k]; if(j>=i||vis[j]) continue;if(Y2[i]==Y1[j]-1) ++x;else if(Y1[i]==Y2[j]+1) ++x;vis[j]=1;if(Y1[i]>Y2[j]||Y1[j]>Y2[i]) continue;if(Y1[i]==Y1[j]) --x;if(Y2[i]==Y2[j]) --x;x+=2*(min(Y2[i],Y2[j])-max(Y1[i],Y1[j])+1);}}if(XX1[X2[i]+1]){int p=XX1[X2[i]+1];for(Reg int k=0;k<Xs1[p].size();++k){int j=Xs1[p][k]; if(j>=i||vis[j]) continue;if(Y2[i]==Y1[j]-1) ++x;else if(Y1[i]==Y2[j]+1) ++x;vis[j]=1;if(Y1[i]>Y2[j]||Y1[j]>Y2[i]) continue;if(Y1[i]==Y1[j]) --x;if(Y2[i]==Y2[j]) --x;x+=2*(min(Y2[i],Y2[j])-max(Y1[i],Y1[j])+1);}}if(YY2[Y1[i]-1]){int p=YY2[Y1[i]-1];for(Reg int k=0;k<Ys2[p].size();++k){int j=Ys2[p][k]; if(j>=i||vis[j]) continue;if(X2[i]==X1[j]-1) ++x;else if(X1[i]==X2[j]+1) ++x;vis[j]=1;if(X1[i]>X2[j]||X1[j]>X2[i]) continue;if(X1[i]==X1[j]) --x;if(X2[i]==X2[j]) --x;x+=2*(min(X2[i],X2[j])-max(X1[i],X1[j])+1);}}if(YY1[Y2[i]+1]){int p=YY1[Y2[i]+1];for(Reg int k=0;k<Ys1[p].size();++k){int j=Ys1[p][k]; if(j>=i||vis[j]) continue;if(X2[i]==X1[j]-1) ++x;else if(X1[i]==X2[j]+1) ++x;vis[j]=1;if(X1[i]>X2[j]||X1[j]>X2[i]) continue;if(X1[i]==X1[j]) --x;if(X2[i]==X2[j]) --x;x+=2*(min(X2[i],X2[j])-max(X1[i],X1[j])+1);}}if(XX2[X1[i]-1]){int p=XX2[X1[i]-1];for(Reg int k=0;k<Xs2[p].size();++k)vis[Xs2[p][k]]=0;}if(XX1[X2[i]+1]){int p=XX1[X2[i]+1];for(Reg int k=0;k<Xs1[p].size();++k)vis[Xs1[p][k]]=0;}if(YY2[Y1[i]-1]){int p=YY2[Y1[i]-1];for(Reg int k=0;k<Ys2[p].size();++k)vis[Ys2[p][k]]=0;}if(YY1[Y2[i]+1]){int p=YY1[Y2[i]+1];for(Reg int k=0;k<Ys1[p].size();++k)vis[Ys1[p][k]]=0;}sum+=x;}printf("%lld",sum);return 0; } View Code

?

?

B. 模板(ac)

$70$分算法：

測試點分治，前$30$分暴力，后$40$分簡單的線段樹合并。

錯誤總結：

1、沒有正確推測測試點，

考試時看到前邊的測試點一個$m<=10$一個$m<=1000$，

然后我ZZ地認為暴力不能跑過$1000$，于是：

if(m<=10){} else{}

結果連暴力的$30$分都沒拿到。

2、題目中顯然沒有給顏色的范圍，于是我把$m>1000$的測試點離散化，然而：

if(m<=10) {dfs(1);for(Reg int i=1,x,c;i<=m;++i){scanf("%lld%lld",&x,&c);change(x,c);}scanf("%lld",&q);for(Reg int i=1,x;i<=q;++i){scanf("%lld",&x);printf("%lld\n",an[x]);} } else {for(Reg int i=1,x,c;i<=m;++i){scanf("%lld%lld",&x,&c);if(!p[c]) p[c]=++top;if(!pos[x]) pos[x]=New();work(pos[x],1,m,c);}memset(vis,0,sizeof(vis));dfs_re(1);scanf("%lld",&q);for(Reg int i=1,x;i<=q;++i){scanf("%lld",&x);printf("%lld\n",ans[x]);} }

上邊沒有離散化。

3、數組我顯然沒開夠(因為我認為$m<=1000$的點不能跑)。

丑陋的考試$20$分代碼：

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<map> #define int long long #define New() new Tree #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) #define abs(x) ((x)<0?(-1*(x)):(x)) #define Maxn 100050 #define Reg register using namespace std; bool vis[Maxn]; int n,m,q,tot,fir[Maxn],fat[Maxn],K[Maxn],lss[25][Maxn],an[25]; int top,lsh[Maxn],ans[Maxn]; map<int,int> p; struct Tu {int st,ed,next;} lian[Maxn*2]; struct Tree {Tree *lch,*rch; int val;}; Tree *pos[Maxn]; void add(int x,int y) {lian[++tot].st=x;lian[tot].ed=y;lian[tot].next=fir[x];fir[x]=tot;return; } void dfs(int x) {vis[x]=1;for(Reg int i=fir[x];i;i=lian[i].next){if(!vis[lian[i].ed]){dfs(lian[i].ed);fat[lian[i].ed]=x;}}return; } void change(int x,int num) {if(lss[x][0]<K[x]){if(!lss[x][num]) ++an[x];++lss[x][0];++lss[x][num];}if(fat[x]) change(fat[x],num);return; } void work(Tree *root,int l,int r,int pos) {if(l==r){root->val=1;return;}int mid=(l+r)/2;if(pos<=mid){if(root->lch==NULL) root->lch=New();work(root->lch,l,mid,pos);}else{if(root->rch==NULL) root->rch=New();work(root->rch,mid+1,r,pos);}root->val=0;if(root->lch!=NULL) root->val+=root->lch->val;if(root->rch!=NULL) root->val+=root->rch->val;return; } Tree* merge(Tree *rot1,Tree *rot2,int l,int r) {if(rot1==NULL) return rot2;else if(rot2==NULL) return rot1;else{if(l==r){rot1->val|=rot2->val;return rot1;}int mid=(l+r)/2;rot1->lch=merge(rot1->lch,rot2->lch,l,mid);rot1->rch=merge(rot1->rch,rot2->rch,mid+1,r);rot1->val=0;if(rot1->lch!=NULL) rot1->val+=rot1->lch->val;if(rot1->rch!=NULL) rot1->val+=rot1->rch->val;return rot1;} } void dfs_re(int x) {vis[x]=1;for(Reg int i=fir[x];i;i=lian[i].next){if(!vis[lian[i].ed]){dfs_re(lian[i].ed);pos[x]=merge(pos[x],pos[lian[i].ed],1,m);}}if(pos[x]!=NULL) ans[x]+=pos[x]->val;return; } signed main() {scanf("%lld",&n);for(Reg int i=1,x,y;i<=n-1;++i){scanf("%lld%lld",&x,&y);add(x,y); add(y,x);}for(Reg int i=1;i<=n;++i) scanf("%lld",&K[i]);scanf("%lld",&m);if(m<=10){dfs(1);for(Reg int i=1,x,c;i<=m;++i){scanf("%lld%lld",&x,&c);change(x,c);}scanf("%lld",&q);for(Reg int i=1,x;i<=q;++i){scanf("%lld",&x);printf("%lld\n",an[x]);}}else{for(Reg int i=1,x,c;i<=m;++i){scanf("%lld%lld",&x,&c);if(!p[c]) p[c]=++top;if(!pos[x]) pos[x]=New();work(pos[x],1,m,c);}memset(vis,0,sizeof(vis));dfs_re(1);scanf("%lld",&q);for(Reg int i=1,x;i<=q;++i){scanf("%lld",&x);printf("%lld\n",ans[x]);}}return 0; } View Code

丑陋的$70$分代碼：

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<map> #define int long long #define New() new Tree #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) #define abs(x) ((x)<0?(-1*(x)):(x)) #define Maxn 100050 #define Reg register using namespace std; bool vis[Maxn]; int n,m,q,tot,fir[Maxn],fat[Maxn],K[Maxn],lss[1050][1050],an[1050]; int top,lsh[Maxn],ans[Maxn]; map<int,int> p; struct Tu {int st,ed,next;} lian[Maxn*2]; struct Tree {Tree *lch,*rch; int val;}; Tree *pos[Maxn]; void add(int x,int y) {lian[++tot].st=x;lian[tot].ed=y;lian[tot].next=fir[x];fir[x]=tot;return; } void dfs(int x) {vis[x]=1;for(Reg int i=fir[x];i;i=lian[i].next){if(!vis[lian[i].ed]){dfs(lian[i].ed);fat[lian[i].ed]=x;}}return; } void change(int x,int num) {if(lss[x][0]<K[x]){if(!lss[x][num]) ++an[x];++lss[x][0];++lss[x][num];}if(fat[x]) change(fat[x],num);return; } void work(Tree *root,int l,int r,int pos) {if(l==r){root->val=1;return;}int mid=(l+r)/2;if(pos<=mid){if(root->lch==NULL) root->lch=New();work(root->lch,l,mid,pos);}else{if(root->rch==NULL) root->rch=New();work(root->rch,mid+1,r,pos);}root->val=0;if(root->lch!=NULL) root->val+=root->lch->val;if(root->rch!=NULL) root->val+=root->rch->val;return; } Tree* merge(Tree *rot1,Tree *rot2,int l,int r) {if(rot1==NULL) return rot2;else if(rot2==NULL) return rot1;else{if(l==r){rot1->val|=rot2->val;return rot1;}int mid=(l+r)/2;rot1->lch=merge(rot1->lch,rot2->lch,l,mid);rot1->rch=merge(rot1->rch,rot2->rch,mid+1,r);rot1->val=0;if(rot1->lch!=NULL) rot1->val+=rot1->lch->val;if(rot1->rch!=NULL) rot1->val+=rot1->rch->val;return rot1;} } void dfs_re(int x) {vis[x]=1;for(Reg int i=fir[x];i;i=lian[i].next){if(!vis[lian[i].ed]){dfs_re(lian[i].ed);pos[x]=merge(pos[x],pos[lian[i].ed],1,m);}}if(pos[x]!=NULL) ans[x]+=pos[x]->val;return; } signed main() {scanf("%lld",&n);for(Reg int i=1,x,y;i<=n-1;++i){scanf("%lld%lld",&x,&y);add(x,y); add(y,x);}for(Reg int i=1;i<=n;++i) scanf("%lld",&K[i]);scanf("%lld",&m);if(m<=1000){dfs(1);for(Reg int i=1,x,c;i<=m;++i){scanf("%lld%lld",&x,&c);if(!p[c]) p[c]=++top;if(!pos[x]) pos[x]=New();change(x,p[c]);}scanf("%lld",&q);for(Reg int i=1,x;i<=q;++i){scanf("%lld",&x);printf("%lld\n",an[x]);}}else{for(Reg int i=1,x,c;i<=m;++i){scanf("%lld%lld",&x,&c);if(!p[c]) p[c]=++top;if(!pos[x]) pos[x]=New();work(pos[x],1,m,p[c]);}memset(vis,0,sizeof(vis));dfs_re(1);scanf("%lld",&q);for(Reg int i=1,x;i<=q;++i){scanf("%lld",&x);printf("%lld\n",ans[x]);}}return 0; } View Code

?

?

總結：

上來先看的$T1$，題意很好理解，可以暴搜。。

然后$10$分鐘碼了一個$n^2$的代碼，樣例過了。

然后想了想，用了個$vector$存邊界，然后就$75$分超時，好像是這個常數有點大。

碼完$T1$之后考試將近一半，

馬上看$T2$，一看$T2$，線段樹合并，然后看到測試點，仿佛可以過掉$10$個點左右。

然后就碼了一顆線段樹合并和一個暴力，測試點分治嘛。

然后兩個樣例直接過。。我以為可以拿到$50$到$60$分，然后就跳到$T3$，

其實這個第二個樣例跟我打的線段樹合并沒什么關系，我第一個暴力的范圍是$m<=10$。。

然后考試最后20分鐘發現。。

我打的線段樹合并，它$RE$，然后非常緊張，調了半天，然后過樣例了。

最后$20$分。。有點可惜。

$T3$他們都說很水，然而，我并沒有剩很長時間，然后碼了$dfs$，還死活調不對，

最后憑借我的"騙分"技巧，輸出樣例$+$錯誤的$dfs$得了$5$分。

最后$75+20+5=100$，第二題有點可惜。

沒什么水平。。。

轉載于:https://www.cnblogs.com/Milk-Feng/p/11263560.html

總結

以上是生活随笔為你收集整理的2019-7-29 考试总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。