网站图片轮播怎么做的,建筑工程有限公司电话,wordpress主题怎么删除边栏,商丘网站建设这次比赛也是比较吃亏的#xff0c;做题顺序出错了#xff0c;先做的第三个#xff0c;错在第三个数据点之后#xff0c;才做的第二个#xff08;因为当时有个地方没检查出来#xff09;所以这次比赛还是一如既往地打拉了
那么就来发一下题解吧
A. Array Divisibility …这次比赛也是比较吃亏的做题顺序出错了先做的第三个错在第三个数据点之后才做的第二个因为当时有个地方没检查出来所以这次比赛还是一如既往地打拉了
那么就来发一下题解吧
A. Array Divisibility 题意对于1kn对于每个k其倍数下标之和一定为k的倍数
思路直接从1赋值到n就行也是水题一个
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n;
signed main()
{cint;while(t--){cinn;for(int i1;in;i){couti ;}cout\n;}return 0;
} B. Corner Twist 题意就是给你两个数组问你两个数组能否按照题上所说的方法相互转换得到
思路将整个大矩阵拆成2*2的小矩阵然后每次只要让左上角那个和下面的变成一样就可以然后我们最后原本只需要检查最后一列和最后一行是否相同就可以ps我写的是逐一比较因为比较好写错了一次是因为比较的时候内层循环写成n了
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n,m;
char a[505][505];
char b[505][505];
signed main()
{cint;while(t--){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}for(int i1;in;i){for(int j1;jm;j){cinb[i][j];}}for(int i1;in-1;i){for(int j1;jm-1;j){int cha ((b[i][j]-0)-(a[i][j]-0)3)%3;if(cha1){a[i][j](a[i][j]1)%30;a[i1][j1](a[i1][j1]1)%30;a[i1][j](a[i1][j]2)%30;a[i][j1](a[i][j1]2)%30;}else if(cha2){a[i][j](a[i][j]2)%30;a[i1][j1](a[i1][j1]2)%30;a[i1][j](a[i1][j]1)%30;a[i][j1](a[i][j1]1)%30;}}}int flag1;for(int i1;in;i){for(int j1;jm;j){if(a[i][j]b[i][j]){continue;}elseflag0;}}if(flag0){coutNO\n;}else{coutYES\n;}}return 0;
} C. Have Your Cake and Eat It Too 题意就说有一个蛋糕 被分成了许多块然后三个人对每部分的蛋糕都有一个自己的价值但是所有块的价值总和是一定的然后问你如何划分这个区间才能满足每个区间都大于(tot2)/3
思路对六种情况分别贪心即可先让两边的取到比sum大的位置然后再看中间的是否比sum大是的话就直接输出如果都不满足最后就只能输出-1了
#includebits/stdc.h
using namespace std;
#define int long long
signed main()
{int t;cint;while(t--){int n;cin n;int a[n1], b[n1], c[n1];int sum 0;for(int i 1;in;i){cin a[i];sum a[i];}sum (sum2)/3;//题中说了上限除法 for(int i 1;in;i){cin b[i];}for(int i 1;in;i){cin c[i];}vectorint p1(n5), p2(n5), p3(n5);//正序前缀和 vectorint s1(n5), s2(n5), s3(n5);//倒序前缀和 for(int i 1; i n; i){p1[i] p1[i-1] a[i];p2[i] p2[i-1] b[i];p3[i] p3[i-1] c[i];}for(int i n; i 1; i--){s1[i] s1[i1] a[i];s2[i] s2[i1] b[i];s3[i] s3[i1] c[i];}//a b c int i 1, j n;while(p1[i-1] sum i n){i;}while(s3[j1] sum j 1){j--;}if(i j p2[j]-p2[i-1] sum){cout 1 i-1 i j j1 n endl;continue;}// a c bi 1, j n;while(p1[i-1] sum i n){i;}while(s2[j1] sum j 1){j--;}if(i j p3[j]-p3[i-1] sum){cout 1 i-1 j1 n i j endl;continue;}// b c ai 1, j n;while(p2[i-1] sum i n){i;}while(s1[j1] sum j 1){j--;}if(i j p3[j]-p3[i-1] sum){cout j1 n 1 i-1 i j endl;continue;}// b a ci 1, j n;while(p2[i-1] sum i n){i;}while(s3[j1] sum j 1){j--;}if(i j p1[j]-p1[i-1] sum){cout i j 1 i-1 j1 n endl;continue;}// c a bi 1, j n;while(p3[i-1] sum i n){i;}while(s2[j1] sum j 1){j--;}if(i j p1[j]-p1[i-1] sum){cout i j j1 n 1 i-1 endl;continue;}// c b ai 1, j n;while(p3[i-1] sum i n){i;}while(s1[j1] sum j 1){j--;}if(i j p2[j]-p2[i-1] sum){cout j1 n i j 1 i-1 endl;continue;}cout -1 endl;}return 0;
}
D. Swap Dilemma 题意就是说给你两个数组然后每次再a数组选两个坐标b数组选两个坐标然后各自再各自的数组交换然后问你最后两个数组能不能变成一样的
思路这题我想到了两种做法
逆序对法
1逆序对的方法众所周知在大学有一门神奇的科目叫做线性代数线性代数里面讲过一个东西叫做逆序对只有逆序对的个数为同一奇偶性才有可能相同因为ab数组每次都要变换一次所以他们的奇偶性一定是都会在每一次变化所以我们需要统计奇偶性然后来判断当然了在之前还需要判断元素种类是否相同如果个数不同一定为no
#includebits/stdc.h
using namespace std;
#define int long long
int mergeSort(vectorint nums, int left, int right)
{if (left right) {return 0;}int mid left (right - left) / 2;int count mergeSort(nums, left, mid) mergeSort(nums, mid 1, right);vectorint tmp(right - left 1);int i left, j mid 1, k 0;while (i mid j right) {if (nums[i] nums[j]) {tmp[k] nums[i];} else {tmp[k] nums[j];count mid - i 1; // 计算逆序数}}while (i mid) {tmp[k] nums[i];}while (j right) {tmp[k] nums[j];}for (int p 0; p tmp.size(); p) {nums[left p] tmp[p];}return count;
}int solve(vectorint nums)
{if (nums.size() 1) {return 0;}return mergeSort(nums, 0, nums.size() - 1);
}void solve()
{mapint,int mp;int n;cin n;vectorint a(n2);vectorint b(n2);for (int i1;in;i) cin a[i];for (int i1;in;i){cin b[i];mp[b[i]]i;}for(int i1;in;i){if(mp.count(a[i])0){coutNO\n;return ;}}int ans1solve(a),ans2solve(b);if (ans1%2 ans2%2) cout YES\n;else cout NO\n;
}
signed main()
{int t;cin t;while (t--) solve();return 0;
} 交换次数法
2那么来讲另一种比较简单的方法交换次数来判断因为题目上所说每次两个数组都要交换那么我们就只交换一个然后统计变成另一个的次数为多少是偶数就是yes是奇数就是no
当然了在之前也是需要判断种类是否相同的
#include bits/stdc.h
using namespace std;
#define int long long
int a[200005], b[200005];
mapint, int mp;
void solve()
{mp.clear();int n;cin n;for (int i1;in;i) cin a[i];for (int i1;in;i){cin b[i];mp[b[i]]i;}int ans 0;for (int i1;in;i){if (b[i] a[i]) continue;if (mp.count(a[i]) 0){cout NO\n;return;}int pmp[a[i]];swap(b[i],b[p]);mp[b[i]]i;mp[b[p]]p;ans1; }if (ans%2 0) cout YES\n;else cout NO\n;
}
signed main()
{int t;cin t;while (t--) solve();return 0;
}
