「小组联考」第二周三次考试

T1 「JOISC 2016 Day 3」电报题目考场思考正解 T2 「CQOI2016」路由表题目考场思考正解 T3 「NOIP2014」飞扬的小鸟题目考场思考正解

---

这次考试感觉迷迷糊糊的。 刚开始睡完午觉还没有清醒，然后就晕了大概半个小时。 然后就开始看题…结果这几个题又是大文章… 以为可以 $A$ 掉 $T3$ ，结果因为题目原因被坑掉 $70pts$ … 看来这个考试可以不用考了…

T1 「JOISC 2016 Day 3」电报

题目

点这里

考场思考

迷迷糊糊，没思考，代码都没交过…

正解

首先，这个题的时间复杂度非常友好… 看看这个图的特性，发现它是基环树。 所谓基环树，就是有 $N$ 个点，$N$ 条边 （部分特性）。 那么，如果我们要将这样一个图变成一个强连通图，说明这样一个图一定是一个大环。 但是知道这些，似乎也不知道怎么做题… 这个题目，似乎没有说这些边拆掉之后怎么接，那么我们就不需要考虑怎么再把边接上去。 所以…嘿嘿嘿管那么多干嘛。 为了将这个图变成一个大环，我们先找出环，将不在环上的点拼成一条单链。 怎么做呢？ 考虑一个不在环上的节点 $u$ ，它的入度 $in[u]$。 如果 $in[u]>1$，那么在连向 $u$ 的边中，留下花费最大的，将其余的都切掉，至于怎么接，这不是我们考虑的范围… 但是如果 $u$ 在环上，同理，留下花费最大的，将其余的都切掉。 但是有一个特殊的地方，每个环必须切掉一条边，不然它们就没有办法和其他的环或者单链练成一个大环。 具体实现

#include<cstdio> #include<cstdlib> #include<vector> #include<queue> #include<algorithm> using namespace std; #define int long long #define rep(q,__a,__b) for(int q=__a,q##_end_=__b;q<=q##_end_;++q) #define dep(q,__a,__b) for(int q=__a,q##_end_=__b;q>=q##_end_;--q) template<class T>inline void qread(T& x){ char c;bool f=false;x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); if(f)x=-x; } template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);} inline int rqread(){ char c;bool f=false;int x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); return f?-x:x; } template<class T>inline T Max(const T x,const T y){return x>y?x:y;} template<class T>inline T Min(const T x,const T y){return x<y?x:y;} template<class T>inline T fab(const T x){return x>0?x:-x;} inline void getInv(int inv[],const int r,const int MOD) {inv[0]=inv[1]=1;for(int i=2;i<=r;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;} const int MAXN=1e5; const int INF=0x3f3f3f3f; struct edge{ int u,w; edge(){} edge(const int U,const int W):u(U),w(W){} }; vector<edge>rG[MAXN+5]; int N,in[MAXN+5],fa[MAXN+5],ans,bel[MAXN+5],Ccnt,faw[MAXN+5],cirNode[MAXN+5]; bool vis[MAXN+5],broken[MAXN+5],flg; inline void topo(){ queue<int>Q; for(int i=1;i<=N;++i)if(in[i]==0) Q.push(i); if(Q.empty())flg=true; while(!Q.empty()){ int now=Q.front();Q.pop(); vis[now]=true,--in[fa[now]]; if(in[fa[now]]==0)Q.push(fa[now]); } //处理属于哪个环 for(int i=1,u;i<=N;++i)if(!vis[i]&&!bel[i]){//是环上点 u=i,++Ccnt; cirNode[Ccnt]=i; while(bel[u]==0){ bel[u]=Ccnt; u=fa[u]; } } if(flg&&Ccnt==1)exit(0&puts("0")); } inline void init(){ qread(N); for(int i=1;i<=N;++i){ qread(fa[i],faw[i]); ++in[fa[i]]; rG[fa[i]].push_back(edge(i,faw[i])); } } inline bool cmp(const edge a,const edge b){return a.w>b.w;} inline void solvenode(){//处理入度多于 1 的点 for(int i=1;i<=N;++i)if(rG[i].size()>1){ sort(rG[i].begin(),rG[i].end(),cmp); for(int j=rG[i].size()-1;j>=1;--j){ ans+=rG[i][j].w; if(bel[i]==bel[rG[i][j].u])broken[bel[i]]=true; } } } inline void breakcircle(){ for(int i=1,j,k,mine;i<=Ccnt;++i)if(!broken[i]){//如果有环还没有被破开 j=k=cirNode[i],mine=faw[j]; do{ // printf("Now k==%lld\n",k); if(rG[k].size()>1)mine=Min(mine,rG[k][0].w-rG[k][1].w);//可以保证，没有被删掉的边一定是环上边 mine=Min(mine,faw[k]); k=fa[k]; }while(k!=j); // printf("circle %lld:mine==%lld\n",i,mine); ans+=mine,broken[i]=true; } } signed main(){ // freopen("04-20.in","r",stdin); init(); topo(); solvenode(); // printf("After node:ans==%lld\n",ans); breakcircle(); printf("%lld\n",ans); return 0; }

---

T2 「CQOI2016」路由表

题目

点这里

考场思考

题目过长直接跳过系列 这道题…它的上辈子是论文吧…看到这长度直接跳过

正解

考完之后，耐下心读了遍题，发现这道题其实是可做的。 首先搞懂题意，掩码就是它会用到的长度，而其他没有用到的地方，直接扔掉就可以了… 操作 $A$： 输入一个网址，加入进网址序列 操作 $Q$： 询问一个网址 $web$，在 $a$ 到 $b$ 的网址加入网址序列时，$web$ 的发送对象会变更多少次。 发送对象是什么呢？ 就是能与其匹配，且最长最精准的网址 再仔细想想，这不就是 $trie$ 树吗？ 加入网址，就是在 $trie$ 树上加入一个长度为 网址掩码 的二进制字符串。 但是因为询问是在不同的时间点，所以我们要建的是持久化 $trie$ 树。 但是操作 $Q$ 呢？ 我们先来想想，发生发送对象变更现象（并不是专业名称，只是作者自己取名下文简称发变现象）时，到底发生了什么。 从定义看，发变就是与询问网址 $web$ 匹配，且最长精确的网址在添加 $a$ 到 $b$ 网址时，发生了变化。 为什么会发生变化？ 假设我们在 $i$ 时刻，添加了网址 $x$ ，在 $j$ 时刻，添加了网址 $y$，令 $y$ 对于询问 $web$ 是优于 $x$ 的。 那么，讨论 $i$ 与 $j$ 的关系

当 $i<j$ 时，我们在时刻 $i$ 到 $j-1$，一定是用网址 $x$ 的，而当到时刻 $j$到的时候，就会发生发变现象，发送对象 $x$ 变成了 $y$。当 $i>j$ 时，说明在 $i$ 之前就有比 $x$ 更优的网址了，那么是不会发生发变现象的

所以，只需要求出 $i<j$ 且 $y$ 优于 $x$ 的情况就行了。 那么怎么处理呢？ 一个好问题，但是我们看看这样的形式： $i<j$ 且 $y$ 优于 $x$ 自然而然想到单调栈虽然我是在老师提醒下发现的 该怎么个单调法呢？ 假若我们以时间顺序，放入网址，以网址的优劣为单调对象，那么时间复杂度是 $O(b-a)$ 级别 呵呵，$1e6$ 玩个锤子 😃。 假若我们以网址优劣为顺序，放入时间。 那么复杂度最多也就 $O(32)$（链的长度） 再说说细节。 依次遍历这条链的节点 （从根到叶，即默认网址由劣到优），遇到一个结尾就考虑怎么放入其时间 $t$。 假设栈顶 $top<t$ ，很和谐，都是自己人。 但是如果 $top>t$ ，和谐个屁，全都滚出去，然后…$pop$ 到 $top$ 再一次小于 $t$才发现，哦，这是自己人，不要开枪… 然后…就是代码

#include<cstdio> #include<stack> using namespace std; #define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q) #define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q) template<class T>inline void qread(T& x){ char c;bool f=false;x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); if(f)x=-x; } template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);} inline int rqread(){ char c;bool f=false;int x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); return f?-x:x; } template<class T>inline T Max(const T x,const T y){return x>y?x:y;} template<class T>inline T Min(const T x,const T y){return x<y?x:y;} template<class T>inline T fab(const T x){return x>0?x:-x;} inline void getInv(int inv[],const int r,const int MOD) {inv[0]=inv[1]=1;for(int i=2;i<=r;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;} const int MAXM=1e6; struct node{ int son[2],siz,ed; }tre[MAXM*32+5]; int rt[MAXM+5],Ncnt,cnt; inline void add(const unsigned int v,const int len,const int t){ rt[++cnt]=++Ncnt; int newnode=rt[cnt],pre=rt[cnt-1]; tre[newnode]=tre[pre]; for(int i=31,now;i>=31-len+1;--i){ now=(v>>i)&1;//取出从高到低第 i 位 pre=tre[pre].son[now]; tre[newnode].son[now]=++Ncnt; newnode=tre[newnode].son[now];//同步向下 tre[newnode]=tre[pre];//继承上一个点信息 ++tre[newnode].siz; } if(!tre[newnode].ed)tre[newnode].ed=t; } inline int getMaxl(int p,const unsigned int v){ p=rt[p]; int ret=0; for(int i=31,now;i>=0;--i){ //这句话不能放到这里 // if(tre[p].ed)ret=Max(ret,31-i+1); now=(v>>i)&1; if(tre[p].son[now])p=tre[p].son[now]; else break; if(tre[p].ed)ret=Max(ret,31-i+1); //放到开头不行 } return ret; } inline int query(int l,int r,const unsigned int v,const int len){ l=rt[l],r=rt[r]; stack<int>sta; for(int i=31,now;i>=0;--i){ now=(v>>i)&1; if(tre[tre[r].son[now]].siz-tre[tre[l].son[now]].siz)//有地方可走 r=tre[r].son[now],l=tre[l].son[now]; else break; if(tre[r].ed&&31-i+1>len){//第二个条件的意思:这个点是否是掩码之内 while(!sta.empty()&&tre[r].ed<sta.top())sta.pop(); sta.push(tre[r].ed); } } return (int)sta.size(); } char ord; int M,len,l,r; unsigned int a[4]; signed main(){ qread(M); for(int t=1;t<=M;++t){ scanf("%s",&ord); if(ord=='A'){ scanf("%d.%d.%d.%d/%d",&a[0],&a[1],&a[2],&a[3],&len); for(int i=1;i<=3;++i)a[0]=a[0]<<8|a[i]; add(a[0],len,t); } else{ scanf("%d.%d.%d.%d %d %d",&a[0],&a[1],&a[2],&a[3],&l,&r); for(int i=1;i<=3;++i)a[0]=a[0]<<8|a[i]; len=getMaxl(l-1,a[0]); printf("%d\n",query(l-1,r,a[0],len)); } } return 0; }

思路来源大佬的博客

---

T3 「NOIP2014」飞扬的小鸟

题目

点这里

考场思考

考试的时候，发现这道题其实很水，然后就开始骗分… 定义 $dp[i][j]$：走到点 $(i,j)$ 时的最小花费。 先初始化 memset(dp,127,sizeof dp) 特殊处理 $dp[i][j]=-1$ 是柱子，不能走。 然后将第 $0$ 排初始附 $0$ 。 最后判最后一排是不是全为 2139062143 即可。 预估分数 $100pts$，实际分数 $40pts$ 。 不要问我为什么，题意理解错了…

#include<cstdio> #include<cstring> #define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q) #define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q) template<class T>inline void qread(T& x){ char c;bool f=false;x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); if(f)x=-x; } template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);} inline int rqread(){ char c;bool f=false;int x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); return f?-x:x; } template<class T>inline T Max(const T x,const T y){return x>y?x:y;} template<class T>inline T Min(const T x,const T y){return x<y?x:y;} template<class T>inline T fab(const T x){return x>0?x:-x;} inline void getInv(int inv[],const int r,const int MOD) {inv[0]=inv[1]=1;for(int i=2;i<=r;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;} const int MAXN=1e4; const int MAXM=1e3; int N,M,K,x[MAXN+5],y[MAXN+5]; int dp[MAXN+5][MAXM+5]; bool flg[MAXN+5]; int pre[MAXN+5],lst; inline void special(){ puts("0"); for(int i=1;i<=N;++i){ pre[i]=pre[i-1]+flg[i-1]; } printf("%d\n",pre[lst]); } signed main(){ qread(N,M,K); for(int i=0;i<N;++i)qread(x[i],y[i]); memset(dp,127,sizeof dp); for(int i=1,p,l,h;i<=K;++i){qread(p,l,h); flg[p]=true; for(int j=0;j<l;++j)dp[p][j]=-1;//理解错误部分 for(int j=h+1;j<=M;++j)dp[p][j]=-1;//理解错误部分 } for(int j=0;j<=M;++j)if(dp[0][j]!=-1)dp[0][j]=0; for(int i=0;i<N;++i)for(int j=0;j<=M;++j)if(dp[i][j]!=-1){ if(i!=1&&j==0)continue; if(j-y[i]>=1){ if(dp[i+1][j-y[i]]!=-1)dp[i+1][j-y[i]]=Min(dp[i+1][j-y[i]],dp[i][j]); } if(j+x[i]>M){ if(dp[i+1][M]!=-1)dp[i+1][M]=Min(dp[i+1][M],dp[i][j]+1); if(dp[i][M]!=-1)dp[i][M]=Min(dp[i][M],dp[i][j]+1);//理解错误部分 } else{ if(dp[i+1][j+x[i]]!=-1)dp[i+1][j+x[i]]=Min(dp[i+1][j+x[i]],dp[i][j]+1); if(dp[i][j+x[i]]!=-1)dp[i][j+x[i]]=Min(dp[i][j+x[i]],dp[i][j]+1);//理解错误部分 } if(dp[i][j]!=2139062143)lst=i; } int ans=2139062143; for(int i=1;i<=M;++i)ans=Min(ans,dp[N][i]); if(ans==2139062143)special(); else printf("1\n%d\n",ans); return 0; }

正解

其实，题目所说的可以通过的管道漏洞是 $(l,h)$ 而不是 $[l,h]$ 然后我就几乎翻车了 但是改了之后也是 $75pts$ ，后来发现题目还有一个点读错了… 这就是语文弱科的不好之处 后来发现，小鸟连续跳时，所跳高度是前一个的 $x$。 我去这道题真是用心出样例，用脚造数据… 具体思路很好想，上升时完全背包，下落时 $01$ 背包，再处理一些细节即可。 部分代码： 上升时考虑完全背包的做法 这里我太懒了，懒得特判，多打了一个循环来处理

for(int j=x[i-1]+1;j<=x[i-1]+M;++j) dp[i][j]=Min(dp[i][j-x[i-1]]+1/*上一列连续按*/,dp[i-1][j-x[i-1]]+1/*只按了一下*/); for(int j=M+1;j<=M+x[i-1];++j) dp[i][M]=Min(dp[i][M],dp[i][j]);//最后把跳出去的部分全部归到 dp[i][M] 中

下降的时候，直接从上一列转移过来即可

for(int j=1;j<=M-y[i-1];++j) dp[i][j]=Min(dp[i][j],dp[i-1][j+y[i-1]]);//注意此处没有 +1

最后把柱子部分特殊处理一下

for(int j=1;j<l[i];++j)dp[i][j]=INF; for(int j=h[i]+1;j<=M;++j)dp[i][j]=INF;

下面是完全代码，时间复杂度 $O(NM)$，空间复杂度 $N(N+M)$，但是其实可以优化到 $M$。

#include<cstdio> #include<cstring> #define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q) #define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q) template<class T>inline void qread(T& x){ char c;bool f=false;x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); if(f)x=-x; } template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);} inline int rqread(){ char c;bool f=false;int x=0; while((c=getchar())<'0'||'9'<c)if(c=='-')f=true; for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48)); return f?-x:x; } template<class T>inline T Max(const T x,const T y){return x>y?x:y;} template<class T>inline T Min(const T x,const T y){return x<y?x:y;} template<class T>inline T fab(const T x){return x>0?x:-x;} inline void getInv(int inv[],const int r,const int MOD) {inv[0]=inv[1]=1;for(int i=2;i<=r;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;} const int MAXN=1e4; const int MAXM=1e3; const int INF=66666666;//十分吉祥 int dp[MAXN+5][(MAXM<<1)+5]; int l[MAXN+5],h[MAXN+5]; int x[MAXN+5],y[MAXN+5]; int N,M,K,ans2;bool flg[MAXN+5],lst; signed main(){ qread(N,M,K); for(int i=0;i<N;++i)qread(x[i],y[i]),l[i]=1,h[i]=M; l[N]=1,h[N]=M; for(int i=1,p,a,b;i<=K;++i){qread(p,a,b); flg[p]=true; l[p]=a+1; h[p]=b-1; } memset(dp,0x3f,sizeof dp); for(int j=0;j<=M;++j)dp[0][j]=0; for(int i=1;i<=N;++i){ lst=false; for(int j=x[i-1]+1;j<=x[i-1]+M;++j) dp[i][j]=Min(dp[i][j-x[i-1]]+1,dp[i-1][j-x[i-1]]+1); for(int j=M+1;j<=M+x[i-1];++j) dp[i][M]=Min(dp[i][M],dp[i][j]); for(int j=1;j<=M-y[i-1];++j) dp[i][j]=Min(dp[i][j],dp[i-1][j+y[i-1]]); for(int j=1;j<l[i];++j)dp[i][j]=INF; for(int j=l[i];j<=h[i];++j)if(dp[i][j]<INF){lst=true;break;}//计算这一列可不可以到 for(int j=h[i]+1;j<=M;++j)dp[i][j]=INF; if(lst&&flg[i])++ans2;//处理一下第二个答案 } int ans=INF; for(int j=1;j<=M;++j)ans=Min(ans,dp[N][j]); if(ans<INF)return 0&printf("1\n%d\n",ans); else printf("0\n%d\n",ans2); return 0; }

又是翻车的一天