这次打的不错,除了B少了break fst了,其他还好,分享一下我的做法
Codeforces Round #553 (Div. 2)

A Maxim and Biology

A题 手速还ok

B Dima and a Bad XOR

B题可以说是很坑了
题意:给定一个 n m n*m nm 的矩阵,在每一行都取一个数,问是否存在一种方法使得异或和不为0
分析: 我是dp做的,其他人有贪心的方法,我的思路就是题目给定1024,我们可以将每一个都拆分成10个点,如果存在一个点的异或和不为0,那么结果就不为0,我们可以采取背包的思想来做, f [ s t e p ] [ i ] [ j ] = t r u e f[step][i][j] = true f[step][i][j]=true,代表我们可以将第step位,选取前i个,异或和为j,于是如果存在 f [ s t e p ] [ i ] [ 1 ] = t r u e f[step][i][1] = true f[step][i][1]=true,那么就存在一个可行解,然后按照背包回退的原理求出一种方案

const int  maxn = 500+10;

bool vis[maxn][1025];
int a[maxn][maxn];
int ans[maxn];
bool f[maxn][2];
int main(void)
{
	int n,m;cin>>n>>m;
	for(int i = 1;i <= n; ++i)
		for(int j = 1;j <= m;++j)
			scanf("%d",&a[i][j]);
	for(int step = 0;step < 10; ++step){
		me(f);
		f[0][0] = 1;
		for(int i = 1;i <= n; ++i){
			for(int j = 1;j <= m; ++j){
				for(int k = 0;k < 2; ++k){
					f[i][k] |= f[i-1][k^((a[i][j]>>step)&1)];
				}
			}
		}
		if(f[n][1]){
			int now = 1;
			for(int i = n;i >= 1; --i){
				for(int j = 1;j <= m; ++j){
					if(f[i-1][now^((a[i][j]>>step)&1)]){
						ans[i] = j;
						now ^= ((a[i][j]>>step)&1);
						break;
					}
				}
			}
			cout<<"TAK"<<endl;
			for(int i=  1;i <= n; ++i)
				cout<<ans[i]<<" ";
			return 0;
		}
	}
	cout<<"NIE"<<endl;
   return 0;
}

C Problem for Nazar

题意:这个题意有点复杂
分析:直接求前n个有多少个奇数多少个偶数就ok了
前i个偶数的和为 i ( i + 1 ) i*(i+1) i(i+1)
前i个奇数的和为 i i i*i ii;

LL solve(LL n){
	if(n <= 0) return 0;
	bool flag = 1;
	LL t = 1;
	LL sum1 = 0;
	LL sum2 = 0;
	for(LL i = 0;i < n; ){
		LL nxt = min(i + t,n);
		if(flag)
			sum1 += (nxt-i);
		else
			sum2 += (nxt-i);
		t *= 2;
		i = nxt;
		flag ^= 1;
	}
	// cout<<sum1<<" "<<sum2<<endl;
	LL ans = sum2%mod*((sum2+1)%mod)%mod+sum1%mod*(sum1%mod)%mod;
	return ans%mod;
}
int main(void)
{
    LL l,r;cin>>l>>r;
    cout<<((solve(r)-solve(l-1))%mod+mod)%mod<<endl;
   	return 0;
}

D - Stas and the Queue at the Buffet

题意:给定 a i , b i a_i,b_i ai,bi,要求重排使得 a i ( j 1 ) + b i ( n j ) a_i \cdot (j-1) + b_i \cdot (n-j) ai(j1)+bi(nj)最小
分析: 直接按照 a i b i a_i-b_i aibi排序即可

typedef pair<LL,LL> P;
const int maxn = 1e5+10;
LL a[maxn],b[maxn];
P p[maxn];
bool cmp(const P &a,const P &b){

	return a.FI - a.SE > b.FI - b.SE;
}
int main(void)
{
	int n;cin>>n;
	for(int i = 1;i <= n; ++i)
		scanf("%lld%lld",&a[i],&b[i]),p[i] = P(a[i],b[i]);	
	sort(p+1,p+n+1,cmp);

	// reverse(p+1,p+n+1);
	LL ans = 0;
	for(int i =1;i <= n; ++i)
		{
			ans += p[i].FI*(i-1)+p[i].SE*(n-i);
			// cout<<ans<<endl;
			// cout<<p[i].FI<<" "<<p[i].SE<<endl;
		}
	cout<<ans<<endl;

    

   return 0;
}

E - Number of Components

题意:给定一条链,链上每个点都有一个权值,定义 f ( l , r ) f(l,r) f(l,r) 留下权值 [ l , r ] [l,r] [l,r]的节点,联通块的数量,求 l = 1 n r = l n f ( l , r ) \sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) l=1nr=lnf(l,r)
分析:我们直接一个点可以做多少个节点的区间左端点
如果 a [ i ] &gt; a [ i 1 ] a[i] &gt; a[i-1] a[i]>a[i1] 就是 ( a [ i ] a [ i 1 ] ) ( n a [ i ] + 1 ) , (a[i]-a[i-1])*(n-a[i]+1), (a[i]a[i1])(na[i]+1),
如果 a [ i ] &lt; a [ i 1 ] a[i] &lt; a[i-1] a[i]<a[i1] 就是 ( a [ i 1 ] a [ i ] ) a [ i ] (a[i-1]-a[i])*a[i] (a[i1]a[i])a[i]

有几个同***系我或者评论E题看不懂,我就再更一下,希望大家能通过我的博客学到
我们就通过样例举例

  1. 首先你需要明白我们面对的不是一棵树,其实就是一个链
  2. 我给出的公式可能不太明白
    我们模拟一下样例或许就比较清晰了
    比方说第一个数2,他作为一个联通块的左端点有四种情况
    [ l , r ] = [ 1 , 2 ] , [ 1 , 3 ] , [ 2 , 2 ] , [ 2 , 3 ] [l,r] = [1,2],[1,3],[2,2],[2,3] [l,r]=[1,2],[1,3],[2,2],[2,3]
    发现什么规律了吗,就是这个区间的l 必须小于等于 a [ i ] a[i] a[i],区间额r必须大于等于 a [ i ] a[i] a[i],我们将他前面的数当成0,于是我们有第一个位置的贡献 ( 2 0 ) ( 3 2 + 1 ) (2-0)*(3-2+1) (20)(32+1)
    对于第二个数1,他作为区间左端点的贡献有减去2,作为区间左端点的贡献的情况
    所以 r &lt; 2 r &lt; 2 r<2,本身的值为1,所以区间只能是
    [ l , r ] = [ 1 , 1 ] [l,r] = [1,1] [l,r]=[1,1]
    对于第三个数3,他作为区间左端点的贡献需要减去1作为左端点的贡献
    l &gt; 1 l &gt; 1 l>1,同时自身的限制, r >= 3
    [ 2 , 3 ] , [ 3 , 3 ] [2,3],[3,3] [2,3],[3,3]
    是不是就是 ( a [ i ] a [ i 1 ] ) ( n a [ i ] + 1 ) = ( 3 1 ) ( 3 3 + 1 ) = 2 (a[i]-a[i-1])*(n-a[i]+1) = (3-1)*(3-3+1) = 2 (a[i]a[i1])(na[i]+1)=(31)(33+1)=2,
    综上,我们发现每个点的贡献然后计算他可能在那些区间存在,减去它左边点作为区间左端点的情况
const int maxn = 1e5+10;
LL a[maxn];
int main(void)
{
	LL ans = 0;
	int n;cin>>n;
	LL  M = 0;
	LL cnt =0;
	for(int i = 1;i <= n; ++i){
		scanf("%lld",&a[i]); 
		if(a[i] > M)
			cnt = 1,M = a[i];
		else if(a[i] != a[i-1] && a[i] == M)
			cnt++;
		LL t = 0;
		if(a[i] > a[i-1])
			t = (a[i]-a[i-1])*(n-a[i]+1);
		else if(a[i] != a[i-1])
			t = abs(a[i]-a[i-1])*(a[i]);
		// t = t*(t+1)/2;
		// cout<<t<<endl;
		ans +=t;
	}    
	// ans += (n-M)*cnt;


	cout<<ans<<endl;

   return 0;
}

F - Sonya and Informatics

题意: 给定一个01串,每次取出一组 ( l , r ) 1 l &lt; r n (l,r) 1 \leq l &lt; r \leq n (l,r)1l<rn,交换 s [ l ] , s [ r ] s[l],s[r] s[l],s[r],,求经过k次之后变成升序的概率是多大?
分析:现在我们知道有 s n sn sn个1和 n s n n-sn nsn个0,我们还知道多少个1在它的位置了,
共有四种0和1,
1 在规定位置,不在规定位置
0 在规定位置 不在规定位置
每一次交换可能引起的变化有三种:不变,+1,-1
目的是1全在规定位置,按照取出l,r列出转移矩阵就ok了

const int maxn = 100+10;
int n;
struct Matrix{
	int n,m;
	Matrix(int nn = 1,int mm = 1):n(nn),m(mm){ memset(a,0,sizeof(a));};
	long long a[maxn][maxn];
};
// void print(const Matrix &a)
// {
// for(int i = 1;i <= a.n; ++i,cout<<endl)
// for(int j= 1;j <= a.m; ++j)
// cout<<a.a[i][j]<<" ";
// }
Matrix operator*(Matrix a,Matrix b)
{
	Matrix c(a.n,b.m);
	for(int i = 0;i <= a.n; ++i)
	{
		for(int j = 0;j <= b.m; ++j)
		{
			for(int k = 0;k <= a.m; ++k)
			{
				c.a[i][j] += a.a[i][k] * b.a[k][j];
				c.a[i][j] %= mod;
			}
		}
	}
// print(c);
	return c;
}
int  ar[maxn];
Matrix ans,fac;
int main(void)
{
    int n,k;
    cin>>n>>k;
    rep(i,0,n) cin>>ar[i];//,cout<<ar[i];
    int sn = 0;
    rep(i,0,n) sn += ar[i]==1;
    int now = 0;
    for(int i = n-sn;i < n;++i)
    	now += ar[i]==1;
    // cout<<now<<endl;
    // cout<<sn<<endl;
     ans.n = ans.m = fac.n = fac.m = sn;
    ans.a[0][now] = 1;
    for(int i = 0;i <= sn; ++i){
    	// 四种情况 1 :i,sn-i
    	// 0 :sn-i,n-i-sn+i-sn+i = n-2*sn+i
    	fac.a[i][i] = n*(n-1)/2-(sn-i)*(sn-i)-i*(n-2*sn+i);// 保持原状
    	if(i+1<=sn)
    		fac.a[i][i+1] = (sn-i)*(sn-i);// 加1
    	if(i)
    		fac.a[i][i-1] = i*(n-2*sn+i); // 减1
    }
   
    LL K = k;
    while(k){
    	if(k&1)
    		ans = ans*fac;
    	fac = fac*fac;
    	k >>= 1;
    }
    // cout<<ans.a[0][sn]<<endl;
    cout<<ans.a[0][sn]*qpow(qpow(n*(n-1)/2,K),mod-2)%mod<<endl;



   return 0;
}