|
|
下面是容斥原理的代码(主要用来计数)：f(i)是指具有性质i的个数
Code：
int s = 0;
for(int i=1;i<(1<<n);i++){
int ccount = 0;
for(int j=0;j<n;j++){
int test = ((1<<j)&i);
if(test!=0) ccount++;
}
if(ccount&1) s += f(i);
else s -= f(i);
}
练习：
PKU 2773
HDU 3507
spfa是使用队列进行渐近求最短路的方法：
思想为：
1、只保存被更新但未扩展的节点（即未进队的节点）
做法：
1、n建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空
2、n期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
使用队列的伪代码：
queue <Node *> Q;
while(!Q.empty()) Q.pop();
memset(visit , 0 , sizeof(visit));
for(i = 2;i <= p; ++ i) dist[i] = inf;
dist[1] = 0;
Q.push(father[1]);
visit[1] = true;
练练手：HDU 3499
用队列如何判断负环呢？当某个节点n次进入队列，则存在负环，此时时间复杂度为O(n*m),n为节点，m为边，
当n= 1000000 m=2000000是，那时间就相当可观了。
有什么更好的方法吗？有！深度优先搜索，得到一个更新的节点接扩展，
然后利用栈，当出现栈中的节点时，则存在负环。时间复杂度就基本保持在O(m)内；
实战 WordRings(ACM-ICPC Centrual European 2005)
先上代码：
 
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <string.h>
using namespace std;
const int inf = 0x7ffffff;
#define Max 410
int flow[Max][Max],d[Max]; //flow is the network
int sta,end,N; //sta is the sourse ,end is the end,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0;
int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front<rear)
{
int k=q[front++];
for(int i=0;i<=N;i++)
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if (k==end)
return sum;
int os = sum;
for(int i=0;i<=N&∑i++)
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.
flow[k][i] -= a;
flow[i][k] += a;
sum -= a;
}
return os-sum;
}
int main()
{
int i,j,n,np,nc,m;
int x,y,v;
char s[20],*p;
while (scanf("%d %d %d %d",&n,&np,&nc,&m) != EOF)
{
sta = n; end = N = n + 1;
memset(flow,0,sizeof(flow));
for (i = 1; i <= m; i++)
{
scanf("%s",s);
p = s + 1;
sscanf(p,"%d",&x);
p = strchr(p,',') + 1;
sscanf(p,"%d",&y);
p = strchr(p,')') + 1;
sscanf(p,"%d",&v);
flow[x][y] += v;
}
for (i = 1; i <= np; i++)
{
scanf("%s",s);
p = s + 1;
sscanf(p,"%d",&x);
p = strchr(p,')') + 1;
sscanf(p,"%d",&v);
flow[sta][x] = v;
}
for (i = 1; i <= nc; i++)
{
scanf("%s",s);
p = s + 1;
sscanf(p,"%d",&x);
p = strchr(p,')') + 1;
sscanf(p,"%d",&v);
flow[x][end] = v;
}
int ret = 0;
while(bfs(sta))
ret += dinic(sta,inf);
printf("%d\n",ret);
}
return 0;
}
题意：n个接口不同的插板，m个有用电器有各自的接口，k种可进行接口转换的适配器（数量不限），问最少多少个用电器不能用电（同时）。
分析：直接转换为典型的最大流问题，源点汇点自定，不同类型接口的插板与汇点相连权值为1；用电器与源点相连，权值为一；适配器的接口之间相连，权值为无穷大。建完图后，dinic模板一贴，完美解决。
注意：接口类型为字符串，用map映射转换。
cpp代码：
#include<iostream>
#include <cstdio>
#include <map>
#include <string>
#include <memory.h>
using namespace std;
map <string,int> mp;
const int inf = 0x7ffffff;
#define Max 605
int flow[Max][Max],d[Max],cnt; //flow is the network
int sta,end,N; //sta is the sourse ,end is the end,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0;
int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front<rear)
{
int k=q[front++];
for(int i=0;i<=N;i++)
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if (k==end)
return sum;
int os = sum;
for(int i=0;i<=N&∑i++)
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.
flow[k][i] -= a;
flow[i][k] += a;
sum -= a;
}
return os-sum;
}
int main()
{
int i,j,n,m,k;
char s[30],se[30];
sta = 0; end = N = Max - 1;
while (scanf("%d",&n) != EOF)
{
memset(flow,0,sizeof(flow));
mp.clear();
cnt = 0;
//读入插座类型
for (i = 1; i <= n; i++)
{
scanf("%s",s);
if (mp.count(s) == 0)
mp[s] = ++cnt;
flow[mp[s]][end] ++;
}
//读入用电器类型
scanf("%d",&m);
for (i = 1; i <= m; i++)
{
scanf("%s",s);
scanf("%s",s);
if (mp.count(s) == 0)
mp[s] = ++cnt;
flow[sta][mp[s]] ++;
}
//读入适配器类型
scanf("%d",&k);
for (i = 1; i <= k; i++)
{
scanf("%s %s",s,se);
if (mp.count(s) == 0)
mp[s] = ++cnt;
if (mp.count(se) == 0)
mp[se] = ++cnt;
flow[mp[s]][mp[se]] = inf;
}
int ret = 0;
while(bfs(sta))
ret += dinic(sta,inf);
printf("%d\n",m - ret);
}
return 0;
}
题意：找最小角中的最大角，具体见题分析：纯枚举A选的点，计算此点能得到的最小角，枚举完后取最大。
主要用到atan2(y,x)求(0,0)与(x,y)的连线与0-x轴的弧度[-PI , PI].
PI = acos(-1.0). cpp代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double PI = acos(-1.0);
double x[1010],y[1010],MAX,MIN;
double d[1010];
int n;
inline double myatan2(double y,double x)
{
double t = atan2(y,x);
// printf("%lf\n",t >= 0 ? t : t + 2*PI);
return t >= 0 ? t : t + 2*PI;
}
int main()
{
int i,j,k,cnt;
while (scanf("%d",&n) && n >= 3)
{
MAX = -1.0;
for (i = 1; i <= n; i++)
scanf("%lf %lf",&x[i],&y[i]);
for (i = 1; i <= n; i++)
{
MIN = PI;
cnt = 0;
for (j = 1; j <= n; j ++)
if (j != i)
d[++cnt] = myatan2(y[j]-y[i],x[j]-x[i]);
sort(d+1,d+cnt+1);
for (k = 2; k <= cnt; k++)
if (MIN > d[k]-d[k-1])
{
MIN = d[k] - d[k-1];
}
double temp = (2*PI - (d[cnt] - d[1]));
if (MIN > temp)
{
MIN = temp;
}
if (MIN > MAX)
MAX = MIN;
}
printf("%.4lf\n",(MAX*180)/PI);
}
return 0;
}
题意：最小二分图匹配的变形，边的权值为两定点的乘积，求匹配中的最大乘积最小。分析：首先，两组数据中全为正时，只有大乘小才能得到最大中的最小。
明白这点后，分析两组数据的情况，都为正，都为负，一负一正，部分负部分正，考虑清楚，并想出对应的解法即可。还有就是0既可以看成负数，也可看成正数。
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const long long inf = -1LL<<60;
long long a[100010],b[100010];
int xa,xb,ya,yb;
int n;
int main()
{
int i,j,k;
long long max;
while (scanf("%d",&n) != EOF)
{
max = inf;
xa = xb = ya = yb = 0;
for (i = 1; i <= n; i++)
{
scanf("%I64d",&a[i]);
if (a[i] <= 0)
ya ++;
else xa ++;
}
for (i = 1; i <= n; i++)
{
scanf("%I64d",&b[i]);
if (b[i] <= 0)
yb ++;
else xb ++;
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
//a，b全为正
if ((xa == n && xb == n) ||(xa == 0 && xb == 0))
{
for (i = 1; i <= n; i++)
if (max < a[i]*b[n-i+1])
max = a[i]*b[n-i+1];
printf("%I64d\n",max);
continue;
}
//a，b一正一负
if ((xa == n && xb == 0) || (xa == 0 && xb == n))
{
for (i = 1; i <= n; i++)
if (max < a[i]*b[i])
max = a[i]*b[i];
printf("%I64d\n",max);
continue;
}
//a全为正
if (xa == n)
{
for (i = 1; i <= xb;i++)
if (max < a[i]*b[n-i+1])
max = a[i]*b[n-i+1];
printf("%I64d\n",max);
continue;
}
//a全为负
if (xa == 0)
{
for (i = 1; i <= yb; i++)
if (max < a[n-i+1]*b[i])
max = a[n-i+1]*b[i];
printf("%I64d\n",max);
continue;
}
//b全为正
if (xb == n)
{
for (i = 1; i <= xa;i++)
if (max < b[i]*a[n-i+1])
max = b[i]*a[n-i+1];
printf("%I64d\n",max);
continue;
}
//b全为负
if (xb == 0)
{
for (i = 1; i <= ya; i++)
if (max < b[n-i+1]*a[i])
max = b[n-i+1]*a[i];
printf("%I64d\n",max);
continue;
}
//a的正==b的负
if (xa == yb)
{
for (i = 1; i <= ya; i++)
if (max < a[i]*b[yb+i])
max = a[i]*b[yb+i];
for (i = 1; i <= yb; i++)
if(max < b[i]*a[ya+i])
max = b[i]*b[yb+i];
printf("%I64d\n",max);
continue;
}
//a的正 》b的负，余下全为正
if (xa > yb)
{
for (i = ya+1,j = n - ya; i <= n-yb; i++,j--)
if (max <a[i]*b[j])
max = a[i]*b[j];
printf("%I64d\n",max);
continue;
}
//a的正小于b的负，余下全为负
if (xa < yb)
{
for (i = xb+1,j = n- xb; i <= n - xa; i++,j--)
if (max < a[i]*b[j])
max = a[i]*b[j];
printf("%I64d\n",max);
continue;
}
}
return 0;
}
朴素的最大流代码：
//BOJ 1154
#include <cstdio>
const int inf = 1<<25;
int cap[205][205];
int pre[205],s,t,i,j,n,m,x,y,v,que[205];
bool vis[205];
/***********************************************/
bool bfs()
{
for (i = 1; i <= m; i++)
vis[i] = false;
int f = 0,r = 1,st;
que[r] = s; vis[1] = true;
while (f < r)
{
st = que[++f];
for (i = 1; i<= m; i++)
if (vis[i] != true && cap[st][i] > 0)
{
pre[i] = st;
vis[i] = true;
if (i == t)
return true;
que[++r] = i;
}
}
return false;
}
int max_flow()
{
int sum = 0,min;
while (bfs())
{
min = inf;
i = t;
while (i != s)
{
if (cap[pre[i]][i] < min)
min = cap[pre[i]][i];
i = pre[i];
}
i = t;
sum += min;
while (i != s)
{
cap[pre[i]][i] -= min;
cap[i][pre[i]] += min;
i = pre[i];
}
}
return sum;
}
/*****************************************************************/
int main()
{
while (scanf("%d %d",&n,&m) != EOF)
{
for (i = 1;i <= m; i++)
for (j = 1; j <= m; j ++)
cap[i][j] = 0;
for (i = 1; i <= n; i++)
{
scanf("%d %d %d",&x,&y,&v);
cap[x][y] += v;
}
s = 1; t = m;
printf("%d\n",max_flow());
}
return 0;
}
Dinic 的最大流代码：
#include<iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
/************Dinic**********************/
#define Max 210
int flow[Max][Max],d[Max]; //flow is the network
int sta,end,N; //sta is the sourse ,end is the end,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0;
int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front<rear)
{
int k=q[front++];
for(int i=0;i<=N;i++)
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if (k==end) return sum;
int os = sum;
for(int i=0;i<=N&∑i++)
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.
flow[k][i]-=a;
flow[i][k]+=a;
sum -= a;
}
return os-sum;
}
/*******************************************/
int main()
{
int n,x,y,v;
while (scanf("%d %d",&n,&N) != EOF)
{
memset(flow,0,sizeof(flow));
for (int i = 1; i <= n; i++)
{
scanf("%d %d %d",&x,&y,&v);
flow[x][y] += v;
}
/**********************/
int ret=0;
sta = 1; end = N;
while(bfs(sta))
ret += dinic(sta,0x7ffffff);
/***************************/
printf("%d\n",ret);
}
return 0;
}
//考点: 计算几何
//思路:多个线段的投影有公共点 <=> 存在这样一条直线,该直线穿过所有的线段.
思考发现,满足条件的直线可以 <=> 给定2*n个线段端点中的某两个端点所确定的直线.
换句话说,如果存在穿过所有线段的直线X,那么X"旋转"之后会被某两个线段的端点"卡住".
只要证明：任何一条跟所有线段相交的直线都可以转化成所有端点中某两个端点的情况。
于是枚举任意两个端点，然后判断直线相交。
//提交情况: 6WA 2AC
主要WA在没有考虑到非常特殊的情况:所有的线段都是同一个点 比如给了 5个线段 所有的端点都是1.0000
//经验: 如果存储的时候把起点和终点存在相邻的两格中枚举的时候就好做多了 另外issame的用法也比较巧(谢谢zhaozhouyang学长的无私帮助)
//收获: 枚举端点写的灰常的纠结啊... const doubel eps = 1e-8
//AC code
#include<stdlib.h>
#include <math.h>
#include<stdio.h>
#include <algorithm>
using namespace std;
#define maxN 300
const double eps = 1e-8;
/*double max(double a, double b)
{
if(a>b) return a;
else return b;
}
double min(double a, double b)
{
if(a<b) return a;
else return b;
}*/
typedef struct
{
double x,y;
}point;
point l[maxN*2];
double direction(point p1,point p2, point p3)
{//向量p1p3和向量p2p3的叉积 p3相对p1p2的转向
return (p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y);
}
bool online(point p1,point p2,point p3)
{
return (min(p1.x,p2.x)<=p3.x&&p3.x<=max(p1.x,p2.x))&&(min(p1.y,p2.y)<=p3.y&&p3.y<=max(p1.y,p2.y));
}
bool insect(point p1,point p2,point p3,point p4)
{
//double d1=direction(p3,p4,p1);
// double d2=direction(p3,p4,p2);
double d3=direction(p1,p2,p3);
double d4=direction(p1,p2,p4);
if(d3*d4<0)
return true;
// else if(d1==0&&online(p3,p4,p1)) return true;
// else if(d2==0&&online(p3,p4,p2)) return true;
else if(d3==0) return true;
else if(d4==0) return true;
return false ;
}
int main()
{
//freopen("segment.in","r",stdin);
// freopen("segment.out","w",stdout);
int cnt = 0;
int N,n,i,j,k;
bool flag;
scanf("%d",&N);
while(N--)
{
cnt ++;
scanf("%d",&n);
for(i=0;i<2*n-1;i+=2)
{
scanf("%lf%lf%lf%lf",&l[i].x,&l[i].y,&l[i+1].x,&l[i+1].y);
}
/* if (N == 39)
{
for(i=0;i<2*n-1;i+=2)
{
printf("%.0lf %.0lf,%.0lf %.0lf\n",l[i].x,l[i].y,l[i+1].x,l[i+1].y);
}
system("pause");
}*/
bool issame = true;
flag = false;
for(i=0;i< 2*n -1 && flag==false;i++)
for(j=i+1;j < 2*n && flag==false;j++)
{
if (fabs(l[i].x-l[j].x) <= eps && fabs(l[i].y-l[j].y) <= eps)
//if (l[i].x == l[j].x && l[i].y == l[j].y)
continue;
issame = false;
flag=true;
for(k=0;k<2*n-1;k+=2)
{
if(insect(l[i],l[j],l[k],l[k+1]) == false)
{flag=false;
break;}
}
}
if(flag==true || issame)
{printf("Yes\n");}
else printf("No\n");
}
// printf("%d\n",cnt);
return 0;
}
摘要: RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题 主要方法及复杂度(处理复杂度和查询复杂度)如下: 1.朴素（即搜索） O(n)-O(n) 2.线段树(segment tree) O(n)-O(qlogn) ... 阅读全文
摘要: 题意：给你两个0-1矩阵，编程验证后一个矩阵是不是前一个矩阵的一部分。分析：解法一：在N*N中枚举M*M大小矩阵的左上角，然后比较这部分的矩阵行列的1个数是否相等，若全相等则一一比较。用C++交，压着时间过。解法二：字符串匹配的Rabin_Karp算法的二维拓展。下面是摘要RK算法的描述：1. 问题描述
给定目标字符串 T[... 阅读全文
|