1.铺瓷砖
（tile.cpp/c/pas）
【问题描述】
有一面很长很长的墙。 你需要在这面墙上贴上两行瓷砖。 你的手头有两种不同尺寸的瓷
砖，你希望用这两种瓷砖各贴一行。瓷砖的长可以用分数表示，贴在第一行的每块瓷砖长度
为 A
B ，贴在第二行的每块瓷砖长度为
C
D 。本问题中你并不需要关心瓷砖的宽度。
如上图所示， 两排瓷砖从同一起始位置开始向右排列， 两排瓷砖的第一块的左端的缝隙
是对齐的。你想要知道，最短铺多少距离后，两排瓷砖的缝隙会再一次对齐。
【输入】
输入的第 1 行包含一个正整数 T，表示测试数据的组数。
接下来 T 行，每行 4 个正整数 A，B，C，D，表示该组测试数据中，两种瓷砖的长度分
别为 A
B 和
C
D 。
【输出】
输出包含 T 行， 第 i 行包含一个分数或整数， 表示第 i 组数据的答案。 如果答案为分数，
则以“X/Y”的格式输出，不含引号。分数必须化简为最简形式。如果答案为整数，则输出
一个整数 X。
【输入输出样例 1】
tile.in tile.out
2
1 2 1 3
1 2 5 6
1
5/2
见选手目录下的 tile/tile1.in 与 tile/tile1.out
【输入输出样例 1 说明】
对于第一组数据，第一行瓷砖贴 2 块，第二行贴 3 块，总长度都为 1，即在距离起始位
置长度为 1 的位置两行瓷砖的缝隙会再次对齐。
对于第二组数据，第一行瓷砖贴 5 块，第二行贴 3 块，总长度都为 5
2 。
【输入输出样例 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<iostream> #include<cstdio> #define ll long long using 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<<x/y<<endl; return; } gcd=Gcd(x,y); cout<<x/gcd<<"/"<<y/gcd<<endl; } int main() { freopen("tile.in","r",stdin); freopen("tile.out","w",stdout); T=init(); while(T--){ A=init();B=init();C=init();D=init(); lcm=Lcm(B,D); A*=lcm/B;C*=lcm/D;B=lcm;D=lcm; lcm=Lcm(A,C); Printf(lcm,B); } return 0; }
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.out
7
1 3 2
2 3 1
3 5 1
5 4 2
4 6 3
5 7 3
5
9
见选手目录下的 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<iostream> #include<cstdio> #include<cstring> #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 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<n;i++){ u=init();v=init();t=init(); e[i].u=u;e[i].v=v;e[i].t=t; Up(u,t);Up(v,t);r[u]++;r[v]++; } for(int i=1;i<n;i++){ int u=e[i].u,v=e[i].v; int x=r[u]-1,y=r[v]-1,z; ans+=(ll)y*x*(x-1)/2; ans+=(ll)x*y*(y-1)/2; if(mx[u][0]==e[i].t){ x=mx[u][1];y=mx[u][2]; } else if(mx[u][1]==e[i].t){ x=mx[u][0];y=mx[u][2]; } else{ x=mx[u][0];y=mx[u][1]; } if(mx[v][0]==e[i].t) z=mx[v][1]; else z=mx[v][0]; mxx=max(mxx,x+y+z+e[i].t); if(mx[v][0]==e[i].t){ x=mx[v][1];y=mx[v][2]; } else if(mx[v][1]==e[i].t){ x=mx[v][0];y=mx[v][2]; } else{ x=mx[v][0];y=mx[v][1]; } if(mx[u][0]==e[i].t) z=mx[u][1]; else z=mx[u][0]; mxx=max(mxx,x+y+z+e[i].t); } cout<<ans<<endl<<mxx<<endl; return 0; }
啦啦啦 拼凑的几个题
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 Input
7 3
3 2 2 4 3 2 3
2.5 Sample Output
3
2.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 = 2
2 n ≤ 10 对所有 i，A i = 1 或 A i = 2
3 n ≤ 1000 对所有 i，A i = 1 或 A i = 2
4 n ≤ 1000 对所有 i，A i = 1 或 A i = 2
5 n ≤ 10 5 对所有 i，A i = 1 或 A i = 2
6 n ≤ 10 5
7 n ≤ 10 5
8 n ≤ 10 6 对所有 i，A i = 1 或 A i = 2
9 n ≤ 10 6
10 n ≤ 10 6
/* 暴力+骗分 40+10 下午看了一眼题解发现自己写慢了 有个性质就是 l-r 区间内的点移动到 中间的时候 总路径最小 然后就剩下的一层枚举中间合并到哪 但是吧 答案来时大一 调了一下午了 还wa这 以后改对了再发喽 */ #include<cstdio> #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 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 ",ans); return 0; }
3 string
3.1 Description
给定三个字符串 a,b,s，它们的字符集均为 小?字?，即 {a, b, ..., z}。
令
F 0 = a
F 1 = b
F 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 Input
a
b
bb
4
4
4 1 5
4 1 1
4 2 4
6 2 11
3.5 Sample Output
1
0
1
2
3.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 ≤ 10
3 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 ≤ 1000
5 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 5
7 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 5
9 |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<iostream> #include<cstdio> #include<cstring> #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 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 ",cnt); } return 0; }