acwing第6周周赛

周周赛"/>

acwing第6周周赛

状态压缩+点集

给定一个由 n 个点和 m 条边构成的无向连通图。

我们希望通过一系列操作将其变为一个完全图（即每对不同的顶点之间都恰有一条边相连）。

每次操作时，可以选择其中一个点，找到所有和它直接相连的点，使这些点两两之间连边（若两点之间已经存在边，则无需重复连接）。

请问，至少多少次操作以后，可以将整个图变为一个完全图？

输入格式
第一行包含两个整数 n,m。

接下来 m 行，每行包含两个整数 u,v，表示点 u 和点 v 之间存在一条边。

所有点编号 1∼n。

输出格式
第一行输出最少操作次数。

第二行输出每次操作所选的点的编号，整数之间空格隔开。如果最少操作次数为 0，则无需输出第二行。

如果答案不唯一，则输出任意合理方案均可。

数据范围
前三个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n≤22，0≤m≤n(n−1)2，1≤u,v≤n，u≠v。
保证没有重边和自环，保证给定图是连通的。
思路：
逐步往外扩，类比prim算法
一个极大团不断吞并别的团
也就是一个核心core链接另一个core之后会将原来的点集扩大
直到状态全是1111111111
做法：
1.初始化init
f【状态】=操作数
e【点j】=这个点所连接的状态
g【状态2】={状态1 ， j }表示状态2是由状态1连接了j所拥有的点集之后的状态
2.从小到大枚举所有状态i
然后枚举i所链接的点集，也就是枚举j个点，然后走到了k这个状态
k=i或上e【j】
3.输出最后的满状态111111也就是f【2^n-1】

#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;
const int N = 22, M=1<<22;
typedef pair<int,int> PII;
int n,m;
int f[M];
int e[N];
PII g[M];
int main(){cin>>n>>m;if(2*m==n*(n-1)){puts("0");return 0;}memset(f,0x3f,sizeof f);for(int i=0;i<n;i++)e[i]=1<<i;for(int i=0;i<m;i++){int x,y;cin>>x>>y;x--,y--;e[x]|=1<<y;e[y]|=1<<x;}for(int i=0;i<n;i++)f[e[i]]=1,g[e[i]]={0,i};//每次操作时，可以选择其中一个点，找到所有和它直接相连的点，使这些点两两之间连边for(int i=0;i<1<<n;i++){//枚举每个状态连接的点集for(int j=0;j<n;j++){if(f[i]==0x3f3f3f3f)continue;if(i>>j&1){//团i连接着j点int k=i|e[j];//新的更大的团是由原来的团i并上小团j所得到的if(f[k]>f[i]+1){f[k]=f[i]+1;//状态k是由状态i连上点j所得到的g[k]={i,j};//状态k是由状态i连上点j所得到的}}}}int k=(1<<n)-1;cout<<f[k]<<endl;while(k){cout<<g[k].y+1<<" ";k=g[k].x;}//递归输出，状态k没连上j之前是状态x，那么状态x是哪个状态连上哪个点走过来的呢？//在这里我们递归处理}

用 f(x) 来表示满足下列条件的最小正整数 a：

a≥x。
a 的各个数位不包含除了 4 和 7 以外的其他数字。
现在，给定两个整数 l,r(l≤r)，请你计算 f(l)+f(l+1)+…+f® 的值。

输入格式
一行，两个整数 l,r。

输出格式
一行，一个整数表示求得的和。

数据范围
前三个测试点满足 1≤l≤r≤10，
所有测试点满足 1≤l≤r≤109。

上面那个是状态压缩dp

下面这个是裸思维题，当时比赛没写出来，但是出去打个球回来很快就写好了
有两个版本

#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r,init[1000010],ans,ansl,ansr,sum[1000010];
int a,p;
signed main(){cin>>l>>r;init[1]=4;init[2]=7;sum[1]=4;sum[2]=11;a=4;p=2;for(int i=1;i<2048;i++){init[++p]=a*10+4;init[++p]=a*10+7;a=init[p-i-1];}int i=1;while(l>init[i])i++;int ansl=i;while(r>init[i])i++;int ansr=i;if(ansr>ansl){ans+=(1+init[ansl]-l)*init[ansl];ans+=(r-init[ansr-1])*init[ansr];}else {ans=init[ansl]*(r-l+1);}if(ansr-ansl>1){for(int p=ansl+1;p<ansr;p++){ans+=init[p]*(init[p]-init[p-1]);}}cout<<ans<<endl;
}

第二个版本

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;typedef long long LL;vector<LL> S;void dfs(int u, LL x)
{S.push_back(x);if (u == 10) return;dfs(u + 1, x * 10 + 4);dfs(u + 1, x * 10 + 7);
}int main()
{dfs(0, 0);sort(S.begin(), S.end());LL l, r;cin >> l >> r;LL res = 0;for (int i = 1; i < S.size(); i ++ ){LL a = S[i - 1] + 1, b = S[i];res += S[i] * max(0ll, (min(r, b) - max(l, a) + 1));}cout << res << endl;return 0;
}作者：yxc
链接：/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

yxc用的是dfs爆搜进行的初始化
贼niubi
很可以，我又学到了一个小技巧