NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

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

顯示文章

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

文章 - liouzhou_101

頁: [1] 2 3
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
NPSC2009高中組決賽 / Re: NPSC 2009 高中組決賽 E. 大風吹
« 於: 六月 12, 2012, 10:24:36 pm »
這題比較正統的解法有兩個:
一、Voronoi圖,時間複雜度O(NlogN)。當然這個比較難做,一些起來就是上10KB的程式...果斷放棄...
二、k-d Tree,時間複雜度O(N*sqrt(N))。這個比較好些,在Zerojudge上我的代碼也比較短,才3KB,運行時間45xms,效率過得去。
注意:具體實現時,可以把距離平方,不用處理浮點數,這裡需要用long long。
分享一下我的程式://有更好的解法,歡迎分享!
代碼: [選擇]
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int MaxN=50010;
const long long INF=10000000000000000LL;

int N;
struct point
{
int x,y,p;
}p[MaxN];

inline bool cmp_x(const point &A,const point &B)
{
return A.x<B.x;
}

inline bool cmp_y(const point &A,const point &B)
{
return A.y<B.y;
}

int tot;
struct node
{
point pv;
int Lx,Rx,Ly,Ry;
int kd;
node *Lc,*Rc,*pre;
}tree[MaxN],*root;

long long dis;
int get;
int ans[MaxN];

inline int abs(int x)
{
return (x>=0)?x:-x;
}

inline long long distance(int x1,int y1,int x2,int y2)
{
return (long long)(x1-x2)*(x1-x2)+(long long)(y1-y2)*(y1-y2);
}

inline node *build(int flag,int L,int R,int Lx,int Rx,int Ly,int Ry)
{
if (L>R) return 0;
node *it=&tree[++tot];
it->Lx=Lx;
it->Rx=Rx;
it->Ly=Ly;
it->Ry=Ry;
it->kd=flag;
if (!flag)
{
sort(p+L,p+R+1,cmp_x);
int mid=(L+R)>>1;
while (mid<R)
{
if (p[mid+1].x==p[mid].x)
++mid;
else
break;
}
it->pv=p[mid];
it->Lc=build(1,L,mid-1,Lx,p[mid].x,Ly,Ry);
it->Rc=build(1,mid+1,R,p[mid].x+1,Rx,Ly,Ry);
}
else
{
sort(p+L,p+R+1,cmp_y);
int mid=(L+R)>>1;
while (mid<R)
{
if (p[mid+1].y==p[mid].y)
++mid;
else
break;
}
it->pv=p[mid];
it->Lc=build(0,L,mid-1,Lx,Rx,Ly,p[mid].y);
it->Rc=build(0,mid+1,R,Lx,Rx,p[mid].y+1,Ry);
}
if (it->Lc) it->Lc->pre=it;
if (it->Rc) it->Rc->pre=it;
return it;
}

inline void check(node *it,int p,int px,int py)
{
if (!it) return;
long long d=INF;
if (it->Lx<=px&&px<=it->Rx)
{
long long t=min(abs(it->Ly-py),abs(it->Ry-py));
d=min(d,t*t);
}
else if (it->Ly<=py&&py<=it->Ry)
{
long long t=min(abs(it->Lx-px),abs(it->Rx-px));
d=min(d,t*t);
}
else
{
long long tx=min(abs(it->Lx-px),abs(it->Rx-px));
long long ty=min(abs(it->Ly-py),abs(it->Ry-py));
d=min(d,tx*tx+ty*ty);
}
if (d>dis) return;
d=distance(it->pv.x,it->pv.y,px,py);
if (it->pv.p!=p) if (d<dis||d==dis&&it->pv.p<get)
{
dis=d;
get=it->pv.p;
}
check(it->Lc,p,px,py);
check(it->Rc,p,px,py);
}

inline void solve(node *it,int p,int px,int py)
{
if (!it) return;
long long d=distance(it->pv.x,it->pv.y,px,py);
if (it->pv.p!=p) if (d<dis||d==dis&&it->pv.p<get)
{
dis=d;
get=it->pv.p;
}
if (!it->kd)
{
if (px<=it->pv.x)
{
solve(it->Lc,p,px,py);
check(it->Rc,p,px,py);
}
else
{
solve(it->Rc,p,px,py);
check(it->Lc,p,px,py);
}
}
else
{
if (py<=it->pv.y)
{
solve(it->Lc,p,px,py);
check(it->Rc,p,px,py);
}
else
{
solve(it->Rc,p,px,py);
check(it->Lc,p,px,py);
}
}
}

void init()
{
cin>>N;
for (int i=1;i<=N;++i)
{
scanf("%d%d",&p[i].x,&p[i].y);
p[i].p=i;
}
tot=0;
root=build(0,1,N,0,1000000,0,1000000);
}

void work()
{
for (int i=1;i<=N;++i)
{
dis=INF;
get=0;
solve(root,p[i].p,p[i].x,p[i].y);
ans[p[i].p]=get;
}
for (int i=1;i<=N;++i)
printf("%d\n",ans[i]);
}

int main()
{
freopen("try.in","r",stdin);
freopen("try.out","w",stdout);
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}

4
NPSC2011高中組初賽 / Re: pD. 巨集危機
« 於: 三月 25, 2012, 09:11:40 pm »
根据phat所说的做法,将x替换为一个实际的表达式,然后再枚举去掉哪些括号。
只是本人的程式写得有些太麻烦了......

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

using namespace std;

string X="4+7";

char task[100];
string s,t;
int len,num,ans;
int pL[100],pR[100],mark[100],a[100];
long long v;

deque<int> Q;
deque<char> q,r;
long long st[100];

long long value(string s)
{
q.clear();
r.clear();
int len=s.length();
for (int i=0;i<len;++i)
{
if (s[i]=='(')
{
q.push_back(s[i]);
continue;
}
if (s[i]==')')
{
while (1)
{
char c=*q.rbegin();
if (c=='(') break;
r.push_back(c);
q.pop_back();
}
q.pop_back();
if (!q.empty())
if (*q.rbegin()=='*')
{
r.push_back('*');
q.pop_back();
}
continue;
}
if (s[i]>='0'&&s[i]<='9')
{
r.push_back(s[i]);
if (!q.empty())
if (*q.rbegin()=='*')
{
r.push_back('*');
q.pop_back();
}
continue;
}
if (s[i]=='+'||s[i]=='*')
{
q.push_back(s[i]);
if (q.size()>1)
if (*q.rbegin()=='+')
{
q.pop_back();
char c=*q.rbegin();
if (c=='+'||c=='*')
{
r.push_back(*q.rbegin());
q.pop_back();
}
q.push_back('+');
}
continue;
}
}
int tot=0;
for (deque<char>::iterator it=r.begin();it!=r.end();++it)
{
char c=*it;
if (c>='0'&&c<'9')
{
++tot;
st[tot]=c-48;
continue;
}
if (c=='+') st[tot-1]+=st[tot];
if (c=='*') st[tot-1]*=st[tot];
--tot;
}
return st[1];
}

void init()
{
cin>>task;
cin>>task;
getchar();
gets(task);
s.clear();
for (int i=0;i<strlen(task);++i)
{
if (task[i]=='x')
s+=X;
else if (task[i]!=' ')
s+=task[i];
}
v=value(s);
Q.clear();
len=s.length();
num=-1;
memset(mark,0,sizeof(mark));
for (int i=0;i<len;++i)
{
if (s[i]=='(')
{
++num;
pL[num]=i;
mark[i]=num;
Q.push_back(num);
}
if (s[i]==')')
{
pR[*Q.rbegin()]=i;
mark[i]=*Q.rbegin();
Q.pop_back();
}
}
}

bool check()
{
t.clear();
a[0]=0;
for (int i=0;i<len;++i)
if (!a[mark[i]])
t+=s[i];
int w=value(t);
return v==w;
}

void DFS(int x,int k)
{
if (ans<=k) return;
if (x>num)
{
if (check()) ans=k;
return;
}
a[x]=0;
DFS(x+1,k+1);
a[x]=1;
DFS(x+1,k);
}

void work()
{
ans=num;
DFS(1,0);
cout<<num-ans<<endl;
}

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

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

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

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

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

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

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

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

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

13
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.

14
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 G.
« 於: 八月 13, 2011, 09:41:56 pm »
這樣就可以構造出了最短路模型,即對於一個無向圖G=(E,V),求節點s到節點t的最短路徑,這可以用SPFA或dijkstra來求的。

最後,我們來分析一下空間和時間的開銷,由於有O(N)個圓,他們互相的公切線上的切點個數是O(N2)的,而點與點之間邊的個數是O(N4)的。
於是空間複雜度約為O(N4),時間複雜度約為求最短路徑長度的時間複雜度。

另外,由於此題做的都是浮點數運算,存在不小的誤差,具體實現時要處處小心。

至此,此題得到完美解決。

15
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 G.
« 於: 八月 13, 2011, 09:41:19 pm »
以下求一條線段與已知圓的距離。

設線段的兩端點為(x1,y1)和(x2,y2),解析式為Ax+By+C=0,已知圓為(x0,y0,r0),圓心到直線Ax+By+C=0的距離為d。
故過圓心與直線Ax+By+C=0垂直的直線方程為Bx-Ay+Ay0-Bx0=0。
設圓心在直線Ax+By+C=0上的投影為P(xP,yP)。
有方程組
AxP +ByP+C=0
BxP -AyP+Ay0-Bx0=0
可以解得P(xP,yP)。
於是

d=
dis((x0,y0),(xP,yP))                                       (当x1<=xP<=x2时)
Min{ dis((x0,y0),(x1,y2)),dis((x0,y0),(x2,y2)) }                (否则)

至此,解決了求已知線段與已知圓的距離,其實就是已知直線與已知點的距離。
該問題具有一般性。

16
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 G.
« 於: 八月 13, 2011, 09:40:33 pm »
接下來,我們應該要判斷兩個點之間是否可以直接相連(即通過一條直線或一條已知圓的圓弧相連)。

設兩點為(x1,y1)和(x2,y2),不妨設x1<= x2。

顯然,當兩點在同一圓上時,我們只需求得兩端點為這兩點的劣弧長度即可。
設該圓為(x,y,r),所求劣弧長為l。
設向量a = (x1-x,y1-y),向量b = (x2-x,y2-y)。
則l=<a, b>•r。
而cos<a, b>=a•b / (|a|•|b|),故可求出<a, b>。
這裏有
arccos x =
arctan((√(1-x2)) / x)       (x>0)
π/2                   (x=0)
π- arccos (–x)           (x<0)

當兩點不在同一圓上時,我們只需判斷這兩點組成的線段與所有圓的距離是否大於該圓半徑,若對於所有圓,這兩點組成的線段與圓的距離都大於該圓半徑,則這兩點之間可以通過一條直線相連,長度是d= dis((x1,y1),(x2,y2))。

於是該問題便轉移到了求一條線段與已知圓的距離。

17
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 G.
« 於: 八月 13, 2011, 09:39:29 pm »
以下求兩圓的交點。

設兩個圓分別為(x1,y1,r1)和(x2,y2,r2),圓心分別為O1,O2。
設圓心距為d= dis((x1,y1),(x2,y2))。
設向量a=(x1-x2,y1-y2)。
由於兩圓相交則有d< r1 + r2。
設交點分別為P1和P2,P1P2與O1O2的交點為P(xP,yP),PP1=PP2=h。
設三角形O1O2P1的面積為S,有海倫公式得
S=√p(p- r1)(p- r2)(p-d)
其中p=(r1+r2+d)/2。
由三角形面積一定得h=2S / d。
設PO1= d1,PO2= d2。
故有
d12= r12 + h2
d22= r22 + h2

PO1/PO2= d1/d2

(x1 - xP) / (x2 - xP) = d1/d2
(y1 - yP) / (y2 - yP) = d1/d2
解得
xP = (x1 d2 + x2 d1) / (d1+d2)
yP = (y1 d2 + y2 d1) / (d1+d2)
設向量w•a = 0,且|w| = h,
故P1,2 = P±w。

至此,已經解決了求兩圓交點的問題,從而解決了求兩圓公切線上的切點的問題。

18
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 G.
« 於: 八月 13, 2011, 09:38:29 pm »
以下求的是兩圓的公切線上的切點。

由於兩圓相離,故兩圓的公切線有4條。
由此,設兩個圓分別為(x1,y1,r1)和(x2,y2,r2),圓心分別為O1,O2。
由於對稱性,不妨設r1<=r2。
設圓心距為d= dis((x1,y1),(x2,y2))。
設向量a=(x1-x2,y1-y2)。

①兩個圓都在公切線的同側,這樣的公切線有2條。
若兩圓半徑相等,
設向量w•a = 0,且|w| = r1,
則4個切點分別為O1±w和O2±w。
若兩圓半徑不相等,
設這兩條公切線的交點為P,
則由三角形相似得PO1/PO2 = r1/r2。
設PO1= l (注:這裏l是L的小寫),則有
l / (l+d) = r1/r2
解得
l = dr1/( r1+r2)
故P= O1+l/d•a。
這樣,
在圓O1上的切點,可以看做圓O1與圓(xP,yP, √(l2-r12))的交點;
在圓O2上的切點,可以看做圓O2與圓(xP,yP, √((l+d)2-r22))的交點。
②兩個圓在公切線異側,這樣的公切線有2條。
設這兩條公切線的交點為P,
則由三角形相似得PO1/PO2 = r1/r2。
設PO1= d1,PO2= d2。
則有
d1/d2 = r1/r2
d1+d2=d
解得
d1=dr1/( r1+r2)
d2=dr2/( r1+r2)
又設P(xP,yP)
則有
(x1 - xP) / (x2 - xP) = r1/r2
(y1 - yP) / (y2 - yP) = r1/r2
解得
xP = (x1 r2 + x2 r1) / (r1+r2)
yP = (y1 r2 + y2 r1) / (r1+r2)
這樣,
在圓O1上的切點,可以看做圓O1與圓(xP,yP,d1)的交點;
在圓O2上的切點,可以看做圓O2與圓(xP,yP,d2)的交點。

至此,求兩圓公切線上的切點已經轉化為求兩相交圓的交點。

19
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)。

20
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.

頁: [1] 2 3