题目大意：给定两个区间，[a,b] [c,d] 设x属于第一个区间，y属于第二个区间，求gcd(x,y)=k的实数对有多少个。
方法：对两个区间分别除以k，转化为求新区间内，互质的实数对有多少个。
容斥原理：|t1Ut2U...Utn| = sum[ti] - sum[ti n tj] + sum[ti n tj n tk] - ... + (-1)^(m+1)|t1 n t2 n ... n tn|
把所有有是1的倍数的点对加起来 减去既有1也有（2，3，5。。。）的点对 加上既有1也有2也有3.。的点对
#include <stdio.h>
#include <algorithm>
using namespace std;
bool mark[100010];
int prim[10000], tot =0, sum = 0;
struct node{
int v; //v存的是数 就是乘积 k是记录减还是加
int k;
}tb[70000];
void di(long long p,int k,int odd) {//奇数个因数的就加 偶数个因数的就减
if (k == tot) return;
long long tmp = p*prim[k];
if (tmp > 100000) return;
di(p,k+1,odd);
tb[sum].v = tmp;
tb[sum++].k = -odd;
di(tmp,k+1,-odd);
}
void swap(int &a,int &b) {
a += b;
b = a-b;
a = a-b;
}
int cmp(node a,node b) {
return a.v < b.v;
}
int main () {
int i, j;
for (i = 2; i <= 100000; i++) {
if (!mark[i]) {
prim[tot++] = i;
for (j = i+i; j <= 100000; j += i)
mark[j] = 1;
}
}
tb[0].v = 1; tb[0].k = 1;
sum = 1;
di(1,0,1);
sort(tb,tb+sum,cmp);
int kase, a, b, c, d, k, o = 1;
scanf("%d", &kase);
while (kase--) {
scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
if (k == 0) {
printf("Case %d: 0\n", o++);
continue;
}
int x = b/k;
int y = d/k;
if (x == 0 || y == 0) {
printf("Case %d: 0\n", o++);
continue;
}
if (x > y) swap(x,y);
long long ans = 0;
for (i = 0; i < sum; i++) {
if (x < tb[i].v) break;
long long tmpx = x/tb[i].v;
long long tmpy = y/tb[i].v;
long long c = tmpx*tmpy-(tmpx-1)*tmpx/2;
ans += c*tb[i].k;
}
printf("Case %d: %I64d\n",o++,ans);
}
return 0;
}
pku 2186 注意此题是单case，若想统计有几个连通分量可以根据belong数组进行操作。
#include<iostream>
#incldue<string.h>
#include<stdlib.h>
#include<stdio.h>
#define N1 50005
using namespace std;
struct Edge
{
int a, b;
}edges[N1];
bool visited[N1];//深搜时候，记录节点是否被访问过
int N,M;
int end_order[N1];//记录深搜的时候，节点访问结束顺序
int index;
int first[N1]; //用于存储图，first[i]指向第一条起始节点为i的边
int belong[N1];//belong[i]记录节点i属于哪个强连通分量
int cnt[N1]; //cnt[i]记录节点i强连通分量中节点的数量
bool is_out[N1]; //is_out[i]记录第i个强连通分量是否有出边
int cmp1(const void *a, const void *b)
{
return ((Edge*)a)->a-((Edge*)b)->a;
}
int cmp2(const void *a, const void *b)
{
return ((Edge*)a)->b-((Edge*)b)->b;
}
void dfs1(int source)
{
if(visited[source]) return ;
visited[source]=true;
for(int i=first[source]; i<first[source+1]; i++)
dfs1(edges[i].b);
end_order[index++]=source;//记录节点访问结束顺序
}
void dfs2(int source ,int k)
{
if(visited[source]) return ;
visited[source]=true;
for(int i=first[source]; i<first[source+1]; i++)
dfs2(edges[i].a, k);
belong[source]=k;//记录节点所属的强连通分量
cnt[k]++;//强连通分量内节点计数
}
int main()
{
int ans;
scanf("%d %d", &N, &M);
for(int i=0; i<M; i++){
scanf("%d %d", &edges[i].a, &edges[i].b);
edges[i].a--; edges[i].b--;
}
edges[M].a=edges[M].b=-1; //简化下面first数组的构建
qsort(edges, M, sizeof(edges[0]), cmp1);
int last_source=0;
first[last_source]=0;
int k=0;
while(last_source<N){
if(edges[k].a==last_source) k++;
else first[++last_source]=k;
}
memset(visited, 0, sizeof(visited));
index=0;
for(int i=0; i<N; i++)
dfs1(i);
qsort(edges, M , sizeof(edges[0]), cmp2);
last_source=0;
first[last_source]=0;
k=0;
while(last_source<N){
if(edges[k].b==last_source) k++;
else first[++last_source]=k;
}
memset(visited, 0, sizeof(visited));
memset(cnt, 0, sizeof(cnt));
k=0;
for(int i=index-1; i>=0; i--){
if(visited[end_order[i]]) continue;
dfs2(end_order[i], k); //第二次搜索
k++;
}
for(int i=0; i<M; i++){//记录哪些强连通分量有出边
if(belong[edges[i].a]!=belong[edges[i].b])
is_out[belong[edges[i].a]]=true;
}
int no_out=0;
for(int i=0; i<k; i++){//统计无出边的强连通分量的个数
if(!is_out[i]){
no_out++;
ans=cnt[i];
}
}
if(no_out==1)//输出
printf("%d\n", ans);
else
printf("0\n");
return 0;
}
pku1639 这题郁闷啊，手抄prayer的模板都抄不对~~~
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<stdio.h>
#include<string>
#define N1 110
using namespace std;
int const INF=100000000;
int cost[N1][N1];//花费 = 边
int used[N1][N1];//表示这条边是否在生成树中
int father[N1];//生成树中点的父节点
int maxlen[N1];//表示i点到根路径上除了与根直接相连的边外，边权最大的边权
int vis[N1];//标记
int d[N1]; //求最小生成树时的最小生成树代价
int AnsMst;//当前m度生成树的代价
int N, degree, lim;//degree表示最小限度，lim表示限度值
int g[N1][N1];//生成树中的儿子关系，正向表
map<string, int> mat;
void MST(int S) //求从S点开始的最小生成树
{
while(1){
int K=-1;
for(int i=1; i<=N; i++){
if(!vis[i] && d[i]!=INF && (K==-1||d[K]>d[i]))
K=i;
}
if(K==-1) break;
vis[K]=1;
AnsMst+=d[K];
g[father[K]][++g[father[K]][0]]=K;//记录儿子
if(d[K]!=0) maxlen[K] = max(maxlen[father[K]], d[K]);//算边权最大的边
used[K][father[K]] = used[father[K]][K] = 1;//标记边在生成树中
for(int i=1; i<=N; i++){
if(!vis[i] && cost[K][i]<d[i]){
father[i]=K;
d[i]=cost[K][i];
}
}
}
}
void Build()
{
for(int i=1; i<=N; i++)
father[i]=i;
for(int i=1; i<=N; i++)
d[i]=INF;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
used[i][j] = 0;//所有的边都在生成树外
for(int i=1; i<=N; i++)
g[i][0]=0; //儿子数全为0
for (int i = 1; i <= N; i++) vis[i] = 0; // 标记清空
vis[1]=1;
degree=0;
maxlen[1]=-INF; //根的maxlen为-INF;
AnsMst=0; //开始时生成树的代价为0
while(1){
int K=-1;
for(int i=1; i<=N; i++){
if(!vis[i] && (K==-1 ||cost[1][i]<cost[1][K]))
K=i; //找个距根边权最小的点开始做最小生成树
}
if(K==-1) break;
father[K]=1; //father 为 1
maxlen[K]=-INF; //maxlen[k]=--INF;
d[K]=0;
degree++;//连通分支个数加1
AnsMst+=cost[1][K]; //生成树代价增加
MST(K);
}
}
void Init()//开始的输入处理
{
mat.clear();
mat["Park"]=1;
N=1;
int M;
scanf("%d", &M);
for(int i=1; i<=30; i++)
for(int j=1; j<=30; j++)
cost[i][j]=INF;
while(M--){
string a, b;
int c;
cin>>a>>b>>c;
int ida, idb;
if(mat.find(a)==mat.end()) mat[a]=++N, ida=N;
else ida=mat[a];
if(mat.find(b)==mat.end()) mat[b]=++N, idb=N;
else idb=mat[b];
cost[ida][idb]=cost[idb][ida]=c;
}
scanf("%d", &lim);
}
void Dfs(int nod, int fa) //更新维护maxlen和生成树中的父子关系
{
father[nod]=fa;
vis[nod]=1;
if(fa==1) maxlen[nod]=-INF;
else
maxlen[nod]=max(maxlen[fa], cost[nod][fa]);
for(int i=1; i<=g[nod][0]; i++)
if(used[nod][g[nod][i]]&&!vis[g[nod][i]])
Dfs(g[nod][i], nod);
}
void Solve(){
if(degree>lim)
printf("Error\n");
int ans=AnsMst;
while(degree<lim){
degree++;
int id=-1;
int delta=INF;
for(int i=1; i<=N; i++){//找代价最小的进行扩张
if(cost[1][i]!=INF && !used[1][i]){
if(id==-1){
id=i;
delta=cost[1][i]-maxlen[i];
continue;
}
if(cost[1][i]-maxlen[i]<delta){
id=i;
delta=cost[1][i]-maxlen[i];
}
}
}
if(id==-1){ break;}
AnsMst+=delta;//加上delta值
ans=min(ans, AnsMst);
int Len=maxlen[id];
used[1][id]=used[id][1]=1;//表示边被加入到当前的生成树中
g[1][++g[1][0]]=id; //表示根多加了一个儿子
while(cost[id][father[id]]!=Len){//找最大的边，并顺路维护儿子关系
int fa=father[id];
g[id][++g[id][0]]=fa;
id=fa;
}
used[id][father[id]]=used[father[id]][id]=0;//标记边被删去
for(int i=1; i<=N; i++)
vis[i]=0;
Dfs(1, 1);//维护
}
printf("Total miles driven: %d\n", ans);
}
int main()
{
Init();
Build();
Solve();
return 0;
}
先讨论有根树的同构：
试图确定两颗树的最小表示，如果最小表示相同则同构。
明确一下树的大小判断标准：
① 根节点度数大的树大
② 根节点度数一样时，将子树排序，然后依次判断每个子树，第一个子树大的树大
复杂度分析：
时间：排序均用快排，compare的复杂度是O(n)，快速排序进行nlogn次compare，排序的复杂度是O(n2logn)更新link的复杂度为O(n2logn)，计算rank的复杂度为O(n2)，总的时间复杂度是O(n2logn)（上述考虑的是最坏情况，实际情况原小于理论值）
有根树的同构pku1635
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
const int Mod = 9901;
const int Max = 3010;
const int Mul = 9110;
vector<int> adj[Max];
int father[Max], hash[Max];
bool cmp(int a, int b)
{
return hash[a]<hash[b];
}
int rebuild(char *str)
{
for(int i=0; i<Max; i++)
adj[i].clear();
for(int i=0, j=1, k=0; str[i]; i++){
if(str[i]=='0'){
adj[k].push_back(j);
father[j]=k;
k=j;
j++;
}
else
k=father[k];
}
return 0;
}
int dfs(int k)
{
int val = 0;
if(adj[k].size()==0)
val=1;
else{
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
hash[j]=dfs(j);
}
sort(adj[k].begin(), adj[k].end(), cmp);
val=1908;
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
val=((val*Mul)^hash[j])%Mod;
}
}
return val;
}
int main()
{
int i,j,n;
char s[Max];
scanf("%d",&n);
while(n--){
int hash1, hash2;
scanf("%s", s); //读入一个01字符串，0代表远离根节点，1代表靠近根节点
rebuild(s);
hash1=dfs(0);
scanf("%s",s);
rebuild(s);
hash2=dfs(0);
printf("%s\n", hash1==hash2?"same":"different");
}
return 0;
}
对于无根树，只要确定一个根，就转换成有根树同构的判断了
将树看成无向图，进行拓扑排序(每次删除度为1的点)，最后剩余1或2个点。
如果是1个点，以该点为根建立有根树
如果是2个点，一棵树以任一点为根建树，另一棵树分别以2个点建立树，判断两次。
2009合肥赛区网络预赛 ustc 1117 Bean Language
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
const int Mod = 9901;
const int Max = 1010; //节点数
const int Mul = 9110;
vector<int> adj[Max];
int g[Max][Max], q[Max], level[Max], visit[Max];
int father[Max], hash[Max], one[2], two[2];
bool cmp(int a, int b)
{
return hash[a]<hash[b];
}
void Top(int n, int x) //拓扑排序找根
{
memset(visit, 0, sizeof(visit));
int head=0, tail=0;
for(int i=0; i<n; i++){
if(g[i][n]==1){
visit[i]=1;
level[tail]=0;
q[tail++]=i;
}
}
while(head<tail){
int now=q[head], l=level[head++];
for(int i=0; i<n; i++)
if(!visit[i] && g[now][i]){
g[i][n]--;
if(g[i][n]<=1){
level[tail]=l+1;
q[tail++]=i;
visit[i]=1;
}
}
}
int l=level[tail-1], k=0;
for(int i=tail-1; level[i]==l; i--){
if(k==0){
one[x]=q[i]; k++;
}
else
two[x]=q[i];
}
}
void build(int root, int n)
{
visit[root]=1;
for(int i=0; i<n; i++){
if(!visit[i] && g[root][i]){
adj[root].push_back(i);
build(i, n);
}
}
}
int dfs(int k)
{
int val = 0;
if(adj[k].size()==0)
val=1;
else{
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
hash[j]=dfs(j);
}
sort(adj[k].begin(), adj[k].end(), cmp);
val=1908;
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
val=((val*Mul)^hash[j])%Mod;
}
}
return val;
}
int main()
{
int i,j,n,cas,a,b;
char s[Max];
scanf("%d",&cas);
while(cas--){
int hash1, hash2;
scanf("%d",&n); //读入n个节点
memset(g, 0, sizeof(g));
one[0]=-1; one[1]=-1; two[0]=-1; two[1]=-1;
for(i=0; i<n-1; i++){ //n-1条边，无重边
scanf("%d %d", &a, &b);
a--; b--;
g[a][b]++; g[b][a]++;
g[a][n]++; g[b][n]++;
}
Top(n,0);
memset(visit, 0, sizeof(visit));
for(int i=0; i<n; i++)
adj[i].clear();
build(one[0],n);
hash1=dfs(one[0]);
memset(g, 0, sizeof(g));
for(i=0; i<n-1; i++){
scanf("%d %d", &a, &b);
a--; b--;
g[a][b]++; g[b][a]++;
g[a][n]++; g[b][n]++;
}
Top(n,1);
memset(visit, 0, sizeof(visit));
for(int i=0; i<n; i++)
adj[i].clear();
build(one[1],n);
hash2=dfs(one[1]);
if(hash1!=hash2 && two[1]!=-1){
memset(visit, 0, sizeof(visit));
for(int i=0; i<n; i++)
adj[i].clear();
build(two[1],n);
hash2=dfs(two[1]);
}
// printf("%d %d %d %d\n", one[0], two[0], one[1], two[1]);
printf("%s\n", hash1==hash2?"same":"different");
}
return 0;
}
朴素的prim，还是自己写的用着习惯 pku 1251
#include<stdio.h>
#include<string.h>
#define N 30
#define M 1<<27
int g[N][N],n; //g[][]的初值为M, 下标从0开始
int prim()
{
int i,j,k,ans=0;
int dis[N], visit[N], pre[N];
for(i=0; i<n; i++){
dis[i]=g[0][i];
visit[i]=0;
pre[i]=0;
}
visit[0]=1;
for(i=1; i<n; i++){
int mn=M, v=0;
for(j=0; j<n; j++)
if(!visit[j] && dis[j]<mn){
mn=dis[j];
v=j;
}
if(v==0) break;
visit[v]=1;
ans+=mn;
for(j=0; j<n; j++)
if(!visit[j] && dis[j]>g[v][j]){
dis[j]=g[v][j];
pre[j]=v;
}
}
return ans;
}
int main()
{
int i,j,k,p,q,z;
char s[5];
while(scanf("%d", &n) && n){
for(i=0; i<n; i++)
for(j=0; j<n; j++)
g[i][j]=M;
for(i=0; i<n-1; i++){
scanf("%s %d", s, &k);
p=s[0]-'A';
for(j=0; j<k; j++){
scanf("%s %d", s, &z);
q=s[0]-'A';
g[p][q]=g[q][p]=z;
}
}
printf("%d\n", prim());
}
return 0;
}
先做一遍prim，求出最小生成树的value，和路径。每次去掉一条路径上的边，再做最小生成树，若出现新的value和第一次的value相等，则次小生成树不唯一。否则，取枚举过程中最小的一个value即可。
#include<stdio.h>
#include<string.h>
#define N 110
#define M 1<<27
int g[N][N], pre[N],low[N];
bool visit[N];
struct Now
{
int x, y, z;
}now[N], cur;
int prim(int n){
int i,j,k, ans=0;
for(i=1; i<=n; i++){
low[i]=g[1][i];
pre[i]=1;
visit[i]=false;
}
visit[1]=true;
k=1;
for(i=2; i<=n; i++){
int mn=-1, p;
for(j=1; j<=n; j++)
if(!visit[j] && (mn==-1 || low[j]<mn)){
mn=low[j];
p=j;
}
if(mn==-1) break;
ans+=mn;
k=p;
visit[k]=true;
for(j=1; j<=n; j++){
if(!visit[j] && low[j]>g[k][j]){
low[j]=g[k][j];
pre[j]=k;
}
}
}
return ans;
}
int main()
{
int i,j,n,m,ca,x,y,z;
scanf("%d", &ca);
while(ca--){
scanf("%d %d", &n, &m);
for(i=0 ; i<=n ; i++)
for(j=0; j<=n; j++)
g[i][j]=M;
for(i=0; i<m; i++){
scanf("%d %d %d", &x, &y, &z);
g[x][y]=g[y][x]=z;
}
int value=prim(n);
j=0;
for(i=2; i<=n; i++){
now[j].x=i;
now[j++].y=pre[i];
}
int t=0;
for(i=0; i<n-1; i++){
int a, b, aa, bb;
a=now[i].x;
b=now[i].y;
now[i].z=g[a][b];
g[a][b]=g[b][a]=M;
if(i>0){
aa=now[i-1].x;
bb=now[i-1].y;
g[aa][bb]=g[bb][aa]=now[i-1].z;
}
int tmp=prim(n);
if(tmp==value){
t=1;
break;
}
}
if(t)
printf("Not Unique!\n");
else
printf("%d\n", value);
}
return 0;
}
首先为除根之外的每个点选定一条入边，这条入边一定要是所有入边中最小的 除第一个点外，在另外点上找是否有向环的起点 如果有，先把环上边权加到res中,标记环上的点,再调整有向环的起点上的入边 调整有向环上其它点的入边和出边(取环上点到非环上点的最小值为环到k的值)（把环上点缩到i上） 如果找全就跳出返回最小树形图的值 调整的时候入边要减掉in[u];
//pku 3164
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 110
#define M 1<<27
struct P
{
double x, y;
}p[N];
double g[N][N],ans;
int visit[N],n,m,pre[N],circle[N],del[N];
double minn(double a, double b)
{
return a<b?a:b;
}
double dis(P a, P b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void dfs(int x)
{
for(int i=1; i<=n; i++)
if(!visit[i] && g[x][i]!=M){
visit[i]=1;
dfs(i);
}
}
int exist(){//判连通
int i,root=1;
memset(visit, 0, sizeof(visit));
visit[root]=true;
dfs(root);
for(i=1; i<=n; i++)
if(!visit[i])
return 0;
return 1;
}
void S_Tree()
{
int i,j,k,in,mark;
memset(del, 0, sizeof(del));
while(1){
for(i=2; i<=n; i++)
if(!del[i]){//找每个点的最小入度
pre[i]=i;
g[i][i]=M;
for(j=1; j<=n; j++)
if(!del[j] && g[j][i]<g[pre[i]][i]){
pre[i]=j;
}
}
for(i=2; i<=n; i++)
if(!del[i]){
memset(visit, 0, sizeof(visit));
mark=i;
while(!visit[mark] && mark!=1){//找环
visit[mark]=1;
mark=pre[mark];
}
if(mark==1) //若无环，则必会找到根节点，continue；
continue;
i=mark; //否则就有环
ans+=g[pre[i]][i];
for(j=pre[i]; j!=i; j=pre[j]){
ans+=g[pre[j]][j]; //加环上的权值
del[j]=1;
}
for(j=1; j<=n; j++) //处理外界点与环上点的权值
if(!del[j]){
if(g[j][i]!=M)
g[j][i]-=g[pre[i]][i];
}
for(j=pre[i]; j!=i; j=pre[j]){ //处理环上点与外界点的权值
for(k=1; k<=n; k++)
if(!del[k]){
g[i][k]=minn(g[i][k], g[j][k]);
if(g[k][j]!=M){
g[k][i]=minn(g[k][i], g[k][j]-g[pre[j]][j]);
}
}
}
break;//做完一次缩点工作就跳出，继续生成新的图
}
if(i>n){
for(j=2; j<=n; j++)
if(!del[j]){
ans+=g[pre[j]][j];
}
break;
}
}
}
int main()
{
int i,j,k;
while(scanf("%d %d",&n, &m)!=EOF){
ans=0;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
g[i][j]=M;
for(i=1; i<=n; i++)
scanf("%lf %lf", &p[i].x, &p[i].y);
for(i=0; i<m; i++){
scanf("%d %d", &j, &k);
g[j][k]=dis(p[j], p[k]);
}
i=exist();
if(!exist())
printf("poor snoopy\n");
else{
S_Tree();
printf("%.2lf\n", ans);
}
}
return 0;
}
这是个很完善的模板O(∩_∩)O~
#include <stdio.h>
#include <math.h>
const int N = 100010;
int mark[N];
struct Point
{
double x,y;
};
struct stline
{
Point a,b;
} line1,line2, p[N];
int dblcmp(double a,double b)
{
if (fabs(a-b)<=1E-6) return 0;
if (a>b) return 1;
else return -1;
}
//***************点积判点是否在线段上***************
double dot(double x1,double y1,double x2,double y2) //点积
{
return x1*x2+y1*y2;
}
int point_on_line(Point a,Point b,Point c) //求a点是不是在线段bc上，>0不在，=0与端点重合，<0在。
{
return dblcmp(dot(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y),0);
}
//**************************************************
double cross(double x1,double y1,double x2,double y2)
{
return x1*y2-x2*y1;
}
double ab_cross_ac(Point a,Point b,Point c) //ab与ac的叉积
{
return cross(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
int ab_cross_cd (Point a,Point b,Point c,Point d) //求ab是否与cd相交，交点为p。1规范相交，0交点是一线段的端点，-1不相交。
{
double s1,s2,s3,s4;
int d1,d2,d3,d4;
Point p;
d1=dblcmp(s1=ab_cross_ac(a,b,c),0);
d2=dblcmp(s2=ab_cross_ac(a,b,d),0);
d3=dblcmp(s3=ab_cross_ac(c,d,a),0);
d4=dblcmp(s4=ab_cross_ac(c,d,b),0);
//如果规范相交则求交点
if ((d1^d2)==-2 && (d3^d4)==-2)
{
p.x=(c.x*s2-d.x*s1)/(s2-s1);
p.y=(c.y*s2-d.y*s1)/(s2-s1);
return 1;
}
//如果不规范相交
if (d1==0 && point_on_line(c,a,b)<=0)
{
p=c;
return 0;
}
if (d2==0 && point_on_line(d,a,b)<=0)
{
p=d;
return 0;
}
if (d3==0 && point_on_line(a,c,d)<=0)
{
p=a;
return 0;
}
if (d4==0 && point_on_line(b,c,d)<=0)
{
p=b;
return 0;
}
//如果不相交
return -1;
}
经历了各种TLE，各种WA，还有一次RE，终于在网上找到两句至理名言，靠这两个剪枝，在北大上AC了这道错了25次的1011. 但不行的是在Hdu，依然WA中，预知后事如何，请听下回分解。 强大的剪枝！1.搜索每根大木棍的时候，如果因为安放了第一段木棍就无法提供合理解的时，就不用去试探其他小木棍在第一段位置的情况了。所以回溯到上一个大木棍的搜索，是第一个大木棍的第一段出现问题，那么该长度肯定不符合要求。 2.每个大木棍的最后一段，如果不合要求，那么也不用去试图去安放其他的小木棍了，直接回溯到上段木棍即可。因为，换成更小的木棍，即便也可使木棍填满，小木棍也有可能在将来的时候无法安放。简单的说，如果它不行，采用别的更小的木棍也不行；如果它可以，采用别的更小的木棍也一定可以。
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int a[100],n,sum, get, mark[100];
int cmp(int c, int b)
{
return c>b;
}
int dfs(int nowlen, int nowget, int nowi)
{
for(int i=nowi; i<n; i++)
if(mark[i]==0 && nowlen>=a[i]){
mark[i]=1;
if(nowlen>a[i]){
if(dfs(nowlen-a[i], nowget, i+1)==1)
return 1;
else if(nowlen==sum/get) //剪枝1
{ mark[i]=0; return 0; }
}
else if(nowlen==a[i]){
if(nowget+1==get) return 1;
if(dfs(sum/get, nowget+1, 0)==1)
return 1;
else{
mark[i]=0;//剪枝2
return 0;
}
}
mark[i]=0;
}
return 0;
}
int main()
{
int i,j,k;
while(scanf("%d",&n) && n){
sum=0;
memset(a, 0, sizeof(a));
for(i=0; i<n; i++){
scanf("%d",&a[i]);
sum+=a[i];
}
sort(a, a+n, cmp);
get=sum/a[0];
while(sum%get!=0){
get--;
}
while(1){
memset(mark, 0, sizeof(mark));
if(dfs(sum/get, 0, 0)==1)
break;
else{
get--;
while(sum%get!=0){
get--;
}
}
}
printf("%d\n",sum/get);
}
return 0;
}
空间点绕任意轴旋转变换公式
P点绕A向量旋转θ角后得到P'：
P' = Pcosθ + (A × P)sinθ + A(A·P)(1 - cosθ)
注意：视口为向量指向的位置，就是向量指向你，θ为逆时针旋转的角。
A × P = (Ay*Pz - Az*Py,Az*Px - Ax*Pz,Ax*Py - Ay*Px)
注意：A必须是单位向量
|