【codeforces】【比賽題解】#849 CF Round #431 (Div.2)

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

先看看題目吧：點我。

這次比賽是北京時間21:35開始的，算是比較良心。

【A】奇數與結束

"奇數從哪里開始，又在哪里結束？夢想從何處起航，它們又是否會破滅呢？"

給定一個長度為n的序列。確定能不能將序列分成奇數個長度為奇數的非空字串，而且這其中每個子串以奇數開頭，以奇數結尾。可以只分成一個（1也是奇數）。

輸入

第一行一個正整數n，表示序列長度。

第二行n個整數，表示序列中的元素。

輸出

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

樣例輸入1

5
1 0 1 5 1

樣例輸出1

Yes

樣例輸入2

4
3 9 9 3

樣例輸出2

題解

當時想了一個n2的DP，之后發現實在是太naive。

講一下DP思路吧，用f1[i]表示能否將a[1...i]分割成奇數個奇數長度的子串，并且每個子串以奇數開頭結尾，f2[i]表示能否分割成偶數個子串。

于是f1[i]=OR(f2[j] (a[j+1...i]長度為奇數并且以奇數開頭結尾) )，f2[i]=OR(f1[j] (a[j+1...i]長度為奇數并且以奇數開頭結尾) ).

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

這種做法就可以過了，但是有更優秀的做法：

把序列分成奇數個奇數長度的序列，那么這個序列也是奇數長度的。偶數長度的直接No。

再考慮把序列分成兩個以上的序列，那么最開始的序列的起始元素必須是奇數，最末尾的序列的結尾元素也必須是奇數。

這就對應了原序列的第一個與最后一個元素必須是奇數，而這時我們只分一段就好了。

就是說我們只需要判斷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】

目前沒做出來，調出來了再說自己的做法吧

先貼標程：

 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】

題目都沒看懂，真的很難受，這題挺難的。

標程：

 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

"無論目標何在，無論遇見何人，讓我們一同將這首歌傳唱。"

在平面直角坐標系中，有一個長方形舞臺，四角分別是(0,0)，(0,h)，(w,0)，(w,h)。

可以看出在有任何人進入舞臺之前，不會有任何碰撞發生。

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

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

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

按照編舞指導，第i個舞者需要在前ti毫秒內站著不動，然后沿著指定方向以1單位/毫秒的速度前進，直到碰到舞臺的邊界為止。

當兩個舞者碰撞時，她們會立刻改變各自的前進方向，然后繼續沿著新的方向前進。

舞者們只要碰到了舞臺的邊界就會停止，請求出每個舞者最終停下的位置。

輸入

第一行有三個數n,w,h。表示舞者數量，舞臺的長寬。

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

保證0<xi<w，0<yi<h。并保證沒有兩個舞者既在相同的組，還有相同的位置和等待時間。

輸出

n行，每行兩個數xi,yi。表示第i個舞者最終停在哪里。

樣例輸入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

數據范圍及提示

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

對于樣例數據1，這是對應的圖：

對于樣例數據2，沒有舞者碰撞。

題解

很難的一題，不過我看來比C題簡單……

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

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

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

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

對于(pi-ti)相同的舞者，我們如何處理呢？

試著把舞臺斜過來看吧！讓(0,0)在最下方，(w,h)在最頂端，(0,h)在左側，(w,0)在最右側。

這樣，對于那些(pi-ti)相同的舞者，即出發后(xi+yi)相同的舞者們，她們在同一時間點必然處在同一水平線上。

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

這時候的碰撞要如何處理呢？

注意到在沒有碰撞發生前，舞者從左到右的順序是先是水平方向的舞者，坐標從大到小下來，然后是豎直方向的舞者，坐標從小到大往右走。

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

或者……這是另一種形式的交換了呢？注意到在水平方向坐標最大的舞者沒有去到她本來應該去的位置，而是去了豎直方向第一個舞者應該去的位置。

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

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

復雜度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 }