网站建设技术支持,建设工程职称论文查询网站,乐清小程序,付费恶意点击软件Sum of Three
题目大意#xff1a;将一个正整数n分成3个不同的正整数x,y,z,保证三个数都不能整除3#xff0c;如果无法实现就输出NO.
思路#xff1a;这个题实际上特别简单#xff0c;我们可以发现当n比较大的时候#xff0c;我们可以从中取1#xff0c;然后第二个数也…Sum of Three
题目大意将一个正整数n分成3个不同的正整数x,y,z,保证三个数都不能整除3如果无法实现就输出NO.
思路这个题实际上特别简单我们可以发现当n比较大的时候我们可以从中取1然后第二个数也是取一个个位数就能得到答案。所以我们直接暴力。
#includebits/stdc.h
using namespace std;
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);int flag0;for(int i2;in;i){if(i%3(n-i-1)%3i!(n-1-i)i!1n-i-1!1i0n-i-10) {flag1;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一个在BA和B相交或者相切。不过这道题还有一点麻烦的是输出的结果要是小数误差不超过1e-6,这个可以通过设置循环退出的判断条件来实现现在关键的还是check函数我们可以预先计算出O和P到A和B的距离然后确定一个半径后就可以判断在OP是否在AB中以及上面的三种情况是否至少有一种能满足。
#includebits/stdc.h
using namespace std;
double dmax(double a,double b)
{if(ab) return a;else return b;
}
double pa,pb,oa,ob,ab;
int check(double x)
{int cpa0,cpb0,coa0,cob0;if(pax) cpa1;if(pbx) cpb1;if(obx) cob1;if(oax) coa1;if(cpacoa) return 1;//同在aif(cpbcob) return 1;//同在bif((cpbcoa)||(cpacob))//一个在a一个在b{if(ab2*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);pasqrt((xp-xa)*(xp-xa)(yp-ya)*(yp-ya)),pbsqrt((xp-xb)*(xp-xb)(yp-yb)*(yp-yb)),oasqrt((xa)*(xa)(ya)*(ya)),obsqrt((xb)*(xb)(yb)*(yb));absqrt((xb-xa)*(xb-xa)(yb-ya)*(yb-ya));double mxdmax(pa,pb);mxdmax(mx,oa);mxdmax(mx,ob);double l0,rmx;while(r-l1e-8){double mid(lr)/2;if(check(mid)) rmid;else lmid;} printf(%.8lf\n,l);}
}
ps对于浮点数的二分每次更新直接将mid赋值给l或者r即可。
Decreasing String
题目大意我们现有一个字符串s1我们删除一个字符生成s2使s2是所有情况中字典序最小的然后从s2中删除一个字符得到s3要求一样是所有情况中字典序最小的以此类推到仅有一个字母的字符串sm我们将这些都拼起来得到ss1s2s3...sm现在要求的是s的第k位是什么字符s中的下标从1开始。
思路这题很明显是贪心要找到一个最优的删除策略我们先就样例讨论一下 cab ab b 这个是最优的删法可以发现ac且a在c后面所以将c删掉可以降低字典序 然后对于abb的字典序大于a那么就将b删除。 以此类推一个字符串中后一个字母的字典序如果小于前一个字符那么将前一个字母删掉肯定是优解而且因为字典序是从前往后比的所以我们删除的位置越靠前越好。 那么删除的策略就得到了先正序遍历如果后一个字母的字典序小于前一个字母的字典序就将其删除最后得到一个字典序非递减的序列然后再从后往前删除。但是我们注意到一个字母可能不止小于前面一个可能小于前面好几个但是前面的那好几个是非减的关系在它们被访问的时候不会被删除所以我们对于一个小的出现时要往前遍历不能删一个就往后遍历去了因为我们最后想要的是一个非递减的字符串。
然后我们再来考虑因为字符串的长度最大到1e6肯定不能真的暴力把s生成然后遍历去找第k位那么就要想一想有什么可以替代的方法。
我们在遍历的过程中每删除一个字母就相当于生成了一个长度比上一个小1的字符串那么我们将这些长度累计起来sum不就相当于得到了目前已经拼接的字符串的长度一旦它大于等于k那么第k位的字符肯定在我们当前的这个字符串中。然后我们就要来考虑如何可以得到我们当前的字符串。
我们用一个临时变量tmp来存没有在遍历中被弹出的字母这个思路有点像YetnotherrokenKeoard我们只考虑哪些是实际能够出现在结果中的然后当sumk的时候退出遍历然后将后面还没访问到的字符全部放入tmp中得到的字符串就是我们当前的字符串因为删除操作都发生在它前面然后我们只统计了没有被删除的字母然后将后面没删除的字母也放进去那么得到的自然是我们想要的当前字符串因为被删的都去掉了只留下了没被删的那么自然是我们想要的。
然后就要从这个字符串中找我们的结果首先肯定要把这个字符串前面生成的那些字符串的长度从k中减掉才能知道我们想要的结果在当前字符串中是第几位这个的计算可以用等差数列公式来算这里需要累计一下我们当前的字符串是第几个字符串 s1 len s2 len-1 s3 len-2 sm len-m1 alllen(lenlen-m1)*m/2 然后在这个字符串中找目标位置即可。
另外还有一种情况需要考虑就是我们已经得到了一个非递减的字符串tmp后总长度还是小于k那么这种情况下就要从后往前来弹出进而生成新字符串剩下的处理和上面类似。
#includebits/stdc.h
using namespace std;
#define int long long
signed main()
{int t;scanf(%lld,t);while(t--){string s,tmp;cins;int k;scanf(%lld,k);int ls.size(),sums.size(),i,c1;for(i0;is.size()-1;i){if(sumk) break;tmp s[i];if(s[i1]s[i]) {int jtmp.size()-1,di1;while(s[d]tmp[j]tmp.size())//虽然比前面的小但是前面那个根本没被放进去,所以我们只用考虑被放入的那些{l - 1, sum l,c;//新生成一个字串tmp.pop_back();if(sumk) break;j--;}}}for(ii;is.size();i) tmp s[i];if(sumk){c--;int lens.size();k-(lenlen-c1)*c/2;//答案在此时的tmp中但是要确定是第几个那么就要将前面的都减掉for(int j0;jtmp.size();j){if(j1k) {couttmp[j];break;}}}else{for(int itmp.size();i0;i--){l - 1,sum l,c,tmp.pop_back();if(sumk) break; //加上此时的tmp后超了}c--;int lens.size();k-(lenlen-c1)*c/2;for(int j0;jtmp.size();j){if(j1k) {couttmp[j];break;}}}}
}
