20210815 图论模拟赛
2021/8/16 6:08:39
本文主要是介绍20210815 图论模拟赛,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一次运气很好的模拟赛。
赛前
是有点开心也有点紧张的,一方面因为图论专题本人比较简单,另一方面其实这方面一向debug起来很费劲……
赛时
开题便觉得自己完了。四道题都没看懂可怎么做啊?
再度遍历后,“总算”读懂了\(T2\)和\(T3\)。\(T4\)因为“题面引起歧义”(出题人亲承)一直没有搞出样例。
眼看着过了近\(1h\),想着必须要开始写题了,就开了\(T4\)。感觉像是签到题,但是自己理解的题意总是和样例相差1,于是只好输出ans-1
(ans表示经过点的数量,ans-1表示经过边的数量)。
大概20分钟敲完\(T4\)并调试完,开的\(T2\)。一眼望去是种类并查集,再次基础上思考发现种类并查集可能性很大。故写上后用着并不太正确的数学方法调出了样例和自己造的数据。
赛后:这里是数学方法确实不正确,另外此题考查也完全不是并查集……
约用了一个小时。
然后看着\(T3\),一道暴力可以稳拿\(60\)的题,还是想了近半个小时的正解,一直都是很接近,但是还差那么一点……
剩余约\(1h20\min\)放弃,开敲暴力。
剩余\(40\min\),还是没太舍得放下\(T1\)。连想带敲了\(30\min\)后发现题面理解错了……无解只能准备文件后提交……
赛时结束还是很慌的,感觉自己爆了。
赛后
期望得分:\(0+[0,50]+60+[0,100]=[0,210]\)
实际得分:\(0+30+60+10=190\).
说实话,看到这个分数还是非常惊喜的。认真想的题没有挂分,还得到了一些意外的分数。
T1是确实想错了,加上题目本身知识点比较综合,丢分不是很可惜。
T2想错了还能拿到\(30pts\),确实幸运。
T3(完全没调试)就稳拿了60的暴力分,还是很满意的。
T4在题目理解歧义的情况下还是AC了。
嗯。很满意的分数。
T1
从给定的每个长度为3的子串中构造出原串。
思路很奇妙的一道题。
对于每个串,可以看做前两位与某个串的后两位相同,同理后两位可以与某个的前两位相同。
由此想到:可以从自己前两位向自己后两位建一条边。
比如abc
,则是ab
\(\to\)bc
.
特殊地,aaa
视为建一条aa
到自己的边。
如此下来,可以用一系列边和点确定这个序列。
剩下的问题,则是如何走完这些边。
通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。
通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的无向图或有向图称为欧拉图。
于是,考虑在构造出的图上判断是否可以找出欧拉路径即可。输出答案即为根据欧拉路径构造原串。
理论如上。实际还有一个细节:如何建图?
显然,用aa
这种表示节点肯定不合适。
于是,用类似于处理hash的思想,将其构造出对应的节点,离散化后使用。最后注意还原的细节即可。
#include <bits/stdc++.h> #define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) using namespace std; const int INF = 0x3f3f3f3f , N = 4e5+5; typedef long long ll; typedef unsigned long long ull; inline ll read(){ ll ret = 0 ; char ch = ' ' , c = getchar(); while(!(c >= '0' && c <= '9')) ch = c , c = getchar(); while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar(); return ch == '-' ? -ret : ret; } int n,m; int ecnt = -1,head[N],ind[N],oud[N]; int f[N]; int find(int x){return f[x] == x ? x : find(f[x]);} inline void merge(int x,int y){f[find(x)] = find(y);} struct Edge{int to,nxt;}e[N]; inline void add_edge(int u,int v){ // printf(" add (%d->%d)\n",u,v); e[++ecnt] = (Edge){v,head[u]}; head[u] = ecnt; ind[v] ++ , oud[u] ++; merge(u,v); } inline int getint(char c){return c >= '0' && c <= '9' ? c-'0'+1 : c >= 'a' && c <= 'z' ? c-'a'+11 : c-'A'+37;} inline char getch(int x){ return x >= 1 && x <= 10 ? x+'0'-1 : x >= 11 && x <= 36 ? x+'a'-11 : x+'A'-37;} stack<int>stk; void dfs(int u){ for(int i = head[u] ; ~i ; i = head[u]){ int v = e[i].to; head[u] = e[i].nxt; // printf(" dfs(%d,%d)\n",u,v); dfs(v); } stk.push(u); } int a[N][2],p[N]; void init(){ for(int i = 1 ; i <= m ; i ++) head[i] = -1 , ind[i] = oud[i] = 0 , f[i] = i; ecnt = -1; } void work(){ char ch[4]; n = read(); for(int i = 1 ; i <= n ; i ++) scanf("%s",ch+1), p[(i-1)*2+1] = a[i][0] = getint(ch[1])*65+getint(ch[2]) , p[(i-1)*2+2] = a[i][1] = getint(ch[2])*65+getint(ch[3]); sort(p+1,p+n+n+1); m = unique(p+1,p+n+n+1)-p-1; init(); for(int i = 1 ; i <= n ; i ++){ int u = lower_bound(p+1,p+m+1,a[i][0])-p, v = lower_bound(p+1,p+m+1,a[i][1])-p; // printf(" pre: add[%d] -> [%d]\n",a[i][0],a[i][1]); add_edge(u,v); } int s = 1 , sum = 0; for(int i = 1 ; i <= m ; i ++){ if(abs(ind[i]-oud[i]) > 1){puts("NO");return;} if(oud[i]-ind[i] == 1) s = i; sum += oud[i] != ind[i]; if(i != 1 && find(i) != find(i-1)){puts("NO");return;} } // printf("sum = %d , m = %d\n",sum,m); if(sum != 0 && sum != 2){puts("NO");return;} puts("YES"); dfs(s); if(!stk.empty()) putchar(getch(p[stk.top()]/65)); while(!stk.empty()) putchar(getch(p[stk.top()]%65)),stk.pop(); puts(""); } signed main(){ // fo("recover"); int T = read(); while(T--) work(); } /* 1 5 ACA ABA ABA CAB BAC */
T2
一道很好的题啊。
对于每个有敌对关系的节点,我们标记为二分图染成不同颜色。对于跟他敌对的点敌对的点(有点拗口hhh),通过递归的方式也标记上(此时就要强制与它是同色了。)若染色冲突则不可行。
否则,通过以上方式,可以将节点分割为多个联通块。
问题转化:在每组两个的多组联通块中各选取其中一个,使得选取总值最接近\(\dfrac n2\)。
此过程使用分组背包来实现。
#include <bits/stdc++.h> #define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) using namespace std; const int INF = 0x3f3f3f3f , N = 1e2+5; typedef long long ll; typedef unsigned long long ull; inline ll read(){ ll ret = 0 ; char ch = ' ' , c = getchar(); while(!(c >= '0' && c <= '9')) ch = c , c = getchar(); while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar(); return ch == '-' ? -ret : ret; } int n; int a[N][N]; bool vis[N],col[N]; int siz[N][2],tot; int dp[N][N]; bool dfs(int u,int co,int bel){ if(vis[u]) return col[u] == co; // printf(" color [%d]->%d :%d\n",u,co,bel); vis[u] = 1, col[u] = co; siz[bel][co] ++; for(int v = 1 ; v <= n ; v ++) if(!a[u][v]) if(!dfs(v,!co,bel)) return 0; return 1; } void init(){ tot = 0; memset(siz,0,sizeof(siz)); memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); } void work(){ n = read(); init(); for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= n ; j ++) a[i][j] = read(); if(n == 1){puts("No solution");return;} for(int i = 1 ; i <= n ; i ++) for(int j = 1; j <= n ; j ++) a[i][j] = a[j][i] = a[i][j] & a[j][i]; for(int i = 1 ; i <= n ; i ++) if(!vis[i]){ tot ++; if(!dfs(i,0,tot)){puts("No solution");return;} } dp[0][0] = 1; int ans = INF; for(int i = 1 ; i <= tot ; i ++) for(int j = n ; j ; j --) for(int k = 0 ; k <= 1 ; k ++) if(j >= siz[i][k]) dp[i][j] |= dp[i-1][j-siz[i][k]]; // for(int i = 0 ; i <= n ; i ++) // printf("%d:%d\n",i,dp[i]); for(int i = 0 ; i <= n ; i ++) if(dp[tot][i]) ans = min(ans,abs(n-i*2)); printf("%d\n",ans); } signed main(){ // fo("team"); int T = read(); while(T--) work(); return 0; }
T3
瓶颈就在,经过的边必须是在\([L,R]\)区间内建好的。
考虑进行离线,边权为建设时间。
将多个询问按左端点降序排序,这样处理起来,只有加边操作。
每添加一条边\(u\to v\)时,都只有dis[u]
和可dis[v]
能改变。
这样,令dis[u][k] = dis[v][k] = min(dis[u][k],ans[v][k])
,直接维护即可。
#include <bits/stdc++.h> #define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) using namespace std; const int INF = 0x3f3f3f3f , N = 1e3+5 , M = 1e5+5; typedef long long ll; typedef unsigned long long ull; inline ll read(){ ll ret = 0 ; char ch = ' ' , c = getchar(); while(!(c >= '0' && c <= '9')) ch = c , c = getchar(); while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar(); return ch == '-' ? -ret : ret; } int n,m,k; struct Edge{int u,v;}e[M]; struct Ask{int l,r,s,t,id;}q[M]; inline bool operator < (const Ask a,const Ask b){return a.l > b.l;} int dis[N][N],ans[M]; signed main(){ // fo("plan"); memset(dis,0x3f,sizeof(dis)) ; n = read() , m = read() , k = read(); for(int i = 1 ; i <= m ; i ++){ e[i].u = read() , e[i].v = read(); } // printf(" %d -> %d\n",st,ed); for(int i = 1 ; i <= k ; i ++){ int l = read() , r = read() , s = read() , t = read(); q[i] = (Ask){l,r,s,t,i}; } sort(q+1,q+k+1); q[0].l = m+1; for(int i = 1 ; i <= k ; i ++) { int s = q[i].s , t = q[i].t; // printf(" ask[%d -> %d],(%d,%d)\n",s,t,q[i].l,q[i].r); for(int j = q[i-1].l-1 ; j >= q[i].l ; j --){ int u = e[j].u , v = e[j].v; // printf(" add[%d][%d]\n",u,v); dis[u][v] = dis[v][u] = j; for(int j = 1 ; j <= n ; j ++) dis[u][j] = dis[v][j] = min(dis[u][j],dis[v][j]); } // printf("dis = %d\n",dis[s][t]); ans[q[i].id] = dis[s][t] <= q[i].r; } for(int i = 1 ; i <= k ; i ++) puts(ans[i] ? "Yes" : "No"); return 0; }
T4
很水的签到题,这里就不再赘述了吧……
只需要判断新建边和序列的关系,给无向边定向即可。
#include <bits/stdc++.h> #define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) using namespace std; const int INF = 0x3f3f3f3f , N = 5e4+5 , M = 2e5+5; typedef long long ll; typedef unsigned long long ull; inline ll read(){ ll ret = 0 ; char ch = ' ' , c = getchar(); while(!(c >= '0' && c <= '9')) ch = c , c = getchar(); while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar(); return ch == '-' ? -ret : ret; } int n,m,k; int ecnt,head[N]; struct Edge{int to,nxt;}e[M<<1]; inline void add_edge(int u,int v){ // printf("add (%d,%d)\n",u,v); e[++ecnt] = (Edge){v,head[u]}; head[u] = ecnt; } int buc[N]; queue<int>q; int st,ed; int dis[N];bool vis[N]; inline void init(){ memset(head,-1,sizeof(head));ecnt = -1; for(int i = 1 ; i <= n ; i ++)buc[i] = 0,vis[i] = 0; } void bfs(){ while(!q.empty())q.pop(); vis[st] = 1 , dis[st] = 0; q.push(st); while(!q.empty()){ int u = q.front();q.pop(); if(u == ed)return; for(int i = head[u] ; ~i ; i = e[i].nxt){ int v = e[i].to; // printf("bfs(%d %d)\n",u,v); if(!vis[v]) dis[v] = dis[u] + 1, vis[v] = 1, q.push(v); } } } void work(){ n = read() , m = read() , k = read(); init(); int u = read(),v; buc[u] = 1;st = u; for(int i = 1 ; i <= k ; i ++){ v = read(); buc[v] = i + 1; add_edge(u,v); u = v; } ed = v; // printf(" %d -> %d\n",st,ed); for(int i = 1 ; i <= m - k ; i ++){ u = read() , v = read(); if(!buc[u] || !buc[v])continue; if(buc[u] < buc[v])add_edge(u,v); else add_edge(v,u); } bfs(); printf("%d\n",dis[ed]); } signed main(){ // fo("seqpath"); int T = read(); while(T--) work(); return 0; }
明天接种疫苗第二针。早睡早睡。
这篇关于20210815 图论模拟赛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?