sgu 247 Difficult Choice

BT阿。。这明明就是IMO1996年的竞赛题阿。。
设A={1..p},B={p+1..2*p}
那么A和B是一种选法。。
然后对于其他的每一种选法。必然有A也有B。。
那么把它的全体B中的数+1、+2、+3、。。、+p-1由于p是素数。。
所以必有p-1个和模p不为0的选法与其对应。。
于是答案就是(C(2n,n)-2)/p+2。。。
高精写次了。。用Java算了答案后交了个表。。

USACO 2004 Feb (2)

1986.Distance Queries
大意:
给一颗树。。每次询问两点之间的距离。。
很明显是要求lca的。。又不是要求在线算法。。于是我就用tarjan了。。
#include<cstdio>
#include<utility>
#include<vector>
using namespace std;
const int maxn=40000;
typedef pair<int,int> pi;
int F[maxn];
inline void makeset(int x)
{
F[x]=x;
}
int find(int x)
{
if(x!=F[x]) F[x]=find(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=find(x);y=find(y);
F[y]=x;
}
int cnt=0;
vector<pi> Ask[maxn],E[maxn];
int Ans[maxn],Dep[maxn];
bool vis[maxn]={0};
void addQuery(int x,int y)
{
Ask[x].push_back(pi(y,cnt));
Ask[y].push_back(pi(x,cnt));
cnt++;
}
void addEdge(int s,int t,int c)
{
E[s].push_back(pi(t,c));
E[t].push_back(pi(s,c));
}
int n,m,k;
void dfs(int x,int dep)
{
vis[x]=true;
Dep[x]=dep;
makeset(x);
for(int v,i=0;i<E[x].size();i++)
if(!vis[v=E[x][i].first])
{
dfs(v,dep+E[x][i].second);
Union(x,v);
}
for(int lca,v,i=0;i<Ask[x].size();i++)
if(vis[v=Ask[x][i].first])
{
lca=find(v);
Ans[Ask[x][i].second]=Dep[x]+Dep[v]-2*Dep[lca];
}
}
int main()
{
scanf("%d %d",&n,&m);
int s,t,l;char c;
while(m–)
{
scanf("%d %d %d %c",&s,&t,&l,&c);s–;t–;
addEdge(s,t,l);
}
scanf("%d",&k);
for(int i=0;i<k;i++)
{
scanf("%d %d",&s,&t);s–;t–;
addQuery(s,t);
}
dfs(0,0);
for(int i=0;i<k;i++)
{
printf("%dn",Ans[i]);
}
}1987.Distance Statistics
这道有点意思:
给一颗树。。求出其中距离不超过K的点有多少对。。
明显是要用分治。。首先多叉转二叉。。所有点到兄弟的边长度都为0。。
之所以要多叉转二叉是因为如果不转的话。。有些情况(例如星形树。。)你就悲剧了。。
这样两点之间的距离还是不变的。。
然后用基于边的分支。。每次找出中心边。。再分成两棵子树。。
然后两个点都在子树内部的可以递归解决。。需要算的是两个点在不同子树的。。
两个子树所有节点都按到根的距离排序。。然后就可以扫描了。。
可惜我的Code写次了。。时间超了1倍。。需要去改改。。
没AC就不发了。。

USACO 2004 Feb (1)

这绝对是树窝。。全是关于树的题目。。。倒。。
1984.Navigation Nightmare
大意:
就是一个地图。。每次告诉你一个点相对于另一个点的坐标。。然后有一些询问。。
都是问两个点之间的曼哈顿距离是多少。。如果信息不够就输出-1。。
好像有点难。。如果不是动态查询的话只好算出每个点的坐标就可以了。。但这里是动态的。
很麻烦。。我想了想发现是可以用并查集做的。。
对每个点i。F[i]是其父亲。。D[i]是相对于其父亲他的坐标。。
那么在路径压缩的时候可以顺便维护D[i]。。
对于一个点Find一下就可以算出其对于根的坐标。。查询如果根不同则不知道。。
连接的时候记得要转换一下相对的坐标。。
否则就是坐标的曼哈顿距离。。
Code。。
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
const int maxn=40000;
typedef pair<int,int> pi;
inline int abs(int x){return x<0?-x:x;}
inline pi operator+(const pi&x,const pi&y)
{
return pi(x.first+y.first,x.second+y.second);
}
inline pi operator-(const pi&x,const pi&y)
{
return pi(x.first-y.first,x.second-y.second);
}
inline int dist(const pi&x,const pi&y)
{
return abs(x.first-y.first)+abs(x.second-y.second);
}
pi get(int l,char d)
{
switch(d)
{
case ‘N':return pi(0,l);
case ‘S':return pi(0,-l);
case ‘E':return pi(l,0);
case ‘W':return pi(-l,0);
}
}
struct data
{
int s,t,l;
char d;
}D[maxn];
struct query
{
int x,y,t,n;
bool operator<(const query&x) const
{return t<x.t;}
}Q[maxn];
int n,m,k;
void init()
{
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d %d %d %c",&D[i].s,&D[i].t,&D[i].l,&D[i].d);
scanf("%d",&k);
for(int i=0;i<k;i++)
scanf("%d %d %d",&Q[i].x,&Q[i].y,&Q[i].t),Q[i].n=i;
sort(Q,Q+k);
}
int F[maxn];
pi P[maxn];
void set(int n)
{
for(int i=0;i<n;i++)
F[i]=i,P[i]=pi(0,0);
}
void find(int x)
{
if(x!=F[x])
find(F[x]),P[x]=P[x]+P[F[x]],F[x]=F[F[x]];
}
void Union(int x,int y,pi d)
{
find(x);d=d-P[x];x=F[x];
find(y);d=d+P[y];y=F[y];
F[x]=y;P[x]=d;
}
int ask(int x,int y)
{
find(x);find(y);
if(F[x]!=F[y]) return -1;
return dist(P[x],P[y]);
}
void deal(data x)
{
x.s–;x.t–;
pi d=get(x.l,x.d);
Union(x.s,x.t,d);
}
int main()
{
init();
set(n);
int last=0;
int Ans[maxn];
for(int i=0;i<k;i++)
{
for(int j=last;j<Q[i].t;j++)
{
deal(D[j]);
}
last=Q[i].t;Ans[Q[i].n]=ask(Q[i].x-1,Q[i].y-1);
}
for(int i=0;i<k;i++)
printf("%dn",Ans[i]);
}1985.Cow Marathon
大意:
一颗树,求其中距离最远的两点的距离。。
经典算法。。两次dfs。。
也可以DP。。
水题就不多说了。。。
Code。。
#include<cstdio>
#include<utility>
#include<vector>
#include<cstring>
using namespace std;
typedef pair<int,int> pi;
typedef vector<pi>::iterator it;
const int maxn=40000;
int n,m;
vector<pi> E[maxn];
inline void add(int s,int t,int c)
{
E[s].push_back(pi(t,c));
E[t].push_back(pi(s,c));
}
void init()
{
scanf("%d %d",&n,&m);int s,t,c;char a;
while(m–)
{
scanf("%d %d %d %c",&s,&t,&c,&a);s–;t–;
add(s,t,c);
}
}
int dist[maxn];
bool vis[maxn];
void dfs(int x,int d)
{
vis[x]=true;dist[x]=d;
for(it i=E[x].begin();i!=E[x].end();i++)
if(!vis[i->first])
{
dfs(i->first,d+i->second);
}
}
int find(int t)
{
memset(vis,false,sizeof(vis));
dfs(t,0);int mi=0;
for(int i=1;i<n;i++)
if(dist[i]>dist[mi])
mi=i;
return mi;
}
int main()
{
init();
int t=find(0);
printf("%dn",dist[find(t)]);
}

sgu 377

N久没做sgu了。。。
这道题意思是说给你一个n*m的棋盘每个数或为1或为0,每一个2*2的子矩阵的和都是2。。
求方法数。。
n和m那么大肯定是有公式的。。
先是写了状压DP算了一下。。看出公式是2^m+2^n-2。。
我是这么推导的。。
因为第一行有2^m种放法。。其中除了010101和101010之外。。
第一行一确定其他行也都确定了。。于是就有2^m-2种。。
又如果第一行是010101或101010。。那么第二行也只能选这两种。。
每一行都有两种选择。。于是就是2^n种。。
加一下就是答案了。。。
#include<iostream>
#include<cstring>
using namespace std;
const int maxl=1000;
struct bignum
{
int Q[maxl],last;
bignum()
{
memset(Q,0,sizeof(Q));last=0;
}
void set(int a)
{               
Q[last]=a;
}
int& operator[](int v){return Q[v];}
bignum operator+(bignum&x)
{
bignum ans;ans.last=max(last,x.last);int d=0;
for(int i=0;i<=ans.last;i++)
{
d+=x[i]+Q[i];
ans[i]=d%10;
d/=10;
}
if(d)ans[++ans.last]=d;
return ans;
}
void operator-=(int x)
{   
for(int i=0;i<=last;i++)
{
if(Q[i]>=x) {Q[i]-=x;return;}
else{Q[i]=10+Q[i]-x;x=1;}
}
}
bignum operator*(int x)
{
int d=0;bignum ans;ans.last=last;
for(int i=0;i<=ans.last;i++)
{
d+=Q[i]*x;
ans[i]=d%10;
d/=10;
}
while(d)
{
ans[++ans.last]=d%10;
d/=10;
}
return ans;
}
void operator=(const bignum&x)
{
memmove(Q,x.Q,sizeof(Q));
last=x.last;
}
void print()
{
for(int i=last;i>=0;i–)
cout<<Q[i];
}
}a,b;
int main()
{
int n,m;cin>>n>>m;
if(n<m){int t=n;n=m;m=t;}
b.set(1);
for(int i=1;i<=n;i++)
{
b=b*2;
if(i==m) a=b;
}
a=a+b;
a-=2;
a.print();cout<<endl;
}

Page 2 of 212