网站建设ftp,最好的wordpress 网站,配置无法运行wordpress,html静态网页源代码Codeforces986B [Petr and Permutations] 看到两个随机的swap次数#xff0c;很容易想到跟奇偶性有关。然后就凉了。赛后思考了一下#xff0c;这个思路应该没问题#xff0c;那就需要考虑swap的奇偶性与排列的关系。因此#xff0c;我们考虑如何把两个不相邻数的swap… Codeforces986B [Petr and Permutations] 看到两个随机的swap次数很容易想到跟奇偶性有关。然后就凉了。赛后思考了一下这个思路应该没问题那就需要考虑swap的奇偶性与排列的关系。因此我们考虑如何把两个不相邻数的swap转换为相邻的数的swap以便于利用逆序数进行推导。假设swap(a[x],a[y])可以转化为把a[y]向左移动一直换到x这个位置再把现在位于x1这个位置上的a[x]向右移动一直换到y这个位置。显然这个过程一共做了(y-x) (y-(x1)) 2*(y-x)-1次交换每次交换逆序数的变化的绝对值为1那么对于一次交换逆序数的变换一定为奇数。那么显然一个排列的初始逆序数都为0如果最终的逆序数为奇数则一定进行了奇数次交换否则进行了偶数次交换那结论就很明显了只要最终的逆序数与某种方式swap次数奇偶性一致答案就是这种方式。看别人代码发现不用求逆序数只要求出一种交换方案的交换次数再判断奇偶性就行了复杂度比较优秀用上面的结论也很好证明我这里还是用的逆序数的方法可以过。 #include cstdio
typedef long long ll;
const int N 1e6 100;
using namespace std;
int n,a[N],ans0;
int B[N];
int ask(int x){int ans0;for(int ix;i;i-(i(-i)))ansB[i];return ans;
}
void add(int x,int v) {for(int ix;in;i(i(-i)))B[i]v;
}
int main() {scanf(%d,n);for(int i1;in;i) {scanf(%d,a[i]);ans(ask(n)-ask(a[i]));add(a[i],1);}if((ans1)((3*n)1))puts(Petr);else puts(Um_nik);return 0;
} Codeforces986C [AND Graph] 一个01串与它有边的01串就是它的补集的所有子集。对于m个01串暴力计算它的补集的所有子集如果某个子集出现在这m个串里就继续暴力计算这个数所有子集的补集。状态数只有2^22搜索的复杂度有保证。为啥想不到 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
typedef long long ll;
const int N (123);
using namespace std;
int n,m,a[N],vis[N],in[N],ans;
void dfs(int s) {if(vis[s])return;vis[s]1;if(in[s])dfs((1n)-1-s);rep(i,0,n-1)if(s(1i))dfs(s^(1i));
}
int main() {scanf(%d%d,n,m);rep(i,1,m)scanf(%d,a[i]),in[a[i]]1;rep(i,1,m)if(!vis[a[i]])dfs((1n)-1-a[i]),ans;printf(%d\n,ans);return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9112520.html
