10.27 noip模擬試題

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;
}

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.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;
}

View Code

啦啦啦拼湊的幾個題

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\n",ans);return 0;
}

View Code

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\n",cnt);}return 0;
}