[POI2009]Baj 最短回文路

[POI2009]Baj 最短回文路

Time Limit:10000MS  Memory Limit:165536K
Total Submit:10 Accepted:1
Case Time Limit:3000MS

Description

N个点用M条有向边连接,每条边标有一个小写字母。

对于一个长度为D的顶点序列,回答每对相邻顶点Si到Si+1的最短回文路径。

如果没有,输出-1。

如果有,输出最短长度以及这个字符串。

Input

第一行正整数N和M ( 2 ≤ N ≤ 400 , 1 ≤ M ≤ 60,000 )
接下来M行描述边的起点,终点,字母。
接下来D表示询问序列长度 ( 2 ≤ D ≤ 100 )
再接下来D个1到N的整数

Output

对于D-1对相邻点,按要求输出一行。
如果没合法方案,输出-1。

如果有合法,输出最短长度以及这个字符串。空格隔开。

Sample Input

6 7

1 2 a

1 3 x

1 4 b

2 6 l

3 5 y

4 5 z

6 5 a

3

1 5 3

Sample Output

3 ala

-1

Source
首先一开始我的想法是对于
(a,b)如果a->c的边和b->c上的边的字母一样的话就可以转移。。然后状态就是(a,b)。。
这样状态数有N^2。。每次转移是度数的平方级别的。。显然会TLE囧。。。
然后换种思路:
这个更新说白了就是a走一步,b顺着同样的边走一步。
那么有两种可能的情况轮到a走,轮到b走。。
如果是a走,那么a随便走一步就行了。。
如果是b走,b要跟a走到那个一样。。
换言之状态就是 (a,b,now,pre)a和b意义如上,now表示是a走还是b走,pre表示上一个是哪个(a走到话就忽略)。。
那么实际上就一共有N*N*(26+1)种状态。。同时更新也变成O(M)级别了。。
A了。。代码如下。。。
http://www.ideone.com/EpXy9

AHOI2005

[Ahoi2005]LANE 航线规划
这题目看上去很BT。。但想想也不难囧。。首先肯定是要倒过来处理的。。
然后建一颗树,那么可以发现非树边肯定不是割边,同时本来树上都是割边。
插入一条边后,这条路径上所有的边就都不是割边了。。
那么变成一个路径维护问题。。。看上去树链剖分一下就没问题了。。
不过从zxytim神牛哪里知道了一个更加NB的做法。。就是这个题目跟一般
的路径询问/修改问题不同在于每条边最多被Mark一次,那么显然可以弄一个
平摊O(m)的做法,再一想发现只要用并查集维护某个点往上第一个未被覆盖
的祖先就可以了。。然后Dfs建棵树,用树状数组维护一下。。再写个Lca就差不多了。。
我WA了好几次是因为数组开小了囧。。。
[Ahoi2005]Code 矿藏编码
这个题目也没什么好说的,写个高精度,再扫描一下就毫无问题了。。。
[Ahoi2005]SHUFFLE 洗牌
这个题目之前讲过了。。不过我觉得这种题目的难点还在于发现规律,之后的解方程
就水到渠成了。。
[Ahoi2005]VIRUS 病毒检测
这个破题目。。一开始我TLE了好几次因为我用了记忆化搜索囧。。
设模板串为A,当前串为B
恩。。是这样样子的,设F[i][j]表示A的前i个跟B的前j个是否匹配。。
那么F[i][j]=
{
A[i]=’*’  : f[i][j-1]|f[i-1][j-1]|F[i-1][j]
A[i]=’?’ : f[i-1][j-1]
else f[i-1][j-1]&&A[i]=B[j]

[Ahoi2005]CROSS 穿越磁场
恩。。这个题目离散化一下。。然后再随便套个最短路就可以解决了。。
不过由于边权要么是0要么是1,有O(m)的算法。。
[Ahoi2005]COMMON 约数研究
这个题目只要考虑每个因子出现的次数就可以了。。

[POI2009]Prz

[POI2009]Prz

Time Limit:10000MS  Memory Limit:165536K
Total Submit:16 Accepted:1
Case Time Limit:1000MS

Description

你的任务是计算一个函数F(x, y),其中x和y是两个正整数序列。F的定义如下:

boolean F(x, y)

if W(x) ≠ W(y) then return 0

else if |W(x)| = |W(y)| = 1 then return 1

else return F(p(x), p(y)) AND F(s(x), s(y)).

W(x)表示序列x中元素的集合。(元素的顺序和出现次数将被无视)

p(x)表示序列x的最长前缀,满足:W(x) ≠ W(p(x))

s(x)表示序列x的最长后缀。满足:W(x) ≠ W(s(x))

|Z|表示集合Z中元素个数

Input

第一行k表示数据组数。
对于每组数据,第一行n,m分别表示x序列的长度与y序列的长度,第二行n个数表示xi,第三行m个数表示yi
1<=k<=13
1<=n,m<=100000
1<=xi,yi<=100

Output

k行,对于每组数据,若F(x,y)为真输出1,否则输出0。

Sample Input

2
4 5
3 1 2 1
1 3 1 2 1
7 7
1 1 2 1 2 1 3
1 1 2 1 3 1 3

Sample Output

0
1

Hint

感谢MT大牛贡献译文.

Source

这个题。。。。额。。非常恶心。。
首先找规律是要悲剧的囧。。。我弄了半天毫无成效。。
然后想的就是DP。。。。
比如说F(l1,r1,l2,r2)表示X的l到r,Y的l2到r2是否匹配。。
然后Prefix和Suffix都可以预处理。所以就是N^4。。无压力TLE
然后注意到两个字串中的不同数的数量肯定是一样的。。//就是W
然后F(l1,l2,num)表示X从l1开始,Y从l2开始。。都是num个不同的字符。。是否匹配。。?
设K=100
N^2*K。。。无压力TLE。。
然后注意到这个是检查是否相等。。所以可以用Hash。。
就是把它的prefix和suffix随便Hash一下。。然后两个判断X和Y是否相等。。
这样的话要考虑如何算Prefix。。如果预处理每个一位到下一个每种数的最近值(前和后)。。?
可以在O(K)的时间搞定Prefix和Suffix。。
然后就可以在N*K^2的时间搞定Hash。。。
然后再考虑如果对每一位的信息进行排序。。
可以做到O(LogK)的时间搞定Prefix和Suffix。。就是N*K*LogK
我现在写的就是这样。。TLE的非常严重。。但是我发现我写的这样要比
标程快很多瀑布汗。。。root的时限好紧啊囧。。。
然后接下来还是可以优化。。不过七夕节到了有别的事要忙就先不写了囧。。。。
如果用扫描的办法可以在N*K的时间内算出所有Prefix和Suffix。。然后
复杂度就是N*K了。。应该可以AC吧囧。。。
终于AC。。泪流满面。。。

[Ahoi2005]SHUFFLE 洗牌

[Ahoi2005]SHUFFLE 洗牌

Time Limit:3000MS  Memory Limit:65536K
Total Submit:66 Accepted:22
Case Time Limit:1000MS

Description

为了表彰小联为Samuel星球的探险所做出的贡献,小联被邀请参加Samuel星球近距离载人探险活动。
由于Samuel星球相当遥远,科学家们要在飞船中度过相当长的一段时间,小联提议用扑克牌打发长途旅行中的无聊时间。玩了几局之后,大家觉得单 纯玩扑克牌对于像他们这样的高智商人才来说太简单了。有人提出了扑克牌的一种新的玩法。
对于扑克牌的一次洗牌是这样定义的,将一叠N(N为偶数)张扑克牌平均分成上下两叠,取下面一叠的第一张作为新的一叠的第一张,然后取上面一叠的 第一张作为新的一叠的第二张,再取下面一叠的第二张作为新的一叠的第三张……如此交替直到所有的牌取完。
如果对一叠6张的扑克牌1 2 3 4 5 6,进行一次洗牌的过程如下图所示:

从图中可以看出经过一次洗牌,序列1 2 3 4 5 6变为4 1 5 2 6 3。当然,再对得到的序列进行一次洗牌,又会变为2 4 6 1 3 5。
游戏是这样的,如果给定长度为N的一叠扑克牌,并且牌面大小从1开始连续增加到N(不考虑花色),对这样的一叠扑克牌,进行M次洗牌。最先说出经 过洗牌后的扑克牌序列中第L张扑克牌的牌面大小是多少的科学家得胜。小联想赢取游戏的胜利,你能帮助他吗?

Input

有三个用空格间隔的整数,分别表示N,M,L
(其中0< N ≤ 10 ^ 10 ,0 ≤ M ≤ 10^ 10,且N为偶数)。

Output

单行输出指定的扑克牌的牌面大小。

Sample Input

6 2 3

Sample Output

6

Source

Day1
额。。这题就是找规律。。然后解方程。。
可以发现方程就是
(2^M)*x % (N+1) = L
。。。。然后就没什么问题了。。

[Hnoi2010]chorus 合唱队

[Hnoi2010]chorus 合唱队

Time Limit:4000MS  Memory Limit:65536K
Total Submit:97 Accepted:59
Case Time Limit:1000MS

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

8

Hint

Source
额。。这个题目显然可以直接Dp。。状态就是当前队列(只肯是一个连续子序列)和最后一个是左边还是右边。。
然后就可以无压力AC了囧。。
Code:

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=1000,mod=19650827;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int Dp[maxn][maxn][2]={};
int A[maxn],n;
inline void Update(int&x,int c)
{
x+=c;if(x>=mod)x-=mod;
}
int main()
{
//freopen("in","r",stdin);
cin>>n;rep(i,n)scanf("%d",A+i),Dp[i][i][0]=1;
for(int s=1;s<n;s++)
for(int l=0;l+s<=n;l++)
{
int r=s+l;
{
int&ret=Dp[l][r][0];
if(A[l]<A[l+1])Update(ret,Dp[l+1][r][0]);
if(A[l]<A[r])Update(ret,Dp[l+1][r][1]);
}
{
int&ret=Dp[l][r][1];
if(A[r]>A[r-1])Update(ret,Dp[l][r-1][1]);
if(A[r]>A[l])Update(ret,Dp[l][r-1][0]);
}
}
int ans=0;Update(ans,Dp[0][n-1][0]);
Update(ans,Dp[0][n-1][1]);
printf("%dn",ans);
}

[Hnoi2010]Planar

[Hnoi2010]Planar

Time Limit:10000MS  Memory Limit:65536K
Total Submit:118 Accepted:33
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

Source

Day1

恩。。这个题目还是挺水的。。就是我好久没写判二分图了多次WA囧。。。
把这个哈密顿回路拉成一个环。。那么可以发现如果两条边在环上相交。。
显然需要一个在环内一个在环外。。就可以看成2-染色。。
然后就没有然后了。。

[SHOI2008]汉诺塔

[SHOI2008]汉诺塔

Time Limit:1000MS  Memory Limit:165536K
Total Submit:21 Accepted:15

Description

汉诺塔由三根柱子(分别用A B C表示)和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上,大的在下面,小的在上面,形成了一个塔状的锥形体。


对汉诺塔的一次合法的操作是指:从一根柱子的最上层拿一个盘子放到另一根柱子的最上层,同时要保证被移动的盘子一定放在比它更大的盘子上面(如果 移动到空柱子上就不需要满足这个要求)。我们可以用两个字母来描述一次操作:第一个字母代表起始柱子,第二个字母代表目标柱子。例如,AB就是把柱子A最 上面的那个盘子移到柱子B。汉诺塔的游戏目标是将所有的盘子从柱子A移动到柱子B或柱子C上面。
有一种非常简洁而经典的策略可以帮助我们完成这个游戏。首先,在任何操作执行之前,我们以任意的次序为六种操作(AB、AC、BA、BC、CA和 CB)赋予不同的优先级,然后,我们总是选择符合以下两个条件的操作来移动盘子,直到所有的盘子都从柱子A移动到另一根柱子:
(1)这种操作是所有合法操作中优先级最高的;
(2)这种操作所要移动的盘子不是上一次操作所移动的那个盘子。
可以证明,上述策略一定能完成汉诺塔游戏。现在你的任务就是假设给定了每种操作的优先级,计算按照上述策略操作汉诺塔移动所需要的步骤数。

Input

输入有两行。第一行为一个整数n(1≤n≤30),代表盘子的个数。第二行是一串大写的ABC字符,代表六种操作的优先级,靠前的操作具有较高的优先级。 每种操作都由一个空格隔开。

Output

只需输出一个数,这个数表示移动的次数。我们保证答案不会超过10的18次方。

Sample Input

3
AB BC CA BA CB AC

Sample Output

7

Source
这题很有意思。。
首先如果n<=3的话可以暴力模拟。。
然后可以证明这个一定满足Fn=Fn-1*a+b
所以可以算出a和b之后。。推出Fn。

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1;
using namespace std;
typedef long long ll;
int Moves[6][2],n;
void init()
{
cin>>n;
char a;
rep(i,6)
{
scanf(" ");
rep(j,2)cin>>a,Moves[i][j]=a-‘A';
}
}
int Stupid_Cal(int n)
{
vector<int> Stack[3];
for(int i=n;i>=1;i–)Stack[0].pb(i);
int last=0;
for(int num=0;;)
{
if(Stack[1].size()==n||Stack[2].size()==n)
return num;
rep(i,6)
{
int from=Moves[i][0],to=Moves[i][1];
if(Stack[from].size()&&Stack[from].back()!=last)
if(Stack[to].size()==0||Stack[from].back()<Stack[to].back())
{
last=Stack[from].back();
Stack[from].pop_back();
Stack[to].pb(last);
num++;
break;
}
}
}
}
void Solve()
{
if(n<=3){cout<<Stupid_Cal(n)<<endl;return;}
int a2=Stupid_Cal(2),a3=Stupid_Cal(3);
int a=a3/a2,b=a3-a*a2;
ll ans=a3;
for(int i=4;i<=n;i++)
ans=ans*a+b;
cout<<ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
init();
Solve();
}

Interconnect Interconnect

Interconnect Interconnect

Time Limit:10000MS  Memory Limit:65536K
Total Submit:48 Accepted:37
Case Time Limit:1000MS

Description

给出无向图G(V, E). 每次操作任意加一条非自环的边(u, v), 每条边的选择是等概率的. 问使得G连通的期望操作次数. (|V| <= 30, |E| <= 1000)

Input

第一行两个整数N,M
1<=N<=30
0<=M<=1000
接下来M行,每行两个整数X,Y表示两者之间已修好一条道路.
两点之间可以不止修了一条路,也有可能M条路已使N个点成为一个整体.

Output

输出一个小数,表示新修道路条数的期望值,保留六位小数.

Sample Input

4 2
1 2
3 4

Sample Output

1.500000

Source
这个题目我看到之后第一感觉就是状态压缩Dp。。
状态就是各个联通块的大小。。
然后发现状态最多只有5604个。。
然后就可以无压力Dp了。。
为了方便我使用了Map存数据,vector存状态,
速度奇慢无比。。

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(VI::iterator e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1;
using namespace std;
typedef vector<int> VI;
map<VI,double> Map;
int n,m;
int total;
double Dp(VI A)
{
if(Map.count(A))return Map[A];
double&x=Map[A];
if(A.size()==1)return x=0;
double same=0;
rep(i,A.size())
rep(j,i+1)
if(i==j)
same+=double(A[i]*(A[i]-1)/2)/total;
else
{
VI New=A;
New[i]+=New[j];swap(New[j],New[New.size()-1]);
New.pop_back();sort(New.begin(),New.end());
x+=double(A[i]*A[j])/total*Dp(New);
}
x=(x+1)/(1-same);
return x;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;total=n*(n-1)/2;
VI comp(n);
rep(i,n)comp[i]=i;
int s,t;
rep(i,m)
{
cin>>s>>t;–s;–t;int that=comp[t];
if(comp[s]!=comp[t])
rep(j,n)if(comp[j]==that)
comp[j]=comp[s];
}
VI count(n,0),Now;
rep(i,n)count[comp[i]]++;
rep(i,n)if(count[i])Now.pb(count[i]);
sort(Now.begin(),Now.end());
printf("%0.6lfn",Dp(Now));
//cout<<Map.size()<<endl;
}

不相交路径

不相交路径

Time Limit:10000MS  Memory Limit:65536K
Total Submit:40 Accepted:14
Case Time Limit:1000MS

Description

给出一个N(n<=150)个结点的有向无环简单图。给出4个不同的点a,b,c,d,定义不相交路径为两条路径,两条路径的起点分别为a 和c,对应的两条路径的终点为b和d,要求满足这两条路径不相交,即两条路径上没有公共的点。
现在要求不相交路径的方案数。

Input

第一行为N,M。表示这个有向无环图有N个节点,M条边。
接下来M行,每行两个整数x,y。表示x至y有一条有向边。
接下来一行四个数a,b,c,d,意义如题中所述。

Output

输出为一行,即答案(方案数)。

Sample Input

5 6
1 5
1 3
2 5
2 4
5 3
5 4
1 3 2 4

Sample Output

3

Source
我看到这个题目之后。。第一感觉就是需要高精。。
然后感觉正难则反嘛。。所以可以用补集转化。。
首先拓扑排序一下。。
然后设G[s][t]为s到t的路径条数。。
随便Dp一下就出来了。。
然后设F[t]为s1->t,s2->t之前不相交的路径对数。。
显然枚举一下在前面相交的,减掉即可。。
F[t]=G[s1][t]*G[s2][t]-Sum{F[k]*G[k][t]^2}..
然后就差不多OK了。。
Ans=G[s1][t1]*G[s2][t2]-Sum{F[k]*G[k][t1]*G[k][t2]}。。
就OK了。。

Page 20 of 54« First...10...1819202122...304050...Last »