2019ICPC南昌 重现
待补
B. A Funny Bipartite Graph
题解
C. And and Pair
题意：
给定一个很大的数n的二进制表示s(也就是01串)，计算满足条件的数对<i，j>的数量 条件： 0<=j<=i<=n i&n=i i&j=0
其中&符号表示位运算与 答案对1e9+7取模
数据范围：|s|<=1e5
解法：
很容易看出可以用数位dp来解 当s[i]=1的时候，i可以为0或者1，i=0时j=0/1，i=1时j=0 当s[i]=0的时候，i只能为0，i=0时j=0/1 当存在最高位限制的时候，i=0时j=0，此时j不能为1 详见代码
需要注意的点是平常数位dp是从高位到低位dp，拆分数的时候一般把高位放在数组的右边 但是给定的01串高位在左边，低位在右边，需要改一下dp的顺序，或者将串翻转一下。
ps： 似乎还有其他解法，组合数学什么的
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e5+5;
const int mod
=1e9+7;
char s
[maxm
];
int d
[maxm
];
int dfs(int len
,int limit
){
if(!len
)return 1;
if(!limit
&&d
[len
]!=-1)return d
[len
];
int ans
=0;
if(s
[len
]==1){
if(limit
){
ans
+=dfs(len
-1,1)+dfs(len
-1,0);
}else{
ans
+=dfs(len
-1,0)*3;
}
}else{
if(limit
){
ans
+=dfs(len
-1,1);
}else{
ans
+=dfs(len
-1,0)*2;
}
}
ans
%=mod
;
if(!limit
)d
[len
]=ans
;
return ans
;
}
int solve(){
int len
=strlen(s
+1);
reverse(s
+1,s
+1+len
);
for(int i
=1;i
<=len
;i
++){
d
[i
]=-1;
s
[i
]-='0';
}
return dfs(len
,1);
}
signed main(){
int T
;cin
>>T
;
while(T
--){
scanf("%s",s
+1);
int ans
=solve();
cout
<<ans
<<endl
;
}
return 0;
}
E. Bob’s Problem
题意：
给定n个点m条边的无向图，和一个整数k 每条边是黑色或者白色，且每条边有边权 现在你必须在图中选择一些边，最多选择k条白边， 要求选择的边能使得图连通 问选择出的边的最大边权和是多少 如果无解则输出-1
数据范围：n<=5e4，m<=5e5
解法：
要使得边权和最大，因为黑边没有数量限制所以全选，并查集维护一下连通性，把白边存下来
然后白边按边权从大到小排序 遍历白边，如果白边两端不连通则选定且k-=1，否则先不选 如果k次机会选完了还是不连通则无解 如果连通之后k还有剩余，则优先把剩下的边权大的选下来
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e6+5;
struct E
{
int x
,y
,w
;
friend bool operator<(E a
,E b
){
return a
.w
>b
.w
;
}
};
vector
<E
>temp
;
int mark
[maxm
];
int pre
[maxm
];
int n
,m
,k
;
int ffind(int x
){
return pre
[x
]==x
?x
:pre
[x
]=ffind(pre
[x
]);
}
signed main(){
int T
;cin
>>T
;
while(T
--){
cin
>>n
>>m
>>k
;
temp
.clear();
for(int i
=1;i
<=n
;i
++){
pre
[i
]=i
;
}
int ans
=0;
for(int i
=1;i
<=m
;i
++){
int x
,y
,w
,c
;cin
>>x
>>y
>>w
>>c
;
if(c
==0){
ans
+=w
;
pre
[ffind(x
)]=ffind(y
);
}else{
temp
.push_back({x
,y
,w
});
}
}
sort(temp
.begin(),temp
.end());
int len
=temp
.size();
for(int i
=0;i
<len
;i
++){
mark
[i
]=0;
}
for(int i
=0;i
<len
&&k
;i
++){
int x
=ffind(temp
[i
].x
);
int y
=ffind(temp
[i
].y
);
if(x
!=y
){
pre
[x
]=y
;
ans
+=temp
[i
].w
;
mark
[i
]=1;
k
--;
}
}
if(k
){
for(int i
=0;i
<len
&&k
;i
++){
if(!mark
[i
]){
ans
+=temp
[i
].w
;
k
--;
}
}
}
int cnt
=0;
for(int i
=1;i
<=n
;i
++){
if(pre
[i
]==i
){
cnt
++;
if(cnt
>1)break;
}
}
if(cnt
!=1){
puts("-1");
}else{
cout
<<ans
<<endl
;
}
}
return 0;
}
G. Eating Plan
题意：
给定长度为n的排列a，其中a[i]=k表示第i个盘子中的食物重量为(k的阶乘)
你的胃很奇怪，当吃了重量为x的食物的时候，剩下的食物质量为x
