|
cf链接：Dashboard - The 2020 ICPC Asia Taipei-Hsinchu Site Programming Contest - Codeforces
B. Make Numbers（dfs+模拟，优先级问题）
思路：考虑把连接也看成一种运算，那么就有+、-、*、连接 这四种运算，优先级是：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【连接】 > 【*】 > 【+、-】
注意数字的顺序会影响运算结果，所以考虑用全排列+dfs，其中dfs负责符号运算。
注意dfs中的去重操作：相同vector，相同的当前操作，对答案贡献就重复了，要用set去重。
#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
// #define int long long
#define pii pair<int,int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
const int N = 1e4+5;
set<pair<vector<int>,int>> st;
int ans=0,vis[N];
void dfs(vector<int> v,int op){
if(st.count({v,op})) return;
st.insert({v,op});
int sz=v.size();
if(sz==1){ //只剩一个数，可以检查是否满足题意
if(v[0]>=0 && !vis[v[0]]) ans++, vis[v[0]]=1; //没有重复，符合题意
return;
}
if(op==1 || op==2){ //处理连接和*
dfs(v,op+1); //跳过这一步
if(sz==2 && op==1) return; //全部连一起，非法了
FOR(i,0,sz-2){ //遍历op的作用位置
vector<int> t; //临时vector，用来存处理完之后的结果
FOR(j,0,i-1) t.push_back(v[j]); //把前面的数放进去
if(op==1) t.push_back(v[i+1]>=10 ? v[i]*100+v[i+1] : v[i]*10+v[i+1]); //1.合并
if(op==2) t.push_back(v[i]*v[i+1]); //2.乘法
FOR(j,i+2,sz-1) t.push_back(v[j]); //把后面的数放进去
dfs(t,op); //重复本操作
}
}
if(op==3){ //处理+和-
vector<int> t;
t.push_back(v[0]+v[1]); //加法
FOR(j,2,sz-1) t.push_back(v[j]); //把后面的数放进去
dfs(t,op);
t[0] = v[0]-v[1]; //换成-
dfs(t,op);
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
vector<int> v;
int x; FOR(i,1,4) cin>>x, v.push_back(x);
sort(v.begin(), v.end());
do{dfs(v,1);}while(next_permutation(v.begin(), v.end()));
cout<<ans<<'\n';
}
C. Pyramid （思维，简单dp）
注意到一个非常重要的性质，一个点走过x次，那么它的左孩子走过(x+1)/2次（即一半向上取整），右孩子走过x/2次（即一半向下取整）。这样就可以dp推出前k-1次每个点走过的小球个数。写法很简单。
#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
#define pii pair<int,int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 0x3f3f3f3f;
const int N = 1e4+5;
int T,n,k, f[N][N];
inline void solve(){
FOR(i,0,n-1) FOR(j,0,i) f[i][j]=0; //init
cin>>n>>k;
int ans=0; //ans表示当前走到的位置（每往右走一次，ans就+1）
f[0][0]=k-1;
for(int i=0; i<n-1; i++){
if(f[i][ans]%2) ans++;
for(int j=0; j<=i; j++){
f[i+1][j] += (f[i][j]+1)/2;
f[i+1][j+1] += f[i][j]/2;
}
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>T; while(T--) solve();
}
E. A Color Game（区间dp）
[i,j]区间中，如果可以只剩余k类字母的话，那么用f[i][j][k]来记录最多剩余k类字母的数量。
如果不能只剩余k类字母（即至少要剩余两种字母），那么f[i][j][k]用-inf作为非法标记
如果能全部消除，但一个k类字母也剩余不了，那f[i][j][k]就是0（剩了0个也算它剩了，因为它没有不合法）
dp初始化是f[i][i][mp[s[i]]=1，其他都用-inf标记。
剩下就是基础的区间dp了。注意如果一个[l,r]区间可以被全部消除，需要标记所有f[l][r][k]为合法（至少也得是0，可以更大）
最终，f[0][n-1][k]必须要有一个>=m，来完成最后的一次消除。
#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
#define pii pair<int,int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
const int N = 550;
map<char,int> mp;
string s;
int m, f[N][N][10];
inline void getmx(int&a,int b){a=max(a,b);}
inline void init(){
memset(f,-0x3f3f3f3f,sizeof(f));
mp['R'] = 0; mp['G'] = 1; mp['B'] = 2;
mp['C'] = 3; mp['M'] = 4; mp['Y'] = 5;
mp['K'] = 6;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
cin>>s>>m; int n=s.size();
if(m==1) {cout<<"Yes"<<'\n'; return 0;} //特判m=1
FOR(i,0,n-1) f[i][i][mp[s[i]]]=1;
FOR(len,2,n) for(int l=0,r=l+len-1; r<=n; l++,r++){
bool ok=0;
for(int j=l; j<r; j++){ //断点
FOR(c,0,6){
getmx(f[l][r][c], f[l][j][c]+f[j+1][r][c]); //[l,r]区间中最多剩多少个c？
if(f[l][r][c]>=m) ok=1; //[l,r]区间合法了
}
}
if(ok) FOR(c,0,6) getmx(f[l][r][c],0); //合法化设置
}
FOR(i,0,n-1) if(f[0][n-1][i]>=m) {cout<<"Yes"; return 0;}
cout<<"No";
}
F. Cable Protection?
题意：求基环树的最小点覆盖。（基环树就是中间有一个环的树，把环中一条边切掉就是普通树）
思路：基环树不好弄，考虑直接切掉一条边变成普通树。比如切s-t，然后因为s，t中必须至少有一个要放，所以s和t各dfs一次，答案就是min(s放，t放)。注意因为分别让s放了，t放了，所以切掉的边不会影响结果。
#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
#define pii pair<int,int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
const int N = 2e5+5,inf=0x3f3f3f3f;
vector<int> g[N];
int n,m,s=-1,t=-1;
int f[N][2];
void dfs(int u,int fa){
f[u][0]=1; f[u][1]=0;
for(int v:g[u]){
if(v==fa) continue;
dfs(v,u);
f[u][0]+=min(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>m; int u,v;
FOR(i,1,n+m){
cin>>u>>v;
if(u<n && v<n && s==-1){ //本题核心！！找出环中要切掉的一条边
s=u; t=v; continue;
}
g[u].push_back(v); g[v].push_back(u);
}
dfs(s,-1);
int ans1=f[s][0];
memset(f,0,sizeof(f));
dfs(t,-1);
cout<<min(ans1,f[t][0]);
}
H. Optimization for UltraNet
题意：给出一个图，给出的边可用可不用，求一棵生成树，使得：1.首先保证树的最小边权最大。2.在保证1的前提下，使得所有边权的和最小。
题目要求输出所有点对的路径上最小边权的和。
#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
#define pii pair<int,int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
const int inf=0x3f3f3f3f;
const int N = 1e4+5, M=5e5+5;
int n,m,fa[N],f[N];
long long ans=0;
struct node{int to,w;}; vector<node> g[N];
struct edge{int u,v,w;} e[M];
inline bool cmp(const edge&a,const edge&b){return a.w<b.w;} //按权值排序
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} //并查集find函数
inline void init(){FOR(i,1,n) fa[i]=i;} //init并查集
inline int check(int x){ //检查最小权值边是否能>=x
init(); int cnt=n;
FOR(i,1,m){
if(cnt==1) break; //已经连通，ok
if(e[i].w < x) continue; //跳过权值不够的
int r1=find(e[i].u), r2=find(e[i].v);
if(r1!=r2) cnt--, fa[r2]=r1; //merge r1 with r2
}
if(cnt==1) return 1; //连通，ok
else return 0; //不连通，false
}
inline void build(int x){ //根据二分得到的最小边权结果，建一棵树
//要注意，相同最小边权可能建出不同的数，如果把合法边全加上了，可能是一个图而不是树
//所以还要根据连通性来保证建的是一棵树而不是一个图（否则后面dfs会出问题）
init(); int cnt=0;
FOR(i,1,m){ //按照边权从小到大建树，这样就能保证总边权最小！！
if(cnt==n-1) return; //建树完成，结束
if(e[i].w < x) continue; //权值不够，跳过
int r1=find(e[i].u), r2=find(e[i].v);
if(r1==r2) continue; //已经连通，跳过
//下面进行建边
int u=e[i].u, v=e[i].v, w=e[i].w;
g[u].push_back({v,w});
g[v].push_back({u,w});
fa[r2] = r1; //建完边之后，记得记录连通，防止边建多了
cnt++; //建边数量+1
}
}
void dfs(int u,int fa){ //dfs求出起点s到每个点的最小边权
for(auto i:g[u]){
int v=i.to, w=i.w;
if(v==fa) continue;
f[v]=min(f[u],w);
ans+=f[v];
dfs(v,u);
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>m;
FOR(i,1,m) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1,cmp); //按权值排序
int l=0, r=1e7, mid, res;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) res=mid, l=mid+1;
else r=mid-1;
}
build(res);
FOR(i,1,n){
f[i]=inf;
dfs(i,0);
}
cout<<ans/2;
}
M. Keystroke?
暴力枚举所有情况，因为总共就16种情况，预处理一下即可。
#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"!!!"<<endl;
#define pii pair<int,int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 0x3f3f3f3f;
const int N = 2e5+5;
set<int> zuo[20], you[20];
int T,n,m,a[N],b[N];
inline void init(){
FOR(i,0,15){
for(int j=0; j<4; j++){
if(!((i>>j)&1)) continue;
if(j==0) zuo[i].insert(0), you[i].insert(0);
else if(j==1) zuo[i].insert(0), you[i].insert(1);
else if(j==2) zuo[i].insert(1), you[i].insert(0);
else zuo[i].insert(1), you[i].insert(1);
}
}
}
inline void solve(){
cin>>n>>m;
FOR(i,1,n) cin>>a[i];
FOR(i,1,m) cin>>b[i];
int ans=0;
FOR(i,0,15){
if(!(n==zuo[i].size() && m==you[i].size())) continue;
bool ok=1;
FOR(j,1,n) if(!zuo[i].count(a[j])) {ok=0; break;}
FOR(j,1,m) if(!you[i].count(b[j])) {ok=0; break;}
if(ok)ans++;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
cin>>T; while(T--) solve();
}
|