企业网站运营问题,电商网站建设技术交流问题,长春服务好的网站建设,仕德伟做的网站文章目录畅通工程题意#xff1a;题解#xff1a;代码#xff1a;小希的迷宫题解#xff1a;代码#xff1a;Express Mail Taking题意#xff1a;题解#xff1a;代码#xff1a;Reports题意#xff1a;题解#xff1a;代码#xff1a;放苹果题意#xff1a;题解题解代码小希的迷宫题解代码Express Mail Taking题意题解代码Reports题意题解代码放苹果题意题解代码Monthly Expense题意题解代码String Typing题意题解代码Diagonal Walking题意题解代码畅通工程
题意
最少建多少道路使得两两城镇之间都能连通
题解
利用并查集 题意很清楚我们来分析下例子第一行告诉你一共有4个点2条路。下面两行告诉你1、3之间有条路4、3之间有条路。那么整幅图就被分成了1-3-4和2两部分。只要再加一条路把2和其他任意一个点连起来畅通工程就实现了那么这个这组数据的输出结果就是1。
那该怎么办呢可以运用学过的并查集啊给每个父数组一个初值-1代表尚未与其他路接通每连通一个路便将-1置去因此和普通并查集不同的地方为初始化应为如下
for(int i0;in;i)pre[i]-1;此时Find函数应为
int Find(int x)
{if(pre[x]-1) return x;return pre[x]Find(pre[x]);然后即可简单的写出程序需要注意的是需要创建的边数永远为城镇数减一然后永远有一个根节点未置去-1程序如下
代码 #includecstdio
int pre[1010];
int find(int a)//find函数查找他的领导
{int leadera;while(pre[leader]!leader)//领导不是自己找自己的上一级领导 leaderpre[leader]; int t,ba;while(b!leader){tpre[a];pre[a]leader;bt;}return leader;
}
int main()
{int n,m,point1,point2,all,lead1,lead2;//point表示城镇编号 while(scanf(%d,n),n){alln-1;//n个点不连成环需要n-1条边 for(int i1;in;i){pre[i]i;//初始化为自己的领导是自己 }scanf(%d,m);for(int j0;jm;j){scanf(%d%d,point1,point2);lead1find(point1);lead2find(point2);if(lead1!lead2){pre[lead2]lead1;all--;//根据题目给出的条件每连通一条总数减一 }}printf(%d\n,all);}return 0;
}
小希的迷宫
题解
该题用并查集做难度不大判断是否成环即判断是否要合并的两个结点的根结点相同即可因此稍稍改变了一下join函数。 需要注意的是还有一点是每个房间必须连通这一点我一开始忽视了于是过样例却WA因为样例都是保证全连通
代码
#includebits/stdc.h
using namespace std;
int pre[100005];
bool vis[100005];int find(int x){int r x;while(pre[r] ! r){r pre[r];}int i x, j;while(i ! r){j pre[i];pre[i] r;i j;}return r;
}bool join(int x, int y){int i find(x), j find(y);if (i ! j){pre[j] i;return true;}else return false;
}int main()
{int a, b;while(scanf(%d%d, a, b) ! EOF){for (int i 1; i 100005; i) pre[i] i;memset(vis, 0, sizeof(vis));if (a -1 b -1) break;if (a 0 b 0){printf(Yes\n);continue;}bool flag 1;while(a ! 0){vis[a] vis[b] 1;//判断是否成环if(!join(a, b)) flag 0;scanf(%d%d, a, b);}int root 0;//判断是否全连通for (int i 1; i 100005; i)if (vis[i] pre[i] i) root;if (root 1) flag 0;if (flag) printf(Yes\n);else printf(No\n);}return 0;
}Express Mail Taking
题意
现在有n个柜子依次排列这些柜子编号从1~n。每个柜子之间距离为1 其中柜子编号为k的是特殊的这是个密码柜要向打开其他柜子就必须在这个柜子输入密码。现在你有m个快递在这些柜子中你从入口进入取完快递后从入口出来问你需要走的最小距离。
题解
贪心做法 由于这些快递这件是没有关联的所以这道题是非常简单的在没有取完快递之前我们都需要先去密码柜再输入密码再去取快递这些步骤都是等效的。 那么这道题为什么会有最小距离呢重要的就是在取最后一个快递的时候我们取完最后一个快递是不是没必要回到密码柜了直接走到出口故最后一个快递的位置显得极为重要这也是决定性因素。所以我们想要让最后一个快递的位置靠近入口即可。此题则易解。
代码
#includebits/stdc.h //POJ不支持#define rep(i,a,n) for (int ia;in;i)//i为循环变量a为初始值n为界限值递增
#define per(i,a,n) for (int ia;in;i--)//i为循环变量 a为初始值n为界限值递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pairusing namespace std;const int inf 0x3f3f3f3f;//无穷大
const int maxn 1e6;//最大值。
typedef long long ll;
typedef long double ld;
typedef pairll, ll pll;
typedef pairint, int pii;
//*******************************分割线以上为自定义代码模板***************************************//ll t,n,m,k;
ll a[maxn];
int main(){//freopen(in.txt, r, stdin);//提交的时候要注释掉IOS;while(cint){while(t--){cinnmk;rep(i,0,m-1){cina[i];}sort(a,am);ll ansk-1;per(i,m-1,1){ansabs((a[i]-k)*2);}if(a[0]k)ansk-1;else{ansabs((a[0]-k)*2)k-1;}coutansendl;}}return 0;
}Reports
题意
给你某一天的报告在这一天总共报告n nn次其中1 11表示入校0 00表示离校当且仅当不连续存在两个相同的报告类型时这份报告才算正确。现在请你判断这份报告是否有误。
题解
根据题意直接判断是否有相邻元素相等就行
代码
#includebits/stdc.h #define rep(i,a,n) for (int ia;in;i)//i为循环变量a为初始值n为界限值递增
#define per(i,a,n) for (int ia;in;i--)//i为循环变量 a为初始值n为界限值递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pairusing namespace std;const int inf 0x3f3f3f3f;//无穷大
const int maxn 1e5;//最大值。
typedef long long ll;
typedef long double ld;
typedef pairll, ll pll;
typedef pairint, int pii;int t,n;
int a[maxn];
int main(){//freopen(in.txt, r, stdin);//提交的时候要注释掉IOS;while(cint){while(t--){cinn;rep(i,0,n-1){cina[i];}bool flagfalse;rep(i,0,n-2){if(a[i]a[i1]){flagtrue;break;}}if(flag)coutNOendl;elsecoutYESendl;}}return 0;
}放苹果
题意
把M个同样的苹果放在N个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法用K表示511和151 是同一种分法。
题解
首先设 i个苹果放在 k个盘子里的放法总数是 f(i,k) 分类讨论有两种情况 1当 k i 时f ( i , k ) f ( i , i ) 2当 k i时总放法 有盘子为空的放法没盘子为空的放法 f ( i , k ) f ( i , k - 1 ) f ( i - k , k )
代码
#includeiostream
using namespace std;
//设 i个苹果放在 k个盘子里的放法总数是 f(i,k)
int f(int i,int k){if(k i){//当 k i时f(i,k) f(i,i) return f(i,i);}if(i 0)return 1;if(k 0){return 0;}//k i时总放法 有盘子为空的放法没盘子为空的放法//f(i,k) f(i,k-1) f(i-k,k) return f(i,k-1)f(i-k,k);
}int main(){int t,i,k,count0;cint;while(t--){cinik; coutf(i,k)endl;}return 0;
} Monthly Expense
题意
给出农夫在n天中每天的花费要求把这n天分作m组每组的天数必然是连续的要求分得各组的花费之和应该尽可能地小最后输出各组花费之和中的最大值
题解
各组最小和的最大值应该用二分做枚举一个答案然后验证是否合理不断缩小范围最后确定答案
代码
#includeiostream
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includestring
#includecstdlib
#includequeue
#includevector
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 100001
#define MOD 123
#define E 1e-6
using namespace std;
int n,m;
int a[N];
bool judge(int value)//判断当前花费可把n分成几组
{int sum0;//花费总和int cnt1;//初始时只有一组for(int i0;in;i)//枚举每天花费{if(suma[i]value)suma[i];else{suma[i];cnt;}}if(cntm)//若分组数比规定数要多则mid偏小需调整左值return false;else//若分组数比规定数要少则mid偏大需调整右值return true;
}
int main()
{while(scanf(%d%d,n,m)!EOF){int left0,right0;for(int i0;in;i){scanf(%d,a[i]);leftmax(left,a[i]);righta[i];}int mid;while(leftright){mid(leftright)/2;if(judge(mid))rightmid-1;elseleftmid1;}printf(%d\n,mid);}return 0;}String Typing
题意
给一个字符串可以复制某一段字符问最少需要多少步能将其输出比如abcabcd先输入abc然后再赋值abc再输入d就只需要5步。 复制的这段字符 必须是从字符串的0位置开始复制的 而且只能粘贴一次 例abcabcabc 输出为7
题解
string中的str.substrij 截取字符串str第i位置开始的长度为j的一段字符 从开始截取长度为i的一段看是否和后面有重复的
代码
#include bits/stdc.h
//freopen(1.txt, r, stdin);
using namespace std;
const int maxn 10010, INF 0x7fffffff;int main()
{int n;string str;cin n str;int res n;for(int i1; in/2; i)if(str.substr(0, i) str.substr(i, i)) res n - i 1;cout res endl;return 0;
}Diagonal Walking
题意
给出n个操作相连的U和R 可以看为一步问一共多少步
题解
直接按照题目模拟即可遇到UR或者RU就跳过其他的计算步数
代码
#include bits/stdc.h
typedef long long ll;
using namespace std;
int main(){int n;cin n;string s;cin s;int u 0, r 0, ans 0;int len s.size();for(int i 0; i s.size(); i){if((s[i] U s[i1] R) || (s[i] R s[i1] U)){i; // 相连的U和R看为一步}ans;}cout ans endl;return 0;
}
