程序杂谈

77 阅读 0 评论 51 点赞

我是靠谱客的博主优秀猎豹，最近开发中收集的这篇文章主要介绍程序杂谈，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.#include <bits/stdc++.h>

using namespace std;

int n,m;

int s[2005][2];

int sum=0;

int fd[1005];//1-n站点标示

int find(int x)

{ //并查集

if(fd[x]==x) return x;

return fd[x]=find(fd[x]);

}

int main()

{

cin>>n>>m;

for(int i=0;i<m;i++)

cin>>s[i][0]>>s[i][1];

int k1,k2;

cin>>k1>>k2;

for(int i=0;i<m;i++)

{ //枚举每一条边 然后去掉 然如果连通 就不是关键点

for(int ii=1;ii<=n;ii++) fd[ii]=ii;

for(int j=0;j<m;j++)

{

if(i!=j)//去掉第i条边所构成的并查集,查看是否为关键点

{

int a=find(s[j][0]); //并查集

int b=find(s[j][1]);

if(a!=b)

fd[a]=b;

}

int a=find(k1);

int b=find(k2); //查看两个端点是否连通

if(a!=b) sum++;

}

cout<<sum<<endl;

return 0;

}

//法二

const int MAX = 100000;

int t,n,q;

int original[MAX+10];

int parent[MAX+10];

int to[100000010]; //活跃度数组

int GetParent(int a)

{ //获取a的根,并把a的父节点改为根

return parent[a]==a ? a : parent[a]=GetParent(parent[a]);

}

//查询a,b是否在一个团体

int query(int a,int b)

{

return GetParent(a)==GetParent(b);

}

//合并a,b;

void Merge(int a,int b)

{

int p1 = GetParent(a);

int p2 = GetParent(b);

if( p1 == p2 ) return;

parent[p2] = p1;

}

int main()

{

int a; //活跃度

int k; //需要踢的最低活跃度

int total=0;

memset(parent,-1,sizeof(parent));

memset(parent,-1,sizeof(original));

scanf("%d",&t); //t组数据

while(t--)

{

scanf("%d%d",&n,&q); //n个整数q次询问

for(int i = 1;i <= n; ++i)

{

scanf("%d",&a);

original[i]=i; //保存原始值 当 parent需要恢复时用

parent[i] = i;

to[i]=a;

}

for(int i = 1;i <= q; ++i)

{

total=0;

scanf("%d",&k);

memcpy(parent,original,sizeof(parent)); //恢复parent

//剔除活跃度低于k的人

for(int j = 1;j <= k; ++j)

{

for(int x=1;x<=n;x++)

{

if(to[x]<=k) parent[x]=-1;

}

//组团体

for(int d = 1;d < n; ++d)

{

if(parent[d]!=-1)

{

for(int e = d+1;e <= n; ++e)

{

if(parent[e]!=-1)

{

if(abs(to[d]-to[e])==1 && !query(d,e) )

{

Merge(d,e);

}

//统计团体数

for(int d = 1;d <= n; ++d)

{

if(parent[d]==d)

{

total++;

}

printf("%d ",total);

}

printf("n");

}

return 0;

}

3。在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成了若干堆，小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后，就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。

假定每个水果重量都为 1，并且已知水果的种类数和每种水果的数目，你的任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费值。例如有 3 种水果，数目依次为 1，2，9。可以先将 1，2 堆合并，新堆数目为3，耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆，耗费体力为 12。所以小明总共耗费体力=3+12=15，可以证明 15 为最小的体力耗费值。

n(1<=n<=10000),表示水果的种类数，第二行包含 n 个整数，用空格分隔，第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。

贪心+最小堆

int main()

{

priority_queue <int, vector <int>, greater <int> > Q;

int n, i, iData;

while (~scanf("%d", &n) && n)

{

for (i = 0; i < n; ++i)

{

scanf("%d", &iData);

Q.push(iData);

}

if(n==1)

{

printf("%dn", iData);

Q.pop();

continue;

}

int sum = 0;

while (!Q.empty())

{

int tmp1 = Q.top();

Q.pop();

if(!Q.empty())

{

int tmp2 = Q.top();

Q.pop();

tmp1 += tmp2;

Q.push(tmp1);

sum += tmp1;

}

else

printf("%dn", sum);

}

return 0;

}

4.会议安排

struct Meet

{

int beg;

int end;

}meet[100];

bool cmp(Meet x,Meet y)

{

if(x.end==y.end) return x.beg>y.beg);//开始时间从大到小

return x.end < y.end;//结束时间从小到大

}

sort(meet,meet+n,cmp);

int ans =1;//记录会议个数

int last = meet[0].end ;//记录第一个会议结束的时间

for(int i=1;i<n;i++)

{

if(meet[i].beg>=last)

{

ans++;

last=meet[i].end;

}

return ans;

6.吉哥一共有m天的假期，每天的编号从1到m，一共有n份可以做的工作，每份工作都知道起始时间s，终止时间e和对应的工资c，每份工作的起始和终止时间以天为单位(即天数编号)，每份工作必须从起始时间做到终止时间才能得到总工资c，且不能存在时间重叠的工作。比如，第1天起始第2天结束的工作不能和第2天起始，第4天结束的工作一起被选定，因为第2天吉哥只能在一个地方工作。

现在，吉哥想知道怎么安排才能在假期的m天内获得最大的工资数（第m+1天吉哥必须返回学校，m天以后起始或终止的工作是不能完成的）。

Input：每组数据的第一行是2个正整数：假期时间m和可做的工作数n；接下来n行分别有3个正整数描述对应的n个工作的起始时间s，终止时间e，总工资c。

动态规划：dp[i]表示到今天所能挣到最多的钱，dp[i] = MAX(dp[i], dp[j] + a[j+1][i]);其中a[i][j]表示：从i到j天的工资！

const int MAXN = 110;

int main()

{

int T, iHoliday, iWorks, i, j, iStart, iEnd, iSalary;

int iWorkDay[MAXN][MAXN];

int dp[MAXN];

scanf("%d", &T);

while(T--)

{

scanf("%d %d", &iHoliday, &iWorks);

memset(iWorkDay, 0, sizeof(iWorkDay));

memset(dp, 0, sizeof(dp));

for(i = 0; i < iWorks; ++i)

{

scanf("%d %d %d", &iStart, &iEnd, &iSalary);

if(iStart > iHoliday || iEnd > iHoliday)

continue ;

if(iSalary > iWorkDay[iStart][iEnd])

iWorkDay[iStart][iEnd] = iSalary;

}

for(i = 1; i <= iHoliday; ++i)

{

for(j = 0; j < i; ++j)

{

dp[i] = MAX(dp[i], dp[j] + iWorkDay[j+1][i]);

}

printf("%dn", dp[iHoliday]);

}

return 0;

}

7.工作室是一个N行M列的矩形布局，小Q每个同事进行了评分（为区别男女，男生一律用负整数表示，女生一律用正整数表示）。

　　现在，小Q把所有人的数据记录下来，并且这样定义一个位置的价值：

　　1、一个位置的价值只和其上下左右四个邻居的魅力值有关（对于靠边的位置，只考虑其存在的邻居）；

　　2、如果某位置的邻居和该位置主人性别不同，则总分加上邻居魅力值的绝对值，否则减去；

3、对周围所有邻居的数据处理后，最终的得分即为这个位置的最终得分，得分越高，则该位置越好；计算最佳位置？

每组测试数据的第一行包含2个整数N和M，表示工作室的布局是N行M列；

接下来的N行，每行有M个整数，分别表示对应位置员工的魅力值数据Ki，

正整数表示女生的魅力值，负整数表示男生的魅力值；

N和M为0的时候表示输入数据结束。

In：2 3 out: 1 2 11

5 -4 3

-6 3 7

0 0

const int MAXN = 25;

int fabs(int a)

{

return a > 0 ? a : (-a);

}

int Find_Abs(int a, int b)

{

if(a * b < 0) return fabs(b);

else if(a * b > 0) return -fabs(b);

else return 0;

}

int main()

{

int Graph[MAXN][MAXN];

int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

int CurVal;

int i, j, k, xpos, ypos;

int MaxNum;

int row, col;

while(scanf("%d%d", &row, &col) && (row + col))

{

memset(Graph, 0, sizeof(Graph));

for(i = 1; i <= row; ++i)

for(j = 1; j <= col; ++j)

scanf("%d", &Graph[i][j]);

MaxNum = INT_MIN , xpos = 1, ypos = 1;

for(i = 1; i <= row; ++i)

{

for(j = 1; j <= col; ++j)

{

CurVal = 0;

for(k = 0; k < 4; ++k)

{

int x = i + dir[k][0];

int y = j + dir[k][1];

if(x < 1 || x > row || y < 1 || y > col)

continue ;

CurVal += Find_Abs(Graph[i][j], Graph[x][y]);

}

if(CurVal > MaxNum)

{

MaxNum = CurVal;

xpos = i, ypos = j;

}

printf("%d %d %dn", xpos, ypos, MaxNum);

}

return 0;

}

11.定义一个二维数组： int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0, };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

struct Pos

{

int r,c;

int father; //父节点在队列中的下标,-1表示本节点是起点

Pos(int rr=0,int cc=0,int ff=0):r(rr),c(cc),father(ff) { }

};

int maze[8][8];

Pos que[100];

int head,tail; //队列头尾指针

Pos dir[4] = {Pos(-1,0),Pos(1,0),Pos(0,-1),Pos(0,1)}; //移动方向

int main() {

memset(maze,0xff,sizeof(maze));

for( int i = 1;i <= 5; ++i)

for (int j = 1; j <= 5; ++j )

cin >> maze[i][j];

head = 0;tail = 1;

que[0] = Pos(1,1,-1);

while( head != tail )

{ //队列不为空

Pos ps = que[head];

if( ps.r == 5 && ps.c == 5 )

{ //目标节点出队列

vector<Pos> vt;

while(true)

{

vt.push_back(Pos(ps.r,ps.c,0));

if( ps.father == -1 )//起点

break;

ps = que[ps.father];

};

for( int i = vt.size()-1; i >= 0; -- i )

cout << "(" << vt[i].r-1 << ", " <<vt[i].c-1 << ")" << endl;

return 0;

}

else

{//队头节点不是目标节点

int r = ps.r, c = ps.c;

for( int i = 0;i < 4; ++i)

if(! maze[r+dir[i].r][c+dir[i].c])

{

que[tail++] =Pos(r+dir[i].r,c+dir[i].c,head);

//新扩展出来的节点的父节点在队列里的下标是head

maze[r+dir[i].r][c+dir[i].c] = 1;

}

++head;

}

return 0;

}

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ... mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

输入

标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行,

第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000).

第2行:n 个地点的位置m1 , m2, ... mn ( 1000000 > mi > 0 且为整数,升序排列)

第3行:n 个地点的餐馆利润p1 , p2, ... pn ( 1000 > pi > 0 且为整数)

输出

对于每组测试数据可能的最大利润

样例输入

3 11

1 2 15

10 2 30

3 16