技術文章 » Codeforces Round #663 (Div. 2) A-D 題解

Codeforces Round #663 (Div. 2) A-D 題解

2020-08-10 11:56:49

圖片好像掛了，不過都是題面，晚上修復

A. Suborrays

題目鏈接

題目原文

[外連圖片轉存失敗,源站可能有防盜鏈機制 機製,建議將圖片儲存下來直接上傳(img-qsnL4Fyp-1597031714049)(https://s3.ap-northeast-1.wasabisys.com/img.tw511.com/202008/1391A4oqzejnfybt.jpg)]

題目大意

如果存在一個排列，對於其任意的連續子序列pi…pjp_i \dots p_j都滿足pi  OR  pi+1  OR  …  OR  pj⩾j−i+1p_i \;OR \;p_{i+1} \;OR \;\dots \;OR \;p_j \geqslant j-i+1，則稱這個排列爲好排列。現在請輸出任意長度爲n的好排列。

解題思路

顯然直接按從小到大輸出一定能滿足要求

解法

直接輸出1  2  3  4  …  n1 \; 2 \; 3 \; 4 \; \dots \; n

程式碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n,a[maxn];
int main()
{
 	#ifdef lemon
	freopen("A.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) printf("%d ",i);
/*		for(int i=1;i<=n;i++)
		{
			for(int j=i;j<=n;j++)
			{
				int temp=0;
				for(int p=i;p<=j;p++) temp|=p;
				if(temp<j-i+1) printf("NO\n");
			}
		}*/
		printf("\n");
	}
	return 0;
}

B. Fix You

題目鏈接

題目原文

[外連圖片轉存失敗,源站可能有防盜鏈機制 機製,建議將圖片儲存下來直接上傳(img-UIbC5og0-1597031714056)(https://s3.ap-northeast-1.wasabisys.com/img.tw511.com/202008/1391B0kk3vbwuhex.jpg)]

題目大意

給出n行m列的矩陣，每個格子的值是’R’或者’D’。當移動到一個值爲’R’的格子，那麼會自動向右移動一格；當移動到一個值爲’D’的格子，那麼會自動向下移動一格。求至少修改多少個格子的值，能夠滿足「無論起始位置在哪，中途不能移動到邊界外，並且最終都能到達最右下角的格子。

解題思路

我們發現’R’和’D’都是單調的，也就是說不會往回走，大體上的趨勢一定是向右下角走的，我們只需要考慮是否會移出邊界。

  • 判斷第n行每一列的值是否爲’R’，如果不是，則必須修改，否則會移出邊界。
  • 判斷第m列每一列的值是否爲’D’，如果不是，則必須修改，否則會移出邊界。

解法

答案即爲第n行格子值爲’D’的數量和第m列格子值爲’R’的數量之和。

程式碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n,m,a[105][105];
char str[maxn];
int main()
{
 	#ifdef lemon
	freopen("B.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%s",str+1);
			for(int j=1;j<=m;j++)
				if(str[j]=='R') a[i][j]=0;
				else a[i][j]=1; 
		}
		int ans=0;
		for(int i=1;i<=n-1;i++) if(!a[i][m]) ans++;
		for(int i=1;i<=m-1;i++) if(a[n][i]) ans++;
		printf("%d\n",ans);
	}
	return 0;
}

C. Cyclic Permutations

題目鏈接

題目原文

[外連圖片轉存失敗,源站可能有防盜鏈機制 機製,建議將圖片儲存下來直接上傳(img-eJDQ74EM-1597031714058)(https://s3.ap-northeast-1.wasabisys.com/img.tw511.com/202008/1391Cxeurw5t1vhu.jpg)]

題目大意

語言表達能力比較差，敘述上存在困難，直接看原文吧……那兩個條件就是與最近的大於它的下標連邊。

解題思路

考慮i<j<ki<j<k，那麼我們發現只有ai>aj<aka_i>a_j<a_k能夠構成簡單環（此時ii與jj連邊，jj與kk連邊，ii與kk連邊）。因爲題目只需要滿足存在一個簡單環就行了，那就是隻需要存在一個子序列（不一定連續）滿足這個條件的就可以。

最開始嘗試去用排列組合的方法直接算，後來發現比較困難，有重複情況。然後後來想到可以用總方案數-不滿足要求的方案數。

顯然總方案數爲n!，那麼現在考慮不滿足要求的方案數。前面說到只要存在一個小的在中間，兩邊存在兩個比它大的就行。那麼我們就考慮最大的數，也就是n的位置。

  • 將n放第1個位置，左邊放0個數，右邊放n-1個數，且順序必須是從大到小，所以方案數爲C(n-1,0)
  • 將n放第2個位置，左邊放1個數（從n-1個數中選1個），右邊放n-2個數，且兩邊順序必須是從n的位置開始，向兩邊從大到小排列（合唱隊形），所以方案數爲C(n-1,1)
  • 將n放第3個位置，左邊放2個數（從n-1個數中選2個），右邊放n-3個數，且兩邊順序必須是從n的位置開始，向兩邊從大到小排列（合唱隊形），所以方案數爲C(n-1,2)
  • 將n放第n個位置，左邊放n-1個數（從n-1個數中選n-1個），右邊放0個數，且兩邊順序必須是從n的位置開始，向兩邊從大到小排列（合唱隊形），所以方案數爲C(n-1,n-1)

所以不合法的方案數爲∑i=0n−1(n−1i)=2n−1\sum\limits_{i=0}^{n-1}\dbinom{n-1}{i} = 2^{n-1}

解法

答案即爲n!−2n−1n!-2^{n-1}

程式碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000005;
const long long mod=1e9+7;
long long fac[maxn];
long long poww(long long x,long long k)
{
	long long ans=1;
	while(k)
	{
		if(k&1) ans=(ans*x)%mod;
		x=(x*x)%mod;
		k>>=1;
	}
	return ans;
}
int main()
{
 	#ifdef lemon
	freopen("C.txt","r",stdin);
	#endif
	long long n;
	scanf("%lld",&n);
	long long ans=0;
	fac[0]=fac[1]=1;
	for(long long i=2;i<=n;i++) fac[i]=(fac[i-1]*i)%mod;
	ans=fac[n];
	ans=ans-poww(2ll,n-1);
	ans=(ans%mod+mod)%mod;
	printf("%lld\n",ans);
	return 0;
}

D. 505

題目鏈接

題目原文

[外連圖片轉存失敗,源站可能有防盜鏈機制 機製,建議將圖片儲存下來直接上傳(img-XtoaP9wi-1597031714061)(https://s3.ap-northeast-1.wasabisys.com/img.tw511.com/202008/1391D2o2peq3twoq.jpg)]

題目大意

如果一個二進制矩陣是good的，那麼它的所有邊長爲偶數的子矩陣中1的個數都是奇數個。
給出n行m列的矩陣，求修改多少次矩陣中的值能夠使這個矩陣變爲good的。如果不存在修改方案滿足要求，輸出-1。

解題思路

如果n1||m1，那麼沒有邊長爲偶數的子矩陣，輸出0
如果n>=4&&m>=4，那麼考慮兩個連續的2x2的矩陣。如果這兩個連續的2x2矩陣都滿足要求，也就是說這兩個連續的矩陣中1的個數都是奇數，那麼這兩個矩陣合起來的2x4的矩陣中1的個數就爲偶數了。所以n>=4&&m>=4一定不存在合法的矩陣，也就是無論怎麼修改都不能滿足要求，所以輸出-1

現在n就只能是2或3了，考慮動態規劃。f[i][j]表示第i列的狀態爲j，j爲3位二進制，表示這一列的3位分別爲0或者1。那麼我們可以列舉這一列的狀態和上一列的狀態進行轉移。
假設這一列原來的狀態是now（輸入的狀態），列舉的狀態是j，上一列的狀態是p。如果j和p滿足要求，那麼我們就可以進行轉移，而滿足的要求爲這相鄰的兩列所有長度爲偶數的子矩陣的1的個數爲奇數，這裏預處理一下就好（最大也就是3x2的矩陣）。

解法

轉移方程f[i][j]=min(f[i][j],f[i-1][p]+(now^j)中1的個數);
now^j中1的個數即爲需要修改這一列的數的個數。

程式碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int maxn=1000005;
int n,m,ans=0x7f7f7f7f;
int a[4][maxn],f[maxn][8];
bool ok[8][8]={false};
int calc(int x)
{
	int ans=0;
	while(x)
	{
		if(x&1) ans++;
		x>>=1;
	}
	return ans;
}
int main()
{
 	#ifdef lemon
//	freopen("D.txt","r",stdin);
	#endif
	scanf("%d%d",&n,&m);
	if(n>=4&&m>=4) return printf("-1\n"),0;
	if(n==1||m==1) return printf("0\n"),0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) scanf("%1d",&a[i][j]);
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<8;j++)
		{
			int t[3];
			t[0]=t[1]=t[2]=0;
			for(int p=0;p<n;p++)
			{
				if((1<<p)&i) t[p]++;
				if((1<<p)&j) t[p]++;
			}
			bool flag=true;
			for(int p=0;p<n-1;p++)
			{
				if(!((t[p]+t[p+1])&1)) flag=false;
			}
			if(flag) ok[i][j]=true;
		}
	}
	memset(f,0x7f7f7f7f,sizeof(f));
	for(int i=0;i<8;i++) f[0][i]=0;
	for(int i=1;i<=m;i++)
	{
		int now=a[1][i]+a[2][i]*2+a[3][i]*4;
		for(int j=0;j<8;j++)
		{
			for(int p=0;p<8;p++)
			{
				if(!ok[j][p]) continue;
				f[i][j]=min(f[i][j],f[i-1][p]+calc(now^j));
			}
		}
	}
	for(int i=0;i<8;i++) ans=min(ans,f[m][i]);
	printf("%d\n",ans);
	return 0;
}