Codeforces 思维训练（二）

我们一直在焦虑未来，却不曾想现在正是以前的自己梦寐以求的状态

为了锻炼我的解题思路以及分析问题的能力，我会在codeforces上找一下适合自己难度的题目，就以自己现在的实力来说，可以考虑刷codeforces上难度范围1100左右的题目，这一难度的题目对算法的考察相对较少，更多的是一些贪心，数学之类的解题思维能力，现在可以通过联系这一类的题目，提升自己的代码编写能力，思维能力，题目分析能力以及自己debug的能力。

B. Transfusion

题目链接：Problem - 2050B - Codeforces

这个题的意思就是，对于给定的一个数组，对于任意的一个从2 - n-1的a[i]，都可以让a[i-1]  + 1 && a[i+1] - 1 || a[i-1] + 1 && a[i+1] -1，然后问你能不能通过任意次的这样的操作，使得所有的元素都相等，首先我们分析，这两个数一个加1一个减1，他们的总和还是不变的，所以在任意次的操作之后，这两个数是可以“平均分”的（即是可以相互弥补的）因为是中间隔着一个数，1和3可以相互弥补，3又可以和5相互弥补，那么是不是1,3,5三个数之间都可以相互弥补呢？同理，2,4,6等等这样的偶数位置的数也可以相互弥补，所以我们可以统计奇数位置上的数和偶数位置上的数，然后看他们是否能均分，然后再看均分之后的值相等不相等就行了。

// Problem: B. Transfusion
// Contest: Codeforces - Codeforces Round 991 (Div. 3)
// URL: https://codeforces.com/problemset/problem/2050/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int n;cin>>n;vector<int> a(n+5,0);for(int i=1;i<=n;i++) cin>>a[i];int an1 = 0, an2 = 0;for(int i=1;i<=n;i+=2) an1 += a[i];//统计奇数位置上的和for(int i=2;i<=n;i+=2) an2 += a[i];//统计偶数位置上的和int fm1 = n / 2;int fm2 = n / 2;//分别计算奇数和偶数的个数if(n & 1) fm1 ++;//如果n是奇数的话 奇数的个数++if(an1 % fm1 || an2 % fm2)//如果不能整除，那就不可能相等{NOreturn ;}an1 /= fm1;an2 /= fm2;//能整除了 就判断值是否相等if(an1 == an2) YESelse NO
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

C. Preparing for the Exam

题目链接：Problem - 2051C - Codeforces

这是一道很简单的模拟题，难点应该就是读懂题目意思了，大致的意思就是，给定你一个n，表示一共有n个问题，然后给定一个m，表示有m套卷子，然后再给定一个k，表示他现在会k道题，然后第二行分别给出你m套卷子的情况，m[i] = x表示除了第x道题其他的都在卷子上，第三行给定你k个数，表示他现在会哪些题，最后需要你判断对于每一套卷子，这套卷子上的题他是否全部都会。

分析很简单，因为每张卷子都有n-1道题，一共有n道题，而他会k道题，如果n-1 > k的话，也就是说在每一套卷子上都至少有两道题是他不会的，而卷子上又一定是n-1道题，所以至少有一道题是他不会而且还考到了的，所以这种情况下，他所有的卷子都无法通过考试，输出m个0就好了，接下来就是第二种情况：如果n-1刚好等于k，那么我们就对于每一套卷子都进行判断，如果他不会的题刚好没有考（正好等于m[i]）就是1，否则就是0，具体可以用一个bool类型的数组来表示这道题他会不会，最后一种情况就是n == k了，这种情况说明所有的题他都会，那么只需要输出m个1就行了。

// Problem: C. Preparing for the Exam
// Contest: Codeforces - Codeforces Round 995 (Div. 3)
// URL: https://codeforces.com/problemset/problem/2051/C
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int n,m,k;cin>>n>>m>>k;vector<int> a(m+1);for(int i=1;i<=m;i++) cin>>a[i];vector<bool> ok(n+1,false);for(int i=1;i<=k;i++){int x;cin>>x;ok[x] = true;//标记这道题是会的}string s;if(n > k + 1) //第一种情况{while(m--) cout<<"0";cout<<endl;return ;}if(n == k + 1)//第二种情况{for(int i=1;i<=m;i++) if(!ok[a[i]]) s += "1";else s += "0";cout<<s<<endl;return ;}while(m--) cout<<"1";//第三种情况cout<<endl;return ;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Crafting

题目链接：Problem - 2055B - Codeforces

这个题的意思就是，给你一个数组a，再给你一个数组b，然后数组a中的所有元素a[i]都要大于等于b[i]，对于数组a有一个操作：可以对a[i]加1，但是代价就是除了这个a[i]以外所有的数就都要减去一个1，问你最后可不可能实现。

其实这道题还是很有意思的，一开始看可能没有什么思路，可是仔细想想就能发现，如果存在两个位置的a[i]小于b[i]了，就一定不可能，因为你在给一个a[i]加的时候，另一个就会少，所以他俩一直互相消耗，最终还是不可能同时加，分析到这里，就还有一个情况了：如果只有一个位置的a[i]小于b[i]，那么我们就需要先计算他差几个，然后还需要计算所有的a[i] - b[i]取最小值，因为《短板效应》，看一下最小的差值能不能满足使得这一组a[i]加到b[i]，这样就已经将所有的情况判断完了。

// Problem: B. Crafting
// Contest: Codeforces - Codeforces Round 996 (Div. 2)
// URL: https://codeforces.com/problemset/problem/2055/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int n;cin>>n;vector<int> a(n+1),b(n+1);int num = inf;for(int i=1;i<=n;i++) cin>>a[i];int cha = 0;for(int i=1;i<=n;i++) cin>>b[i];int f = 0;for(int i=1;i<=n;i++){if(a[i] < b[i]){f ++;cha = max(cha,b[i] - a[i]);//不用max也可以，因为只有在f = 1的时候cha才有用}else num = min(num,a[i] - b[i]);}if(f >= 2) NO//超过一组就是NOelse if(f == 1 && cha > num) NO//一组但是短板过于短也是NOelse YES
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Gorilla and the Exam

题目链接：Problem - 2057B - Codeforces

这个问题的大致意思就是：对于给定的数组，你有一种操作，选取一个范围区间l - r，然后将这个区间内的所有的最小值都给删去，但是现在给你k次机会，每次都可以从数组中删去一个数，然后问题在最多删除k个数之后，数组中元素个数变为0所需要的操作次数是多少。

首先考虑的是贪心，因为要想以最少的操作次数删除所有的元素，我们每次选择的区间长度就是整个剩余的数组，这样才能保证一次性删除所有的同一个数，然后我们要分析这k次操作怎么样才能最优，我们要在最后的操作次数最少，我们就需要所剩数组中的元素类型个数最少，我们的删除的k个数就应该优先删去出现次数少的数，这样就能保证最后所剩余的元素类型最少了，代码如下：

// Problem: B. Gorilla and the Exam
// Contest: Codeforces - Hello 2025
// URL: https://codeforces.com/problemset/problem/2057/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int n,k;cin>>n>>k;vector<int> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];map<int,int> mp;for(int i=1;i<=n;i++) mp[a[i]] ++;//统计每一个元素所出现的次数int ans = mp.size();vector<int> arr;for(auto &i : mp) arr.push_back(i.se);sort(arr.begin(),arr.end());//将每个元素出现的次数进行从小到大排序for(auto &i : arr){if(k >= i)//优先减去出现次数少的{k -= i;ans --;}else break;}if(ans <= 0) ans = 1;//最后需要特判cout<<ans<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. MIN = GCD

题目链接：Problem - 2084B - Codeforces

这个是让一个数组内的元素分为两部分，让其中一部分取最小值，另一部分取GCD，然后问你有没有一种可能使得min = gcd。

首先分析，要想使最小值等于GCD，那么最小值我们是知道的，因为必须是所有元素中的最小值，只有这样才能保证min = gcd，gcd的值是不会超过gcd中所有的元素的，那么我们可以首先对数组进行排序，然后我们既要遍历所有的元素，只有在当前元素是最小值的倍数都情况下，我们才考虑将其放入GCD那一块中，而且GCD的值随着元素的增多只会小不会大，所以我们只需要不断计算GCD的值，当等于最小值的时候直接输出yes就行了。

// Problem: B. MIN = GCD
// Contest: Codeforces - Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/2084/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define ys cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
const int inf = 0x3f3f3f3f;void solve()
{int n;cin>>n;vector<int> a(n,0);for(int i=0;i<n;i++){cin>>a[i];}sort(a.begin(),a.end());int ans=0;bool f=0;for(int i=1;i<n;i++){if(a[i]%a[0]==0){if(f){ans = __gcd(ans,a[i]);}else{f=1;ans=a[i];}if(ans==a[0]){ysreturn;}}	}no
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Kevin and Geometry

题目链接：Problem - 2061B - Codeforces

这道题的题意很简单，就是从一堆木棍中找到四根木棍凑出一个等腰梯形，所以我们就直接用map存就行了（但是用unordered_map会被卡时间不知道为什么），如果有能拼成正方形或者长方形的，就直接输出，如果只有一组两个相等的边，我们就要对所有的木棍进行排序，找到相差最小的两根木根，然后和腰做对比，如果满足了cha < 2 * l就说明能构成等腰梯形了。找相差最小的可以用排序来代替双重循环。

// Problem: B. Kevin and Geometry
// Contest: Codeforces - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/2061/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f3f3f3f3f;void solve()
{map<int,int> mp;int n;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]] ++;}vector<int> to;for(auto &i : mp){if(i.se >= 4)//能拼成正方形{cout<<i.fi<<' '<<i.fi<<' '<<i.fi<<' '<<i.fi<<endl;return ;}if(i.se >= 2){to.push_back(i.fi);if(to.size() == 2)//能拼成长方形{cout<<to[0]<<' '<<to[0]<<' '<<to[1]<<' '<<to[1]<<endl;return ;}}}if(to.size() == 0)//没有一组相等的腰{cout<<"-1"<<endl;return ;}int l = to[0],r = l;int u,d,cnt = 0;for(int i=1;i<=n;i++){if(a[i] == l)//两个腰已经用过了，所以将这两个腰排除掉{cnt++;a[i] = 0;if(cnt == 2) break;}}sort(a.begin() + 1,a.end());//排序 方便找查找最小的两根for(int i=3;i<n;i++){int u = a[i],d = a[i+1];int cha = d - u;if(cha < 2 * l)//符合就输出{cout<<l<<' '<<r<<' '<<u<<' '<<d<<endl;return ;}}cout<<"-1"<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Pile Shuffling

题目链接：Problem - 2122B - Codeforces

这道题很有意思，大致题意很简单，让你找最小的操作次数，我们只需要在遍历的时候对a和c，b和d的大小进行判断就行了，如果a大于c了，就说明当前堆的0的个数是多余的，那么这时候肯定是有其他的堆的0的个数是缺失的，所以我们不需要管这个堆上的0放到哪里了，反正是取填补的需要的那一堆上去了，所以这时候的次数就是a-c，然后这时候需要将a更新成c了，然后判断b和d的大小关系，同理如果b大于d了，说明肯定是有一堆需要这个1的，而因为每次都只能从堆顶拿出来元素，所以我们要先将堆顶的0移到下面，再将1移出来，然后插入到需要堆的位置，因为可以随便插到一个位置，所需要的操作次数为a + b - d，最后累加就行了。

// Problem: B. Pile Shuffling
// Contest: Codeforces - Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/2122/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n;cin>>n;int cnt = 0;for(int i=1;i<=n;i++){int a,b,c,d;cin>>a>>b>>c>>d;if(a > c) cnt += a - c,a = c;if(b > d) cnt += a + b - d;}cout<<cnt<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Farmer John's Card Game

题目链接：Problem - 2060B - Codeforces

这道题的大致意思就是，对于n头牛，每个牛里面都有m张牌，然后问你有没有一种出牌的顺序，使得所有的牛按照顺序出牌之后牌的顺序也是从0到n * m - 1递增的。

这道题没什么说的，就先进行第一轮找出顺序，看这个顺序能不能符合之后的顺序就行了。

// Problem: B. Farmer John's Card Game
// Contest: Codeforces - Codeforces Round 998 (Div. 3)
// URL: https://codeforces.com/problemset/problem/2060/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n,m;cin>>n>>m;unordered_map<int,int> mp;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int x;cin>>x;mp[x] = i;//用map映射出来每一张牌在哪一头牛手里}}vector<int> ans(n,-1);for(int i=0;i<n;i++) ans[i] = mp[i];//先让所有的牛按照顺序出牌 确定牛的顺序int index = 0;for(int i=n;i<n*m;i++){if(i%n == 0) index = 0;//出完一轮了开始下一轮if(mp[i] != ans[index])//如果当前牌所在的牛的序号与当前出牌的牛的序号不一样 就直接-1{cout<<"-1"<<endl;return ;}index ++;}for(auto &i : ans) cout<<i<<' ';cout<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

D. Subtract Min Sort

题目链接：Problem - 2060D - Codeforces

这道题的题意很简单，就是对于给定的数组，从第一个到第n-1个，你都可以将两个数同时减去min(a[i],a[i + 1])，然后问你能不能通过这样的操作若干次，使得最后的数组非递减。

这也是贪心的思想，我们想让整个数组非递减，那么我们是不是就需要让前面的数都尽量小一点，那么此时我们就需要将所有的两两相邻的数都进行这个相减的操作，这样就能保证前面的数都尽可能的小，如果原来的两个数是递增的关系，他们同时减去一个数的话就还是递增的关系，所以每两个数都进行这个操作不会让原先递增的变为递减，最多是都成了0，那如果确确实实相减了还是递减的话，就直接是输出NO就行了。

// Problem: D. Subtract Min Sort
// Contest: Codeforces - Codeforces Round 998 (Div. 3)
// URL: https://codeforces.com/problemset/problem/2060/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<n;i++){int mi = min(a[i],a[i+1]);a[i] -= mi;a[i+1] -= mi;}for(int i=1;i<n;i++){if(a[i] > a[i+1]){cout<<"NO"<<endl;return ;}}cout<<"YES"<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Subsequence Update

题目链接：Problem - 2063B - Codeforces

这道题的题目意思就是给定的一个数组，你可以进行一次操作，选择任意数量的子序列（可以不连续），然后将他们进行顺序颠倒，最后问你通过这一次操作之后l到r的区间内的和最小是多少。

首先我们分析顺序颠倒所产生的具体影响，我们可以选择非连续的子序列，要想使区间内的和最小，我们就需要用区间以前的最小的数来代替区间内的数，顺序颠倒，说白了实质上就是在区间之前选择n个数，然后在区间内选n个数，颠倒位置之后就相当于是互换了位置，也就是说我们可以将区间之前的所有数中选出区间长度个最小值放入区间，同理区间右端也是这样，所以我们只需要对左右两端进行排序，分别选区间长度个数取最小值就行了。

// Problem: B. Subsequence Update
// Contest: Codeforces - Codeforces Round 1000 (Div. 2)
// URL: https://codeforces.com/problemset/problem/2063/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n,l,r;cin>>n>>l>>r;vector<int> a(n+1),b(n+1);for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) b[i] = a[i];sort(a.begin() + 1,a.begin() + r + 1);sort(b.begin()+l,b.end());int an1 = 0;for(int i=1;i<=r-l+1;i++) an1 += a[i];int an2 = 0;for(int i=l;i<=r;i++) an2 += b[i];cout<<min(an1,an2)<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Perfecto

题目链接：Problem - 2071B - Codeforces

// Problem: B. Perfecto
// Contest: Codeforces - Codeforces Round 1007 (Div. 2)
// URL: https://codeforces.com/problemset/problem/2071/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n;cin>>n;int x = (n+1) * n / 2;//元素总和x = sqrt(x);if(x * x == (n+1) * n / 2)//元素总和就是一个完全平方数的话就是-1了{cout<<"-1"<<endl;return ;}vector<int> a(n+1);for(int i=1;i<=n;i++) a[i] = i;int sum = 0;for(int i=1;i<=n;i++){sum += a[i];int s = sqrt(sum);if(s * s == sum)//如果加上当前的数变成了完全平方数了{sum -= a[i];//就不加这个数了sum += a[i+1];//改为加后面的数swap(a[i],a[i+1]);//那就要再之后考虑这个数了 所以要交换位置 //要注意的数一定要在计算sum之后再交换位置！！！}}for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. Vicious Labyrinth

题目链接：Problem - 2078B - Codeforces

这道题也是一个思维题，可以对k的就行进行判断，如果是奇数的话，就可以让1 - n-1都传送到n 然后n传送到n-1，否则就让1 - n-2都传送到n-1 n-1传送到n,n传送到n-1就行了。

// Problem: B. Vicious Labyrinth
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/problemset/problem/2078/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n,k;cin>>n>>k;if(k&1)//必须传送奇数次的话 就让1 - n-1都传送到n 然后n传送到n-1即可{for(int i=1;i<n;i++) cout<<n<<' ';cout<<n-1<<endl;}else//必须传送偶数次的话 就让1 - n-2都传送到n-1 n-1传送到n,n传送到n-1{for(int i=1;i<n-1;i++) cout<<n-1<<' ';cout<<n<<' ';cout<<n-1<<endl;}
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
}