1400——1475C,1332B;
2021/10/6 23:12:00
本文主要是介绍1400——1475C,1332B;,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
今天2021.10.6。
中午组队赛,遇到一个分层图最短路的模板题,但是不会做。。没学过,所以现学了一下:https://blog.csdn.net/Mr_dimple/article/details/120629967;
把昨天最后的那道题补了:
1475.C Ball in Berland(思维,容斥)
题意:
一共n对关系 (xi,yi)
,从中挑出两对,确保两队中人不冲突(同一个人不在两个队中),一共可以挑选出多少组两对?
思路:
只能在O(N)
或者O(logN)
的时间内过。
依次遍历n对关系,统计当前关系可以和多少对关系组成一组?
对于该对关系中的 x
,统计出和其一对的y的个数 sum1
;
对于该对关系中的 y
,统计出和其一对的x的个数 sum2
;
那么,和当前关系(x,y)
配对的关系一共有n - (sum1 + sum2 - 1)
个。(和当前关系有牵连的都不能要,其他的都可以。此外,多加了一个这对关系本身,要去掉)
除此之外,前面的 x 位置可能与后面的 y 位置组合,但是后面枚举到 y 位置时,又把 x 位置算一遍,每个位置都多算了,总结果要除2。
Code:
const int N = 200010, mod = 1e9+7; int T, n, m; PII a[N]; int main(){ Ios; cin>>T; while(T--) { int k; cin>>n>>m>>k; mp1.clear(); mp2.clear(); for(int i=1;i<=k;i++){ cin>>a[i].first;mp1[a[i].first]++; } for(int i=1;i<=k;i++){ cin>>a[i].second;mp2[a[i].second]++; } ll ans=0; for(int i=1;i<=k;i++) { int x=a[i].first,y=a[i].second; ans+=k-(mp1[x]+mp2[y]-1); } cout<<ans/2<<"\n"; } return 0; }
1332.B. Composite Coloring(思维)
题意:
给出长度为 n 的数列,其中每个数大小[4,1000]
。现将其染色,确保:互质的两个数不能染成同一颜色。
输出所需要的颜色个数,并依次输出每个位置的颜色。
思路:
数4~1000中,正好能由前面11个"奇数"(2,3,5,7,11,13,17,19,23,29,31)的倍数组成。
所以,一种数的所有倍数一种颜色。
Code:
const int N = 200010, mod = 1e9+7; int T, n, m, a[N]; int f[12]={0,2,3,5,7,11,13,17,19,23,29,31}; int flag[12]; int ans[N]; int main(){ Ios; cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; mem(flag,0); int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=11;j++) { if(a[i]%f[j]==0){ if(!flag[j]) flag[j]=++cnt; ans[i]=flag[j]; break; } } } cout<<cnt<<"\n"; for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<'\n'; } return 0; }
明天加油!
这篇关于1400——1475C,1332B;的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25安卓NDK 是什么?-icode9专业技术文章分享
- 2024-12-25caddy 可以定义日志到 文件吗?-icode9专业技术文章分享
- 2024-12-25wordfence如何设置密码规则?-icode9专业技术文章分享
- 2024-12-25有哪些方法可以实现 DLL 文件路径的管理?-icode9专业技术文章分享
- 2024-12-25错误信息 "At least one element in the source array could not be cast down to the destination array-icode9专业技术文章分享
- 2024-12-25'flutter' 不是内部或外部命令,也不是可运行的程序 或批处理文件。错误信息提示什么意思?-icode9专业技术文章分享
- 2024-12-25flutter项目 as提示Cannot resolve symbol 'embedding'提示什么意思?-icode9专业技术文章分享
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享