[Hnoi2010]Planar

Posted on by

[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]汉诺塔

Posted on by

[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

Posted on by

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

不相交路径

Posted on by

不相交路径

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了。。

[Usaco2006 Open]Two-Headed Cows

Posted on by

。。。八中OJ上居然没有题目。。
不过我还是找到了题目。。
tdt.sjtu.edu.cn/~rma/USACO/task/2006/Open/twohead.txt
这个下午没什么心情。。就去八中OJ刷USACO的水题。。
水了很多道囧。发现这道算最有意思的瀑布汗。。
首先可以发现显然可以贪心的分配。。
就是每次都到一个个往当前的段加，知道不满足为止。。
判断是否满足就是个简单的2-SAT。。
我考虑了两个想法。。
要么是每次暴力2-SAT。。显然TLE。。
如果二分的话。。那么也是可能会TLE的。。
所以只好搞动态维护。。
先说一下构图。。
1A表示Cow1的头A。。
那么如果1A 讨厌 2A。
那么1A <-> 2B 1B<->2A..
连线表示一定要在一边。。
如果什么时候发现1A<->1B。。
就矛盾了。。
我表示传统的并查集面对这样的询问只能悲剧。。
所以只好使用非常规的。。就是启发式合并的那个。。
而且为了询问是否有这种。。需要用set。。。
然后就差不多了。。
恩。。这个复杂度有点惊悚。。
启发式合并本身就是NLogN的，加上还要用set。。
就是NLogN^2的。。。
不过居然AC了。。
#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(set<int>::iterator e=x.begin();e!=x.end();e++)
#define trV(e,x) for(vector<int>::iterator e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=50000;
using namespace std;
struct UF
{
set<int> node[maxn];
int root[maxn];
UF()
{
rep(i,maxn)
root[i]=i,node[i].insert(i);
}
bool Union(int i,int j)
{
i=root[i];j=root[j];
if(i!=j)
{
if(node[i].size()<node[j].size())
swap(i,j);
tr(e,node[j])
{
int x=*e;
if(node[i].find(x^1)!=node[i].end())return false;
node[i].insert(x);root[x]=i;
}
node[j].clear();
}
return true;
}
}U;
int n,m;
vector<int> E[maxn];
void AddEdge(int s,int t)
{
if(s<t)swap(s,t);
E[s].pb(t);
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;int s;char c;
rep(i,m)
{
cin>>s>>c;–s;int a=s*2+c-‘A’;
cin>>s>>c;–s;int b=s*2+c-‘A’;
AddEdge(a,b^1);AddEdge(b,a^1);
}
int ans=0;int pre=-1;
rep(i,n)
{
for(int t=i*2;t<i*2+2;t++)
trV(e,E[t])if(*e>pre*2+1&&!U.Union(t,*e))
{
ans++;
pre=i;
continue;
}
}
ans++;
cout<<ans<<endl;
}

NOI 网上同步赛。。

Posted on by


这个。。我表示震惊。。
恩。。就写点总结吧。。
首先我感觉我的水平比去年NOIP的时候是要强多了。。其实这个倒是其次，
重要的是心态好多了。。。。
Day1的话前两题都算是运气好。一个是刚好做过Zap。。一个是刚好会搞划分树。。
第三题的话现在想想确实不够稳重额。。实际上在网络流可以80分的情况下，偏偏
要写不熟悉的平面图最短路。。然后就悲剧掉了50分。。。甚至我直接放弃下一半
输入数据。。我觉得有脑子就应该发现这肯定是有问题的。。看样子当时是被前两题
冲昏了头脑。。以后一定要冷静啊。。
Day2的话暴露了我各种不行的地方囧。。
首先是Problem 1。。。看样子我确实是过于浮躁。。
没有多想就写了个暴力算法和一个囧囧的贪心。。实际上这题也不是非常难的。。
第二题就更悲剧了。。完全没有认真专研剪枝的心思。。写了个很垃圾的剪枝。。
第三题彻底悲剧。。我一开始看了数据。。感觉又一些是一维的，显然可以Dp。
有一些是经典的落盘子问题。。也可以Dp。。前三个都可以暴力。。
但由于我过于SB。。懒得去写Dp。。直接写了个每次去最近点的贪心。。
可能也是因为windows下Linux的check不能用吧。。我当时很慌。。
但是一估摸时间还有1个小时。。于是就强作镇定的自己写了一个check。。
然后调了半天才能用。。
我不行的地方…
复杂一点的贪心。。。剪枝的技巧。。。耐心和恒心。。考场上的判断力。。。

SRM 478 Solution。。

Posted on by

哎。这场极度失败的SRM。。。。看来自己不行的地方还有很多啊囧。。。
250：
注意到所有的变换都是x->2^n*x+2^n-1
设F(a,x)=2^n*x+2^n-1,
那么可以证明F(a,F(b,x))=F(a+b,x)..
然后变换只有a=2和a=3.。那么找出最小的t使得F(t,x)%1000…007为0.。。
然后把t表示成2和3的和就OK了。。
悲剧的是我忘了考虑一开始就可以的状态了。。然后果断被Cha。。0分。。
500：
也就是个状态压缩的Dp汗。。
设Ans[subset]为把subset的那些归并成一堆可以得到的钱，
Dp[subset]subset那些可以得到的最大钱
然后穷举一下啊subset的子集就可以了。。
1000：
设sum为所有的取法数，
考虑先算出p[i]=取的时候在第i个盒子里取的概率（就是这个盒子被选中了并且抽中了。。）
根据这个就可以算出全部了。。
设 Dp[total]为选total个苹果的方法总数，Dp2[total]为忽略第i个盒子这样的方法总数，
那么 with=Dp[total]-Dp2[total]就是选第i个盒子这样的方法总数，
那么with/sum*(Size[i]/total)就是这种情况下的概率。。
然后枚举total。。全部+起来就可以搞出p[i]了。。就OK了汗。。
Size[i]是第i个盒子中苹果总数
。。我就是一个傻X。。。