做并查集时有三个步骤，即:初始化(makeset)——>查找根(findset)——>合并集合(union)。只要掌握了这三步，一些简单的并查集也就差不多OK了。
一、初始化:
官方点的话说就是把每个点所在的集合初始化为其自身。
这个不难，就直接把代码贴上：
void makeset(int x)
{
int i;
for(i=1;i<=x;x++)
{
p[i]=i; /*数组p[x]表示x的老爸的编号*/
r[i]=1;
}
}
二、查找(我们也可以叫做”寻根”):
官方说法:查找元素所在集合。
这个查找返回的是该元素的根,返回[……]
经过一天在网上搜各种资料，马马虎虎总结了套模板，虽然个别地方不太理解，这个模板也是比较大众化的。
核心公式就是Pick定理：S=内点个数+边上点个数/2-1；
难点也就在于计算点的个数；
思路是先求最好求的边上点的个数，就是对每组x，y的绝对值求最大公约数加和可得；
然后就是计算多边形面积，这个也是纠结了老半天；这里主要是要知道有个叉乘，即：x1*y2-y1*x2！
具体的见代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
struct Area
{[……]
A：To save the princess
找规律题（霞娘指点）。先求行与列的最大公约数，说白了就是把行和列约分化简。之后很容易得到规律：行+列-1。。
代码：
#include<stdio.h>
int gy(int a,int b)
{
int t;
if(a<b)
{
t=a;
a=b;
b=t;
}
t=a%b;
while(t!=0)
{
a=b;
b=t;
t=a%b;
}
return b;
}
int main()
{
int n,m;
while(scanf(“%d %d”,&n,&am[……]
A
a题看的时候就想，要是没有交点就简单了，没交点的话必然是（m+n-1）。那怎么把有交点的化成没交点的呢？分成全等的就好了嘛。所以，最大公约数求一下。然后，这题没什么要注意的细节，1A就是了。
B
开始看是英文就跳过去了，后来发现好多人都A了，无奈英语坑去看了，开始想各种办法去模拟进制，后来突然发现只有这十二个数……好了。记得敲上“sring.h”头文件。
C
小兵这个可以算作是递归吧。最简单的是“1 1”的时候，只有两种，那么对应的“n 1”显而易见都是（n+1）种。对于（n m）来说，可以理解为有（n +1）个选择（[……]
应队友要求，以后的每次比赛都要写一份总结，利于纠正赛场上出现的错误，防止下次比赛再次出现，这件事自然就落在了我这个文艺二逼小青年身上了。
2013年6月8日，风和日丽，由于青岛离烟台不算远，所以在热身赛当天前往中国石油大学。好久没有6点多起床了，导致起床到上车前都是一副快死的节奏。。上车了，直接进入死的状态，几乎一路睡到目的地，到了中石油的时候已经中午了，随便吃了吃，就去场地参加热身赛。
热身赛A题很简单，就是比较两组数的的平均数是否大于等于50，hmh上机敲了敲，然后又教了教他环境如何使用，A题就这么解决了。接下来B题，题意也不难，求完全覆盖两个不相交的圆的最小矩形的面积，或许受[……]
这道题是POJ1063，这里找了一篇解释详细的报告：
题意:给定一个数N (10 <=N <= 30),然后给你N个数,这N个数由0和1组成,这N个数可以看做是一个环.然后现在又一种操作,可以将连续的三个数进行翻转,也可以将整个序列顺时针旋 转一圈.现在问是否存在通过一个操作来是的实现将所有的1都靠在一起.
这题刚开始分析的时候只注意到连续的三个数的8种组合情况,然后只有四种情况是在翻转过程中产生变化的.但是这样的想法还是没有多大帮助.实在是不 会了.因为我的整个思路在于去构造一个方法能够使得所有的1都连在一起.而题目只要我们输出YES或者是NO.参看了题解后恍然大悟:[……]
Description
http://poj.org/problem?id=2362
dfs+多重剪枝
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int num[20];
int v[20],n;
int cmp(const int& a,const int& b)
{
return a>b;
}
int dfs(int s_len,int sum,int stick_num,int start)
{[......]
A company offers personal computers for sale in N towns (3 <= N <= 35). The towns are denoted by 1, 2, …, N. There are direct routes connecting M pairs from among these towns. The company decides to build servicing stations in several towns, so that f[……]
这题感觉没什么好说的,考的思维,看出规律模拟即可。。不过发现dfy的代码写的比我好多了~~就把她的贴上来吧。
#include <stdio.h>
#include <stdlib.h>
int main()
{
int t,x,y,i,j,a[100][100],n,m;
scanf("%d",&m);
while(m--)
{
memset(a,0,sizeof(a));
scanf("%d",&n);
t[......]
这道题是改编题，原题是：http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=394#problem/E
网上关于此题的代码和解释非常多，各种思路，我就不解释了，下面是我的做法，供参考～
#include <stdio.h>
int n;
long k;
void spa()
{ int ln=1;
if(k<0)
k=-k;
while(ln*(ln+1)/2<k)
ln++;
while((ln*(ln+1)/2-k)%2!=0||(ln*(ln+1)/[......]
分析：
在计算机上进行高精度计算，首先要处理好以下几个基本问题：
1、数据的接收与存储；
2、计算结果位数的确定；
3、进位处理和借位处理；
4、商和余数的求法；
输入和存储
运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。能表示多个数的数据类型有两种：数组和字符串。
（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；优点：每一位都是数的形式，可以直接加减；运算时非常方便缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；
（2）字符串：字符串的最大长度是255，可以表示255位[……]
2013年3月21日
只有C题需要注意，若字符窜循环中用是strlen的会超时……
B题： Good boy, laiyifa!（最短路）
#include <stdio.h>
#define INF 1001
int n,h;
int map[505][505],clost[505],vis[505];
int Dijsk(int s,int e){
int i,j,k,Min;
for(i=0;i<n;i++){
clost[i]=map[s][i];
vis[i]=0;
}
vis[s]=1;
for(i=1;i<n;i++){
Min=INF;
for(j=0;j<n;j++){
if(!vis[j] && clost[j]<Min){
Min=clost[j];
k=j;
}
}
vis[k]=1;
for(j=0;j<n;j++)
if(!vis[j] && clost[j]>clost[k]+map[k][j])
clost[j]=clost[k]+map[k][j];
}
return clost[e];
}
int main(){
while(scanf("%d%d",&n,&h)!=EOF){
int i,j,Min;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&map[i][j]);
if(!map[i][j])
map[i][j]=INF;
}
}
Min=Dijsk(0,n-1)+Dijsk(n-1,0);
if(Min<h)
printf("%d\n",Min);
else
printf("-1\n");
}
return 0;
}
C题：Loli vs CET-4（暴力）
#include <string.h>
#include<stdio.h>
int cnt[30],num[30],Max;
char str[4][30][60];
void dfs(int i){
int j,k;
if(i==4){
int sum=0;
for(i=0;i<26;i++)
sum+=cnt[i]*cnt[i];
Max=Max>sum?Max:sum;
return ;
}
for(j=0;j<num[i];j++){
for(k=0;str[i][j][k];k++)
cnt[str[i][j][k]-'a']++;
dfs(i+1);
for(k=0;str[i][j][k];k++)
cnt[str[i][j][k]-'a']--;
}
}
int main(){
int cases;
while(scanf("%d",&cases)!=EOF){
while(cases--){
int i,j;
memset(cnt,0,sizeof(cnt));
for(i=0;i<4;i++){
scanf("%d",&num[i]);
for(j=0;j<num[i];j++)
scanf("%s",&str[i][j]);
}
Max=-1;
dfs(0);
printf("%d\n",Max);
}
}
return 0;
}
#include <stdio.h>
#include <string.h>
char str[5][35][60];
int num[5];
int res;
void dfs(int i, int t[]){
if (i == 5){
int sum = 0;
for (int k='a' - 'a'; k<= 'z' - 'a'; k++)
sum += t[k] * t[k];
if (sum > res)
res = sum;
return;
}
for (int j=1; j<=num[i]; j++)
{
int time[30] = {0};
int n = strlen(str[i][j]);
for (int k=0; k<='z' - 'a'; k++)
time[k] = t[k];
for (int k=0; k<n; k++)
time[str[i][j][k] - 'a'] ++;
dfs(i + 1, time);
}
}
int main()
{
int n;
scanf("%d", &n);
while (n--){
memset(str, 0, sizeof(str));
res = 0;
for (int i=1; i<5; i++){
scanf("%d", &num[i]);
getchar();
for (int j=1; j<=num[i]; j++){
scanf("%s", str[i][j]);
}
}
int time[30] = {0};
dfs(1, time);
printf("%d\n", res);
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char s1[40][60],s2[40][60],s3[40][60],s4[40][60];
int num[27];
int n1,n2,n3,n4;
int main()
{
int t,i,j,k,maxx,ans,p,q,x,y;
scanf("%d",&t);
while(t--)
{
maxx=-1;
scanf("%d",&n1);
for(i=0;i<n1;i++) scanf("%s",s1[i]);
scanf("%d",&n2);
for(i=0;i<n2;i++) scanf("%s",s2[i]);
scanf("%d",&n3);
for(i=0;i<n3;i++) scanf("%s",s3[i]);
scanf("%d",&n4);
for(i=0;i<n4;i++) scanf("%s",s4[i]);
for(i=0;i<n1;i++)
{
for(j=0;j<n2;j++)
{
for(k=0;k<n3;k++)
{
for(q=0;q<n4;q++)
{
memset(num,0,sizeof(num));
for(y=0;s1[i][y];y++) num[s1[i][y]-'a']++;
for(y=0;s2[j][y];y++) num[s2[j][y]-'a']++;
for(y=0;s3[k][y];y++) num[s3[k][y]-'a']++;
for(y=0;s4[q][y];y++) num[s4[q][y]-'a']++;
for(p=0,ans=0;p<26;p++)
ans+=num[p]*num[p];
if(ans>maxx)
maxx=ans;
}
}
}
}
printf("%d\n",maxx);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<math.h>
const int MN=60;
char s1[MN][MN],s2[MN][MN],s3[MN][MN],s4[MN][MN];
int hash1[30],hash2[30],hash3[30],hash4[30];
int main()
{
int sum,ans;
int T,n1,n2,n3,n4,i,j,k,t,x,y;
scanf("%d",&T);
while(T--)
{
sum=ans=0;
scanf("%d",&n1);
for(i=0;i<n1;i++) scanf("%s",s1[i]);
scanf("%d",&n2);
for(i=0;i<n2;i++) scanf("%s",s2[i]);
scanf("%d",&n3);
for(i=0;i<n3;i++) scanf("%s",s3[i]);
scanf("%d",&n4);
for(i=0;i<n4;i++) scanf("%s",s4[i]);
for(i=0;i<n1;i++)
{
memset(hash1,0,sizeof(hash1));
for(x=0;s1[i][x];x++) hash1[s1[i][x]-'a']++;
for(j=0;j<n2;j++)
{
memset(hash2,0,sizeof(hash2));
for(x=0;s2[j][x];x++) hash2[s2[j][x]-'a']++;
for(k=0;k<n3;k++)
{
memset(hash3,0,sizeof(hash3));
for(x=0;s3[k][x];x++) hash3[s3[k][x]-'a']++;
for(t=0;t<n4;t++)
{
sum=0;
memset(hash4,0,sizeof(hash4));
for(x=0;s4[t][x];x++) hash4[s4[t][x]-'a']++;
for(y=0;y<26;y++)
{
int tmp=hash1[y]+hash2[y]+hash3[y]+hash4[y];
sum+=(int)pow(tmp*1.0,2);
}
if(ans<sum) ans=sum;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}
[……]
先筛选求素数了，存下500000内的素数然后打表把1000000内的半素数都求出来了。巨麻烦。求简单解法。
#include <stdlib.h>
#include <stdio.h>
int p[2000000]={0},cp[500005]={1,1},sp[1000005]={0};
int main()
{
long i,j,k,n;
for(i=2;i<1000;i++)
for(j=i*i;j<500000;j+=i)
cp[j]=1;
j=0;
for(i=2;i=0;i–)
for(k=0;p[i]*p[k]&l[……]
题目链接：http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=385#problem/L
思路：回溯 或者 stl函数求全排列验证，下面是第二种；
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 500000
int map[50][50],vis[50];//map确[……]
一、能被*整除：
(1) 1与0的特性：
1是任何整数的约数，即对于任何整数a，总有1|a；0是任何非零整数的倍数，a≠0,a为整数，则a|0。
(2) 能被2整除：
若一个整数的末位能被2整除，即这个整数的末位是0、2、4、6、8，则这个数能被2整除。
(3) 能被3整除：
若一个整数的各位数字和能被3整除，则这个数能被3整除。
(4) 能被4整除：
若一个整数的末尾两位数能被4整除，则这个数能被4整除。
(5) 能被5整除：
若一个整数的末位是0或5，则这个数能能被5整除。
(6) 能被6整除：
若一个整数能被2和3整除，则这个数能被6整除。
(7) 能被7整除：[……]
题目链接：http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=388#problem/B
题意：求点数并按升序输出；
我的基本思路：BFS+DFS
code：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 52
char map[MAX][MAX];
int visit[MAX][MAX],sum_dice,d_x[4]={-1,0,1,0},d_y[4]={0,1[……]
题目链接：http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=388#problem/H
做了很长时间才出来，表示弱爆了；题意是求最短时间，用bfs，每次状态入队列就ok了；
my code：
#include <stdio.h>
#include <string.h>
#define MAX 26
int visit[MAX][MAX][4][5];//4:0北，1东，2南，3西 |5：0green，1black,2red,3blue,4white
int plusx[4]={[……]
简单的dfs应用，算是加深了对dfs的理解！
code：
#include <stdio.h>
#include <string.h>
#define MAX 102
int m,n,sum;
char map[MAX][MAX],flag[MAX][MAX];
void dif([……]
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=380
题意容易懂，就是求一个点到另外一个点最少几步（只不过这题的模型是建立在国际象棋棋盘上的），用BFS，此题引入count便于求解（这是关键！）
code：
#include <iostream>
#include <cmalloc>
using namespace std;
typedef struct s
{
in[……]