中小企业门户网站的建设方案,支付通道网站怎么做,东莞做网站优化哪家好,视频网站怎么建传送门:CF
A题:A-characteristic
构造一个只有 1 , − 1 1,-1 1,−1的数组,满足乘积为 1 1 1的数对的个数为 k k k. 发现 n n n的范围很小,考虑直接暴力枚举数组中 1 1 1的个数,记为 i i i,那么对于1的所有数对来说,我们有 i ∗ ( i − 1 ) / 2 i*(i-1)/2 i∗(i−1)/2个,然后…传送门:CF
A题:A-characteristic
构造一个只有 1 , − 1 1,-1 1,−1的数组,满足乘积为 1 1 1的数对的个数为 k k k. 发现 n n n的范围很小,考虑直接暴力枚举数组中 1 1 1的个数,记为 i i i,那么对于1的所有数对来说,我们有 i ∗ ( i − 1 ) / 2 i*(i-1)/2 i∗(i−1)/2个,然后对于 − 1 -1 −1的个数也不难表示出为 n − i n-i n−i,然后此时的贡献为 ( n − i − 1 ) ∗ ( n − i ) / 2 (n-i-1)*(n-i)/2 (n−i−1)∗(n−i)/2,判断即可
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int Tread();while(T--) {int nread(),kread();int ans1-1,ans2-1;for(int i1;in;i) {int jn-i;if((i-1)*i/2(j-1)*j/2k) {ans1i;ans2j;break;}}if(ans1-1) {coutNOendl;}else {coutYESendl;for(int i1;ians1;i) {cout1 ;}for(int i1;ians2;i) {cout-1 ;}coutendl;}}return 0;
}B题:Sort with Step
因为我们只能调换相距为 k k k的数对,那么我们可以将这个数组分为几个轨道,每一个轨道上的数字可以进行交换,不在同一个轨道上的数字不能进行交换.那么假设我们需要进行交换,也肯定是交换不在自己应该在的轨道上的那两个数字.所以我们可以直接记录不在自己应该在的轨道上的数字的个数(记为 k k k).因为我们唯一能使最后序列满足的情况就是将所有数字换到他们应该在的地方.所以当 k k k等于 1 1 1的时候代表其不需要进行初步交换,反之则需要进行 k k k次交换.
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
int main() {int Tread();while(T--) {int nread(),kread();for(int i1;in;i) {a[i]read();}int cnt0;int pos-1;for(int i1;in;i) {if(abs(i-a[i])%k!0) {cnt;}}if(cnt0) {cout0endl;}else {if(cnt2) {cout1endl;}else {cout-1endl;}}}return 0;
}C题:Strongly Composite
一道需要进行分解质因数的题目.首先我们发现b数组的乘积要和a数组一样.那么不妨将a数组中的乘积进行一个分解质因数,先预处理存起来.显然我们最终b数组的所有数字就是由这些质因数组合而成 然后我们考虑强复合的性质.我们贪心的去想,肯定是用最小个数的质因数来组成一个数字是最优的.所以此时我们有两种组合方式: 1.我们拿两个相同的数来组成一个数 b i bi bi,此时我们的 b i bi bi显然是一个平方数,因为其实由两个质数组合而成,所以此时 b i bi bi显然是一个强复合. 2.显然1方案是最优的方案(因为花费的数字最少).但是此方案需要相同的数字.在1的方案下我们用完了所有的相同的数字,那么此时我们剩下来的就是不同的数字了.我们此时会发现一个很有趣的性质,我们拿出三个质数(记为 i i i, j j j, k k k)乘起来显然是一个强复合.因为两个质数乘起来肯定是一个合数,然后三个质数乘起来显然也是一个合数.又因为质因数的性质,此时我们的因子就是 1 , i , j , k , i ∗ j , i ∗ k , j ∗ k , i ∗ j ∗ k 1,i,j,k,i*j,i*k,j*k,i*j*k 1,i,j,k,i∗j,i∗k,j∗k,i∗j∗k,发现恰好是一个强复合数
至此本题也就不难解决了. 本部分介绍一下质因数分解算法的证明,如果熟悉的可以跳过:
for(int j2;j__builtin_sqrt(a[i]);j) {while(temp%j0) {mp[j];temp/j;}
}
if(temp!1) mp[temp];不难发现上述算法只判断到了 n \sqrt{n} n .下面证明一下这个算法的正确性. 首先证明这么做的得到的所有 j j j都是质数: 对于本部分采用反证法进行证明,假设我们当前枚举到的因子 j j j不是一个质数,那么他肯定是一个合数.此时根据唯一分解定理, j j j可以分解成 p 1 k 1 ∗ p 2 k 2 ∗ . . . ∗ p n k n p_1^{k_1}*p_2^{k_2}*...*p_n^{k_n} p1k1∗p2k2∗...∗pnkn这样的形式,那么必然存在 p i j p_ij pij,但是这样的因子我们在之前枚举到 p i p_i pi时的 w h i l e ( t e m p % j 0 ) while(temp\%j0) while(temp%j0)已经消掉了,所以不存在这种情况,所以 j j j必然是一个质数 接下来证明一下为什么只需要枚举到 n \sqrt{n} n ,也就是证明一下最后剩下来的那个数字要么是1要么是一个大于 n \sqrt{n} n 的质数 同样采取反证法进行证明,假设最后存在的那个数字k是一个大于 n \sqrt{n} n 的合数.那么根据之前的证明我们会发现这个合数必然是不存在小于 n \sqrt{n} n 的因子的.又因为他是一个合数,所以必然有两个大于 n \sqrt{n} n 的因子,但是此时两个因子相乘得到的数显然比 n n n大,这是不合理的.所以最后剩下来的那个数必然是一个质数 至此证毕 #include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define int long long
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];mapint,intmp;
mapint,intmp2;
signed main() {int Tread();while(T--) {int nread();mp.clear();mp2.clear();ll sum1;int cnt0;int ans0;for(int i1;in;i) {a[i]read();int tempa[i];if(a[i]1) continue;for(int j2;j__builtin_sqrt(a[i]);j) {while(temp%j0) {mp[j];temp/j;}} if(temp!1) mp[temp];}for(auto it : mp) {ansit.second/2;mp[it.first]it.second-it.second/2*2;}for(auto it : mp) {cntit.second;}anscnt/3;coutansendl;}return 0;
}D题:Unique Palindromes
首先我们需要知道这样的一个事实,也就是我们每一次在一个字符串的后缀中加上一个任意字符a,我们的回文子串的增加个数最大为1. 简单证明一下这个结论: 我们假设现在有一个字符串为 s s s,那么假设我们此时加上一个 a a a使其增加了回文子串的个数.因为子串是连续的,所以此时我们不妨设多出了两个回文子串 s 1 a , s 2 a s1a,s2a s1a,s2a,并且 s 2 s2 s2是 s 1 s1 s1的后缀.不难发现 s 1 a s1a s1a包含了 s 2 a s2a s2a,又因为 s 1 a s1a s1a是一个回文串,所以 s 2 a s2a s2a既是 s 1 a s1a s1a的后缀又是它的前缀.那么此时要么 s 2 a s 1 a s2as1a s2as1a,要么 s 2 a s2a s2a是被 s 2 s2 s2包含的.因为当 s 2 a s2a s2a的长度小于 s 1 a s1a s1a时,又因为是前缀,显然它是被 s 2 s2 s2包含的, s 2 a s2a s2a的长度又不可能大于 s 1 a s1a s1a 至此证毕
所以显然当存在 c [ i ] − c [ i − 1 ] x [ i ] − x [ i − 1 ] c[i]-c[i-1]x[i]-x[i-1] c[i]−c[i−1]x[i]−x[i−1]时我们是无法构造的.此处特判一下 然后我们考虑构造,因为ci3.所以考虑将abc作为前缀,当我们此时的c1不够时不断的补上字符c来使得其满足.可能会存在回文子串够了但是长度不够的情况.所以我们此时需要补上后缀.此时我们可以反复的补上abc.举个简单的栗子: a b c c c ∣ a b c a b c a abccc\;|\; abcabca abccc∣abcabca,此时我们会很神奇的发现这样就不会增加回文子串了. 然后我们遇到了后面的回文条件.为了不会和前面已有的字符形成回文子串,我们考虑使用新的字符即可,比如 d , e , f . . . d,e,f... d,e,f....我们发现k20.所以我们的26个字符是够用的.每一次多增加一个字符我们就可以得到一个贡献,当我们的贡献满时继续使用abc填满即可. 注意此时有一个小细节,我们此时的填充需要继续上述的循环,不然可能出现下述情况:ccc ∣ \;|\; ∣abca ∣ \;|\; ∣dda,我们会发现会导致意外增加了一个回文子串.
光讲可能比较难以理解,建议结合代码食用
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int x[maxn],c[maxn];
int main() {int Tread();while(T--) {int nread(),kread();for(int i1;ik;i) x[i]read();for(int i1;ik;i) c[i]read();int flag0;for(int i1;ik;i) {if(c[i]-c[i-1]x[i]-x[i-1]) {flag1;break;}}if(flag1) {coutNOendl;continue;}vectorcharans;char kkkc;ans.push_back(a);ans.push_back(b);ans.push_back(c);int pos4;int hhh3;char loopa;for(int i1;ik;i) {if(i1) {while(posx[i]) {if(posc[i]) {ans.push_back(c);}else {ans.push_back(loop);loop;if(loopd) loopa;}pos;}}else{while(posx[i]) {if(x[i]-pos1c[i]-c[i-1]) {//先达成条件再补长度ans.push_back(loop);loop;if(loopd) loopa;}else {ans.push_back(ci-1);}pos;}}}coutYESendl;for(int i0;ians.size();i) coutans[i];coutendl;}return 0;
}
文章转载自： http://www.morning.ydfr.cn.gov.cn.ydfr.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn http://www.morning.rlfr.cn.gov.cn.rlfr.cn http://www.morning.zkgpg.cn.gov.cn.zkgpg.cn http://www.morning.tzmjc.cn.gov.cn.tzmjc.cn http://www.morning.hrzymy.com.gov.cn.hrzymy.com http://www.morning.mhybs.cn.gov.cn.mhybs.cn http://www.morning.ywzqk.cn.gov.cn.ywzqk.cn http://www.morning.tmjhy.cn.gov.cn.tmjhy.cn http://www.morning.trfh.cn.gov.cn.trfh.cn http://www.morning.ryxbz.cn.gov.cn.ryxbz.cn http://www.morning.sqfrg.cn.gov.cn.sqfrg.cn http://www.morning.lmcrc.cn.gov.cn.lmcrc.cn http://www.morning.nxstj.cn.gov.cn.nxstj.cn http://www.morning.jxfsm.cn.gov.cn.jxfsm.cn http://www.morning.ggtkk.cn.gov.cn.ggtkk.cn http://www.morning.ljjph.cn.gov.cn.ljjph.cn http://www.morning.srnhk.cn.gov.cn.srnhk.cn http://www.morning.ckxd.cn.gov.cn.ckxd.cn http://www.morning.pbxkk.cn.gov.cn.pbxkk.cn http://www.morning.prkdl.cn.gov.cn.prkdl.cn http://www.morning.yhpl.cn.gov.cn.yhpl.cn http://www.morning.rccpl.cn.gov.cn.rccpl.cn http://www.morning.krkwh.cn.gov.cn.krkwh.cn http://www.morning.rrwgh.cn.gov.cn.rrwgh.cn http://www.morning.ghssm.cn.gov.cn.ghssm.cn http://www.morning.cpfbg.cn.gov.cn.cpfbg.cn http://www.morning.gassnw.com.gov.cn.gassnw.com http://www.morning.cyysq.cn.gov.cn.cyysq.cn http://www.morning.wwwghs.com.gov.cn.wwwghs.com http://www.morning.kcbml.cn.gov.cn.kcbml.cn http://www.morning.ryrgx.cn.gov.cn.ryrgx.cn http://www.morning.rythy.cn.gov.cn.rythy.cn http://www.morning.sffkm.cn.gov.cn.sffkm.cn http://www.morning.qtqjx.cn.gov.cn.qtqjx.cn http://www.morning.lthtp.cn.gov.cn.lthtp.cn http://www.morning.xmyrn.cn.gov.cn.xmyrn.cn http://www.morning.yzygj.cn.gov.cn.yzygj.cn http://www.morning.c7627.cn.gov.cn.c7627.cn http://www.morning.nckzt.cn.gov.cn.nckzt.cn http://www.morning.rycd.cn.gov.cn.rycd.cn http://www.morning.nwcgj.cn.gov.cn.nwcgj.cn http://www.morning.nbdtdjk.cn.gov.cn.nbdtdjk.cn http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.kxscs.cn.gov.cn.kxscs.cn http://www.morning.yfmwg.cn.gov.cn.yfmwg.cn http://www.morning.ltdrz.cn.gov.cn.ltdrz.cn http://www.morning.ldnrf.cn.gov.cn.ldnrf.cn http://www.morning.qnftc.cn.gov.cn.qnftc.cn http://www.morning.jykzy.cn.gov.cn.jykzy.cn http://www.morning.nwqyq.cn.gov.cn.nwqyq.cn http://www.morning.fqtzn.cn.gov.cn.fqtzn.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.wxfjx.cn.gov.cn.wxfjx.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.stcds.cn.gov.cn.stcds.cn http://www.morning.hwprz.cn.gov.cn.hwprz.cn http://www.morning.zdzgf.cn.gov.cn.zdzgf.cn http://www.morning.ysrtj.cn.gov.cn.ysrtj.cn http://www.morning.smdnl.cn.gov.cn.smdnl.cn http://www.morning.pffqh.cn.gov.cn.pffqh.cn http://www.morning.nytqy.cn.gov.cn.nytqy.cn http://www.morning.ghrlx.cn.gov.cn.ghrlx.cn http://www.morning.jqcrf.cn.gov.cn.jqcrf.cn http://www.morning.tsnq.cn.gov.cn.tsnq.cn http://www.morning.gwzfj.cn.gov.cn.gwzfj.cn http://www.morning.nbgfz.cn.gov.cn.nbgfz.cn http://www.morning.yrpd.cn.gov.cn.yrpd.cn http://www.morning.prjns.cn.gov.cn.prjns.cn http://www.morning.cwpny.cn.gov.cn.cwpny.cn http://www.morning.qgkcs.cn.gov.cn.qgkcs.cn http://www.morning.ltpph.cn.gov.cn.ltpph.cn http://www.morning.jhxdj.cn.gov.cn.jhxdj.cn http://www.morning.nxfwf.cn.gov.cn.nxfwf.cn http://www.morning.wdpt.cn.gov.cn.wdpt.cn http://www.morning.mingjiangds.com.gov.cn.mingjiangds.com http://www.morning.pqypt.cn.gov.cn.pqypt.cn http://www.morning.nchlk.cn.gov.cn.nchlk.cn http://www.morning.gtnyq.cn.gov.cn.gtnyq.cn http://www.morning.tpnxj.cn.gov.cn.tpnxj.cn
