2010-04-07 13:47 #include<iostream>
using namespace std;
//最小割+找割边
//给定一个有向带权图，你可以选择一些点来控制，然后删除一些边，使得与城市1不连通
//然后删除一些边，使得与城市1不连通（注意到这些边必定是割边），设获利为选得的点总权值-删除边的权值和
//目标就是获利最大，那么这个1点我们就可以看做是个源点，我们增加一个汇点t，把问题等价成把图分成两部分
//使得源点到汇点不连通，同时要保证和选择的点也不连通，那么对于可选择点，我们向汇点连容量为点权的边
//那么问题最终的结 |
2010-04-06 13:44 #include<iostream>
#include<algorithm>
using namespace std;
//求最大的Pseudoforest森林
//做法kruscal，首先按边权从大到小排序，然后能加边的条件是，（1）两个集合不同，且至少一个没有被染色
//且祖先变成那个有环的那个（2）两个集合相同，且当前集合还没有加环
const int maxn=10000;
const int maxm=100000;
int n,m,ans;
int a[maxn],b[maxn];
typedef struct edge
{
int s,e,d;
bool operator<(const edge |
2010-03-29 22:12 2010-03-24 20:29 #include<iostream>
using namespace std;
//f[1]=a,f[2]=b;f[n]=f[n-1]*f[n-2],求f[n]%p
//定义A[i]表示a在第i项中的个数，B[i]表示b在第i项中的个数
//A[1]=1;A[2]=0;A[3]=1;A[n]=A[n-1]+A[n-2];B[1]=0;B[2]=1;B[3]=1;B[n]=B[n-1]+B[n-2];
//f[n]=a^(A[n])*b^(B[n])%p
//f[n]=(a^A[n]%p)*(b^B[n]%p)%p
//f[n]=(a^(A[n]%phi[p]+phi[p])%p)*(b^(B[n]%phi[p]+phi[p])%p)%p
//对于任意一项而言必定都是a^x*b^y的形式
//注意一点 a^b%c=a^(b%phi(c)+phi(c))当且仅当 b>phi(c);
typed |
2010-03-24 14:49 #include<iostream>
using namespace std;
const int maxn=4;
//数论
//这是个四阶的矩阵 f[1]=1;f[2]=2;
//(s[n-1],a[n]^2,a[n]*a[n-1],a[n-1]^2)=(s[n-2],a[n-1]^2,a[n-1]*a[n-2],a[n-2]^2)*A
//A=|1 0 0 0 |
// |1 1 1 1 |
// |0 2 1 0 |
// |0 1 0 0 |
int mod;
typedef __int64 LL;
int ans[4]={1,4,2,1};
LL phi(LL n)
{
LL sum=1,i;
for(i=2;i*i<=n;i++)
{
|
2010-03-23 18:08 #include<iostream>
using namespace std;
//给定一个网络，求从s到t的最短路条数，注意每个点只能访问一次
//那么问题转化成最小代价的增广路连续出现的次数， 一开始没看到约束条件，整了个SPFA+DP
const int maxn=300*2;
const int maxm=300*300*2*2;
const int INF=100000000;
////////费用流
inline int min(int x,int y){return x<y?x:y;}
typedef struct node
{
int v,flow,cost;//下一点，容量，费用
node *next;
|
2010-03-22 16:11 #include<iostream>
#include<algorithm>
using namespace std;
//线段树
//给定一个序列，求区间出现的数的数值和，若有多个，只计算一次
//当时一个很直观想法就是类似POJ 2761那样动态的增删,不过大致也茶不错
//首先定义一个c数组，是原序列的离散化，pre数组表示当前位置元素上一次出现时间，为0表示还未出现
//那么我们对询问区间按右节点排序，这样我们每次维护的都是从前到当前位置，保证其重复元素不累加
//那 |
2010-03-22 10:10 #include<iostream>
using namespace std;
//给定n个摧毁目标，在剩下的数字中第k个哪个数字，转化成线段树
const int maxn=50005;
int a[maxn],b[maxn];
typedef struct node
{
int l,r,val;
}node;
node tree[4*maxn];
void build(int k,int l,int r)
{
tree[k].l=l;tree[k].r=r;
if(l==r){tree[k].val=a[l+1]-a[l]-1;return ;}
int mid=(l+r)>>1;
build(k*2,l,mid);build(k*2+1,mid+1,r);
tree[k].val=tree[k*2].val+tree[k*2+1].val;
} |
2010-03-22 9:36 #include<iostream>
using namespace std;
//首先这题确实很BT，yayamao大牛神奇的20分钟秒确实很orz，lcc的40分钟秒也很orz
//这题分为这么几个步骤
//问题(1)求得fib[a^b]%c的循环节，这里我开了dp[1000][1000]hash，暴力找出循环节 这样可以得到A[0]
//问题(2)获得A序列后，队序列整体+1求后缀，获得height数组
//问题(3)将模型转化，等价于求在height数组里面找最大的矩形，对于一种字串的解，我们总可以用若干个后缀代替
//他们的公共前缀就是这个字串，而这些后缀体现在height数组中必 |
2010-03-19 18:12 #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=1000000000;
//SPFA+DP
//给你一个任务，需要n天，m为地图上的点数cos表示每次改变运输线路所需要的成本
//给你e个信息，表示某个点在时间区间[l,r]内无法卸货，即无法访问，等价于把这个店在这个区间内从图上删去
//要你制定一份计划，使得最终的费用最小
//dp[i][j]表示从第i天到第j天的最优值，那么转移就是dp[i][j]=min(dp[i][k]+cost+dp[k+1][j])(i<=k<=j-1)
//暴 |
| | |
