2020牛客暑期多校訓練營（第三場）題解

A ：Clam and Fish

簡要題意 •

小月有 n 機關的時間都在釣魚，每個機關時間有四種狀态，

。蛤蜊魚

0:0 // 0

1:0 //1

2:1//0

3: 1//1

小月事先知道這 n 個時間點的狀态。每個時間點有四種可能的動作：

若該時間點有魚，則可以直接釣魚。
若該時間點有蛤蜊，則可以用該蛤蛎制作一個魚餌。
若該時間點身上有至少一個魚餌，則可以用一個魚餌釣一條魚，釣完後就少了一個魚餌。
什麼事都不做。

請問小月最多可以釣多少條魚。

輸入

2

4

0103

1

1

輸出

2

備注:

One possible scenario you can catch two fishes is as follow:

stage 1: Do nothing.

stage 2: Make a pack of fish bait.

stage 3: Catch a fish by a pack of fish bait.

stage 4: Catch the fish that appears in the stage.

狀态2，3 有魚直接釣魚，狀态1，0順序配合釣魚，狀态1，1順序配合釣魚

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
int yi;
int main()
{
 ios::sync_with_stdio(false);
 int t,n,m,yu=0;
 cin>>t;
 while(t--)
 {
 	yu=0;yi=0;
 	cin>>n;
 	cin>>s;
 	for(int i=0;i<n;i++)
 	{
 	  if(s[i]=='2'||s[i]=='3') yu++;
	  else if(s[i]=='1') yi++;
	  else	
	  {
	  	if(yi) 
	  	{
	  	 yi--;yu++;	
		}
	  }
    }
    yu+=yi/2;
	cout<<yu<<endl;
 }
 return 0;	
}

B：Classical String Problem

簡要題意：

有一個字元串，有兩種操作：

詢問第 x 個字元。
把最左邊的 x 個字元搬到最右邊或把最右邊 x 個字元搬到最左邊。

官方題解：

想像成字元串是頭尾接在一起的，隻需維護一個指針指向目前第一個字元的位置，就能以 O(1) 的時間複雜度進行每個操作。

• 以 Sample 為例 •

初始時指針在 n 的前面 |nowcoder •

操作 1 詢問指針右邊第 1 個字元，答案是 n •

操作 2 把 4 個字元搬到右邊，相當于把指針向右移 4 個字元 nowc|oder •

操作 3 詢問指針右邊第 6 個字元，答案是 o •

操作 4 把右邊 3 個字元搬到右邊，相當于把指針向左移 3 個字元 n|owcoder •

…

輸入

nowcoder

A 1

M 4

A 6

M -3

M 1

A 1

輸出

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
 ios::sync_with_stdio(false);
 int n,tmp,tip=0,len;
 string s;
 char c;
 cin>>s>>n;
 len=s.length();
 while(n--)
 {
 	cin>>c>>tmp;
 	if(c=='A') cout<<s[(tip+tmp-1)%len]<<endl;
 	else 
	{
      if(tmp>0) tip=(tip+tmp)%len;
      else tip=(tip+tmp+len)%len;      
	}
 }
 return 0;	
}

C：Operation Love

圖為某機器人右手手印的形狀，左手為右手的對稱圖形，現在給你一個機器人手印(可能經過平移及旋轉，大小不變)，請判斷是左手還右手(保證一定是其中一隻手) 。

2020牛客暑期多校訓練營（第三場）題解

找出邊長為6和9的兩條邊，判斷順逆，注意精度

#include<bits/stdc++.h>
using namespace std;
#define ll long long
double x[25],y[25];
const double eps=0.1; //偏內插補點，有時用1e-10 
int sgn(double x)//判斷x是否等于0 
{
 if(fabs(x)<eps) return 0;	
 return x<0? -1:1; 
} 
struct point 
{
	double x,y;
	point(){}
	point(double x,double y):x(x),y(y){}
	point operator-(point B) {return point(x-B.x,y-B.y);} //向量減法
};
double dis(point a,point b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
double cross(point a,point b)
{
	return a.x*b.y-a.y*b.x;
}
point a[25];
int main()
{
 ios::sync_with_stdio(false);
 int t;
 cin>>t;
 while(t--)
 {
 	for(int i=0;i<20;i++)
 	 cin>>a[i].x>>a[i].y;
 	int bo;
 	for(int i=0;i<20;i++)
 	{
 	 if(sgn(dis(a[i],a[(i+19)%20])-36)==0&&sgn(dis(a[i],a[(i+1)%20])-81)==0)  
 	 {
 	  bo=sgn(cross(a[(i+19)%20]-a[i],a[(i+1)%20]-a[i]));
	  break;	
	 }
 	 if(sgn(dis(a[i],a[(i+19)%20])-81)==0&&sgn(dis(a[i],a[(i+1)%20])-36)==0) 
 	 {
 	  bo=sgn(cross(a[(i+1)%20]-a[i],a[(i+19)%20]-a[i]));
	  break;	
	 } 	 
	}
 	if(bo==-1) cout<<"right"<<endl;
 	else cout<<"left"<<endl;
 }
 return 0;	
}

D:Points Construction Problem

在無限大的格子盤面中，原本所有格子都是白色的，請把其中 n 個格子塗黑，使得滿足格子 x 和格子y 是上下左右相鄰且 x , y 異色的 (x,y) 組數恰好為k 個((x,y)和(y,x) 視為相同)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
    ios::sync_with_stdio(false);
	int t,n,m,x,y,sum,tmp,res; 
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(m%2||m>4*n||m*m<16*n)//m為偶數，最大值4n，最小值m^2>=16n 
         cout<<"No"<<endl;
        else
        {
        	cout<<"Yes"<<endl;
        	int sum=2*n+2;//當n為一排過去時的邊數
        	if(m>sum) //兩種情況，一些在一排裡，一些落單 
        	{
        		tmp=(m-sum)/2;// 
        		for(int i=1;i<=n-tmp;i++) //一排過去，每次邊+2 
        		 cout<<1<<" "<<i<<endl;
        		for(int i=3;i<=3+tmp-1;i++) //斜線，每次邊+4 
        		 cout<<i<<" "<<i<<endl;
			}
			else//L型，最佳情況，abs(x-y)<=1
			{
				//m=2(x+y),極值在abs(x-y)<=1處取到，是以x=m/4 
				x=m/4;y=m/2-x; // 
				for(int i=1;i<=x;i++)
				 cout<<i<<" "<<1<<endl;
				for(int i=2;i<=y;i++)
				 cout<<1<<" "<<i<<endl;
				//L型，往裡填方格，邊不變 
				res=n-(x+y-1);//已填x+y-1個 
				for(int i=2;i<=x&&res;i++)
				 for(int j=2;j<=y&&res;j++,res--)
				  cout<<i<<" "<<j<<endl;
			}
		}
    }
    return 0;
}

E：Two Matchings

詳解

dp[i]=min(dp[i-4]+dp[i]-dp[i-3],dp[i-6]+dp[i]-dp[i-5]);

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[200100]; 
int main()
{
 ios::sync_with_stdio(false);
 int t,n;
 cin>>t;
 while(t--)
 {
 	cin>>n;
 	for(int i=1;i<=n;i++)
 	 cin>>dp[i];
 	sort(dp+1,dp+n+1);
 	dp[4]-=dp[1];
 	dp[6]-=dp[1];
 	dp[8]=dp[8]-dp[5]+dp[4];
 	for(int i=10;i<=n;i+=2)
 	 dp[i]=min(dp[i-4]+dp[i]-dp[i-3],dp[i-6]+dp[i]-dp[i-5]);
 	cout<<2*dp[n]<<endl;
 }
 return 0;	
}

F: Fraction Construction Problem

詳解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b) 
{
    return b==0? a:gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;y=0;return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int pri[2000100],cnt=0;
bool st[2000100];
int m[2000100];//數字i的最小因子（除了1）
void prime()
{
 m[0]=m[1]=1;
 for(int i=2;i<=2000000;i++)
  if(m[i]==0)
  {
   for(int j=i;j<=2000000;j+=i)
    if(m[j]==0)
    m[j]=i;
  }
}
int main()
{
 ios::sync_with_stdio(false);
 int t,a,b,g;
 cin>>t;
 prime();
 while(t--)
 {
   cin>>a>>b;
   g=gcd(a,b); 
   if(g>1)
    cout<<a/g+b/g<<" "<<b/g<<" "<<1<<" "<<1<<endl;
   else
   {
   	//找b的兩個互質因子 
    ll d=1,f=b,k=m[b];
    while(k!=1&&f%k==0) d*=k,f/=k;
    if(d==b&&f==1) cout<<-1<<" "<<-1<<" "<<-1<<" "<<-1<<endl;
    else
    {
     ll e,c;
        exgcd(d,f,e,c);//ed+cf=1 
        //-ed+cf=1
        e*=-1;
        //ax+by=gcd(a,b)的其他解為x=x0+k*b; y=y0-k*a
        while(e<=0||c<=0) c+=d,e+=f;
        e*=a;c*=a;
        cout<<c<<" "<<d<<" "<<e<<" "<<f<<endl;
    }
   }
 }
    return 0;
}

G：Operating on a Graph

官方題解：

給一個 n 個點的 Graph，第 i 個點一剛開始是第 I 種顔色，接着有 k 次操作，第 i 次操作有個參數 oi 代表顔色 oi 會侵略所有和自己相鄰的顔色，于是所有和 oi 相鄰的顔色全都變成 oi (若已沒有顔色oi 已被侵略，則該次操作無效)，求最終每個點的顔色。

對于每個顔色都維護一個點的連結清單，儲存該顔色中尚未把所有相鄰點變為自己顔色的點。
用并查集紀錄每個點屬于哪個顔色。
每次操作就會把顔色 oi 的連結清單中所有相鄰的點所屬的顔色都變為 oi ，就直接把對應的連結清單合并以及在并查集上做對應的操作、

#include<bits/stdc++.h>
using namespace std;
#define ll long long
list<int>G[800100];
int t,n,m,u,v,q,num,fa[800100],fx,fy;
int find(int x)     //找到并更新最終結點
{
    if(x!=fa[x])
     x=fa[x]=find(fa[x]);
    return x;
}
void merge(int x,int y) // 
{
    fx=find(x);
    fy=find(y);
    if(fx==fy) return; //本來就在一組，不用修改 
    fa[fy]=fx;  
    G[fx].splice(G[fx].end(),G[fy]);// 合并 
    G[fy].clear();  //删去
}
int main() 
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++) //一開始指向自己+初始化 
        {
            fa[i]=i;
            G[i].clear();
        }
        for (int i=0;i<m;i++)//存入邊 
        {
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        cin>>q;
        while(q--)
        {
            cin>>num;
            if(find(num)!=num)
                continue;
            //把相連的點歸到自己一組 
            vector<int>v;
            for(auto &j: G[num])  //相連的點 
            {
                if(find(j)!=num)  //需要修改的點 
                 v.push_back(j);
            }
            G[num].clear(); //清空 
            for(auto &j:v)    //修改 
            {
                merge(num,j);
            }
        }
        for (int i=0;i<n;i++)
            cout<<find(i)<<" ";
        cout<<endl;
    }
    return 0;
}

L：Problem L is the Only Lovely Problem

判斷一個字元串是否為 lovely 開頭，不分大小寫。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
 ios::sync_with_stdio(false);
 string s;
 cin>>s;
 for(int i=0;i<6;i++)
  if(s[i]>='A'&&s[i]<='Z')
   s[i]=s[i]-'A'+'a';
 if(s.length()>=6&&s.substr(0,6)=="lovely") cout<<"lovely"<<endl;
 else cout<<"ugly"<<endl;
 return 0;	
}

2020牛客暑期多校訓練營（第三場）題解

繼續閱讀

Visual Studio cannot debug managed applications because a kernel debugger is enabled on the system

js判斷移動端或web端跳轉頁面

submodule內建第三方庫

一方庫、二方庫、三方庫是什麼？

第三方醫學診斷（實驗室）（ICL）

在chrome中按日期搜尋并清除某個關鍵詞的history1 按照日期搜尋history2 批量删除某關鍵詞的history

關閉myeclipse中煩人的滑鼠劃過,自動提示功能--世界終于清靜!

Win32彙編入門概述

OpenStreetMap: User-Generated Street Maps文章讀後記錄

抖音裡面比較火的音樂，2019抖音最熱歌曲排名，抖音十大神曲

DHTML 事件DHTML 事件

如何在CSDN部落格中插入動态圖（GIF）

8088 彙編速查手冊（ZT）

代碼随想錄刷題總結1. 感悟2. 總結

GPS定位坐标糾偏

失敗人士的八個習慣(有則改之，無則加勉，呵呵..)