石家庄哪里做网站比较好,哈尔滨seo,网站建设基本情况介绍,贵阳网站建设制作价格题目#xff1a; 1.寿司 给定一个环形的RB串要求经过两两互换后RB分别形成两段连续区域,求最少操作次数(算法时间O(n)) 2.金字塔 给定一个金字塔的侧面图有n层已知每一层的宽度高度均为1要求在图中取出恰好K个互不相交的矩形#xff08;边缘可以重叠#xff09;,求最多可以取… 题目 1.寿司 给定一个环形的RB串··要求经过两两互换后RB分别形成两段连续区域,求最少操作次数(算法时间O(n)) 2.金字塔 给定一个金字塔的侧面图有n层··已知每一层的宽度··高度均为1··要求在图中取出恰好K个互不相交的矩形边缘可以重叠,求最多可以取出多少面积 n20000k100 3.心灵治愈 给定n,m要求取出不大于m的n个正整数,问有多少种取法使n个数和m的最大公因数为1,n,m10^15 题解 1.分析 首先为了方便我们把环从中间断开看成一个序列我们考虑如果移动R串··那么肯定是找到某一B为中心··B的左边R移到一起··B的右边R移到一起(这里描述有点模糊···如果序列左边的R都移到一起且序列最左边为R右边同理··则实际在环中R肯定是连续的一段··) 因此我们先随意找一个B为中心··然后计算答案··之后我们一次将序列最左端的字符移到最右端(比如序列BBRRR移动后就变成BRRRB)然后考虑答案的变化即可···具体实现参见代码 #includeiostream
#includecstdio
#includecstdlib
#includecmath
#includectime
#includecctype
#includecstring
#includestring
#includealgorithm
using namespace std;
const int N2e65;
int T,n,num[N];
char s[N];
int main()
{//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);scanf(%d,T);while(T--){long long ans0,cnt0;int tot10,tot20,totl0,totr0,mid;scanf(%s,s1);nstrlen(s1);for(int i1;in;i){if(s[i]B) num[i]num[in]1,tot1;else num[i]num[in]2,tot2;}int half(tot11)/2;int temp0;for(int i1;in;i){if(num[i]1) {temp;if(temphalf) midi;}else{if(temphalf){totl;cnttemp;}else {totr;cnt(tot1-temp);}}}anscnt;for(int i1;in;i){if(num[i]1){ int tot0,j;for(jmid1;num[j]!1;j) tot; cnt-totl;cnt(totr-tot);midj;totltot;totr-tot;if(tot1%20) cnt-tot;ansmin(ans,cnt);}else {totl-1;totr1; }}coutansendl;}return 0;
} 2.dp决策单调性/斜率优化 dp方程肯定很好想··第一要明确取的方案··我们肯定是以某一层的宽度为矩形的一边··然后往下取到某一层为一个矩形·矩形的高就是两层高的差·· 然后设f[j][i]为第j块矩形以第i层为一边的最大面积··转移方程即为 f[j][i]max(f[j][i],f[k][i-1](long long)len[j]*(j-k)); 其中k为我们往下枚举的层数··len为j层的宽度·· 然后通过打表(dalao也可以分析)得出该方程满足决策单调性且使用于斜率优化····这里两种方法都能过 决策单调性 #includeiostream
#includecstdio
#includecstdlib
#includecmath
#includectime
#includecctype
#includestring
#includecstring
#includealgorithm
using namespace std;
inline int R()
{char c;int f0;for(cgetchar();c0||c9;cgetchar());for(;c9c0;cgetchar()) f(f3)(f1)c-0;return f;
}
const int N20005;
const int M105;
struct node
{int l,r,pos;
}Que[N];
int n,K;
long long len[N],f[N][M];
inline long long calc(int i,int j,int now)
{return f[j][now-1](long long)len[i]*(i-j);
}
inline int find(node a,int b,int now)
{int lea.l,ria.r,ansa.r1;while(leri){int mid(leri)/2;if(calc(mid,b,now)calc(mid,a.pos,now)) rimid-1,ansmid;else lemid1;}return ans;
}
inline void dp(int now)
{int Head1,Tail0;node tmp;tmp.lnow;tmp.rn;tmp.posnow-1;Que[Tail]tmp;for(int inow;in;i){while(Que[Head].ri) Head;f[i][now]calc(i,Que[Head].pos,now);if(calc(n,i,now)calc(n,Que[Tail].pos,now)){while(HeadTailcalc(Que[Tail].l,i,now)calc(Que[Tail].l,Que[Tail].pos,now)) Tail--;if(HeadTail){int tfind(Que[Tail],i,now);Que[Tail].rt-1;node tmp;tmp.lt,tmp.rn,tmp.posi;Que[Tail]tmp;}else{node tmp;tmp.li1;tmp.rn;tmp.posi;Que[Tail]tmp;}}}
}
int main()
{//freopen(pyramid.out,w,stdout);nR(),KR();int x,y;if(n1000){ for(int i1;in;i){xR(),yR();len[i]y-x1;f[i][1](long long)len[i]*i;}for(int i2;iK;i)for(int ji;jn;j)for(int ki-1;kj;k) f[j][i]max(f[j][i],f[k][i-1](long long)len[j]*(j-k));long long ans0;for(int iK;in;i) ansmax(f[i][K],ans);coutans\n;}else{for(int i1;in;i){xR(),yR();len[i]y-x1;f[i][1](long long)len[i]*i;}for(int i2;iK;i)dp(i);long long ans0;for(int iK;in;i) ansmax(f[i][K],ans); coutans\n;}return 0;
} 3.质因数分解容斥原理 这道题和之前跳蚤的那道题是一模一样的··这里就并不多说了·· 唯一注意的是我发现了自己快速幂的一个漏洞··求a^b之前要将a取模···之前一直没有注意到···还有就是注意最后答案为负的问题 #includeiostream
#includecstdio
#includecstdlib
#includecmath
#includectime
#includecctype
#includecstring
#includestring
#includealgorithm
#includevector
using namespace std;
vectorlong longzhiyinzi;
const long long mod1e97;
long long n,m,ans0;
inline long long ksm(long long a,long long b)
{long long ans1;a%mod; while(b){if(b%21) ans(ans*a)%mod;b/2;a(a*a)%mod;}return ans;
}
inline void dfs(int u,long long tot,long long f)
{if(uzhiyinzi.size()){long long tempm/tot;ans(ansf*ksm(temp,n))%mod;ans(ans%modmod)%mod;return;}dfs(u1,tot,f);dfs(u1,tot*zhiyinzi[u],-f);
}
int main()
{scanf(%I64d%I64d,n,m);long long tempm;for(long long i2;i*im;i){if(itemp) break; if(temp%i0){ while(temp%i0) temp/i;zhiyinzi.push_back(i);}}if(temp!1) zhiyinzi.push_back(temp);dfs(0,1,1);ans(ans%modmod)%mod;coutansendl;return 0;
} 转载于:https://www.cnblogs.com/AseanA/p/7745338.html
