[39] (多校联训) A层冲刺NOIP2024模拟赛01

你们不感觉最近机房网越来越慢了吗，现在下个 10M 的东西要用三分钟，而且期间访问不了网站

整个机房分 1000Mbps 的带宽为啥只能分这么一点, huge 拿我电脑挖矿了？

本来以为多校就是多校的，结果是真的多校，一百一十多个人在一块考

huge: 参加的都是咱们北方这几个强校

你说得对，但是广东为啥是北方

A.构造字符串

维护并查集，同一个连通块内的数字应该相同

对于一个要求 \((x_i,y_i,z_i)\)，应该让 \(\forall j\in[0,z_i-1]\)，连接 \(x_i+j,y_i+j\)，这样才能保证在规定范围内的数字都相等

其次来看不合法的，不合法的就是一定不能相等的，显然应该是每组询问中的 \(x_i+z_i\) 与 \(y_i+z_i\)，因为如果他俩相等的话，答案就不是 \(z_i\) 了，而是 \(z_i+1\)

那么我们可以贪心地做这道题，每次遇到没填的数就考虑填入最小的数，然后把相同连通块内的数都填成一样的数

需要注意你填的时候需要保证能够满足所有的限制条件，比如现在有三个数，\(1\) 与 \(3\) 相同，\(2\) 与 \(3\) 不同，那么你给 \(1,3\) 填了 \(0\)，给 \(2\) 填的时候需要注意一下满足所有的限制条件，赛时没判断后方的限制条件，所以这里填的是 \(0\)，再往后挪一位就错了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+5;
int n,m,a[N];
int x,y,z,k,t,q;
int tot,fa[N];
struct sb{int x,y,z;
}e[N];
bool cmp(sb a,sb b){if(a.x!=b.x)return a.x<b.x;if(a.y!=b.y)return a.y<b.y;return a.z<b.z;
}
int find(int x){return x==fa[x]?x:x=find(fa[x]);
}
bool butong[N][N],tong[N][N],vis[N],v[N];
signed main(){freopen("str.in","r",stdin);freopen("str.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y>>z;if(x>y)swap(x,y);e[i]={x,y,z};}sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++){if(e[i].y+e[i].z>1+n){cout<<-1;return 0;}if(tong[e[i].x+e[i].z][e[i].z+e[i].y]){cout<<-1;return 0;}butong[e[i].x+e[i].z][e[i].z+e[i].y]=butong[e[i].z+e[i].y][e[i].x+e[i].z]=1;for(int j=e[i].x,k=e[i].y;j<e[i].x+e[i].z;j++,k++){if(butong[j][k]){cout<<-1;return 0;}tong[j][k]=tong[k][j]=1;}}for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++){for(int j=1;j<i;j++){if(tong[i][j]){int ii=find(i),jj=find(j);if(ii<jj)fa[jj]=ii;else fa[ii]=jj;}}}for(int i=1;i<=n;i++){for(int j=1;j<i;j++){if(butong[i][j]){// cout<<find(i)<<' '<<find(j)<<endl;butong[find(i)][find(j)]=butong[find(j)][find(i)]=1;}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(butong[i][j]&&tong[i][j]){cout<<-1;return 0;}}}// for(int i=1;i<=n;i++){// 	cout<<fa[i]<<" ";// }cout<<endl;for(int i=1;i<=n;i++){int op=find(i);if(!vis[op]){memset(v,0,sizeof v);for(int j=1;j<=n;j++){int nn=find(j);if(nn<op){if(butong[op][nn]){// if(i==2)cout<<i<<' '<<op<<' '<<j<<' '<<nn<<endl;v[a[nn]]=1;}}}for(int j=0;j<=n;j++){if(v[j]==0){tot=max(tot,j);a[op]=j;break;}}vis[op]=1;}cout<<a[op]<<' ';}return 0;
}

B.寻宝

本场最送

连通性问题，注意到 \(k\) 很小，显然可以缩点，把所有联通的节点都连在一起（忽略传送门）

然后处理传送门，相当于在连通块之间联有向边

判断联通的时候直接跑 DFS 即可，由于边很少，单次查询最高只有 \(O(k)\)

发现只给了 \(n\times m\) 的范围，静态数组开不下，所以题解说用 bitset 存，啥年代了还在用 bitset，vector 扩容不是更好

#include<bits/stdc++.h>
using namespace std;
int n,m,k,q;
vector<vector<int>>mp;
struct door{int x1,x2,y1,y2;
}de[101];
int cnt=0;
struct node{int x,y;
};
queue<node>p;
bool vis[50001];
void bfs(int x,int y,int loc){while(!p.empty()) p.pop();p.push({x,y});while(!p.empty()){node u=p.front();p.pop();if(mp[u.x][u.y]!=0) continue;mp[u.x][u.y]=loc;if(u.x<n) p.push({u.x+1,u.y});if(u.x>1) p.push({u.x-1,u.y});if(u.y<m) p.push({u.x,u.y+1});if(u.y>1) p.push({u.x,u.y-1});}
}
vector<int>e[50001];
bool judge(int x,int tar){if(x==tar) return true;vis[x]=true;for(int i:e[x]){if(!vis[i] and judge(i,tar)) return true;}return false;
}
int main(){
//	freopen("treasure/treasure4.in","r",stdin);
//	freopen("out.out","w",stdout);freopen("treasure.in","r",stdin);freopen("treasure.out","w",stdout);scanf("%d %d %d %d",&n,&m,&k,&q);mp.resize(n+1);for(int i=1;i<=n;++i){mp[i].resize(m+1);}for(int i=1;i<=n;++i){string s;cin>>s;for(int j=0;j<=m-1;++j){mp[i][j+1]=(s[j]=='.'?0:-1);}}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(mp[i][j]==0){bfs(i,j,++cnt);}}}
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=m;++j){
//			cout<<mp[i][j]<<" ";
//		}
//		cout<<endl;
//	}for(int i=1;i<=k;++i){scanf("%d %d %d %d",&de[i].x1,&de[i].y1,&de[i].x2,&de[i].y2);if(mp[de[i].x1][de[i].y1]!=mp[de[i].x2][de[i].y2]){e[mp[de[i].x1][de[i].y1]].push_back(mp[de[i].x2][de[i].y2]);}}while(q--){int a,b,c,d;scanf("%d %d %d %d",&a,&b,&c,&d);for(int i=1;i<=cnt;++i) vis[i]&=0;putchar(judge(mp[a][b],mp[c][d])+'0');putchar('\n');}
}
/*
4 4 2 1
.#..
##..
#...
...#
1 1 1 3
4 1 4 2
4 1 3 2
*/

C.序列

\(n^2\)

设计 \(f_i\) 表示从 \(i\) 开始的子序列最大值

对每次询问转移，转移方程

\[f_i=\begin{cases}\max(a-kb,f_{i+1}+a-kb)\qquad i\ge p_i\\f_{i+1}+a-kb\qquad \text{otherwise}\end{cases} \]

从后向前转移，统计答案从 \([1,p_i]\) 取最大值

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
struct yuanshen{int a,b;
}y[1000001];
int f[1000002];
signed main(){
//	freopen("seq/seq3.in","r",stdin);
//	freopen("out.out","w",stdout);freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);scanf("%lld %lld",&n,&m);for(int i=1;i<=n;++i){scanf("%lld %lld",&y[i].a,&y[i].b);}while(m--){int p,k;scanf("%lld %lld",&p,&k);for(int i=1;i<=n;++i) f[i]&=0;for(int i=n;i>=p;--i){f[i]=max({y[i].a-k*y[i].b,f[i+1]+y[i].a-k*y[i].b});}int ans=f[p];for(int i=p-1;i>=1;--i){f[i]=f[i+1]+y[i].a-k*y[i].b;ans=max(f[i],ans);}cout<<ans<<'\n';}
}

E.我要挂一道题

挂一道题

做之前：若智，这有啥意义

做之后：若智

---

若智，谁放的

我最爱去的唱片店    //在看到这句话之前 我一直以为是 我最爱吃的炒面片
昨天是她的最后一天
曾经让我陶醉的碎片
全都散落在街边
我最爱去的书店    //我最爱吃的薯片
她也没撑过这个夏天   //码的还以为这是啥美食歌
回忆文字流淌着怀念
可是已没什么好怀念
可是你曾经的那些梦
都已变得模糊看不见
那些为了理想的战斗
也不过为了钱
可是我最恨的那个人
他始终没死在我面前   //迷惑句子
还没年轻就变得苍老
这一生无解
没有我的空间
没有我的空间
没有我的空间
没有我的空间
你曾热爱的那个人
这一生也不会再见面
你等在这文化的废墟上
已没人觉得你狂野
那些让人敬仰的神殿
只在无知的人心中灵验
我住在属于我的猪圈      //?
这一夜无眠
我不要在失败孤独中死去
我不要一直活在地下里
物质的骗局    //有这句？
匆匆的蚂蚁
没有文化的人不伤心
我不要在失败孤独中死去
我不要一直活在地下里
物质的骗局
匆匆的蚂蚁
没有文化的人不伤心
他不伤心
我最爱去的唱片店
昨天是她的最后一天
曾经让我陶醉的碎片
全都散落在街边
我最爱去的书店
她也没撑过这个夏天
回忆文字流淌着怀念
已不能怀念
我不要在失败孤独中死去
我不要一直活在地下里
物质的骗局
匆匆的蚂蚁
没有文化的人不伤心
我不要在失败孤独中死去
我不要一直活在地下里
物质的骗局
匆匆的蚂蚁
没有文化的人不伤心
他不伤心
我不要在失败孤独中死去
我不要一直活在地下里
物质的骗局
匆匆的蚂蚁
没有文化的人不伤心
我不要在失败孤独中死去
我不要一直活在地下里
物质的骗局
匆匆的蚂蚁
没有文化的人不伤心
他不会伤心
他也会伤心
伤心