NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » liouzhou_101 的個人資料 » 顯示文章
 主題

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

主題 - liouzhou_101

頁: [1] 2
1
NPSC2012高中組初賽 / pF. 畫蚯蚓
« 於: 二月 02, 2013, 07:00:17 pm »
2012 NPSC 高中組初賽 F. 畫蚯蚓

爲了方便起見,以下所有數組以及字符串都是1-based的。
|s|表示字符串s的長度。
s[l..r]表示字符串s的第l位到第r位的子串。

題目簡述:
給出一個長度為n(n≤1,000,000)的字符串s。
我們定義f(t)的意義為,最少可以用f(t)個字符串t去覆蓋s,假若s不能被t覆蓋,則f(t)=0。
求一個字符串t,使得|t|*f(t)最大。

題目分析:

這題是一道好題,題目與解法都非常優美。
//一直都沒有人來寫這題的題解,我就PO一個上來吧...

爲了方便起見,以下所有數組以及字符串都是1-based的。

在給定的字符串s下,我們用KMP算法O(n)求出s每個位置的失敗指針p[ i ],特別的,p[1]=0。

定義集合A:
①n∈A;
②若x∈A,則p[ x ]∈A。

我們發現,{t|f(t)≠0}是{s[1..x]|x∈A}的子集。

我們枚舉A中的所有元素x,分別對所有t=s[1..x]考察,注意這裡有O(n)個可行的t。

對於每個可行的t,我們採取貪婪策略,每次用t連續覆蓋一段,使得儘量長的s的前綴被覆蓋。
注意到f(t)=O(n/|t|),所以我們模擬覆蓋的次數是O(n/|t|)次。
這裡,我們可以用并查集(dsu)快速找到每次覆蓋后的最長前綴的位置(即長度),時間複雜度可以認為是O(1)的。

這樣,我們的時間複雜度就是∑O(n/|t|)(對所有滿足條件的t)=O(nlogn)。

關鍵在於如何維護并查集。
我們把A中元素排序好,第i小的元素記為A[ i ]。
對每個i,預處理出所有s[1..A[ i ]]是後綴而s[1..A[i+1]]不是後綴的s的前綴,設所有滿足條件的前綴的集合為pre[ i ]。
一開始,把所有s[1..A[1]]為後綴的前綴設為可取。
我們可以從小到大枚舉A中元素A[ i ],處理當前的t=s[1..A[ i ]],更新答案。
對於每次查找,都是查找一個區間中最靠後的可取位置。
最後,我們把pre[ i ]中的所有前綴設為不可取。
具體并查集的處理可參見我的程式。

這樣就完美的解決了本題。

代碼: [選擇]
/**********************************************************************************/
/*  Problem: a593 "F. 畫蚯蚓" from 2012 NPSC 高中組初賽                   */
/*  Language: CPP (1233 Bytes)                                                    */
/*  Result: AC(552ms, 44MB) judge by this@ZeroJudge                               */
/*  Author: liouzhou_101 at 2013-02-02 19:08:03                                   */
/**********************************************************************************/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>

using namespace std;

const int MaxN=1000010;

int n;
char s[MaxN];
int p[MaxN];
vector<int> v[MaxN];
int u[MaxN];

void init()
{
scanf("%s",s+1);
n=strlen(s+1);
for (int i=0;i<=n;++i)
{
v[i].clear();
u[i]=0;
}
for (int i=2;i<=n;++i)
{
int j=p[i-1];
while (j)
{
if (s[j+1]==s[i]) break;
j=p[j];
}
p[i]=j+(s[j+1]==s[i]);
}
for (int i=n;i;i=p[i])
u[i]=1;
}

int F[MaxN];

int father(int x)
{
return (F[x]==x)?x:F[x]=father(F[x]);
}

void work()
{
for (int i=n;i>=1;--i)
F[i]=(u[i])?i:p[i];
for (int i=1;i<=n;++i)
v[father(i)].push_back(i);
for (int i=1;i<=n;++i)
F[i]=i-1;
for (int i=1;i<=n;++i)
if (u[i])
for (int j=0;j<v[i].size();++j)
F[v[i][j]]=v[i][j];
int ans=n;
for (int i=1;i<=n;++i)
{
if (!u[i]) continue;
int t=1,x=i;
while (x!=n)
{
int y=father(min(x+i,n));
if (x>=y) break;
++t;
x=y;
}
if (x==n) ans=max(ans,i*t);
for (int j=0;j<v[i].size();++j)
F[v[i][j]]=father(v[i][j]-1);
}
cout<<ans<<endl;
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

2
NPSC2011高中組決賽 / NPSC 2011 決賽 G.上帝 GOD
« 於: 九月 30, 2012, 01:01:04 pm »
本人懷疑此題測資有誤,具體是第22筆測資到第31筆測資。
能否有人來驗證一下...

第22筆測資到第31筆測資的標準答案:
3557
3579
3559
3567
3562
3979
3980
3977
3978
3978

第22筆測資到第31筆測資的我的答案:
3155
3159
3151
3144
3156
3964
3966
3966
3965
3964

3
NPSC2011高中組決賽 / NPSC 2011 决赛 H.图灵机
« 於: 三月 25, 2012, 12:39:38 pm »
照样模拟就行了。

代碼: [選擇]
#include<cstdio>
#include<iostream>

using namespace std;

int value[255],back[255];

void ready()
{
value['s']=1;
value['u']=2;
for (char i='a';i<='m';++i)
value[i]=i-'a'+3;
back[1]='s';
back[2]='u';
for (char i='a';i<='m';++i)
back[i-'a'+3]=i;
}

int S,M;
int next_S[110][20],next_c[110][20],next_p[110][20];
int len,Q[100010];

void init()
{
cin>>S>>M;
char s[5];
for (int i=3;i<=S;++i)
for (int j=1;j<=M+2;++j)
{
int now_S,now_c;
cin>>now_S>>s;
now_c=value[s[0]];
cin>>next_S[now_S][now_c]>>s;
next_c[now_S][now_c]=value[s[0]];
cin>>s;
if (s[0]=='<')
next_p[now_S][now_c]=-1;
else if (s[0]=='>')
next_p[now_S][now_c]=1;
else
next_p[now_S][now_c]=0;
}
}

void solve()
{
int now_p=1,now_S=3,now_c=Q[now_p];
while (1)
{
int tmp_p=now_p+next_p[now_S][now_c];
int tmp_S=next_S[now_S][now_c];
int tmp_c=next_c[now_S][now_c];
now_S=tmp_S;
if (now_S<=2) break;
if (tmp_p>len) Q[++len]=2;
Q[now_p]=tmp_c;
now_p=tmp_p;
now_c=Q[now_p];
}
if (now_S==2)
{
puts("no");
return;
}
printf("yes ");
for (int i=1;i<=len;++i)
putchar(back[Q[i]]);
puts("");
}

void work()
{
int C;
cin>>C;
char s[1010];
gets(s+1);
while (C--)
{
gets(s+1);
Q[len=1]=1;
for (int i=1;i<=strlen(s+1);++i)
Q[++len]=value[s[i]];
solve();
}
}

int main()
{
ready();
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

4
NPSC2011高中組決賽 / NPSC 2011 决赛 F.田忌赛马
« 於: 三月 23, 2012, 10:26:01 pm »
题目简述:
有两组数据A和B,每组由N个数据。
叫你对A进行一次变换:
A(i)+=M*d(i),其中M为参数,d(i)已给定。
要求你最小化M,使得存在一组关于1..N的排列π,满足A(i)>B(π(i))的i的个数大于K(K为给定值)。

题目分析:
二分答案 & greedy
对M二分答案,我们只要判断对于一个确定的M是否满足条件即可。
我们发现,对M做变换后的A和B可以先进行从小到大的排序。
对B从小到大的枚举A中是否有大于他的数据,若有,就拿A中大于他的且最小的数据与他比。
如此得到的个数一定最大。

代碼: [選擇]
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int MaxN=10010;

int N,K;
int A[MaxN],B[MaxN],C[MaxN];
long long v[MaxN];

void init()
{
cin>>N>>K;
for (int i=1;i<=N;++i)
scanf("%d%d",&A[i],&B[i]);
for (int i=1;i<=N;++i)
scanf("%d",&C[i]);
sort(C+1,C+N+1);
}

bool check(long long M)
{
for (int i=1;i<=N;++i)
v[i]=A[i]+B[i]*M;
sort(v+1,v+N+1);
int j=1,get=0;
for (int i=1;i<=N;++i)
{
while (v[j]<=C[i])
{
++j;
if (j>N) break;
}
if (j>N) break;
++get;
++j;
if (get>=K) return true;
}
return false;
}

void work()
{
long long ans=100000000;
if (!check(ans))
{
puts("-1");
return;
}
int L=0,R=ans;
while (L<=R)
{
long long mid=(L+R)>>1;
if (check(mid))
{
if (ans>mid) ans=mid;
R=mid-1;
}
else
L=mid+1;
}
cout<<ans<<endl;
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

5
NPSC2011高中組決賽 / NPSC 2011 决赛 E.整修中的道路
« 於: 三月 23, 2012, 10:16:01 pm »
题目简述:
给你一个无向图G=(V,E),需要回答询问:若删除其中一条边后,某两点之间是否连通。

题目分析:
Graph & Tarjan & DFS

通过思考我们发现:
假若询问的两节点之间的所有路径中必须经过某条边,那么这条边就是关键边。
假若我们删除了这条关键边,这两点则不连通;假若我们删除了非关键边,这两个点依然连通。

事实上,我们只需要求出的就是所有的关键边,事实上称之为无向图中的“桥”。
无向图中的“桥”的定义是,若将这条边删除,则这个无向图的连通分量发生改变。
求“桥”我们可以用Tarjan算法来实现。

然后,我们随机的生成一个无向图G的生成树T。
对每个点就得到一个DFS序,其中first(i)和second(i)分别表示节点i的第一次访问时间和最后一次访问时间。

假若删除了某条树上的边,那么这棵树T就变成了两个部分,设其中不含T的根节点的那部分的根为p。
若询问中两个点x和y之间连通,则说明first(p)≤first(x)≤second(p)与first(p)≤first(y)≤second(p)同真假。

这样问题就完美解决了!

代碼: [選擇]
#include<cstdio>
#include<iostream>
#include<vector>

using namespace std;

const int MaxN=32010;
const int MaxM=514010;

int N,M;
int x[MaxM],y[MaxM],key[MaxM];
vector<int> v[MaxN];

int Time,Index;

int DFN[MaxN],LOW[MaxN],first[MaxN],second[MaxN],dis[MaxN];

void init()
{
cin>>N>>M;
for (int i=1;i<=N;++i)
v[i].clear();
for (int i=1;i<=M;++i)
{
scanf("%d%d",&x[i],&y[i]);
v[x[i]].push_back(y[i]);
v[y[i]].push_back(x[i]);
key[i]=0;
}
}

void tarjan(int x,int pre,int d)
{
DFN[x]=LOW[x]=++Time;
first[x]=second[x]=++Index;
dis[x]=d;
for (vector<int>::iterator it=v[x].begin();it!=v[x].end();++it)
{
int p=*it;
if (!DFN[p])
{
tarjan(p,x,d+1);
LOW[x]=min(LOW[x],LOW[p]);
second[x]=++Index;
}
else if (p!=pre)
LOW[x]=min(LOW[x],DFN[p]);
}
}

void find_key_edge()
{
Time=Index=0;
for (int i=1;i<=N;++i)
DFN[i]=0;
for (int i=1;i<=N;++i)
if (!DFN[i]) tarjan(i,0,1);
for (int i=1;i<=M;++i)
if (DFN[x[i]]<LOW[y[i]]||DFN[y[i]]<LOW[x[i]]) key[i]=1;
}

void work()
{
int D;
cin>>D;
while (D--)
{
int k,px,py;
scanf("%d%d%d",&k,&px,&py);
if (!key[k])
{
putchar('N');
continue;
}
int p=(dis[x[k]]>dis[y[k]])?x[k]:y[k];
putchar(((first[px]>=first[p]&&first[px]<=second[p])^(first[py]>=first[p]&&first[py]<=second[p]))?'Y':'N');
}
puts("");
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
find_key_edge();
work();
}
return 0;
}

6
NPSC2011高中組決賽 / NPSC 2011 决赛 D.河川改道之术
« 於: 三月 23, 2012, 10:01:30 pm »
题目简述:
一个N×M的矩形的每个格子只有A和B两种形态,分别对应不同的划分方法,将矩形分成若干块。
要你进行修改,使得修改后
①矩形分成的块数最少;
②修改次数最少;
③修改后矩形形态的字典序最小。

题目分析:
greedy
每次我们都只修改形态为B的格子,若这个格子的左下角和右上角分别属于不同的连通块。
这样就可以得到最优解了。
具体实现时,需要用到并查集(Disjoint Sets)。

代碼: [選擇]
//learned from chenboy

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int MaxN=510;

int N,M;
char map[MaxN][MaxN];
int place[MaxN][MaxN];
int F[MaxN*MaxN],used[MaxN*MaxN];
char s[MaxN*MaxN];

int father(int x)
{
return (F[x]==x)?x:F[x]=father(F[x]);
}

void addedge(int x,int y)
{
int Fx=father(x),Fy=father(y);
if (Fx==Fy) return;
if (!Fx) F[Fy]=0;
else if (!Fy) F[Fx]=0;
else F[Fx]=Fy;
}

void init()
{
cin>>N>>M;
for (int i=0;i<=N;++i)
for (int j=0;j<=M;++j)
{
place[i][j]=i*(M+1)+j+1;
F[place[i][j]]=place[i][j];
}
for (int i=1;i<=N;++i)
for (int j=1;j<=M;++j)
{
char c=getchar();
while (c!='A'&&c!='B') c=getchar();
map[i][j]=c;
(c=='A')?addedge(place[i-1][j],place[i][j-1]):addedge(place[i-1][j-1],place[i][j]);
}
}

unsigned int get_hash(const char *s)
{
unsigned int h=1315423911;
for (unsigned int i=0;*s;s++,i++)
h^=((h<<5)+(*s)+(h>>2));
h&=0x7FFFFFFF;
return h;
}

void work()
{
int MinAns=0;
for (int i=0;i<=N;++i)
for (int j=0;j<=M;++j)
used[place[i][j]]=0;
for (int i=0;i<=N;++i)
for (int j=0;j<=M;++j)
used[father(place[i][j])]=1;
for (int i=0;i<=N;++i)
for (int j=0;j<=M;++j)
MinAns+=used[place[i][j]];
for (int i=0;i<=N;++i)
F[father(place[i][0])]=F[father(place[i][M])]=0;
for (int j=0;j<=M;++j)
F[father(place[0][j])]=F[father(place[N][j])]=0;
int MinCost=0,Len=0;
for (int i=1;i<=N;++i)
for (int j=1;j<=M;++j)
{
if (map[i][j]=='B'&&father(place[i][j-1]))
{
++MinCost;
--MinAns;
s[Len]='*';
addedge(place[i-1][j],place[i][j-1]);
}
else
s[Len]='.';
++Len;
}
s[Len]='\0';
cout<<MinAns<<" "<<MinCost<<endl<<get_hash(s)<<endl;
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

7
NPSC2011高中組決賽 / NPSC 2011 决赛 C.破解密码
« 於: 三月 23, 2012, 09:50:34 pm »
题目简述:
明文按照一种方式进行加密变成密文。
加密的方法为:首先选出一个字串S,那么
B(i)=(A(i)+S(i))%26   若i≤L
    =(A(i)+B(i-L))%26 若i>L
其中L是字串S的长度。
给你N组明文A和密文B,求出L最小的S。

题目分析:
记Len(i)表示第i组明文的长度。
假若L≥Max{Len(i)|1≤i≤N},那么很容易就可以得到S。

我们考虑如下情况:
若存在一个i(1≤i≤N),使得L<Len(i)。
设这时的明文为A,密文为B,那么定义C:
C(i)=(B(i)-A(i)+26)%26。
这时,我们会发现,C的一个后缀子串一定是B的前缀,而C的前面那部分就是一个可行解!!!
具体实现我们可以用KMP算法。

拿范例做例子:
A="CAKES",B="DEOHW",则C="BEEDE"。
这时C的一个后缀字串"DE"正是B的前缀,而S="BEE"就是一个可行解。

我们就可以对每一组明文和密文进行求解,找到所有的可行解,而所有组的可行解的交集就是真正的S。
S可能有多个,我们去长度最小的一个。

代碼: [選擇]
//discuss with void_rank

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int MaxN=10;
const int MaxLen=30010;

int N,Limit,Common;
char A[MaxN][MaxLen],B[MaxN][MaxLen],v[MaxN][MaxLen];
int Len[MaxN];
int used[MaxLen],pre[MaxLen],fail[MaxLen];

void init()
{
cin>>N;
Limit=0;
for (int i=1;i<=N;++i)
{
scanf("%s%s",A[i]+1,B[i]+1);
Len[i]=strlen(A[i]+1);
if (Limit<Len[i]) Limit=Len[i];
for (int j=1;j<=Len[i];++j)
{
v[i][j]=B[i][j]-A[i][j];
if (v[i][j]<0) v[i][j]+=26;
v[i][j]+='A';
}
}
}

void KMP(int k)
{
for (int i=2;i<=Len[k];++i)
{
int j=fail[i-1];
while (B[k][j+1]!=B[k][i])
{
j=fail[j];
if (!j) break;
}
fail[i]=(B[k][j+1]==B[k][i])?j+1:0;
}
for (int i=2;i<=Len[k];++i)
{
int j=pre[i-1];
while (B[k][j+1]!=v[k][i])
{
j=fail[j];
if (!j) break;
}
pre[i]=(B[k][j+1]==v[k][i])?j+1:0;
}
for (int p=pre[Len[k]];p;p=fail[p])
++used[Len[k]-p];
for (int p=Len[k];p<=Common;++p)
++used[p];
}

void work()
{
Common=0;
for (int i=1;i<=Limit;++i)
{
int flag=0;
int way=0;
for (int j=1;j<=N;++j)
if (Len[j]>=i) way=j;
for (int j=1;j<=N;++j)
if (Len[j]>=i&&v[way][i]!=v[j][i]) flag=1;
if (flag) break;
++Common;
used[i]=0;
}
if (!Common)
{
puts("-");
return;
}
for (int i=1;i<=N;++i)
KMP(i);
for (int i=1;i<=Common;++i)
if (used[i]==N)
{
int way=0;
for (int j=1;j<=N;++j)
if (Len[j]>=i) way=j;
for (int j=1;j<=i;++j)
putchar(v[way][j]);
puts("");
return;
}
puts("-");
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

8
NPSC2011高中組決賽 / NPSC 2011 决赛 A.三角形金砖
« 於: 三月 23, 2012, 09:22:08 pm »
题目简述:
给你∠A为钝角的△ABC的边AB和BC的长,在边BC上有一点D,使得∠BAD=∠ACD,求△ACD的面积与△ABC的面积之比。
题目分析:
geometry
由相似三角形的判定,△BAD∽△BCA。
因此AB/BD=BC/AB,即BD=AB*AB/BC。
而△ACD的面积/△ABC的面积=CD/BC=(BC-BD)/BC=1-BD/BC=1-(AB*AB)/(BC*BC)。
代碼: [選擇]
#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
int T;
cin>>T;
while (T--)
{
long double AB,BC;
cin>>AB>>BC;
cout<<setprecision(3)<<fixed<<1-AB*AB/BC/BC<<endl;
}
return 0;
}

9
NPSC2011國中組決賽 / G. 數據加密
« 於: 三月 20, 2012, 10:22:56 pm »
greedy
考慮一個字符x插入的位置p,若這個字符x在該位置之後不再出現,且該位置后的那個字符y有x<y,那麼我們就可以將x插入到位置p上。
代碼: [選擇]
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int MaxN=1010;

int n,len;
char s[MaxN],t[MaxN];
int v[MaxN][27];

void init()
{
scanf("%s%d",s+1,&n);
len=strlen(s+1);
for (int i=1;i<=len;++i)
t[i]=s[i];
sort(t+1,t+len+1);
for (int i=1;i<=len;++i)
putchar(t[i]);
putchar(';');
n-=(len*2+1);
}

void work()
{
for (int i=1;i<=26;++i)
v[len][i]=0;
v[len][s[len]-'a'+1]=1;
for (int i=len-1;i>=1;--i)
for (int j=1;j<=26;++j)
v[i][j]=v[i+1][j]+(s[i]-'a'+1==j);
for (int i=1;i<=len;++i)
{
for (int k=1;k<=s[i]-'a';++k)
if (!v[i][k])
{
while (n)
{
putchar(k+'a'-1);
--n;
}
if (!n) break;
}
putchar(s[i]);
}
while (n--) putchar('a');
puts("");
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

10
NPSC2011國中組決賽 / B. 分組競賽
« 於: 三月 20, 2012, 10:18:18 pm »
DP

代碼: [選擇]
#include<iostream>

using namespace std;

const int MOD=1000000007;
const int MaxG=520;
const int MaxK=10010;

int G,K,R;
int g[MaxG];
int F[MaxG][MaxK];

void init()
{
cin>>G>>K>>R;
for (int i=1;i<=G;++i)
{
cin>>g[i];
g[i]%=K;
}
}

void work()
{
F[0][0]=1;
for (int i=1;i<=G;++i)
for (int j=0;j<K;++j)
F[i][j]=(F[i-1][(j+g[i])%K]+F[i-1][(j-g[i]+K)%K])%MOD;
cout<<F[G][R]<<endl;
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

11
NPSC2005高中組決賽 / NPSC 2005 高中組 決賽 H.光輪2005
« 於: 十一月 05, 2011, 11:22:10 pm »
題目簡述:
給出一個山形折線,兩人分別從左右山麓上山,最後同時到達最高的山峰,求出最少的轉彎次數。其中,在任意時刻兩人與水平面的距離保持相等。

題目分析:
乍看題目,感到毫無頭緒,很難抽象出模型,進而很難解決。
顯然,每個山峰(谷)的水準位置並無意義,可以略去。
而且這題的解法頗多,這裏僅介紹本人的一種解法:構造最短路模型。
儘量將原題中的一些狀態抽象成一些點,這些點之間可以互相到達,同時也有起點和目標點,於是就可以將原題轉為最短路模型,而狀態的表示則可以用DP來實現。
這裏,定義從左至右的山峰(穀)編號1至N,同時將左山麓抽象成山谷0,將右山麓抽象成山谷N+1。再定義每個山峰(穀)i左側的山坡為山坡i,這裏i=1,2,3,…,N+1。
設F(i,j)表示兩個人中有一個人在山峰(穀)i,而另一個人在山坡j的最少轉彎數。這便可得到F(i,j)的一些關係式。
將每個狀態(i,j)抽象成一個點,於是就可以構造出了最短路模型。
具體實現時非常複雜,要注意情況:
①   山峰(谷)i是山峰還是山谷
②   存在兩個或以上的山峰(穀)的高度相等,這個要特判。
具體細節可參考程式。

這題的做法應該不止此法,若有其他做法歡迎分享!

代碼: [選擇]
const
MaxN=210;

var
H : array[0..MaxN] of longint;
F : array[0..MaxN,0..MaxN] of longint;
qx,qy : array[1..100000] of longint;
top,n : longint;

procedure init;
var
i,flag : longint;
begin
H[0]:=0;
top:=0;
for i:=1 to n do begin
readln(flag,H[i]);
if H[top]<H[i] then top:=i;
end;
readln;
H[n+1]:=0;
end;

procedure work;                          //转最短路模型
var
i,j,head,tail,nowx,nowy,low,high,ans : longint;
procedure check(x,y:longint);
begin
if (x>=0) and (x<=n+1) and (y>=1) and (y<=n+1) then
if F[x,y]>F[nowx,nowy]+1 then begin
F[x,y]:=F[nowx,nowy]+1;
tail:=tail+1;
qx[tail]:=x;
qy[tail]:=y;
end;
end;
begin
for i:=0 to n+1 do
for j:=1 to n+1 do
F[i,j]:=1000000000;
F[0,n+1]:=0;
F[n+1,1]:=0;
head:=1;
tail:=2;
qx[1]:=0;
qy[1]:=n+1;
qx[2]:=n+1;
qy[2]:=1;
while head<=tail do begin
nowx:=qx[head];
nowy:=qy[head];
low:=nowy div 2*2;
high:=(nowy-1) div 2*2+1;
if nowx and 1=1 then begin   //山峰
if nowx-1>=0 then begin
if H[nowx-1]>=H[low] then
check(nowx-1,nowy);
if H[nowx-1]<=H[low] then
check(low,nowx);
if H[nowx-1]=H[low] then begin
if low<high then
check(nowx-1,nowy-1)
else
check(nowx-1,nowy+1);
check(low,nowx-1);
end;
end;
if nowx+1<=n+1 then begin
if H[nowx+1]>=H[low] then
check(nowx+1,nowy);
if H[nowx+1]<=H[low] then
check(low,nowx+1);
if H[nowx+1]=H[low] then begin
if low<high then
check(nowx+1,nowy-1)
else
check(nowx+1,nowy+1);
if nowx+2<=n+1 then
check(low,nowx+2);
end;
end;
end else begin               //山谷
if nowx-1>=0 then begin
if H[nowx-1]<=H[high] then
check(nowx-1,nowy);
if H[nowx-1]>=H[high] then
check(high,nowx);
if H[nowx-1]=H[high] then begin
if low<high then
check(nowx-1,nowy+1)
else
check(nowx-1,nowy-1);
check(high,nowx-1);
end;
end;
if nowx+1<=n+1 then begin
if H[nowx+1]<=H[high] then
check(nowx+1,nowy);
if H[nowx+1]>=H[high] then
check(high,nowx+1);
if H[nowx+1]=H[high] then begin
if low<high then
check(nowx+1,nowy+1)
else
check(nowx+1,nowy-1);
if nowx+2<=n+1 then
check(high,nowx+2);
end;
end;
end;
head:=head+1;
end;
if F[top,top]>F[top,top+1] then
ans:=F[top,top+1]
else
ans:=F[top,top];
if ans<1000000000 then
writeln(ans-1)
else
writeln('mission impossible');
end;

begin
while true do begin
readln(n);
if n=0 then break;
init;
work;
end;
end.

12
NPSC2010高中組決賽 / NPSC 2010 高中組 決賽 G.
« 於: 八月 13, 2011, 09:33:42 pm »
題目簡述:
給你N(0<=N<=10)個相離的圓,叫你求出從點(0,0)到點(1000,1000)的最短路徑長度,使得路徑不經過任何圓的內部。

題目分析:
這題是一道最短路徑的題目,應該建立最短路模型,然後用SPFA或dijkstra求單源最短路。
首先有如下定理。

定理:最短路徑必定是由多條線段或已知圓的圓弧首尾相接而成的,這些線段和已知圓的圓弧的兩端點必定是兩圓的公切線上的切點或是一個圓與過起點或終點的切線上的切點。
證明:略。

這樣,問題的核心便轉移到了如何求所有兩圓的公切線上的切點和所有圓與過起點或終點的切線上的切點。

一個圓與過起點或終點的切線上的切點,可以看作是該圓與圓心為起點或終點,半徑為0的圓的公切線上的切點。

設圓的表示法為圓(x,y,r),表示該圓圓心為(x,y),半徑為r。
設距離函數dis((x1,y1),(x2,y2))表示兩點(x1,y1)和(x2,y2)之間的距離,故有
dis((x1,y1),(x2,y2))= √((x1-x2)2+(y1-y2)2)。

13
NPSC2010國中組決賽 / [Pascal]D.三生万物
« 於: 一月 11, 2011, 10:33:43 pm »
贪心(贪婪)(greedy)算法。

分以下三步:

1、就是先考虑(-3),依次判断能否让(+3)或2×(+2)+(-1)或(+2)+(+1)或3×(+1)把它中和掉(加起来=0)(注意判断顺序!!!),直到没有(-3)为止;若在中途没有东西能够中和(-3),则“NO”。

2、然后考虑(+3),当(+3)的个数大于1时(想想为什么),依次判断能否让(-3)或2×(-2)+(+1)或(-2)+(-1)或3×(-1)把它中和(注意判断顺序!!!),直到(+3)个数小于等于1为止;若在中途没有东西能够中和(+3),则“NO”。

3、若都没有“NO”,则“YES”。

程序中的时间复杂度为O(n),其实应该有O(1)的做法。还请高手提供...

以下是程序:

代碼: [選擇]
var
  T,n,i,x,k : longint;
  b : array[-3..3] of longint;
procedure work;
  begin
    while b[-3]>0 do begin
      b[-3]:=b[-3]-1;
      if b[3]>0 then b[3]:=b[3]-1
        else if (b[2]>1) and (b[-1]>0) then begin
          b[2]:=b[2]-2;
          b[-1]:=b[-1]-1;
        end else if (b[2]>0) and (b[1]>0) then begin
          b[2]:=b[2]-1;
          b[1]:=b[1]-1;
        end else if b[1]>2 then b[1]:=b[1]-3
          else begin
            writeln('NO');
            exit;
          end;
    end;
    while b[3]>1 do begin
      b[3]:=b[3]-1;
      if b[-3]>0 then b[-3]:=b[-3]-1
        else if (b[-2]>1) and (b[1]>0) then begin
          b[-2]:=b[-2]-2;
          b[1]:=b[1]-1;
        end else if (b[-2]>0) and (b[-1]>0) then begin
          b[-2]:=b[-2]-1;
          b[-1]:=b[-1]-1;
        end else if b[-1]>2 then b[-1]:=b[-1]-3
          else begin
            writeln('NO');
            exit;
          end;
    end;
    writeln('YES');
  end;
begin
  read(T);
  while T>0 do begin
    T:=T-1;
    read(n);
    fillchar(b,sizeof(b),0);
    for i:=1 to n do begin
      read(k);
      b[k]:=b[k]+1;
    end;
    x:=0;
    for i:=-3 to 3 do
      x:=x+b[i]*i;
    if (x>3) or (x<0) then begin       //不在范围内直接“NO”
      writeln('NO');
      continue;
    end;
    work;
  end;
end.

14
NPSC2010國中組決賽 / [Pascal]G.失落的维京战机
« 於: 一月 01, 2011, 10:35:16 pm »
就是字符串的处理,我的code有点诡异。

但也是比较简短的。

注:copy()就是C的strcpy().

代碼: [選擇]
var
  T : longint;
  s : string;
function work(s:string):longint;
  var
    len,i,t : longint;
    c : integer;
  begin
    len:=length(s);
    for i:=1 to len do
      if s[i]='+' then begin
        t:=work(copy(s,1,i-1))+work(copy(s,i+1,len-i));
        work:=t;
        exit;
      end;
    for i:=1 to len do
      if s[i]='*' then begin
        t:=work(copy(s,1,i-1))*work(copy(s,i+1,len-i));
        work:=t;
        exit;
      end;
    val(s,t,c);
    work:=t;
  end;
begin
  readln(T);
  while T>0 do begin
    T:=T-1;
    readln(s);
    writeln(work(s));
  end;
end.

15
NPSC2010國中組決賽 / [Pascal]F.一棵开花的树
« 於: 一月 01, 2011, 10:30:52 pm »
简单图论,其实就是处理一棵树。

关键在于存图的技巧,这样可以减轻code的负担。

代码比较简短:

代碼: [選擇]
var
  T,n,m,k,p,i,j,x,ans : longint;
  F,L,R,s,b,sit : array[1..50000] of longint;
begin
  read(T);
  while T>0 do begin
    T:=T-1;
    read(n,m,k);
    p:=0;
    F[1]:=1;
    for i:=1 to n do begin
      L[i]:=p+1;
      read(x);
      p:=p+x;
      R[i]:=p;
      for j:=L[i] to R[i] do begin
        read(s[j]);
        F[s[j]]:=i;
      end;
      b[i]:=0;
    end;
    for i:=1 to m do begin
      read(x);
      sit[i]:=1;
      for j:=1 to x do begin
        read(p);
        sit[i]:=s[L[sit[i]]+p-1];
      end;
    end;
    for i:=1 to k do begin
      read(x);
      x:=sit[x];
      b[x]:=1;
      while b[F[x]]=0 do begin
        x:=F[x];
        b[x]:=1;
      end;
    end;
    ans:=0;
    for i:=1 to n do
      if b[i]=1 then ans:=ans+1;
    writeln(ans);
  end;
end.

16
NPSC2010國中組決賽 / [Pascal]E.得分
« 於: 一月 01, 2011, 10:27:48 pm »
简单DP。

小心超longint!

代碼: [選擇]
var
  T,n,s,i,j : longint;
  F : array[0..10000] of qword;
  a : array[1..100] of longint;
begin
  read(T);
  while T>0 do begin
    T:=T-1;
    read(n,s);
    for i:=1 to n do
      read(a[i]);
    fillchar(F,sizeof(F),0);
    F[0]:=1;
    for j:=1 to n do
      for i:=1 to s do
        if i-a[j]>=0 then
          F[i]:=F[i]+F[i-a[j]];
    writeln(F[s]);
  end;
end.

17
NPSC2010國中組決賽 / [Pascal]C.魔法气泡
« 於: 一月 01, 2011, 10:24:07 pm »
就是基于状态压缩的动态规划。

时间复杂度O(H*W^C).

我的程序似乎有点乱...

代碼: [選擇]
type
  map=array[1..6] of longint;
var
  T,H,W,C,i,j,k,x,p,flag : longint;
  F : array[1..14,1..729] of qword;
  a,b : map;
  ans : qword;
function make(var d:map;j:longint):longint;
  var
    t,k : longint;
  begin
    t:=j;
    for k:=1 to W do begin
      d[k]:=t mod C;
      t:=t div C;
    end;
    for k:=2 to W do
      if d[k]=d[k-1] then begin
        make:=1;
        exit;
      end;
    make:=0;
  end;
begin
  read(T);
  while T>0 do begin
    T:=T-1;
    read(H,W,C);
    fillchar(F,sizeof(F),0);
    x:=1;
    for i:=1 to W do
      x:=x*C;
    for i:=1 to H do
      for j:=1 to x do begin
        flag:=0;
        if make(a,j)=1 then continue;
        if i=1 then begin
          F[i,j]:=F[i,j]+1;
          continue;
        end;
        for k:=1 to x do begin
          if make(b,k)=1 then continue;
          flag:=0;
          for p:=1 to W do
            if a[p]=b[p] then begin
              flag:=1;
              break;
            end;
          if flag=1 then continue;
          F[i,j]:=F[i,j]+F[i-1,k];
        end;
      end;
    ans:=0;
    for i:=1 to x do
      ans:=ans+F[H,i];
    writeln(ans);
  end;
end.

18
NPSC2006高中組初賽 / [PASCAL]D. Mitlab
« 於: 七月 25, 2010, 07:14:18 pm »
题目说明:矩阵计算。

解法不一,只要能够计算出结果就可以了。

我的方法是用“高斯消去法”(大陆称为“高斯消元法”)计算出每个矩阵的行列式和该矩阵的“反矩阵”(大陆称为“逆矩阵”)(如果有的话)。

高斯消元法和逆矩阵的求法在我的程序中有说明。

有人说这题是无意义的苦工题,但我却不是这么认为的。其实这题所考察的是数学矩阵的计算,也是对程序员编程的技巧。
//尽管我的程序好像并不是很精简

具体说明详见以下程序:

代碼: [選擇]
type matrix=record                     //矩阵的类型
       x,y : longint;                      //x和y分别表示矩阵的行数和列数
       v : array[0..31,0..62] of real;//整个矩阵
                                   //注意:由于计算过程中可能出现小数,所以要用实数类型。
       num : real;                        //矩阵的行列式
     end;
var a,b : array[1..26] of matrix;   //a[i]记录第i个矩阵,b[i]记录第i个矩阵的逆矩阵
    s : ansistring;                       //读入一行的信息,由于一行字符可能超过255,故用超长字符串
    i : longint;
procedure swap(var x,y:real);      //交换两个数的值
  var t : real;
  begin
    t:=x;
    x:=y;
    y:=t;
  end;
procedure make_arc(k:longint);   //用高斯消元法计算第k个矩阵的行列式和逆矩阵
  var w : matrix;
      t,best : real;
      i,j,L,z : longint;
  begin
    w:=a[k];                             //以下计算行列式
    with w do begin
      for i:=1 to x do begin
        z:=i;                            //z表示第z个矩阵的第一个非零系数最大
        best:=abs(v[i,i]);           //best记录当前方程第一个非零系数绝对值的最大值
        for j:=i+1 to x do
          if abs(v[j,i])>best then begin
            best:=abs(v[j,i]);
            z:=j;
          end;
        if z<>i then                   //如果第i个矩阵的第一个非零系数不是最大的,就与最大的交换
          for j:=i to y do             //这样可以减小浮点数的误差,得到更正确的答案
            swap(v[i,j],v[z,j]);
        if v[i,i]=0 then break;      //如果出现零,说明该矩阵的行列式为0
                                            //退出后不影响结果,可以直接退出。
        if v[i,i]<0 then
          for j:=1 to y do
            v[i,j]:=-v[i,j];            //如果第一个非零系数为负数,调整正负
        for j:=i+1 to x do begin  //***高斯消元法
          t:=v[j,i]/v[i,i];
          for L:=i to y do
            v[j,L]:=v[j,L]-v[i,L]*t;
        end;
      end;
      a[k].num:=1;                  //计算行列式
      for i:=1 to x do
        a[k].num:=a[k].num*v[i,i];
    end;
    if a[k].x<>a[k].y then exit;//如果该矩阵没有逆矩阵则退出
    w:=a[k];                         //计算该矩阵的逆矩阵
    with w do begin
      for i:=1 to x do              //建立扩展矩阵
        for j:=y+1 to x+y do
          v[i,j]:=0;
      for i:=1 to x do
        v[i,y+i]:=1;
      y:=x+y;
      for i:=1 to x do begin     //用高斯消元法建立上三角矩阵
        z:=i;
        best:=abs(v[i,i]);
        for j:=i+1 to x do
          if abs(v[j,i])>best then begin
            best:=abs(v[j,i]);
            z:=j;
          end;
        if z<>i then
          for j:=i to y do
            swap(v[i,j],v[z,j]);
        if v[i,i]=0 then exit;
        if v[i,i]<0 then
          for j:=1 to y do
            v[i,j]:=-v[i,j];
        for j:=i+1 to x do begin
          t:=v[j,i]/v[i,i];
          for L:=i to y do
            v[j,L]:=v[j,L]-v[i,L]*t;
        end;
      end;
      for i:=1 to x do begin      //反向迭代,得到逆矩阵
        t:=v[i,i];
        for j:=i to y do
          v[i,j]:=v[i,j]/t;
      end;
      for i:=x downto 1 do
        for j:=i-1 downto 1 do begin
          t:=v[j,i]/v[i,i];
          for L:=i to y do
            v[j,L]:=v[j,L]-v[i,L]*t;
        end;
    end;
    b[k].x:=w.x;                   //将b[k]赋值为a[k]的逆矩阵
    b[k].y:=b[k].x;
    for i:=1 to b[k].x do
      for j:=1 to b[k].y do
        b[k].v[i,j]:=w.v[i,j+w.x];
  end;
procedure scanf(k:longint);  //输入第k个矩阵
  var i,j,t : longint;
      c : integer;                  //调用函数用的参数,,C/C++的可以不用理会
      s1 : ansistring;
  begin
    delete(s,1,6);                //删掉无用信息
    s:=s+' ';                       //增加一个空格,使得字符串好处理
    with a[k] do begin          //具体输入
      if s[1]=']' then begin
        x:=0;
        y:=0;
        fillchar(v,sizeof(v),0);
        exit;
      end;
      i:=1;
      j:=0;
      while true do begin
        t:=pos(' ',s);
        s1:=copy(s,1,t-1);
        delete(s,1,t);
        if s1=']' then break;
        if s1=';' then begin
          i:=i+1;
          j:=0;
          continue;
        end;
        j:=j+1;
        if j>y then y:=j;
        val(s1,v[i,j],c);
      end;
      x:=i;
    end;
    make_arc(k);                //计算第k个矩阵的行列式和逆矩阵
  end;
procedure jia(k,x,y:longint);//矩阵加法
  var i,j : longint;
  begin
    a[k].x:=a[x].x;
    a[k].y:=a[y].y;
    for i:=1 to a[x].x do
      for j:=1 to a[y].y do
        a[k].v[i,j]:=a[x].v[i,j]+a[y].v[i,j];
  end;
procedure jian(k,x,y:longint);//矩阵减法
  var i,j : longint;
  begin
    a[k].x:=a[x].x;
    a[k].y:=a[y].y;
    for i:=1 to a[x].x do
      for j:=1 to a[y].y do
        a[k].v[i,j]:=a[x].v[i,j]-a[y].v[i,j];
  end;
procedure cheng(k:longint;x,y:matrix);//矩阵乘法
  var i,j,L : longint;
  begin
    fillchar(a[k].v,sizeof(a[k].v),0);
    a[k].x:=x.x;
    a[k].y:=y.y;
    if (x.x=0) or (y.y=0) then exit;
    for i:=1 to x.x do
      for j:=1 to y.y do
        for L:=1 to x.y do
          a[k].v[i,j]:=a[k].v[i,j]+x.v[i,L]*y.v[L,j];
  end;
procedure get(k:longint;t:real);//将第k个矩阵的每项乘上t
  var i,j : longint;
  begin
    with a[k] do
      for i:=1 to x do
        for j:=1 to y do
          v[i,j]:=v[i,j]*t;
  end;
procedure compute(k:longint);//矩阵计算
  var i,j : longint;
  begin
    i:=ord(s[5])-96;               //中间变量所表示的矩阵序号
    if length(s)=5 then begin  //若语句是赋值语句就直接赋值并退出
      a[k]:=a[i];
      b[k]:=b[i];
      exit;
    end;
    j:=ord(s[9])-96;               //最右边变量所表示的矩阵序号
    case s[7] of
      '+' : jia(k,i,j);                //矩阵加法
      '-' : jian(k,i,j);               //矩阵减法
      '*' : cheng(k,a[i],a[j]);    //矩阵乘法
      '/' : begin                      //~~~不知道这么说的矩阵运算......
              cheng(k,a[i],b[j]);
              get(k,-a[j].num);
            end;
      '\' : begin
              cheng(k,b[i],a[j]);
              get(k,-a[i].num);
            end;
    end;
    make_arc(k);                   //***同时记住计算第k个矩阵的行列式和逆矩阵,为以后计算做准备
  end;
procedure work(k:longint);    //做输入处理
  begin
    if s[5]='[' then scanf(k)
      else compute(k);
  end;
procedure printf(w:matrix);  //输出答案
  var i,j : longint;
  begin
    write('[');
    with w do
      for i:=1 to x do begin
        for j:=1 to y do
          write(' ',v[i,j]:0:0);
        if i<>x then write(' ;');
      end;
    writeln(' ]');
  end;
begin
  while not eof do begin
    fillchar(a,sizeof(a),0);   //先把所有矩阵和他的逆矩阵清零,以免带来不必发生的错误
    fillchar(b,sizeof(b),0);
    while true do begin
      if eof then break;       //如果输入结束,退出输入
      readln(s);                  //输入语句
      if s='' then break;       //如果有空行,退出本次输入
      work(ord(s[1])-96);
    end;
    for i:=1 to 26 do          //分别输出第i个矩阵
      printf(a[i]);
  end;
end.

//请不要复制这个代码去AC这个你认为无聊的题目

19
NPSC2008國中組初賽 / [PASCAL]F. 世界杯
« 於: 七月 12, 2010, 12:31:01 pm »
就是将输入的信息按一定的顺序排序,可以得到各个队伍的排名情况,然后就是输出答案了。
具体处理很麻烦的!!!
看看就好...
代碼: [選擇]
type arr=record
       name : string;
       value,win,lose : longint;
     end;
var a : array[1..2,1..4] of arr;
    i,j,n,s1n,s2n,x,y : longint;
    s : string;
procedure change(var p,q:arr);
  var t : longint;
      s : string;
  begin
    s:=p.name;
    p.name:=q.name;
    q.name:=s;
    t:=p.value;
    p.value:=q.value;
    q.value:=t;
    t:=p.win;
    p.win:=q.win;
    q.win:=t;
    t:=p.lose;
    p.lose:=q.lose;
    q.lose:=t;
  end;
function big(p,q:arr):boolean;
  begin
    if p.value>q.value then begin
      big:=true;
      exit;
    end;
    if p.value<q.value then begin
      big:=false;
      exit;
    end;
    if p.win>q.win then begin
      big:=true;
      exit;
    end;
    if p.win<q.win then begin
      big:=false;
      exit;
    end;
    if p.lose<q.lose then begin
      big:=true;
      exit;
    end;
    if p.lose>q.lose then begin
      big:=false;
      exit;
    end;
    if p.name>q.name then begin
      big:=true;
      exit;
    end;
    big:=false;
  end;
procedure sort(k:longint);
  var i,j : longint;
  begin
    for i:=1 to 3 do
      for j:=i+1 to 4 do
        if big(a[k,j],a[k,i]) then change(a[k,i],a[k,j]);
  end;
procedure fun(k:longint;s:string);
  var i : longint;
      s1,s2,sx : string;
      c : integer;
  procedure get;
    var w : longint;
    begin
      for w:=1 to length(s) do
        if s[w]=' ' then break;
      i:=w;
    end;
  begin
    get;
    s1:=copy(s,1,i-1);
    delete(s,1,i);
    get;
    sx:=copy(s,1,i-1);
    val(sx,x,c);
    delete(s,1,i);
    get;
    sx:=copy(s,1,i-1);
    val(sx,y,c);
    delete(s,1,i);
    s2:=s;
    for i:=1 to 4 do
      if a[k,i].name=s1 then begin
        s1n:=i;
        break;
      end;
    for i:=1 to 4 do
      if a[k,i].name=s2 then begin
        s2n:=i;
        break;
      end;
  end;
begin
  readln(n);
  while n>0 do begin
    n:=n-1;
    for i:=1 to 2 do
      for j:=1 to 4 do
        with a[i,j] do begin
          readln(name);
          value:=0;
          win:=0;
          lose:=0;
        end;
    for i:=1 to 2 do begin
      for j:=1 to 6 do begin
        readln(s);
        fun(i,s); {s1n,s2n,x,y}
        if x>y then inc(a[i,s1n].value,3)
          else if x<y then inc(a[i,s2n].value,3)
            else begin
              inc(a[i,s1n].value);
              inc(a[i,s2n].value);
            end;
        inc(a[i,s1n].win,x);
        inc(a[i,s1n].lose,y);
        inc(a[i,s2n].win,y);
        inc(a[i,s2n].lose,x);
      end;
      sort(i);
      for j:=1 to 2 do
        writeln(chr(i+64),j,' ',a[i,j].name);
    end;
    write('BEST3 ');
    if big(a[1,3],a[2,3]) then writeln(a[1,3].name)
      else writeln(a[2,3].name);
  end;
end.

//你看2010南非世界杯了吗???

20
NPSC2008國中組初賽 / [PASCAL]E. PK 赛
« 於: 七月 12, 2010, 12:27:16 pm »
很麻烦的一道模拟题,只要模拟和判断所有的情况就可以拿到AC了。

代碼: [選擇]
var n,i : longint;   
    s1,s2 : string;   
procedure fun;   
  var a,b,i : longint;   
  begin 
    a:=0;   
    b:=0;   
    for i:=1 to 5 do begin 
      if i>length(s1) then begin 
        writeln('NO');   
        exit;   
      end;   
      if s1[i]='O' then a:=a+1;   
      if length(s2)>=i then if s2[i]='O' then b:=b+1;   
      if (a>b+5-i+length(s1)-length(s2)) then begin 
        writeln('A');   
        exit;   
      end;   
      if (b>a+5-i) then begin 
        writeln('B');   
        exit;   
      end;   
    end;   
    if i=length(s1) then begin 
      writeln('NO');   
      exit;   
    end;   
    repeat 
      i:=i+1;   
      if s1[i]='O' then a:=a+1;   
      if s2[i]='O' then b:=b+1;   
      if (a>b) and (length(s1)=length(s2)) then begin 
        writeln('A');   
        exit;   
      end;   
      if (b>a) and (length(s1)=length(s2)) then begin 
        writeln('B');   
        exit;   
      end;   
    until i=length(s1);   
    writeln('NO');   
  end;   
begin 
  readln(n);   
  for i:=1 to n do begin 
    readln(s1);   
    readln(s2);
    fun;   
  end;   
end.   

頁: [1] 2