題目大意：給定兩個區間，[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必須是單位向量
|