[TIOJ]1865. 小向的魔法術鬣
題目連結： http://tioj.infor.org/problems/1865 這一題超梗的ww 在看完題目之後不難發現一種Greedy解，即為發現這兩項不是hao的就Operate，並往前檢查有沒有因為這一次Operate而讓之前的變不hao。 如下 # include " lib1865.h " int main (){ int n = GetN(); for(int i = 0 ; i < n-1 ; i++){ if(! Magic_Isdivide (i)){ Magic_Operate(i); for(int j = i-1 ; j >= 0 ; j--){ if(! Magic_Isdivide (j)) Magic_Operate (j); else break; } } } End(); } 但這樣會因為使用太多次魔法而WA。 AC解法： 最慘的狀況就是每一項都需要Operate 然後每一次都需要一直往回Operate到第0項。 加上如果 a丨b ， 對它們Operate還是會維持原樣。 所以直接考慮最慘狀況，不使用Magic_Isdivide 最多只需要用到 (1+999)*999/2 = 499500次。 # include " lib1865.h " int main (){ int n = GetN(); for(int i=0;i<n-1;i++)for(int j=i;j>=0;j--) Magic_Operate(j); End(); }