题目链接：https://codeforces.com/contest/1246/problem/E。
考虑如果一系列操作之后能变成$1$，那么一定能构造出某个序列$b_i$满足$sum_{i=1}^{n}a_ik^{-b_i}=1$。
反过来也成立，考虑如果我们构造出了一组$b_i$，那么一定对应着一个操作序列，可以如下构造：
先找出最大的$b_i$，假设为$x$，显然存在大于等于两个$b_i=x$的位置，因为题目保证了$knot mid a_i$，如果只有一个位置，等式左边就会是一个实数，显然矛盾。然后任意选出两个$b_i=x$的位置然后合并，剩下的又变成了子问题。
那么我们可以根据这个$dp$，设$f_{s,x}$表示用$s$集合这些数能不能构造出一组$b_i$使得$sum_{i=1}^{n}a_ik^{-b_i}=x$。
转移比较显然：考虑每次多加进去一个$b_i=0$的数，$f_{s,x}leftarrow f_{s setminus {i},x-a_i}$；或者每次把所有$b_i$加一，$f_{s,x}leftarrow f_{s,x/k}$。
可以利用$rm bitset$优化转移，复杂度$O(2^n(sum a_i)cdot (1+n/omega))$。
输出方案就逆推转移方程搞出$b_i$，然后利用上面的构造就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
using namespace std;
void (int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 20+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int a[maxn],b[maxn],n,k;
bitset<2001 > f[(1<<16)+10];
int c=0;
void dfs(int s,int t) {
if(!s) return ;
for(;t<=2000;t*=k,c++) {
for(int i=0;i<n;i++)
if(t>=a[i+1]&&(s&(1<<i))&&f[s-(1<<i)][t-a[i+1]]) {
b[i+1]=c;dfs(s-(1<<i),t-a[i+1]);
return ;
}
}
}
int main() {
read(n),read(k);
for(int i=1;i<=n;i++) read(a[i]);
f[0][0]=1;
for(int s=1;s<1<<n;s++) {
for(int i=0;i<n;i++)
if(s&(1<<i)) f[s]|=f[s-(1<<i)]<<a[i+1];
for(int i=2000;i;i--) if(i%k==0) f[s][i/k]=f[s][i/k]|f[s][i];
}
if(!f[(1<<n)-1][1]) return puts("NO"),0;
dfs((1<<n)-1,1);
multiset<pair<int,int > > s;
vector<pair<int,int > > ans;
for(int i=1;i<=n;i++) s.insert(mp(-b[i],a[i]));
for(int i=1;i<=n-1;i++) {
pii p=*s.begin();s.erase(s.begin());
pii q=*s.begin();s.erase(s.begin());
ans.pb(mp(p.sc,q.sc));
p.sc+=q.sc;int x=p.sc;
while(x%k==0) x/=k,p.fr++;
s.insert(mp(p.fr,x));
}
puts("YES");
for(auto x:ans) printf("%d %dn",x.fr,x.sc);
return 0;
}
|
近期评论