文章目录
- 前言
- CF361A Levko and Table
- CF361B Levko and Permutation
- CF360A Levko and Array Recovery
- CF360B Levko and Array
- CF360C Levko and Strings
- CF360D Levko and Sets
- CF360E Levko and Game
前言
361AB比较水
360AB都不错
C是dp好题（建议也看看洛谷官方题解）
D恶心数论题
E是神奇但不太难的水黑题
CF361A Levko and Table
Description \text{Description} Description
Levko 很喜欢幻方，他想构造一个长宽都是 n n n 且每行每列的和都是 k k k 的幻方，请你帮帮他.
Solution \text{Solution} Solution
每个
(
i
,
i
)
(i,i)
(i,i) 的点填
m
m
m 剩下全填
0
0
0 即可.
我写的是对角填
m
−
n
+
1
m-n+1
m−n+1 其他地方填
1
1
1，但都是一个道理.
Code \text{Code} Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=25;
#define r rand()
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();m=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) printf("%d ",m-n+1);
else printf("1 ");
}
putchar('\n');
}
}
CF361B Levko and Permutation
Description \text{Description} Description
给定 n , k n,k n,k，你需要构造一个序列，使得集合 { i ∣ 1 ≤ i ≤ n , g c d ( i , a i ) > 1 } \{i|{1\le i \le n,gcd(i,a_i)>1}\} {i∣1≤i≤n,gcd(i,ai)>1} 的元素个数恰好为 k k k.
Solution \text{Solution} Solution
首先，由于 1 1 1 必然不合法， k = n k=n k=n 时必然无解.
k
<
n
k< n
k<n时，对于
2
≤
i
≤
k
+
1
2\le i\le k+1
2≤i≤k+1我们让
a
i
=
i
a_i=i
ai=i，从而使其全部合法.
使
a
k
+
2
=
1
,
a
1
=
n
,
a
i
=
i
−
1
(
k
+
3
≤
i
≤
n
)
a_{k+2}=1,a_1=n,a_i=i-1(k+3\le i\le n)
ak+2=1,a1=n,ai=i−1(k+3≤i≤n)，从而使剩下的全部元素均不合法.
注意特判
m
=
n
−
1
m=n-1
m=n−1 的情况.
Code \text{Code} Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=25;
#define r rand()
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();m=read();
if(n==m){
printf("-1");return 0;
}
printf("%d ",m==n-1?1:n);
for(int i=2;i<=m+1;i++) printf("%d ",i);
if(m!=n-1) printf("1 ");
for(int i=m+3;i<=n;i++) printf("%d ",i-1);
return 0;
}
CF360A Levko and Array Recovery
Description \text{Description} Description
有一个长度为 n n n 的序列 a 1... n a_{1...n} a1...n，对其进行 m m m 次操作，操作有两种：
- 1 l i r i d i 1\space l_i\space r_i\space d_i 1 li ri di：对于 l i ≤ j ≤ r i l_i\le j\le r_i li≤j≤ri， a j ← a j + d i . a_j\gets a_j+d_i. aj←aj+di.
- 2 l i r i m i 2\space l_i\space r_i\space m_i 2 li ri mi：查询 max a j ( l i ≤ j ≤ r i ) . \max a_j(l_i\le j\le r_i). maxaj(li≤j≤ri).
现在给出 n , m n,m n,m 和操作信息，请你构造出一种合法的序列或者报告无解.
Solution \text{Solution} Solution
设第
i
i
i 个元素当前的增量为
a
d
d
i
add_i
addi，每个元素初始的最大值为
m
x
i
mx_i
mxi.
每次对于操作二，
m
x
j
←
min
(
m
x
j
,
m
i
−
a
d
d
j
)
(
l
i
≤
j
≤
r
i
)
mx_j\gets \min(mx_j,m_i-add_j)(l_i\le j\le r_i)
mxj←min(mxj,mi−addj)(li≤j≤ri).
这样，把操作扫一遍就能求出所有元素的
m
x
i
mx_i
mxi.
得出正确的
m
x
i
mx_i
mxi 后，我们再扫一遍操作序列，对于每一次操作二，设
w
=
max
m
x
j
(
l
i
≤
j
≤
r
i
)
w=\max mx_j(l_i\le j\le r_i)
w=maxmxj(li≤j≤ri).
由于第一次维护的原因，必然有
w
≤
m
i
w\le m_i
w≤mi.
若
w
<
m
i
w< m_i
w<mi，说明区间内的所有元素都达不到
m
i
m_i
mi，报告无解.
如果扫到最后还没有无解，输出
m
x
1...
n
mx_{1...n}
mx1...n 作为构造的序列.
Code \text{Code} Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=5005;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
int mx[N],add[N];
struct query{
int op,l,r,x;
}q[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();m=read();
memset(mx,0x3f,sizeof(mx));
for(int i=1;i<=m;i++){
q[i]=(query){(int)read(),(int)read(),(int)read(),(int)read()};
if(q[i].op==1){
for(int j=q[i].l;j<=q[i].r;j++) add[j]+=q[i].x;
}
else{
for(int j=q[i].l;j<=q[i].r;j++) mx[j]=min(mx[j],q[i].x-add[j]);
}
}
memset(add,0,sizeof(add));
for(int i=1;i<=m;i++){
if(q[i].op==1){
for(int j=q[i].l;j<=q[i].r;j++) add[j]+=q[i].x;
}
else{
int o=-2e9;
for(int j=q[i].l;j<=q[i].r;j++) o=max(o,mx[j]+add[j]);
if(o!=q[i].x){
printf("NO\n");return 0;
}
//printf("i=%d o=%d\n",i,o);
}
}
printf("YES\n");
for(int i=1;i<=n;i++) printf("%d ",min(mx[i],1000000000));
return 0;
}
CF360B Levko and Array
Description \text{Description} Description
给出一个序列
a
1...
n
a_{1...n}
a1...n，可以修改
k
k
k 个值,最小化
max
∣
a
i
−
a
i
+
1
∣
(
1
≤
i
<
n
)
\max|a_i-a_{i+1}|(1\le i<n)
max∣ai−ai+1∣(1≤i<n).
k
≤
n
≤
2000
k\le n\le 2000
k≤n≤2000
Solution \text{Solution} Solution
很巧妙的一道题.
容易想到二分答案，关键就是如何判断合法.
正难则反，改为保留至少
n
−
k
n-k
n−k 个数不变.
设计
d
p
i
dp_i
dpi 表示
[
1
,
i
]
[1,i]
[1,i] 区间中保留
i
i
i 的前提下保留数的最多个数.
转移则是：
d
p
i
=
max
d
p
j
+
1
(
j
<
i
,
∣
a
i
−
a
j
∣
≤
(
j
−
i
)
×
d
)
dp_i=\max dp_j+1(j<i,|a_i-a_j|\le(j-i)\times d)
dpi=maxdpj+1(j<i,∣ai−aj∣≤(j−i)×d)
暴力
n
2
n^2
n2 转移即可通过.
Code \text{Code} Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=6005;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
ll a[N];
int dp[N];
bool check(ll x){
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(abs(a[i]-a[j])<=1ll*(i-j)*x) dp[i]=max(dp[i],dp[j]+1);
}
if(dp[i]+m>=n) return true;
}
return false;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();m=read();
for(int i=1;i<=n;i++) a[i]=read();
ll st=0,ed=2e9;
while(st<ed){
ll mid=(st+ed)>>1;
if(check(mid)) ed=mid;
else st=mid+1;
}
printf("%lld\n",st);
return 0;
}
CF360C Levko and Strings
Description \text{Description} Description
给一个为
n
n
n 的只有小写字母组成的串
s
s
s，定义它与一个长度为
n
n
n 的串
t
t
t 的美丽度为：存在多少个二元组
(
i
,
j
)
1
≤
i
≤
j
≤
n
(i,j) \ 1\leq i \leq j \leq n
(i,j) 1≤i≤j≤n 满足
s
i
.
.
.
j
<
t
i
.
.
.
j
s_{i...j}<t_{i...j}
si...j<ti...j，这里的’<'是字典序比较。求有多少个
t
t
t，使得
s
s
s 与
t
t
t 的美丽度为
k
k
k.
n
,
k
≤
2000
n,k \leq 2000
n,k≤2000
Solution \text{Solution} Solution
很好的 DP 题.
一种不太一样的做法.
容易想到设计
d
p
i
,
j
dp_{i,j}
dpi,j 表示
[
1...
i
]
[1...i]
[1...i] 已经确定的二元组有
j
j
j 个的方案数.
设
u
p
i
up_i
upi 为大于
s
i
s_i
si 的字符数，设
b
o
t
i
bot_i
boti 为小于
s
i
s_i
si 的字符数.
对于第 i i i 位填不同于 s i s_i si 的字符时，比较容易写出转移：
-
t
i
<
s
i
t_i<s_i
ti<si 时，合法二元组数量不变，所以有：
b o t i × d p i − 1 , j → d p i , j bot_i\times dp_{i-1,j}\to dp_{i,j} boti×dpi−1,j→dpi,j -
t
i
>
s
i
t_i>s_i
ti>si 时，对于任意的
i
≤
j
≤
n
i\le j\le n
i≤j≤n，
(
i
,
j
)
(i,j)
(i,j) 都是合法的二元组，一共增加了
n
−
i
+
1
n-i+1
n−i+1 个，所以有：
u p i × d p i − 1 , j → d p i , j + ( n − i + 1 ) up_i\times dp_{i-1,j}\to dp_{i,j+(n-i+1)} upi×dpi−1,j→dpi,j+(n−i+1)
接下来就是 s i = t i s_i=t_i si=ti 的情况，相对比较麻烦.
还是分情况来讨论.
- 连续多位相等，到某一位
t
k
<
s
k
t_k<s_k
tk<sk。合法二元组不变，则有：
b o t k × d p i − 1 , j → d p k , j ( i < k ≤ n ) bot_k\times dp_{i-1,j}\to dp_{k,j}(i<k\le n) botk×dpi−1,j→dpk,j(i<k≤n)
暴力统计显然会 T，但是可以开一个 s u m sum sum 数组然后把 d p i , j dp_{i,j} dpi,j 加到 s u m j sum_j sumj 里面，统计到后面的时候把 s u m j sum_j sumj 里所有的值统计起来即可.
- 连续多位相等，到某一位
t
k
>
s
k
t_k>s_k
tk>sk。对于
i
≤
a
≤
k
,
k
≤
b
≤
n
i\le a\le k,k\le b\le n
i≤a≤k,k≤b≤n，
(
a
,
b
)
(a,b)
(a,b) 都是合法的二元组，增加的二元组数量是
(
k
−
i
+
1
)
×
(
n
−
k
+
1
)
(k-i+1)\times (n-k+1)
(k−i+1)×(n−k+1)，所以有：
u p k × d p i − 1 , j → d p k , j + ( k − i + 1 ) × ( n − k + 1 ) ( i < k ≤ n ) up_k\times dp_{i-1,j}\to dp_{k,j+(k-i+1)\times (n-k+1)}(i<k\le n) upk×dpi−1,j→dpk,j+(k−i+1)×(n−k+1)(i<k≤n)
这个想用类似情况 1 1 1 的方法统计比较困难，但是我们发现，在 n − i n-i n−i 较大时，增加二元组的数量是一个关于 k k k 的二次单峰函数，由于 m m m 只有 O ( n ) O(n) O(n) 级别，所以有效的转移非常少。我们可以从两边暴力转移，增量超过 m m m 就 break 即可.
- 不要忘记还有可能始终到最后都相等，可以直接：
d p i , j → d p n , j dp_{i,j}\to dp_{n,j} dpi,j→dpn,j
Code \text{Code} Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=2005;
const int mod=1e9+7;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
char s[N];
ll dp[N][N],botsum[N];
ll c[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
//debug("%d\n",(int)sizeof(dp)/1024/1024);
n=read();m=read();
scanf(" %s",s+1);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
int bot=s[i]-'a',up='z'-s[i];
(dp[i][j]+=bot*botsum[j])%=mod;
(dp[i][j]+=bot*dp[i-1][j])%=mod;
if(j-(n-i+1)>=0){
(dp[i][j]+=up*dp[i-1][j-(n-i+1)])%=mod;
}
//printf("i=%d j=%d bot=%d up=%d dp=%lld\n",i,j,bot,up,dp[i][j]);
}
for(int j=0;j<=m;j++){
(botsum[j]+=dp[i-1][j])%=mod;
(dp[n][j]+=dp[i-1][j])%=mod;
int l=i+1,r=n;
for(;l<=n;l++){
int add=(l-i+1)*(n-l+1);
if(j+add>m) break;
(dp[l][j+add]+=('z'-s[l])*dp[i-1][j])%=mod;
}
for(;r>l;r--){
int add=(r-i+1)*(n-r+1);
if(j+add>m) break;
(dp[r][j+add]+=('z'-s[r])*dp[i-1][j])%=mod;
}
}
}
printf("%lld\n",dp[n][m]);
return 0;
}
/*
3 3
tsy
*/
CF360D Levko and Sets
Description \text{Description} Description
有两个整数数组 a 1 , a 2 . . . . . . a n a_1,a_2......a_n a1,a2......an 和 b 1 , b 2 . . . . . . b m b_1,b_2......b_m b1,b2......bm，与一个质数 p p p ，现在要生成 n n n 个集合，第 i i i 个集合生成方式如下：
- 开始，集合只有元素 1 1 1.
- 从集合中选一个元素 c c c ，对于所有的 j j j ，如果满足 ( c × a i b j ) % p (c\times a_i^{b_j})\%p (c×aibj)%p 不在当前集合，就把它加入集合.
- 重复以上步骤.
求
n
n
n 个集合的并的大小.
n
≤
1
0
4
,
m
≤
1
0
5
,
p
≤
1
0
9
n\le 10^4,m\le 10^5,p\le 10^9
n≤104,m≤105,p≤109
a
i
≤
p
,
b
i
≤
1
0
9
a_i\le p,b_i\le10^9
ai≤p,bi≤109
Solution \text{Solution} Solution
题意简化一下就是集合里的元素是
a
i
a_i
ai 的（
b
i
b_i
bi组合相加）次幂模
p
p
p 的结果.
设
ϕ
=
p
−
1
,
g
=
gcd
(
ϕ
,
gcd
i
=
1
m
b
i
)
\phi=p-1,g=\gcd(\phi,\gcd_{i=1}^m b_i)
ϕ=p−1,g=gcd(ϕ,gcdi=1mbi)，那么第
i
i
i 个集合可以等价为：
{
a
i
k
g
(
m
o
d
p
)
∣
k
∈
N
}
\{a_i^{kg}(mod\space p)|k\in N\}
{aikg(mod p)∣k∈N}
设
c
i
c_i
ci 为最小的
k
k
k，满足
a
i
g
c
i
=
1
(
m
o
d
p
)
a_i^{gc_i}=1(mod\space p)
aigci=1(mod p)，
c
i
c_i
ci 必然是
ϕ
\phi
ϕ 的因子，可以预处理出
ϕ
\phi
ϕ 的因子后暴力求出.
那么这个集合可以等价为：
{
1
,
a
i
g
,
a
i
2
g
,
.
.
.
,
a
i
(
c
i
−
1
)
g
}
\{1,a_i^{g},a_i^{2g},...,a_i^{(c_i-1)g}\}
{1,aig,ai2g,...,ai(ci−1)g}
设
R
R
R 为
p
p
p 的原根，那么上面的集合等价于：
{
R
0
,
R
ϕ
c
i
,
R
2
×
ϕ
c
i
,
.
.
.
,
R
(
c
i
−
1
)
×
ϕ
c
i
}
\large \{R^0,R^{\frac{\phi}{c_i}},R^{2\times \frac{\phi}{c_i}},...,R^{(c_i-1)\times \frac{\phi}{c_i}}\}
{R0,Rciϕ,R2×ciϕ,...,R(ci−1)×ciϕ}
那么问题就转化为了给出一个数列
c
1...
n
c_{1...n}
c1...n ，求
[
1
,
ϕ
]
[1,\phi]
[1,ϕ] 之间由
c
c
c 数列筛出的数的个数，其中
c
i
c_i
ci 均是
ϕ
\phi
ϕ 的因子.
设
f
x
f_x
fx 为只被
x
x
x 筛掉的数的个数.
就有
f
x
=
ϕ
x
−
∑
f
k
x
f_x=\frac{\phi}{x}-\sum f_{kx}
fx=xϕ−∑fkx
由于所有的
c
i
c_i
ci 都是
ϕ
\phi
ϕ 的因数，所以也只枚举
ϕ
\phi
ϕ 的因数即可.
最后的答案就是把所有是
c
i
c_i
ci 倍数的
x
x
x 的
f
x
f_x
fx 加起来.
Code \text{Code} Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=2e5+100;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
int mod;
inline ll ksm(ll x,ll k){
ll res(1);
while(k){
if(k&1) res=res*x%mod;
x=x*x%mod;k>>=1;
}
return res;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int a[N],b[N],c[N],g;
int pd[N],tot;
int f[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();m=read();mod=read();
int phi=mod-1;g=phi;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=read(),g=gcd(g,b[i]);
for(int i=1;i*i<=phi;i++){
if(phi%i) continue;
pd[++tot]=i;if(i*i<phi) pd[++tot]=phi/i;
}
sort(pd+1,pd+1+tot);
for(int i=1;i<=n;i++){
int d=ksm(a[i],g);
for(int j=1;j<=tot;j++){
if(ksm(d,pd[j])==1){
c[i]=phi/pd[j];break;
}
}
//printf("i=%d c=%d\n",i,c[i]);
}
int res(0);
for(int i=tot;i>=1;i--){
bool flag=0;
for(int j=1;j<=n;j++){
if(pd[i]%c[j]==0){flag=1;break;}
}
if(!flag) continue;
f[i]=phi/pd[i];
for(int j=i+1;j<=tot;j++){
if(pd[j]%pd[i]==0) f[i]-=f[j];
}
res+=f[i];
}
printf("%d\n",res);
return 0;
}
/*
3 3
tsy
*/
CF360E Levko and Game
Description \text{Description} Description
你和你的朋友在一张有 n n n（ n ≤ 1 0 4 n\le 10^4 n≤104）个点， m + k m+k m+k（ m ≤ 1 0 4 , k ≤ 100 m \le 10^4,k\le 100 m≤104,k≤100）条边的带权有向图上玩一个游戏.
一开始你们分别处在 S 1 S_1 S1 和 S 2 S_2 S2 上,你们需要到达 T T T.
你可以将给定的 k k k 条边的权值修改为 [ L , R ] [L,R] [L,R] 中任何数.
问你是否能先到达
T
T
T,如果不能,能否达成平局.
n
,
m
≤
1
0
4
,
k
≤
100
n,m\le 10^4,k\le 100
n,m≤104,k≤100
Solution \text{Solution} Solution
一开始把所有边的权都设成最大.
对于一条边
(
u
→
v
)
(u\to v)
(u→v)，若
d
i
s
1
u
≤
d
i
s
1
v
dis1_u\le dis1_v
dis1u≤dis1v，就把它的边权设成最小，因为如果 B 想用这条边，必败无疑.
改权后可能
d
i
s
dis
dis 的关系发生变化，重新跑 Dijkstra，再次判断即可.
复杂度
O
(
n
k
)
O(nk)
O(nk).
Code \text{Code} Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=1e4+100;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m,k;
struct node{
int to,nxt,frm,w;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y,int w){
p[++cnt]=(node){y,fi[x],x,w};fi[x]=cnt;
return;
}
int id[105];
int u[105],v[105],l[105],r[105];
int s1,s2,t;
ll dis1[N],dis2[N];
bool vis[N];
#define pr pair<int,ll>
#define mkp make_pair
priority_queue<pr,vector<pr>,greater<pr> >q;
void dij(ll *dis,int s){
memset(vis,0,sizeof(vis));
dis[s]=0;q.push(mkp(0,s));
while(!q.empty()){
int now=q.top().second;q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=fi[now];~i;i=p[i].nxt){
int to=p[i].to;
if(dis[to]>dis[now]+p[i].w){
dis[to]=dis[now]+p[i].w;
q.push(mkp(dis[to],to));
}
}
}
return;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
memset(fi,-1,sizeof(fi));cnt=-1;
n=read();m=read();k=read();
s1=read();s2=read();t=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),w=read();
addline(x,y,w);
}
for(int i=1;i<=k;i++){
u[i]=read(),v[i]=read(),l[i]=read(),r[i]=read();
addline(u[i],v[i],r[i]);id[i]=cnt;
}
while(1){
int f=0;
memset(dis1,0x3f,sizeof(dis1));memset(dis2,0x3f,sizeof(dis2));
dij(dis1,s1);dij(dis2,s2);
for(int i=1;i<=k;i++){
if(p[id[i]].w!=l[i]&&dis1[u[i]]<dis2[u[i]]){
f=1;p[id[i]].w=l[i];break;
}
}
if(!f) break;
}
memset(dis1,0x3f,sizeof(dis1));memset(dis2,0x3f,sizeof(dis2));
dij(dis1,s1);dij(dis2,s2);
if(dis1[t]>dis2[t]) printf("LOSE");
else{
if(dis1[t]==dis2[t]) printf("DRAW\n");
else printf("WIN\n");
for(int i=1;i<=k;i++) printf("%d ",p[id[i]].w);
}
return 0;
}
/*
3 3
tsy
*/