天天看點
傳回

Educational Codeforces 70 (Rated for Div.2) 題解Ranklist:

什麼破爛場，題目根本不是Div.2難度的。算了，寫個題解再說吧。

Ranklist:

Educational Codeforces 70 (Rated for Div.2) 題解Ranklist:

A - You’re given two binary strings…

題意：有兩個01字元串 a a a和 b b b，如果把每個字元串看作一個二進制數的話，都會對應一個十進制數。字元串 s s s對應的十進制數記作 f ( s ) f(s) f(s)。你要求出滿足要求的非負整數 k k k，使得 f ( a ) + 2 k ∗ f ( b ) f(a)+2^k*f(b) f(a)+2k∗f(b)轉化為二進制後反序的字典序盡可能小。題目包含多測。

思路：

剛上來就給你一個下馬威，告訴你這不是普通的Div.2.

首先，我們知道，乘 2 2 2的 k k k次方其實就是在二進制數後面添 k k k個 0 0 0，而如果要讓反序的字典序盡可能小，那麼最後一位就要盡可能小，在滿足這個的前提下，倒數第二位也要盡可能小，以此類推。

我們假設 b b b的後 x x x位全部都是 0 0 0，而從右往左數第 x x x位為 1 1 1。那麼 k k k不論取什麼值， f ( a ) + 2 k ∗ f ( b ) f(a)+2^k*f(b) f(a)+2k∗f(b)的後 x x x位永遠不會發生改變，永遠與 a a a的後 x x x位相同。此時，如果第 a a a的第 x x x位為 1 1 1，那麼我們就不用添 0 0 0了，已經取到了最優解。而如果如果第 a a a的第 x x x位為 0 0 0，那麼 f ( a ) + 2 k ∗ f ( b ) f(a)+2^k*f(b) f(a)+2k∗f(b)的第 x x x位為 1 1 1，不是我們想要的。此時我們就要在 b b b的後面添上一個 0 0 0，然後重複上述操作。

簡單來說，假設 b b b最右邊一個 1 1 1是從右往左數第 x x x位，那麼本題要求的答案就是 a a a從右往左數第 x x x位左邊有多少個連續的 0 0 0。

C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;
int T;
string s,t;
int main(){
	cin>>T;
	while(T--){
		cin>>s>>t;
		int ind=-1;
		for(int i=t.size()-1,cnt=0;i>=0;i--,cnt++){
			if(t[i]=='1'){
				ind=cnt;
				break;
			}
		}
		if(ind==-1){
			cout<<0<<endl;
			continue;
		}
		int ans=0;
		for(int i=s.size()-ind-1;i>=0;i--){
			if(s[i]=='0')	ans++;
			else			break;
		}
		cout<<ans<<endl;
	}
	return 0;
}

B - You’re given a decimal string…

題意：給你一個由 0 0 0到 9 9 9組成的字元串。對于所有的 x = 0 , 1 , … , 9 x=0,1,\dots,9 x=0,1,…,9， y = 0 , 1 , … , 9 y=0,1,\dots,9 y=0,1,…,9，問你最少添加多少個數位使得相鄰兩個數位的差 m o d   10 mod\ 10 mod 10要麼等于 i i i，要麼等于 j j j，數位可以在任意位置添加。

思路：

思維難度沒有上一題大，但是實作起來細節很惡心。

首先先 O ( 1 0 5 ) O(10^5) O(105)預處理出在 0 0 0和 k k k之間最少添加多少個數位使得相鄰兩個數位的差 m o d   10 mod\ 10 mod 10要麼等于 x x x，要麼等于 y y y，用 a x , y , k a_{x,y,k} ax,y,k​記錄。然後暴力即可。但是有一個非常惡心的坑點：相鄰兩個字元相同的情況要特判。這也就是為什麼現場很多人WA 2 2 2，進而沒有過這道題的原因。我比賽的時候也在這裡死了好幾次。

C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;
string s;
int a[11][11][11],ans[11][11];
signed main(){
	cin>>s;
	memset(ans,0,sizeof(ans));
	memset(a,63,sizeof(a));
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			for(int k=0;k<10;k++){
				for(int p=0;p<=10;p++){
					for(int q=0;q<=10;q++){
						if((i*p+j*q)%10==k){
							int x=k;
							if(x==0)	x=10;
							if(x==10&&(p==0&&q==0))	continue;
							a[i][j][x]=min(a[i][j][x],p+q);
						}
					}
				}
			}
	for(int i=0;i<s.size()-1;i++){
		int dig1=s[i]-'0',dig2=s[i+1]-'0';
		int dif=(dig2-dig1+20)%10;
		if(dif==0)	dif=10;
		for(int j=0;j<10;j++){
			for(int k=0;k<10;k++){
				if(~ans[j][k]){
					if(a[j][k][dif]==0x3f3f3f3f)	ans[j][k]=-1;
					else							ans[j][k]+=a[j][k][dif]-1;
				}
			}
		}
	}
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

C - You’re given a WASD string…

題意：有一個由“WASD"組成的字元串 s s s，代表機器人的移動指令。"W"表示向上移動一格，"A"表示向左移動一格，"S"表示向下移動一格，"D"表示向右移動一格。這個機器人的軌迹可以被一個矩形正好包圍，現在允許你在 s s s的任意位置添上"WASD"中的一個字元，也可以不添，形成一個新的指令，使得這個矩形的面積盡可能小。題目包含多測。

思路：

我的做法可能和大家不太一樣。

字首和+線段樹。首先我們先用字首和将進行完第 i i i個指令之後機器人的位置求出來。我們記 s u m i , 0 sum_{i,0} sumi,0​表示進行完第 i i i個指令之後機器人的橫坐标， s u m i , 1 sum_{i,1} sumi,1​表示進行完第 i i i個指令之後機器人的縱坐标。是以矩形的面積就是

S = ( m a x ( s u m [ 1 ] [ 0 ] , s u m [ 2 ] [ 0 ] , … , s u m [ n ] [ 0 ] , 0 ) − m i n ( s u m [ 1 ] [ 0 ] , s u m [ 2 ] [ 0 ] , … , s u m [ n ] [ 0 ] , 0 ) + 1 ) ∗ ( m a x ( s u m [ 1 ] [ 1 ] , s u m [ 2 ] [ 1 ] , … , s u m [ n ] [ 1 ] , 0 ) − m i n ( s u m [ 1 ] [ 1 ] , s u m [ 2 ] [ 1 ] , … , s u m [ n ] [ 1 ] , 0 ) + 1 ) ; S=(max(sum[1][0],sum[2][0],\dots,sum[n][0],0)-min(sum[1][0],sum[2][0],\dots,sum[n][0],0)+1)*(max(sum[1][1],sum[2][1],\dots,sum[n][1],0)-min(sum[1][1],sum[2][1],\dots,sum[n][1],0)+1); S=(max(sum[1][0],sum[2][0],…,sum[n][0],0)−min(sum[1][0],sum[2][0],…,sum[n][0],0)+1)∗(max(sum[1][1],sum[2][1],…,sum[n][1],0)−min(sum[1][1],sum[2][1],…,sum[n][1],0)+1);

而我們枚舉每一個位置 i i i，在第 i i i個位置後面添上一個’W’其實就是 s u m i , 1 = s u m i − 1 , 1 + 1 , s u m i + 1 , 1 = s u m i , 1 + 1 , s u m i + 2 , 1 = s u m i + 1 , 1 + 1 , … s u m n + 1 , 1 = s u m n , 1 sum_{i,1}=sum_{i-1,1}+1,sum_{i+1,1}=sum_{i,1}+1,sum_{i+2,1}=sum_{i+1,1}+1,\dots sum_{n+1,1}=sum_{n,1} sumi,1​=sumi−1,1​+1,sumi+1,1​=sumi,1​+1,sumi+2,1​=sumi+1,1​+1,…sumn+1,1​=sumn,1​，其他也一樣，這個可以用線段樹來維護。

C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int T;
string s;
int sum[200005][2];
struct seg{
	struct node{
		int l,r,mn,mx,lz;
	} s[800005];
	inline void build(int k,int l,int r,int type){
		s[k].l=l;s[k].r=r;
		if(l==r){
			s[k].mn=s[k].mx=sum[l][type];
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid,type);
		build(k<<1|1,mid+1,r,type);
		s[k].mn=min(s[k<<1].mn,s[k<<1|1].mn);
		s[k].mx=max(s[k<<1].mx,s[k<<1|1].mx);
	}
	inline void pushdown(int k){
		s[k<<1].mx+=s[k].lz;
		s[k<<1].mn+=s[k].lz;
		s[k<<1].lz+=s[k].lz;
		s[k<<1|1].mx+=s[k].lz;
		s[k<<1|1].mn+=s[k].lz;
		s[k<<1|1].lz+=s[k].lz;
	}
	inline void change(int k,int l,int r,int val){
		if(l>r)	return;
		if(l<=s[k].l&&s[k].r<=r){
			s[k].lz+=val;
			s[k].mx+=val;
			s[k].mn+=val;
			return;
		}
		pushdown(k);
		int mid=(s[k].l+s[k].r)>>1;
		if(r<=mid)		change(k<<1,l,r,val);
		else if(l>mid)	change(k<<1|1,l,r,val);
		else			change(k<<1,l,mid,val),change(k<<1|1,mid+1,r,val);
		s[k].mn=min(s[k<<1].mn,s[k<<1|1].mn);
		s[k].mx=max(s[k<<1].mx,s[k<<1|1].mx);
	}
	inline int query_mn(){
		return s[1].mn;
	}
	inline int query_mx(){
		return s[1].mx;
	}
} st[2];
int area(){
	return (max(st[0].query_mx(),0ll)-min(st[0].query_mn(),0ll)+1)*(max(st[1].query_mx(),0ll)-min(st[1].query_mn(),0ll)+1);
}
signed main(){
	cin>>T;
	while(T--){
		cin>>s;
		s=" "+s;
		for(int i=0;i<=s.size();i++)	sum[i][0]=sum[i][1]=sum[i][2]=sum[i][3]=0;
		for(int i=1;i<s.size();i++){
			sum[i][0]=sum[i-1][0];
			sum[i][1]=sum[i-1][1];
			if(s[i]=='W')	sum[i][0]++;
			if(s[i]=='A')	sum[i][1]--;
			if(s[i]=='S')	sum[i][0]--;
			if(s[i]=='D')	sum[i][1]++;
		}
		st[0].build(1,1,s.size()-1,0);
		st[1].build(1,1,s.size()-1,1);
		int ans=area();
		for(int i=0;i<=s.size();i++){
			st[0].change(1,i,s.size()-1,-1);
			ans=min(ans,(max(st[0].query_mx(),0ll)-min(st[0].query_mn(),min(sum[i-1][0]-1,0ll))+1)*(max(st[1].query_mx(),0ll)-min(st[1].query_mn(),0ll)+1));
			st[0].change(1,i,s.size()-1,1);
			st[0].change(1,i,s.size()-1,1);
			ans=min(ans,(max(st[0].query_mx(),max(sum[i-1][0]+1,0ll))-min(st[0].query_mn(),0ll)+1)*(max(st[1].query_mx(),0ll)-min(st[1].query_mn(),0ll)+1));
			st[0].change(1,i,s.size()-1,-1);
			st[1].change(1,i,s.size()-1,-1);
			ans=min(ans,(max(st[0].query_mx(),0ll)-min(st[0].query_mn(),0ll)+1)*(max(st[1].query_mx(),0ll)-min(st[1].query_mn(),min(sum[i-1][1]-1,0ll))+1));
			st[1].change(1,i,s.size()-1,1);
			st[1].change(1,i,s.size()-1,1);
			ans=min(ans,(max(st[0].query_mx(),0ll)-min(st[0].query_mn(),0ll)+1)*(max(st[1].query_mx(),max(sum[i-1][1]+1,0ll))-min(st[1].query_mn(),0ll)+1));
			st[1].change(1,i,s.size()-1,-1);
		}
		cout<<ans<<endl;
	}
	return 0;
}

D - Print a 1337-string…

題意：給定一個正整數 n n n，讓你構造出一個由"1",“3”,“7"組成的字元串，其中恰好含有 n n n個字串"1337”。題目包含多測。

思路：

這道題可謂是有些毒瘤了，分明是水題，還不放在A或者B題，偏偏跑到個D的位置來，害得我現場做完C沒時間做D。

很容易想到 133...33733...33733...337 133...33733...33733...337 133...33733...33733...337的情況，然後随便亂搞搞就行了，水題不多說。

C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> ans;
signed main(){
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		ans.clear();
		putchar('1');
		for(int i=50005;i>=1;i--){
			while(n>=(i*(i+1)/2)){
				ans.push_back(i+1);
				n-=i*(i+1)/2;
			}
		}
		sort(ans.begin(),ans.end());
		for(int i=1;i<=ans[0];i++)	putchar('3');putchar('7');
		for(int i=1;i<ans.size();i++){
			for(int j=1;j<=ans[i]-ans[i-1];j++)
				putchar('3');
			putchar('7');
		}
		cout<<endl;
	}
}

有巨佬會E或者F的在洛谷上發私信給我，我的洛谷賬号是這個，或者在下面評論哦！

比賽題解 題目 Educational Codeforces 70 字元串 Div.2 題解
上一篇: leetcode之Climbing Stairs
下一篇: JUC（18）ThreadLocal的應用與原理

繼續閱讀