c2c网站免费建设,东莞建设质监网站,固原建设厅官方网站,网站建设相对应的税收分类是Codeforces Round 853 (Div. 2)
C. Serval and Toxels Arrays
思路#xff1a;
求任意两个组合的元素个数。
注意到#xff0c;其实每个元素都是独立的。他在任意组合的出现情况组成的贡献是可以分开讨论的。我们讨论元素x。假设x在m1个数组中出现了cnt次#xff08;一个…Codeforces Round 853 (Div. 2)
C. Serval and Toxels Arrays
思路
求任意两个组合的元素个数。
注意到其实每个元素都是独立的。他在任意组合的出现情况组成的贡献是可以分开讨论的。我们讨论元素x。假设x在m1个数组中出现了cnt次一个数组最多只有一个x。那么对于任意两个数组可能出现的情况有 同时有x这样的组合是C2cnt)贡献1只有一个有x这样的组合是cnt*(m1-cnt)贡献1都没有x不用讨论贡献0我们把每个数都分别这样讨论就是答案。
#include bits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 4e5 10;int a[N];
int cnt[N];
int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin t;while (t--){int n, m;cin n m;for (int i 0; i n m; i)cnt[i] 0;for (int i 1; i n; i){cin a[i];cnt[a[i]] m 1; //如果一个数没被修改他会一直出现共m1次}int p, v;for (int i 1; i m; i){cin p v;cnt[a[p]] - m - i 1; //被修改的数后面都不会再出现了除非再给一次cnt[v] m - i 1; //新的数后面都会出现直到被修改没a[p] v;}ll ans 0;for (int i 1; i n m; i)ans (ll)cnt[i] * (cnt[i] - 1) / 2 (ll)cnt[i] * (m 1 - cnt[i]);cout ans endl;}return 0;
}
D. Serval and Shift-Shift-Shift
思路
看数据1e3说明我们可以进行复杂度为ON^2)的操作首先只要a至少存在一个1我可以用1产生任何值按位一位一位操作可以把他们变成想要的1或者0除了0因为要求位移至少为1所以不能消去自己当我们a的最高位1右区间需要1或者0时我们可以把最高位移动到那里修改他这个操作遍历右区间我们每次操作因为最高位1左边都是0所以不会对操作位左边产生影响。而操作位右边有影响没事我会一位一位向右过去修改。修改左区间同理找最小位1不断左移修改左区间不能还是从高位修改到低位我们这次是利用不影响右区间左区间等下会修改。两者相反。最后注意到ab要么同时为0要么同时不为0a为0无法变成非0a不为0无法变成0
#include bits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 2e3 10;bool a[N], b[N], c[N];
int ans[N];void mysolve()
{int n;string a1, b1;cin n a1 b1;if (a1 b1){cout 0 endl;return;}int cnta 0, cntb 0; //记录啊a与b1的个数int cnt 0; //操作数for (int i 0; i n; i){a[i] a1[i] - 0, b[i] b1[i] - 0;if (a[i])cnta;if (b[i])cntb;}//同时非0if (cnta cntb){int ha n, hb n; //记录a与b的最高位1for (int i 0; i n; i)if (a[i]){ha i;break;}for (int i 0; i n; i)if (b[i]){hb i;break;}//修改b最高位1及往右的区间for (int i hb; i n; i){if (a[i] ! b[i]){int tmp i - ha; //表示位移ans[cnt] ha - i;//先记录后面ha可能更新memcpy(c, a, sizeof(a)); //不能直接a数组间去异或途中会修改a的for (int j i; j n; j){if (j - tmp n)break; //越界后面都是异或0了a[j] ^ c[j - tmp];if (a[j])ha min(ha, j); //hb大于ha时可能更新ha}}}if (ha hb) //如果ha小于注意越高位越小不是大于那么需要把hb前面的1去掉{int la 0; //a的最低位1for (int i n - 1; i 0; --i)if (a[i]){la i;break;}for (int i hb - 1; i 0; --i) //往左更新{if (a[i]) //是1就删{int tmp i - la;ans[cnt] la - i;memcpy(c, a, sizeof(a));for (int j i; j 0; --j){if (j - tmp 0)break;a[j] ^ c[j - tmp];}}}}cout cnt endl;for (int i 1; i cnt; i)cout ans[i] ;cout endl;}else cout -1 endl;
}int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin t;while (t--){mysolve();}return 0;
}
