Sum of Three

題目大意：將一個正整數n分成3個不同的正整數x,y,z,保證三個數都不能整除3，如果無法實現就輸出NO.

思路：這個題實際上特別簡單，我們可以發現當n比較大的時候，我們可以從中取1，然后第二個數也是取一個個位數就能得到答案。所以我們直接暴力。

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);int flag=0;for(int i=2;i<n;i++){if(i%3&&(n-i-1)%3&&i!=(n-1-i)&&i!=1&&n-i-1!=1&&i>0&&n-i-1>0) {flag=1;printf("YES\n");printf("1 %d %d\n",i,n-i-1);break;}}if(!flag) printf("NO\n"); }
}

Fear of the Dark

題目大意：我們要從點(0,0)到點P，現在有A,B兩個燈籠，分別在(xa,ya),(xb,yb)位置處，我們可以調節功率，也即燈光的半徑，最終要實現從O到P都是被照亮的，求最小的功率。

思路：這題要求最小的功率，首先想到二分，那么現在的問題就是check函數怎么寫，實際上合法的只有三種情況，O,P同在A中，同在B中，一個在A，一個在B，A和B相交或者相切。不過這道題還有一點麻煩的是輸出的結果要是小數，誤差不超過1e-6,這個可以通過設置循環退出的判斷條件來實現，現在關鍵的還是check函數，我們可以預先計算出O和P到A和B的距離，然后確定一個半徑后就可以判斷在OP是否在AB中，以及上面的三種情況是否至少有一種能滿足。

#include<bits/stdc++.h>
using namespace std;
double dmax(double a,double b)
{if(a>b) return a;else return b;
}
double pa,pb,oa,ob,ab;
int check(double x)
{int cpa=0,cpb=0,coa=0,cob=0;if(pa<=x) cpa=1;if(pb<=x) cpb=1;if(ob<=x) cob=1;if(oa<=x) coa=1;if(cpa&&coa) return 1;//同在aif(cpb&&cob) return 1;//同在bif((cpb&&coa)||(cpa&&cob))//一個在a，一個在b{if(ab<=2*x) return 1;//ab相切或相交else return 0;}return 0;
}
int main()
{int t;scanf("%d",&t);while(t--){double xp,yp,xa,ya,xb,yb;scanf("%lf%lf%lf%lf%lf%lf",&xp,&yp,&xa,&ya,&xb,&yb);pa=sqrt((xp-xa)*(xp-xa)+(yp-ya)*(yp-ya)),pb=sqrt((xp-xb)*(xp-xb)+(yp-yb)*(yp-yb)),oa=sqrt((xa)*(xa)+(ya)*(ya)),ob=sqrt((xb)*(xb)+(yb)*(yb));ab=sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));double mx=dmax(pa,pb);mx=dmax(mx,oa);mx=dmax(mx,ob);double l=0,r=mx;while(r-l>1e-8){double mid=(l+r)/2;if(check(mid)) r=mid;else l=mid;}	printf("%.8lf\n",l);}
}

ps：對于浮點數的二分，每次更新直接將mid賦值給l或者r即可。

Decreasing String

題目大意：我們現有一個字符串s1，我們刪除一個字符生成s2，使s2是所有情況中字典序最小的，然后從s2中刪除一個字符得到s3，要求一樣，是所有情況中字典序最小的，以此類推到僅有一個字母的字符串sm，我們將這些都拼起來得到s=s1+s2+s3+...+sm，現在要求的是s的第k位是什么字符，s中的下標從1開始。

思路：這題很明顯是貪心，要找到一個最優的刪除策略，我們先就樣例討論一下：

cab

ab

b

這個是最優的刪法，可以發現a<c，且a在c后面，所以將c刪掉可以降低字典序

然后對于ab，b的字典序大于a，那么就將b刪除。

以此類推，一個字符串中后一個字母的字典序如果小于前一個字符，那么將前一個字母刪掉，肯定是優解，而且因為字典序是從前往后比的，所以我們刪除的位置越靠前越好。

?那么刪除的策略就得到了，先正序遍歷，如果后一個字母的字典序小于前一個字母的字典序，就將其刪除，最后得到一個字典序非遞減的序列，然后再從后往前刪除。但是我們注意到，一個字母可能不止小于前面一個，可能小于前面好幾個，但是前面的那好幾個是非減的關系，在它們被訪問的時候不會被刪除，所以我們對于一個小的出現時要往前遍歷，不能刪一個就往后遍歷去了，因為我們最后想要的是一個非遞減的字符串。

然后我們再來考慮，因為字符串的長度最大到1e6，肯定不能真的暴力把s生成，然后遍歷去找第k位，那么就要想一想，有什么可以替代的方法。

我們在遍歷的過程中，每刪除一個字母，就相當于生成了一個長度比上一個小1的字符串，那么我們將這些長度累計起來（sum），不就相當于得到了目前已經拼接的字符串的長度，一旦它大于等于k，那么第k位的字符肯定在我們當前的這個字符串中。然后我們就要來考慮，如何可以得到我們當前的字符串。

我們用一個臨時變量tmp來存沒有在遍歷中被彈出的字母，這個思路有點像YetnotherrokenKeoard，我們只考慮哪些是實際能夠出現在結果中的，然后當sum>=k的時候退出遍歷，然后將后面還沒訪問到的字符全部放入tmp中，得到的字符串就是我們當前的字符串，因為刪除操作都發生在它前面，然后我們只統計了沒有被刪除的字母，然后將后面沒刪除的字母也放進去，那么得到的自然是我們想要的當前字符串，因為被刪的都去掉了，只留下了沒被刪的，那么自然是我們想要的。

然后就要從這個字符串中找我們的結果，首先肯定要把這個字符串前面生成的那些字符串的長度從k中減掉，才能知道我們想要的結果，在當前字符串中是第幾位，這個的計算可以用等差數列公式來算（這里需要累計一下，我們當前的字符串是第幾個字符串）

s1 len

s2 len-1

s3 len-2

sm len-m+1

alllen=(len+len-m+1)*m/2

然后在這個字符串中找目標位置即可。

另外還有一種情況需要考慮，就是我們已經得到了一個非遞減的字符串tmp后，總長度還是小于k，那么這種情況下就要從后往前來彈出，進而生成新字符串，剩下的處理和上面類似。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{int t;scanf("%lld",&t);while(t--){string s,tmp="";cin>>s;int k;scanf("%lld",&k);int l=s.size(),sum=s.size(),i,c=1;for(i=0;i<s.size()-1;i++){if(sum>=k) break;tmp += s[i];if(s[i+1]<s[i]) {int j=tmp.size()-1,d=i+1;while(s[d]<tmp[j]&&tmp.size())//雖然比前面的小，但是前面那個根本沒被放進去,所以我們只用考慮被放入的那些{l -= 1, sum += l,c++;//新生成一個字串tmp.pop_back();if(sum>=k) break;j--;}}}for(i=i;i<s.size();i++) tmp += s[i];if(sum>=k){c--;int len=s.size();k-=(len+len-c+1)*c/2;//答案在此時的tmp中，但是要確定是第幾個，那么就要將前面的都減掉for(int j=0;j<tmp.size();j++){if(j+1==k) {cout<<tmp[j];break;}}}else{for(int i=tmp.size();i>=0;i--){l -= 1,sum += l,c++,tmp.pop_back();if(sum>=k) break; //加上此時的tmp后超了}c--;int len=s.size();k-=(len+len-c+1)*c/2;for(int j=0;j<tmp.size();j++){if(j+1==k) {cout<<tmp[j];break;}}}}
}