1.铺瓷砖
（tile.cpp/c/pas）【问题描述】有一面很长很长的墙。 你需要在这面墙上贴上两行瓷砖。 你的手头有两种不同尺寸的瓷砖，你希望用这两种瓷砖各贴一行。瓷砖的长可以用分数表示，贴在第一行的每块瓷砖长度为 AB ，贴在第二行的每块瓷砖长度为CD 。本问题中你并不需要关心瓷砖的宽度。如上图所示， 两排瓷砖从同一起始位置开始向右排列， 两排瓷砖的第一块的左端的缝隙是对齐的。你想要知道，最短铺多少距离后，两排瓷砖的缝隙会再一次对齐。【输入】输入的第 1 行包含一个正整数 T，表示测试数据的组数。接下来 T 行，每行 4 个正整数 A，B，C，D，表示该组测试数据中，两种瓷砖的长度分别为 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,000，1≤A,B,C,D≤10,000
/*简单数学题 值得一说的是 在linux下%I64d 会wa了23333 然后就wa成傻逼了*/#include#include #define ll long longusing namespace std;ll T,A,B,C,D,lcm,gcd;ll init(){ ll x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x;}ll Gcd(ll x,ll y){ return y==0?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%y==0){ cout<
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,000，1≤x,y≤n，1≤z≤10,000
/*第一次做的时候傻傻的枚举Y最下面那个 慢死今天重新打了一下 枚举中间那条边然后预处理 每个点的度 以及连出去的 最大 次大 次次大然后搞搞就好了 */#include#include #include #define maxn 200010#define ll long longusing namespace std;int n,m,mx[maxn][3],r[maxn],mxx;ll ans;struct node{ int u,v,t;}e[maxn];int init(){ int x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x;}void Up(int x,int t){ if(t>=mx[x][0]){ mx[x][2]=mx[x][1];mx[x][1]=mx[x][0];mx[x][0]=t; } else if(t>=mx[x][1]){ mx[x][2]=mx[x][1];mx[x][1]=t; } else if(t>=mx[x][2])mx[x][2]=t;}int main(){ freopen("question.in","r",stdin); freopen("question.out","w",stdout); n=init(); int u,v,t; for(int i=1;i
啦啦啦 拼凑的几个题
2 sequence
2.1 Description有一个长度为 n 的数列 A，每个数 A i (1 ≤ i ≤ n) 都满足 1 ≤ A i ≤ n。我们定义这个数列的好看程度为 j − i + 1 的最大值，其中 A i ,A i+1 ,··· ,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 对所有 i，A i = 1 或 A i = 22 n ≤ 10 对所有 i，A i = 1 或 A i = 23 n ≤ 1000 对所有 i，A i = 1 或 A i = 24 n ≤ 1000 对所有 i，A i = 1 或 A i = 25 n ≤ 10 5 对所有 i，A i = 1 或 A i = 26 n ≤ 10 57 n ≤ 10 58 n ≤ 10 6 对所有 i，A i = 1 或 A i = 29 n ≤ 10 610 n ≤ 10 6 /*暴力+骗分 40+10 下午看了一眼题解发现自己写慢了 有个性质就是 l-r 区间内的点移动到 中间的时候 总路径最小然后就剩下的一层枚举中间合并到哪但是吧 答案来时大一 调了一下午了 还wa这以后改对了再发喽 */#include#define maxn 1000010using 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 x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){ if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f;}int max(int x,int y){ return x>y?x:y;}void Insert(){ for(int i=1;i<=n;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 i=n;i>=1;i--) if(a[i]==1){ p1[i]=p1[i+1]+n-i+1;p2[i]=p2[i+1]; } else { p2[i]=p2[i+1]+n-i+1;p1[i]=p1[i+1]; }}int Ql(int l,int r,int k){ //l-r里的k都放到1的花费 if(k==1)return s1[r]-s1[l-1]; if(k==2)return s2[r]-s2[l-1]; return g[r]-g[l-1];}int q(int l,int r,int k){ //l-r里的k的个数 if(k==1)return c1[r]-c1[l-1]; if(k==2)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(k==1)return p1[l]-p1[r+1]; if(k==2)return p2[l]-p2[r+1]; return e[l]-e[r+1];}bool Judge(int l,int k,int r){ //l-k-r这一段的a[k]都放到k这里 if(r>n)return 0; int mx=0,cnt=0,s=0; mx=Ql(k,r,a[k]);//右边的 cnt=q(k,r,a[k]); s+=mx-cnt*k-P[cnt-1];sum=cnt; mx=Qr(l,k,a[k]);//左边的 cnt=q(l,k,a[k]); s+=mx-cnt*(n-k+1)-P[cnt-1]; sum+=cnt-1; return s<=T;}void Solve(){ Insert(); for(int s=1;s<=n;s++) for(int k=s+1;k<=n;k++){ int l=0,r=n-k+1; while(l<=r){ int mid=l+r>>1; if(Judge(s,k,k+mid)){ ans=max(ans,sum);l=mid+1; } else r=mid-1; } }}void Gao(){ int mx=0,x,s,ss,t,p; for(int i=1;i<=n;i++){ if(f[i]>mx){ mx=f[i];x=i; } a[i]+=2; } x+=2;p=1;sum=0; while(p<=n){ cnt=0;ss=p; while(a[p]==x){ cnt++;p++; } if(cnt>sum){ sum=cnt;s=ss;t=p-1; } p++; } for(int i=1;i<=n;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 i=n;i>=1;i--) if(a[i]==x)e[i]=e[i+1]+n-i+1; else e[i]=e[i+1]; for(int i=1;i<=n;i++){ int l=0,r=n-s+1; while(l<=r){ int mid=l+r>>1; if(Judge(i,s,s+mid)){ ans=max(ans,sum);l=mid+1; } else r=mid-1; } } for(int i=1;i<=n;i++){ int l=0,r=n-t+1; while(l<=r){ int mid=l+r>>1; if(Judge(i,t,t+mid)){ ans=max(ans,sum);l=mid+1; } else r=mid-1; } }}int main(){ freopen("seq.in","r",stdin); freopen("seq.ans","w",stdout); n=init();T=init(); for(int i=1;i<=n;i++){ a[i]=init(); if(f[a[i]]==0)cnt++; f[a[i]]++; } if(n<=1000)Solve(); else Gao(); printf("%d\n",ans); return 0;}
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+看不懂 */#include#include #include #define maxn 100010#define ll long long#define P 29using 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 i=1;i<=100000;i++) p[i]=p[i-1]*P; le=s.length(); for(int i=1;i<=le;i++) Sub=Sub*P+s[i-1];}void Hash(int x){ if(f[x])return;f[x]=1; int len=S[x].length(); for(int i=1;i<=len;i++) ha[x][i]=ha[x][i-1]*P+S[x][i-1];}ll Query(int x,int l,int r){ return ha[x][r]-ha[x][l-1]*p[r-l+1];}int main(){ freopen("str.in","r",stdin); freopen("str.ans","w",stdout); cin>>S[0]>>S[1]>>s>>q; for(int i=1;i<=q;i++){ cin>>x[i]>>l[i]>>r[i]; n=max(n,x[i]); } Get(); for(int i=2;i<=n;i++) S[i]=S[i-1]+S[i-2]; for(int i=1;i<=n;i++) Hash(i); for(int i=1;i<=q;i++){ int cnt=0,len=S[x[i]].length(); for(int j=l[i];j+le-1<=r[i];j++){ ll mx=Query(x[i],j,j+le-1); if(mx==Sub)cnt++; } printf("%d\n",cnt); } return 0;}