一直覺得這個算法很神奇，昨天用到了，發現效果很好，速度果然很快！
int Montgomery(int a, int p, int m)
{
if(p==0) return 1;
int r=a%m;
int k=1;
while(p>1){
if(p&1!=0){
k=(k*r)%m;
}
r=(r*r)%m;
p/=2;
}
return (r*k)%m;
}
hdu 1811 題目大意： 有n個點，m個序關系，關系只有三種表示方式：a < b , a > b , a = b，問根據給定的關系能否將n個點排成有序，能輸出OK，若兩點之間出現 a < b 且 b < a 的情況，則輸出CONFLICT，若出現某些點間的關系不確定，則輸出UNCERTAIN，若后兩者同時存在，則優先輸出CONFLICT。 題目分析： 由于存在 a = b 的情況，所以需要用并查集，將所有相等的點進行縮點，然后進行拓撲排序，注意！優先輸出CONFLICT。
#include<stdio.h>
#include<string.h>
#include<vector>
#define N 10010
using namespace std;
vector<int>g[N];
int rank[N], f[N], m,n,num[N], save[20005][2], q[N];
int find(int x)//并查集的查找函數
{
if(f[x]==x) return x;
else return f[x]=find(f[x]); //路徑壓縮，而且這樣寫對匯編源碼有優化，不容易因遞歸層數太多出現棧溢出，但僅是不易！
}
void Union(int x, int y)//并查集的合并操作
{
int a=find(x);
int b=find(y);
if(a!=b){
if(rank[a]<rank[b]) //通過判斷兩個集合的大小，將小集合并入大集合，減少遞歸層數，算是個優化
f[a]=b, rank[b]+=rank[a];
else
f[b]=a, rank[a]+=rank[b];
}
}
int main()
{
int i,j,k,a,b,ans,tmp,x,y,tim;
char s[5];
while(scanf("%d %d",&n,&m)!=EOF){
for(i=0; i<=n; i++){
f[i]=i;
g[i].clear();
rank[i]=1;
}
memset(num, 0, sizeof(num));
k=0;
for(i=0; i<m; i++){
scanf("%d %s %d",&a, s, &b);
if(s[0]!='='){
if(s[0]=='>'){
tmp=a;
a=b;
b=tmp;
}
save[k][0]=a, save[k++][1]=b;
}
else if(s[0]=='='){
Union(a, b);
}
}
for(i=0; i<k; i++){
x=find(save[i][0]);
y=find(save[i][1]);
g[x].push_back(y);
num[y]++;
}
ans=0;
int head=0, tail=0; //從這里開始拓撲排序，用隊列做保險啊，直接寫的話很容易錯
k=0;
for(i=0; i<n; i++)
if(num[i]==0 && find(i)==i){ //找到第一輪入度（num[]）為零的點入隊。
q[tail++]=i;
k++;
}
if(k==0)
ans=2;
else{
if(k>1) ans=1; //本題要求
while(head<tail){ //排序過程
x=q[head++]; num[x]=-1; k=0;
for(i=0; i<g[x].size(); i++){
y=g[x][i];
num[y]--;
if(num[y]==0)
q[tail++]=y, k++;
}
if(k>1) ans=1; //本題要求
}
for(i=0; i<n; i++) //本題要求
if(num[i]>0){
ans=2;
break;
}
}
if(ans==0)
printf("OK\n");
else if(ans==1)
printf("UNCERTAIN\n");
else if(ans==2)
printf("CONFLICT\n");
}
return 0;
}
1. Dijkstra算法 這個算法和prime求最小生成樹特別像，都是找到最小邊，把點加進來，然后用新加的點更新其他沒有被加進來的點。
1.
#define N 1002
2.
#define MAX 99999
3.
int edges[N][N],d[N],n;
4.
5.
void dijkstra(int v)
6.
{
7.
int i,j;
8.
bool s[N]={false};
9.
for(i=1;i<=n;i++)
10.
d[i]=edges[v][i];
11.
d[v]=0;s[v]=true;
12.
for(i=1;i<n;i++)
13.
{
14.
int temp=MAX;
15.
int u=v;
16.
for(j=1;j<=n;j++)
17.
if((!s[j])&&(d[j]<temp))
18.
{
19.
u=j;
20.
temp=d[j];
21.
}
22.
s[u]=true;
23.
for(j=1;j<=n;j++)
24.
if((!s[j])&&(edges[u][j]<MAX)&&(d[u]+edges[u][j])<d[j])
25.
d[j]=d[u]+edges[u][j];
26.
}
27.
28.
}
2. SPFA算法 （shortest path faster algorithm） 不斷維護一個隊列，如果隊列里的點，使得其他點的最短路得到松弛，則這個點還有可能使另外的點松弛，所以如果這個點不在隊列里，就把它入隊。 很多時候，給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復雜度又過高，SPFA算法便派上用場了。 此算法時間復雜度為O（2*E），E為邊數。
//pku1860
#include<stdio.h>
#include<string.h>
#include<vector>
#define N 120
using namespace std;
struct Point
{
int id;
double r, c;
};
vector<Point> p[N];
int q[N],n,m,S,visit[N];
double V,dist[N];
int spfa()
{
memset(visit, 0, sizeof(visit));
int i,j,head=0,tail=1,x;
for(i=1; i<=n ;i++)
dist[i]=0; //此題是求換得的貨幣最多，所以初值賦0；
//若求最短路，初值應賦為無窮大
if(V<=0) return 0;
q[0]=S;
dist[S]=V; //S為源，若求最短路，則dist[S]=0;
visit[S]=1;
while(head!=tail){ // Attention！！！由于對隊列長度取模了，所以head<tail不一定成立，應改為head!=tail
x=q[head];
visit[x]=0;
head=(head+1)%N;
for(i=0; i<p[x].size(); i++){
j=p[x][i].id;
if(dist[j]<(dist[x]-p[x][i].c)*p[x][i].r){
dist[j]=(dist[x]-p[x][i].c)*p[x][i].r;
if(!visit[j]){
q[tail]=j;
tail=(tail+1)%N;
visit[j]=1; //若如果j點的最短路徑估計值有所調整，
// 且j點不在當前的隊列中，就將j點放入隊尾
}
}
}
if(dist[S]>V) return 1;
}
return 0;
}
int main()
{
int i,j,a,b;
double rab, cab, rba, cba;
Point p1, p2;
while(scanf("%d %d %d %lf",&n, &m, &S, &V)!=EOF){
for(i=1; i<=n; i++)
p[i].clear();
for(i=0; i<m; i++){
scanf("%d %d %lf %lf %lf %lf",&a, &b, &rab, &cab, &rba, &cba);
p1.id=b; p1.r=rab; p1.c=cab;
p2.id=a; p2.r=rba; p2.c=cba;
p[a].push_back(p1);
p[b].push_back(p2);
}
j=spfa();
if(j)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
第一次接觸字典樹的實現，先看到了一個指針實現的模板，覺得很好理解，用著也方便，先收集過來 :) //字典樹用來查詢有公共前綴的單詞有多少個，插入和查詢的時間復雜度均為O（n)
#include<iostream>
#include<cstring>
#define N 300 //有N個單詞
#define M 1000000//有M次查詢
#define kind 26//26個英文字母
using namespace std;
struct Treenode
{
int count;
Treenode *next[kind];
Treenode(){
for(int i=0; i<kind; i++)
next[i]=NULL;
count=1;
}
};
void insert(Treenode *&root, char *word)
{
int i=0,j,l=strlen(word),branch;
Treenode *location=root;
if(location==NULL){
location=new Treenode();
root=location;
}
for(i=0; i<l; i++){
branch=word[i]-'a';
if(location->next[branch])
location->next[branch]->count++;
else
location->next[branch]=new Treenode();
location=location->next[branch];
}
}
int search(Treenode *&root, char *word)
{
int i, ans=0, l=strlen(word),branch;
Treenode *location=root;
if(location==NULL) return 0;
for(i=0; i<l; i++){
branch=word[i]-'a';
if(!location->next[branch])
return 0;
location=location->next[branch];
ans=location->count;
}
return ans;
}
int main()
{
int i,j,n,m;
char word[50];
Treenode *root=NULL;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%s",word);
insert(root, word);
}
scanf("%d",&m);
for(i=0; i<m; i++){
scanf("%s",word);
printf("%d\n",search(root, word));
}
return 0;
}
<!--[if !supportLists]-->一、<!--[endif]-->網絡流
<!--[if !supportLists]-->1. <!--[endif]-->最大流：bfs
算法模板：
//1是源，point是匯
#include<stdio.h>
#include<string.h>
#include<queue>
#define N 870
using namespace std;
int M=999999;
int g[N][N], pre[N],point, edge, ans=0;
bool visit[N];
void update(int minf)
{
int i=point;
ans+=minf;
while(pre[i]!=0){
g[pre[i]][i]-=minf;
g[i][pre[i]]+=minf;
i=pre[i];
}
}
void bfs()
{
int i,j;
while(1){
queue<int> q;
bool visit[N]={false};
int minflow[N];
memset(pre, 0, sizeof(pre));
visit[1]=true;
minflow[1]=M;
q.push(1);
while(!q.empty()){
j=q.front(); q.pop();
for(i=1; i<=point; i++)
if(visit[i]==false && g[j][i]>0){
minflow[i]=minflow[j]<g[j][i]?minflow[j]:g[j][i];
pre[i]=j;
visit[i]=true;
q.push(i);
}
if(pre[point]>0) break;
}
if(pre[point]>0) update(minflow[point]);
else
break;
}
}
int cal(char s)
{
if(s<'Z' && s>='A')
return s-'A'+1;
else if(s<='z' && s>='a')
return s-'a'+26;
else if(s=='Z')
return 52;
}
int main()
{
int i,j,k,x,y,c,n;
char a[3],b[3];
scanf("%d",&n);
point=52;
for(i=0; i<n; i++){
scanf("%1s%1s%d",&a[0], &b[0], &c);
x=cal(a[0]); y=cal(b[0]);
g[x][y]+=c;
}
bfs();
printf("%d\n",ans);
return 0;
}
2 匈牙利算法 二分匹配
這種題目的難度在于建立模型，算法寫起來很簡潔，還是增廣路
//pku1325
#include<stdio.h>
#include<string.h>
#define N 120
int g[N][N], linked[N];
bool visit[N],n,m;
bool input()
{
int i,j,k,x,y;
scanf("%d",&n);
if(n==0) return false;
scanf("%d %d",&m, &k);
memset(g, 0, sizeof(g));
memset(linked, -1, sizeof(linked));
for(i=0; i<k; i++){
scanf("%d %d %d",&j, &x, &y);
if(x*y)
g[x][y]=1;
}
return true;
}
bool find(int x)
{
int i,j,k;
for(i=0; i<m; i++) //這里標號從零開始
if(!visit[i] && g[x][i]){
visit[i]=1;
if(linked[i]==-1 || find(linked[i])){
linked[i]=x;
return true;
}
}
return false;
}
int main()
{
int i, ans;
while(input())
{
ans=0;
for(i=0; i<n; i++){
memset(visit, 0, sizeof(visit));
if(find(i))
ans++;
}
printf("%d\n", ans);
}
return 0;
}
The Balance
| Time Limit: 5000MS |
|
Memory Limit: 65536K |
| Total Submissions: 930 |
|
Accepted: 384 |
Description
Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights. You are asked to help her by calculating how many weights are required.
 Input
The input is a sequence of datasets. A dataset is a line containing three positive integers a, b, and d separated by a space. The following relations hold: a != b, a <= 10000, b <= 10000, and d <= 50000. You may assume that it is possible to measure d mg using a combination of a mg and b mg weights. In other words, you need not consider "no solution" cases.
The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.
Output
The output should be composed of lines, each corresponding to an input dataset (a, b, d). An output line should contain two nonnegative integers x and y separated by a space. They should satisfy the following three conditions.
- You can measure dmg using x many amg weights and y many bmg weights.
- The total number of weights (x + y) is the smallest among those pairs of nonnegative integers satisfying the previous condition.
- The total mass of weights (ax + by) is the smallest among those pairs of nonnegative integers satisfying the previous two conditions.
No extra characters (e.g. extra spaces) should appear in the output. Sample Input
700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0
Sample Output
1 3
1 1
1 0
0 3
1 1
49 74
3333 1
怎么評價這道題呢，會做了，覺得這題挺水的，但是自己做了一下午，先是TLE后是WA，郁悶的不行，思維啊思維，做競賽考思維啊！ 題目大意： 給定a,b兩種藥品的重量，用他們的組合來測量第三種重量為d的藥品，標準： 1.假設取x個重為a的藥品，取y個重為b的藥品； 2.在滿足以上情況下，使得x+y最小； 3.在滿足以上情況下，使得ax + by最小。 求x和y的值。（x和y均為正整數） 思路： 有三種情況： ax+by=d;(a,b均在左盤) ax-by=d;（a在左盤，b和d在右盤） -ax+by=d;（b在左盤，a和d在右盤） 枚舉a，求滿足條件的解。 代碼：
 #include<iostream>
#include<cmath>
using namespace std;
int main()
   {
 int i,a,b,d,x,y,xx,yy;
int sum1,sum2;
while(cin>>a>>b>>d)
  {
if(a==0 && b==0 && d==0)break;
int min1=9000000,min2=9000000;
int t=0;
xx=0;yy=0;
for(i=0; ; i++){
if((d-a*i)%b==0)//ax+by=d 和 ax-by=d 兩種情況，用絕對值表示，所以合寫成一個if
{
yy=abs((d-a*i)/b);
sum1=i+yy;
sum2=a*i+b*yy;
if(sum1<min1)
min1=sum1,min2=sum2,x=i,y=yy;
else if(sum1==min1 && sum2<min2)
min1=sum1,min2=sum2,x=i,y=yy;
if(i>min1 || i*a>min2)//如果x的值比x+y的值都大或者a*x比a*x+b*y 的值都大了就跳出
break;
 }
int l=i*a+d;
if(l>0 && l%b==0)//-ax+by=d的情況
{
yy=l/b;
sum1=i+yy;
sum2=a*i+b*yy;
if(sum1<min1)
min1=sum1,min2=sum2,x=i,y=yy;
else if(sum1==min1 && sum2<min2)
min1=sum1,min2=sum2,x=i,y=yy;
if(i>min1 || i*a>min2)//如果x的值比x+y的值都大或者a*x比a*x+b*y 的值都大了就跳出
break;
}
}
cout<<x<<" "<<y<<endl;
}
return 0;
 }
Rectangle Cutting
Time Limit: 1.0 Seconds Memory Limit: 65536K
In the small historical village of Basinia, there is a popular activity in wedding ceremonies called rectangle cutting. During this activity, each close relative of the bride comes and cuts a rectangle in the wedding cake (but does not take a piece). The cake has a rectangular shape. The problem is to count how many pieces are in the cake after rectangle-cutting.
For example, in the following figure, the cake size is 3×5, and three people have made rectangular cuts in it. As a result, the cake is cut into six pieces.
Each rectangular cut is specified by the (x, y) coordinates of its two opposite corners. The input for the above figure can be found in the first sample input. As there are large families in Basinia, the number of pieces may be large and we need a computer program to compute it.
Input
The input contains several test cases. Each test has several lines. The first line has two integers w (1 ≤ w ≤ 20) and h (1 ≤ h ≤ 20) which are the width and height of the cake. The second line contains a single integer n (0 ≤ n ≤ 50) which is the number of people who cut rectangles in the cake. After this, there are n lines each containing the integers x1, y1, x2, y2 which are the coordinates of two opposite corners of the cut. You may assume 0 ≤ x1, x2 ≤ w and 0 ≤ y1, y2 ≤ h. The last line of the input is a line containing two zeros.
Output
For each test case, write the number of pieces the cake is cut into.
Sample Input
3 5
3
1 1 3 2
4 0 2 3
4 0 5 1
6 6
2
2 0 5 3
3 1 4 2
0 0
Sample Output
6
3
題目大意：
給定一個w*h的矩形，在這個矩形里切小矩形，最后計算并輸出封閉圖形的個數。
思路：
把矩形看作w*h個小方塊，第n次切割，就在所切的矩形的方塊上標記數字2^n，如果重復切到同一個方塊就把
標記值累加，這樣標記完后再深搜，就得到封閉圖形個數了。（標記為2^n，是ht同學的思想，很巧妙，但只能使用
于數據量比較小的情況）。同時此題應注意w 和 h 的順序，我在這里耽誤了好久，還wa了一次。
代碼：
Source Code
Problem: 3338 User: wic
Memory: 272K Time: 0MS
Language: C++ Result: Accepted
Source Code
#include<iostream>
using namespace std;
int a[25][25];
int mark=-1,k;
int w,h;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int power(int a, int b)//pow的返回值類型不是int，于是自己寫了一個函數
{
int ans=1;
while(b--)
ans*=a;
return ans;
}
bool inside(int x, int y)
{
if(x<=h && x>0 && y<=w && y>0)
return true;
else
return false;
}
void dfs(int x, int y)//自己寫的深搜，嘿嘿
{
for(int i=0; i<4; i++){
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(inside(xx,yy) && a[yy][xx]!=mark && a[yy][xx]==k){
a[yy][xx]=mark;
dfs(xx,yy);
}
}
}
int main()
{
int i,j,n,x1,y1,x2,y2,maxx,maxy,minx,miny,m;
while(cin>>w>>h && w && h){
memset(a, 0, sizeof(a));
cin>>n;
k=0;
int c=0;
int count=0;
while(n--){
cin>>x1>>y1>>x2>>y2;
maxx=(x1>=x2)?x1:x2;
minx=(x1<=x2)?x1:x2;
maxy=(y1>=y2)?y1:y2;
miny=(y1<=y2)?y1:y2;
m=power(2,c);
for(i=miny+1; i<=maxy; i++)
for(j=minx+1; j<=maxx; j++)
a[i][j]+=m;
c++;
}
k=c;
m=power(2,k);
for(k=0; k<m; k++){
for(i=1; i<=w; i++)
for(j=1; j<=h; j++)
if(a[i][j]!=mark&&a[i][j]==k)
{ dfs(j,i); count++;}
}
cout<<count<<endl;
}
return 0;
}
摘要: 這題初看起來被嚇到了，以為要寫成運算符重載，后來發現其實很水，呵呵（但是某人雖然在poj過了，但是卻在tojWA了5次，實在不解，呵呵）思路：接入字符串，去掉空格，從頭到尾掃，遇到字母就檢測它的前后兩位有沒有++（--）如果有進行處理，然后看它的后（前）面第3為是+(-)就加(減)到和sum里；用一個三維數組v[26][3... 閱讀全文
|