Codeforeces Edu 37 D
Codeforeces Edu 37 D
|这题真的是一点思路也没有，好不容易看懂了题解写完了，结果发现理解出了偏差（；´д｀）ゞ
题目来源: Codeforces
题解
思路
在计算怎么转移之前，我们需要先判断是否能够转移出水的体积为V的水桶。
那么，首先我们可以得出，对于$ sum = ^n_{i=1}{v[i]} \(，若\)sum<V$则不可能。
然后我们判断什么时候可以转移。我们可以发现当$ V%k == 0$时，我们永远可以得到一个水的体积为V的水桶。
而当V不是k的整数倍时，V中\(V\%k\)这一部分肯定能够从其它桶凑出。只有此时能够得到一个体积为V的水桶。
然后我们便需要算出是否有几个水桶水量的和能够与V同余。这里我们需要用到简单的动态规划(但我还是把它忘了。。。)。使用dp[i][j]记录到第i个数是否能取到同余k为j的值。
最后只要输出移动方法就行了。因为改题目非固定答案，所以我们可以"套模板",即使用麻烦但是能够达成效果的方法进行移动。
我们可以使用一个flag[i][j]来记录在到达位置i且%k==j时是否取了i这个位置的数。
然后我们把所有取了的数移到一个位置x，没有取的移到一个位置y,再用y把x中的水加至体积为V便可以了。 ### 结论
判断
- \(sum < V\)时: NO
- \(sum\%k==0\)时: YES
- $ S\(使得\)_{iS}{v[i]} V(k)$: YES
- Otherwise: NO
(\(S\)为取出的数的下标的集合)
第2中情况其实可以直接被第三种情况包括，只要初始从dp[0][0] = true开始即可。
DP
我们使用dp[i][j]来表示到第i个数时能否有取法S使得\(\sum_{i\in S}{v[i]} \equiv V(\mod k)\)。那么转移方程如下: \[ dp[i][j] = dp[i-1][j]\ || \ dp[i-1][Mod(j-v[i],k)]\]
其中或运算符左边的是不取当前数值的情况，右边是取当前数值的情况。
这里使用自己写的Mod()函数是为了防止CPP的%算出负值。
在f[i][Mod(j-v[i],k)]为True时flag[i][j]为True
转移步骤
代码
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <cstdio>
#include <cstring>
bool dp[5010][5010];
bool flag[5010][5010];
int v[5010];
int Mod(int a,int b)
{
truewhile (a<0)
truetruea += b;
truereturn a%b;
}
int main()
{
truememset(dp,false,sizeof(dp));
truememset(flag,false,sizeof(flag));
trueint n,k,V,sum = 0;
truescanf("%d%d%d",&n,&k,&V);
truefor (int i =1; i<=n; i++)
true{
truetruescanf("%d",&v[i]);
truetruesum += v[i];
true}
trueif (sum<V)
true{
truetrueprintf("NO\n");
truetruereturn 0;
true}
truedp[0][0] = true;
truefor (int i = 1; i<=n; i++)
truetruefor (int j = 0; j<k; j++)
truetrue{
truetruetrueif (dp[i-1][j])
truetruetruetruedp[i][j] = true;
truetruetrueelse if (dp[i-1][Mod(j-v[i],k)])
truetruetrue{
truetruetruetruedp[i][j] = true;
truetruetruetrueflag[i][j] = true;
truetruetrue}
truetrue}
true
trueif (dp[n][V%k])
true{
truetrueprintf("YES\n");
truetrueint t1=0,t2=0;
truetrueint j = V%k,i=n;
truetruewhile(i>0)
truetrue{
truetruetrueif (v[i]==0)
truetruetrue{
truetruetruetruei--;
truetruetruetruecontinue;
truetruetrue}
truetruetrueif (flag[i][j])
truetruetrue{
truetruetruetruej = Mod(j-v[i],k);
truetruetruetrueif (!t1)
truetruetruetruetruet1 = i;
truetruetruetrueelse{
truetruetruetruetrueprintf("%d %d %d\n",(v[i]+k-1)/k,i,t1);
truetruetruetruetruev[t1] += v[i];
truetruetruetruetruev[i] = 0;
truetruetruetrue}
truetruetrue}else{
truetruetruetrueif (!t2)
truetruetruetruetruet2 = i;
truetruetruetrueelse{
truetruetruetruetrueprintf("%d %d %d\n",(v[i]+k-1)/k,i,t2);
truetruetruetruetruev[t2] += v[i];
truetruetruetruetruev[i] = 0;
truetruetruetrue}
truetruetrue}
truetruetruei--;
truetrue}
truetrueif (V%k==0 && V!=0)
truetrue{
truetruetrueif (t2!=1) t1=1;
truetruetrueelse t1 = 2;
truetruetrueprintf("%d %d %d\n",V/k,t2,t1);
truetrue}
truetrueelse if (t1 && V!=v[t1])
truetrue{
truetruetrueif (!t2)
truetruetrue{
truetruetruetrueif (t1==1) t2=2;
truetruetruetrueelse t2 = 1;
truetruetrue}
truetruetrueif (v[t1]<V)
truetruetruetrueprintf("%d %d %d\n",(V-v[t1])/k,t2,t1);
truetruetrueelse printf("%d %d %d\n",(v[t1]-V)/k,t1,t2);
truetrue}
true}else printf("NO");
}
|