cf的比賽越來(lái)越有難度了……至少我做起來(lái)是這樣。

先看看題目吧：點(diǎn)我。

這次比賽是北京時(shí)間21:35開(kāi)始的，算是比較良心。

【A】奇數(shù)與結(jié)束

"奇數(shù)從哪里開(kāi)始，又在哪里結(jié)束？夢(mèng)想從何處起航，它們又是否會(huì)破滅呢？"

給定一個(gè)長(zhǎng)度為n的序列。確定能不能將序列分成奇數(shù)個(gè)長(zhǎng)度為奇數(shù)的非空字串，而且這其中每個(gè)子串以奇數(shù)開(kāi)頭，以奇數(shù)結(jié)尾?？梢灾环殖梢粋€(gè)（1也是奇數(shù)）。

輸入

第一行一個(gè)正整數(shù)n，表示序列長(zhǎng)度。

第二行n個(gè)整數(shù)，表示序列中的元素。

輸出

輸出"Yes"或"No"來(lái)表示能否做到把序列按要求分割。

樣例輸入1

5
1 0 1 5 1

樣例輸出1

Yes

樣例輸入2

4
3 9 9 3

樣例輸出2

No

題解

當(dāng)時(shí)想了一個(gè)n2的DP，之后發(fā)現(xiàn)實(shí)在是太naive。

講一下DP思路吧，用f1[i]表示能否將a[1...i]分割成奇數(shù)個(gè)奇數(shù)長(zhǎng)度的子串，并且每個(gè)子串以奇數(shù)開(kāi)頭結(jié)尾，f2[i]表示能否分割成偶數(shù)個(gè)子串。

于是f1[i]=OR(f2[j] (a[j+1...i]長(zhǎng)度為奇數(shù)并且以奇數(shù)開(kāi)頭結(jié)尾) )，f2[i]=OR(f1[j] (a[j+1...i]長(zhǎng)度為奇數(shù)并且以奇數(shù)開(kāi)頭結(jié)尾) ).

特別的，f1[0]=false，f2[0]=true。

這種做法就可以過(guò)了，但是有更優(yōu)秀的做法：

把序列分成奇數(shù)個(gè)奇數(shù)長(zhǎng)度的序列，那么這個(gè)序列也是奇數(shù)長(zhǎng)度的。偶數(shù)長(zhǎng)度的直接No。

再考慮把序列分成兩個(gè)以上的序列，那么最開(kāi)始的序列的起始元素必須是奇數(shù)，最末尾的序列的結(jié)尾元素也必須是奇數(shù)。

這就對(duì)應(yīng)了原序列的第一個(gè)與最后一個(gè)元素必須是奇數(shù)，而這時(shí)我們只分一段就好了。

就是說(shuō)我們只需要判斷n的奇偶，a[1]的奇偶和a[n]的奇偶就可以了。

程序：

1 #include <cstdio> 2 static const int MAXN = 102; 3 4 int n; 5 int a[MAXN]; 6 7 int main() 8 { 9 scanf("%d", &n); 10 for (int i = 0; i < n; ++i) scanf("%d", &a[i]); 11 12 puts((n & 1) && (a[0] & 1) && (a[n - 1] & 1) ? "Yes" : "No"); 13 return 0; 14 }

【B】

目前沒(méi)做出來(lái)，調(diào)出來(lái)了再說(shuō)自己的做法吧

先貼標(biāo)程：

1 #include <bits/stdc++.h> 2 #define eps 1e-7 3 using namespace std; 4 int read() 5 { 6 int x=0,f=1;char ch=getchar(); 7 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 8 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 9 return x*f; 10 } 11 int n,a[1007]; 12 bool vis[1007]; 13 bool check(double k,int b) 14 { 15 memset(vis,false,sizeof(vis)); 16 int cnt=0; 17 for (int i=1;i<=n;i++) 18 { 19 if (a[i]-b==1LL*k*(i-1)) 20 { 21 vis[i]=true; 22 ++cnt; 23 } 24 } 25 if (cnt==n) return false; 26 if (cnt==n-1) return true; 27 int pos1=0; 28 for (int i=1;i<=n;i++) 29 if (!vis[i]&&pos1==0) pos1=i; 30 for (int i=pos1+1;i<=n;i++) 31 if (!vis[i]) 32 { 33 if (fabs((double)(a[i]-a[pos1])/(i-pos1)-k)>eps) return false; 34 } 35 return true; 36 } 37 int main() 38 { 39 n=read(); 40 for (int i=1;i<=n;i++) 41 a[i]=read(); 42 bool ans=false; 43 ans|=check(1.0*(a[2]-a[1]),a[1]); 44 ans|=check(0.5*(a[3]-a[1]),a[1]); 45 ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]); 46 if (ans) printf("Yes\n"); else printf("No\n"); 47 return 0; 48 }

【C】

題目都沒(méi)看懂，真的很難受，這題挺難的。

標(biāo)程：

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 using ll = long long; 6 using ld = long double; 7 using D = double; 8 using uint = unsigned int; 9 template<typename T> 10 using pair2 = pair<T, T>; 11 12 #ifdef WIN32 13 #define LLD "%I64d" 14 #else 15 #define LLD "%lld" 16 #endif 17 18 #define pb push_back 19 #define mp make_pair 20 #define all(x) (x).begin(),(x).end() 21 #define fi first 22 #define se second 23 24 int main() 25 { 26 int k; 27 scanf("%d", &k); 28 for (int i = 0; i < 26; i++) 29 { 30 int cnt = 1; 31 while ((cnt + 1) * cnt / 2 <= k) cnt++; 32 k -= cnt * (cnt - 1) / 2; 33 for (int j = 0; j < cnt; j++) printf("%c", 'a' + i); 34 } 35 return 0; 36 }

【D】Rooter's Song

"無(wú)論目標(biāo)何在，無(wú)論遇見(jiàn)何人，讓我們一同將這首歌傳唱。"

在平面直角坐標(biāo)系中，有一個(gè)長(zhǎng)方形舞臺(tái)，四角分別是(0,0)，(0,h)，(w,0)，(w,h)。

可以看出在有任何人進(jìn)入舞臺(tái)之前，不會(huì)有任何碰撞發(fā)生。

在舞臺(tái)的左邊界和下邊界站著一些舞者。分成兩組：

①豎直：站在(xi,0)上，沿著y正方向前進(jìn)（向上）。

②水平：站在(0,yi)上，沿著x正方向前進(jìn)（向右）。

按照編舞指導(dǎo)，第i個(gè)舞者需要在前ti毫秒內(nèi)站著不動(dòng)，然后沿著指定方向以1單位/毫秒的速度前進(jìn)，直到碰到舞臺(tái)的邊界為止。

當(dāng)兩個(gè)舞者碰撞時(shí)，她們會(huì)立刻改變各自的前進(jìn)方向，然后繼續(xù)沿著新的方向前進(jìn)。

舞者們只要碰到了舞臺(tái)的邊界就會(huì)停止，請(qǐng)求出每個(gè)舞者最終停下的位置。

輸入

第一行有三個(gè)數(shù)n,w,h。表示舞者數(shù)量，舞臺(tái)的長(zhǎng)寬。

接下來(lái)n行，每行三個(gè)數(shù)，gi,pi,ti，表示第i個(gè)舞者所在的組（gi=1：豎直組；gi=2：水平組），坐標(biāo)位置（gi=1則pi=xi；gi=2則pi=yi）以及等待時(shí)間。

保證0<xi<w，0<yi<h。并保證沒(méi)有兩個(gè)舞者既在相同的組，還有相同的位置和等待時(shí)間。

輸出

n行，每行兩個(gè)數(shù)xi,yi。表示第i個(gè)舞者最終停在哪里。

樣例輸入1

8 10 8
1 1 10
1 4 13
1 7 1
1 8 2
2 2 0
2 5 14
2 6 0
2 6 1

樣例輸出1

4 8
10 5
8 8
10 6
10 2
1 8
7 8
10 6

樣例輸入2

3 2 3
1 1 2
2 1 1
1 1 5

樣例輸出2

1 3
2 1
1 3

數(shù)據(jù)范圍及提示

1<=n<=100000，2<=w,h<=100000，1<=gi<=2，1<=pi<=99999，0<=ti<=100000。

對(duì)于樣例數(shù)據(jù)1，這是對(duì)應(yīng)的圖：

對(duì)于樣例數(shù)據(jù)2，沒(méi)有舞者碰撞。

題解

很難的一題，不過(guò)我看來(lái)比C題簡(jiǎn)單……

注意到每個(gè)舞者出發(fā)后，每毫秒其坐標(biāo)總是有一個(gè)加一，故(xi+yi)總是在增加。

而且我們發(fā)現(xiàn)，只有(xi+yi)相同的舞者才會(huì)碰撞。我們把(xi+yi)的值相同的舞者分在一起處理。

如何確定(xi+yi)的值呢？？可以發(fā)現(xiàn)對(duì)于每個(gè)舞者，可以把(pi-ti)近似看做(xi+yi)，(pi-ti)相同的舞者可能碰撞，而(pi-ti)不同的不可能碰撞。

我們對(duì)舞者按照(pi-ti)排序，處理出(pi-ti)相同的舞者。

對(duì)于(pi-ti)相同的舞者，我們?nèi)绾翁幚砟?#xff1f;

試著把舞臺(tái)斜過(guò)來(lái)看吧！讓(0,0)在最下方，(w,h)在最頂端，(0,h)在左側(cè)，(w,0)在最右側(cè)。

這樣，對(duì)于那些(pi-ti)相同的舞者，即出發(fā)后(xi+yi)相同的舞者們，她們?cè)谕粫r(shí)間點(diǎn)必然處在同一水平線上。

并且每過(guò)一毫秒，她們向上走√2/2單位，向左或向右走√2/2單位。

這時(shí)候的碰撞要如何處理呢？

注意到在沒(méi)有碰撞發(fā)生前，舞者從左到右的順序是先是水平方向的舞者，坐標(biāo)從大到小下來(lái)，然后是豎直方向的舞者，坐標(biāo)從小到大往右走。

而所有碰撞都發(fā)生了之后呢？？舞者的相對(duì)位置是不會(huì)改變的！原本在最左側(cè)的舞者，仍然在左側(cè)。舞者位置不會(huì)交換。

或者……這是另一種形式的交換了呢？注意到在水平方向坐標(biāo)最大的舞者沒(méi)有去到她本來(lái)應(yīng)該去的位置，而是去了豎直方向第一個(gè)舞者應(yīng)該去的位置。

是的，她們的位置交換了，但是這種交換很有規(guī)律，把舞者分成水平方向和豎直方向，那么水平方向的舞者按順序要去到豎直方向的舞者按順序應(yīng)該去到的位置。依次推下來(lái)，就可以確定舞者最終的位置。我不太好解釋這種方法的具體實(shí)現(xiàn)，先貼代碼吧。

排序時(shí)要注意第一關(guān)鍵字是(pi-ti)，第二關(guān)鍵字是先水平，后豎直，第三關(guān)鍵字是初始坐標(biāo)，水平的從大到小，豎直的從小到大。

復(fù)雜度O(nlogn)

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define F(i,a,b) for(int i=a;i<=b;++i) 5 #define F2(i,a,b) for(int i=a;i<b;++i) 6 int n,w,h,g[100002],p[100002],t[100002],I[100002],Ans[100002],Ansg[100002]; 7 inline bool cmp(int x,int y){ 8 if(p[x]-t[x]<p[y]-t[y]) return 1; 9 else if(p[x]-t[x]>p[y]-t[y]) return 0; 10 else{ 11 if(g[x]>g[y]) return 1; 12 else if(g[x]<g[y]) return 0; 13 else{ 14 if(g[x]==1) return p[x]<p[y]; 15 else return p[x]>p[y]; 16 } 17 } 18 } 19 int main(){ 20 scanf("%d%d%d",&n,&w,&h); 21 F(i,1,n) scanf("%d%d%d",g+i,p+i,t+i),I[i]=i; 22 std::sort(I+1,I+n+1,cmp); 23 I[n+1]=0; p[0]=99999999; t[0]=-99999999; 24 int hor=0,ver=0; 25 F(i,1,n){ 26 if(g[I[i]]==1) ++ver; else ++hor; 27 if(p[I[i]]-t[I[i]]!=p[I[i+1]]-t[I[i+1]]){ 28 int j=i-hor-ver+1, k=i-ver+1,l,o; 29 for(l=k,o=j;l<=i;++l,++o) 30 Ans[I[o]]=p[I[l]],Ansg[I[o]]=g[I[l]]; 31 for(;o<=i;++o,++j) 32 Ans[I[o]]=p[I[j]],Ansg[I[o]]=g[I[j]]; 33 ver=hor=0; 34 } 35 } 36 F(i,1,n) if(Ansg[i]==1) printf("%d %d\n",Ans[i],h); else printf("%d %d\n",w,Ans[i]); 37 return 0; 38 }

【E】

沒(méi)看題，以后再補(bǔ)吧。

轉(zhuǎn)載于:https://www.cnblogs.com/PinkRabbit/p/7466204.html

總結(jié)

以上是生活随笔為你收集整理的【codeforces】【比赛题解】#849 CF Round #431 (Div.2)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。