怎么弄网站做网站卖东西,亚购物车功能网站怎么做的,旅游网站建设策划方案,wordpress评论框第三方1.铺瓷砖#xff08;tile.cpp/c/pas#xff09;【问题描述】有一面很长很长的墙。 你需要在这面墙上贴上两行瓷砖。 你的手头有两种不同尺寸的瓷砖#xff0c;你希望用这两种瓷砖各贴一行。瓷砖的长可以用分数表示#xff0c;贴在第一行的每块瓷砖长度为 AB #xff0c;贴… 1.铺瓷砖tile.cpp/c/pas【问题描述】有一面很长很长的墙。 你需要在这面墙上贴上两行瓷砖。 你的手头有两种不同尺寸的瓷砖你希望用这两种瓷砖各贴一行。瓷砖的长可以用分数表示贴在第一行的每块瓷砖长度为 AB 贴在第二行的每块瓷砖长度为CD 。本问题中你并不需要关心瓷砖的宽度。如上图所示 两排瓷砖从同一起始位置开始向右排列 两排瓷砖的第一块的左端的缝隙是对齐的。你想要知道最短铺多少距离后两排瓷砖的缝隙会再一次对齐。【输入】输入的第 1 行包含一个正整数 T表示测试数据的组数。接下来 T 行每行 4 个正整数 ABCD表示该组测试数据中两种瓷砖的长度分别为 AB 和CD 。【输出】输出包含 T 行 第 i 行包含一个分数或整数 表示第 i 组数据的答案。 如果答案为分数则以“X/Y”的格式输出不含引号。分数必须化简为最简形式。如果答案为整数则输出一个整数 X。【输入输出样例 1】tile.in tile.out21 2 1 31 2 5 615/2见选手目录下的 tile/tile1.in 与 tile/tile1.out【输入输出样例 1 说明】对于第一组数据第一行瓷砖贴 2 块第二行贴 3 块总长度都为 1即在距离起始位置长度为 1 的位置两行瓷砖的缝隙会再次对齐。对于第二组数据第一行瓷砖贴 5 块第二行贴 3 块总长度都为 52 。【输入输出样例 2】见选手目录下的 tile/tile2.in 与 tile/tile2.out【数据规模与约定】对于 50%的数据1≤A,B,C,D≤20对于 70%的数据T≤10对于 100%的数据T≤100,0001≤A,B,C,D≤10,000 /*简单数学题 值得一说的是 在linux下%I64d 会wa了23333 然后就wa成傻逼了*/
#includeiostream
#includecstdio
#define ll long long
using namespace std;
ll T,A,B,C,D,lcm,gcd;
ll init(){ll x0;char sgetchar();while(s0||s9)sgetchar();while(s0s9){xx*10s-0;sgetchar();}return x;
}
ll Gcd(ll x,ll y){return y0?x:Gcd(y,x%y);
}
ll Lcm(ll x,ll y){return x/Gcd(x,y)*y;
}
void Printf(ll x,ll y){if(x%y0){coutx/yendl;return;}gcdGcd(x,y);coutx/gcd/y/gcdendl;
}
int main()
{freopen(tile.in,r,stdin);freopen(tile.out,w,stdout);Tinit();while(T--){Ainit();Binit();Cinit();Dinit();lcmLcm(B,D);A*lcm/B;C*lcm/D;Blcm;Dlcm;lcmLcm(A,C);Printf(lcm,B);}return 0;
} View Code 2.小 Y 的问题question.cpp/c/pas【问题描述】有个孩子叫小 Y一天小 Y 拿到了一个包含 n 个点和 n-1 条边的无向连通图图中的点用 1~n 的整数编号。小 Y 突发奇想想要数出图中有多少个“Y 字形”。一个“Y 字形”由 5 个不同的顶点 A、B、C、D、E 以及它们之间的 4 条边组成其中 AB、BC、BD、DE 之间有边相连如下图所示。同时无向图中的每条边都是有一定长度的。一个“Y 字形”的长度定义为构成它的四条边的长度和。小 Y 也想知道图中长度最大的“Y 字形”长度是多少。【输入】第一行包含一个整数 n表示无向图的点数。接下来 n 行每行有 3 个整数 x、y、z表示编号为 x 和 y 的点之间有一条长度为 z 的边。【输出】输出包含 2 行。第 1 行包含一个整数表示图中的“Y 字形”的数量。第 2 行包含一个整数表示图中长度最大的“Y 字形”的长度。【输入输出样例 1】question.in question.out71 3 22 3 13 5 15 4 24 6 35 7 359见选手目录下的 question/question1.in 与 question/question1.out【输入输出样例 1 说明】图中共有 5 个“Y 字形”如图中用红色标出的部分所示。其中长度最大的“Y 字形”是编号 3、5、7、4、6 的顶点构成的那一个长度为 9。【输入输出样例 2】见选手目录下的 question/question2.in 与 question/question2.out【数据规模与约定】对于 30%的数据n≤10对于 60%的数据n≤2,000对于 100%的数据n≤200,0001≤x,y≤n1≤z≤10,000 /*
第一次做的时候傻傻的枚举Y最下面那个 慢死
今天重新打了一下 枚举中间那条边
然后预处理 每个点的度 以及连出去的 最大 次大 次次大
然后搞搞就好了
*/
#includeiostream
#includecstdio
#includecstring
#define maxn 200010
#define ll long long
using namespace std;
int n,m,mx[maxn][3],r[maxn],mxx;
ll ans;
struct node{int u,v,t;
}e[maxn];
int init(){int x0;char sgetchar();while(s0||s9)sgetchar();while(s0s9){xx*10s-0;sgetchar();}return x;
}
void Up(int x,int t){if(tmx[x][0]){mx[x][2]mx[x][1];mx[x][1]mx[x][0];mx[x][0]t;}else if(tmx[x][1]){mx[x][2]mx[x][1];mx[x][1]t;}else if(tmx[x][2])mx[x][2]t;
}
int main()
{freopen(question.in,r,stdin);freopen(question.out,w,stdout);ninit();int u,v,t;for(int i1;in;i){uinit();vinit();tinit();e[i].uu;e[i].vv;e[i].tt;Up(u,t);Up(v,t);r[u];r[v];}for(int i1;in;i){int ue[i].u,ve[i].v;int xr[u]-1,yr[v]-1,z;ans(ll)y*x*(x-1)/2;ans(ll)x*y*(y-1)/2;if(mx[u][0]e[i].t){xmx[u][1];ymx[u][2];}else if(mx[u][1]e[i].t){xmx[u][0];ymx[u][2];}else{xmx[u][0];ymx[u][1];} if(mx[v][0]e[i].t)zmx[v][1];else zmx[v][0];mxxmax(mxx,xyze[i].t);if(mx[v][0]e[i].t){xmx[v][1];ymx[v][2];}else if(mx[v][1]e[i].t){xmx[v][0];ymx[v][2];}else{xmx[v][0];ymx[v][1];}if(mx[u][0]e[i].t)zmx[u][1];else zmx[u][0];mxxmax(mxx,xyze[i].t);}coutansendlmxxendl;return 0;
} View Code 啦啦啦 拼凑的几个题 2 sequence2.1 Description有一个长度为 n 的数列 A每个数 A i (1 ≤ i ≤ n) 都满足 1 ≤ A i ≤ n。我们定义这个数列的好看程度为 j − i 1 的最大值其中 A i ,A i1 ,··· ,A j 都相等。现在你最多能操作 T 次每次操作是将相邻的两个数交换。问该数列好看程度最大能达到多少。2.2 Input第一行两个整数 n,T。第二行 n 个整数其中第 i 个整数表示 A i 。2.3 Output一个整数表示最大能达到的好看程度。2.4 Sample Input7 33 2 2 4 3 2 32.5 Sample Output32.6 Sample Explanation一种最优方案是先将最右边的一个 2 与它左边的 3 交换再将这个 2 与它左边的 4交换这样好看程度为 3。2.7 Constraints一共 10 个测试点每个测试点 10 分只有当你的答案与标准答案完全一致时才能得到10 分否则为 0 分。对于所有测试点1 ≤ T ≤ n 2 。3测试点编号 n 特殊限制1 n ≤ 10 对所有 iA i 1 或 A i 22 n ≤ 10 对所有 iA i 1 或 A i 23 n ≤ 1000 对所有 iA i 1 或 A i 24 n ≤ 1000 对所有 iA i 1 或 A i 25 n ≤ 10 5 对所有 iA i 1 或 A i 26 n ≤ 10 57 n ≤ 10 58 n ≤ 10 6 对所有 iA i 1 或 A i 29 n ≤ 10 610 n ≤ 10 6 /*
暴力骗分 4010 下午看了一眼题解发现自己写慢了
有个性质就是 l-r 区间内的点移动到 中间的时候 总路径最小
然后就剩下的一层枚举中间合并到哪
但是吧 答案来时大一 调了一下午了 还wa这
以后改对了再发喽
*/
#includecstdio
#define maxn 1000010
using namespace std;
int n,T,a[maxn],cnt,sum,f[maxn],ans,P[maxn];
int s1[maxn],s2[maxn],c1[maxn],c2[maxn],p1[maxn],p2[maxn];
int g[maxn],c[maxn],e[maxn];
int init(){int x0,f1;char sgetchar();while(s0||s9){if(s-)f-1;sgetchar();}while(s0s9){xx*10s-0;sgetchar();}return x*f;
}
int max(int x,int y){return xy?x:y;
}
void Insert(){for(int i1;in;i){P[i]P[i-1]i;if(a[i]1){s1[i]s1[i-1]i;s2[i]s2[i-1];c1[i]c1[i-1]1;c2[i]c2[i-1];}else {s2[i]s2[i-1]i;s1[i]s1[i-1];c2[i]c2[i-1]1;c1[i]c1[i-1];}} for(int in;i1;i--)if(a[i]1){p1[i]p1[i1]n-i1;p2[i]p2[i1];}else {p2[i]p2[i1]n-i1;p1[i]p1[i1];}
}
int Ql(int l,int r,int k){//l-r里的k都放到1的花费 if(k1)return s1[r]-s1[l-1];if(k2)return s2[r]-s2[l-1];return g[r]-g[l-1];
}
int q(int l,int r,int k){//l-r里的k的个数 if(k1)return c1[r]-c1[l-1];if(k2)return c2[r]-c2[l-1];return c[r]-c[l-1];
}
int Qr(int l,int r,int k){//l-r里的k都都放到n的花费 if(k1)return p1[l]-p1[r1];if(k2)return p2[l]-p2[r1];return e[l]-e[r1];
}
bool Judge(int l,int k,int r){//l-k-r这一段的a[k]都放到k这里 if(rn)return 0;int mx0,cnt0,s0;mxQl(k,r,a[k]);//右边的 cntq(k,r,a[k]);smx-cnt*k-P[cnt-1];sumcnt;mxQr(l,k,a[k]);//左边的 cntq(l,k,a[k]);smx-cnt*(n-k1)-P[cnt-1];sumcnt-1;return sT;
}
void Solve(){Insert();for(int s1;sn;s)for(int ks1;kn;k){int l0,rn-k1;while(lr){int midlr1;if(Judge(s,k,kmid)){ansmax(ans,sum);lmid1;}else rmid-1;}}
}
void Gao(){int mx0,x,s,ss,t,p;for(int i1;in;i){if(f[i]mx){mxf[i];xi;}a[i]2;}x2;p1;sum0;while(pn){cnt0;ssp;while(a[p]x){cnt;p;}if(cntsum){sumcnt;sss;tp-1;}p;}for(int i1;in;i){P[i]P[i-1]i;if(a[i]x){g[i]g[i-1]i;c[i]c[i-1]1;}else{g[i]g[i-1];c[i]c[i-1];}} for(int in;i1;i--)if(a[i]x)e[i]e[i1]n-i1;else e[i]e[i1];for(int i1;in;i){int l0,rn-s1;while(lr){int midlr1;if(Judge(i,s,smid)){ansmax(ans,sum);lmid1;}else rmid-1;}}for(int i1;in;i){int l0,rn-t1;while(lr){int midlr1;if(Judge(i,t,tmid)){ansmax(ans,sum);lmid1;}else rmid-1;}}
}
int main()
{freopen(seq.in,r,stdin);freopen(seq.ans,w,stdout);ninit();Tinit();for(int i1;in;i){a[i]init();if(f[a[i]]0)cnt;f[a[i]];}if(n1000)Solve();else Gao();printf(%d\n,ans);return 0;
} View Code 3 string3.1 Description给定三个字符串 a,b,s它们的字符集均为 小?字?即 {a, b, ..., z}。令F 0 aF 1 bF i F i−1 F i−2 (i 1)其中 表示字符串的连接。现在有 q 个询问每个询问给定 n,l,r要求在由 F n 的第 l 个到第 r 个字符组成的字符串中s 的出现次数。3.2 Input第一行一个字符串 a。第二行一个字符串 b。第三个一个字符串 s。第四行一个整数 q。接下来 q 行每行三个整数 n,l,r表示一个询问。3.3 Output对每个询问输出一行表示该询问的答案。3.4 Sample Inputabbb444 1 54 1 14 2 46 2 113.5 Sample Output10123.6 Sample Explanation• F 2 “ba”• F 3 “bab”• F 4 “babba”• F 5 “babbabab”• F 6 “babbababbabba”3.7 Constraints一共 10 个测试点每个测试点 10 分只有当你的答案与标准答案完全一致时才能得到10 分否则为 0 分。我们用 |A| 来表示字符串 A 的长度。测试点 a b s n q 特殊限制1 a “a” b “b” s “ba” n ≤ 10 q ≤ 10 l 1,r |F n |2 a “a” b “b” |s| ≤ 10 n ≤ 10 q ≤ 103 a “a” b “b” |s| ≤ 1000 |F n | ≤ 1000 q ≤ 1000 l 1,r |F n |4 |a| ≤ 1000 |b| ≤ 1000 |s| ≤ 1000 |F n | ≤ 1000 q ≤ 10005 a “a” b “b” |s| ≤ 10 5 |F n | ≤ 10 5 q ≤ 10 5 l 1,r |F n |6 |a| ≤ 10 5 |b| ≤ 10 5 |s| ≤ 10 5 |F n | ≤ 10 5 q ≤ 10 57 a “a” b “b” |s| ≤ 10 5 |F n | ≤ 10 18 q ≤ 10 5 l 1,r |F n |8 a “a” b “b” |s| ≤ 10 5 |F n | ≤ 10 18 q ≤ 10 59 |a| ≤ 10 5 |b| ≤ 10 5 |s| ≤ 10 5 |F n | ≤ 10 18 q ≤ 10 5 l 1,r |F n |10 |a| ≤ 10 5 |b| ≤ 10 5 |s| ≤ 10 5 |F n | ≤ 10 18 q ≤ 10 5 /*暴力字符串hash40 正解Orz 3000b看不懂 */
#includeiostream
#includecstdio
#includecstring
#define maxn 100010
#define ll long long
#define P 29
using namespace std;
int n,q,le,x[maxn],l[maxn],r[maxn],f[maxn];
ll ha[100][maxn],Sub,p[maxn];
string S[100],s;
void Get(){p[0]1;for(ll i1;i100000;i)p[i]p[i-1]*P;les.length();for(int i1;ile;i)SubSub*Ps[i-1];
}
void Hash(int x){if(f[x])return;f[x]1;int lenS[x].length();for(int i1;ilen;i)ha[x][i]ha[x][i-1]*PS[x][i-1];
}
ll Query(int x,int l,int r){return ha[x][r]-ha[x][l-1]*p[r-l1];
}
int main()
{freopen(str.in,r,stdin);freopen(str.ans,w,stdout);cinS[0]S[1]sq;for(int i1;iq;i){cinx[i]l[i]r[i];nmax(n,x[i]);}Get();for(int i2;in;i)S[i]S[i-1]S[i-2];for(int i1;in;i)Hash(i);for(int i1;iq;i){int cnt0,lenS[x[i]].length();for(int jl[i];jle-1r[i];j){ll mxQuery(x[i],j,jle-1);if(mxSub)cnt;}printf(%d\n,cnt);}return 0;
} View Code 转载于:https://www.cnblogs.com/yanlifneg/p/6005709.html
