外贸网站模板设计,企业查询系统官网天眼查网页版,网页设计做音乐网站,河北建设工程信息网辅助评标系统A: 题意#xff1a; 给出一个矩阵表示蛋糕#xff0c;矩阵中有毒草莓。我们每次可以选择一行或者一列来吃蛋糕#xff0c;要保证改行该列不含有毒草莓。问我们能吃到的最多的小蛋糕快 思路#xff1a; 直接枚举每一行#xff0c;每一列然后吃#xff0c;模拟就行。 #incl…A: 题意 给出一个矩阵表示蛋糕矩阵中有毒草莓。我们每次可以选择一行或者一列来吃蛋糕要保证改行该列不含有毒草莓。问我们能吃到的最多的小蛋糕快 思路 直接枚举每一行每一列然后吃模拟就行。 #include iostream
#include cstdio
#include cmath
#include vector
#include cstring
#include algorithm
#include string
#include set
#include functional
#include numeric
#include sstream
#include stack
#include map
#include queue#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt1
#define rc m 1,r,rt1|1
#define pi acos(-1.0)
#define ll __int64
#define L(x) (x) 1
#define R(x) (x) 1 | 1
#define MID(l, r) (l r) 1
#define Min(x, y) (x) (y) ? (x) : (y)
#define Max(x, y) (x) (y) ? (y) : (x)
#define E(x) (1 (x))
#define iabs(x) (x) 0 ? -(x) : (x)
#define OUT(x) printf(%I64d\n, x)
#define lowbit(x) (x)(-x)
#define Read() freopen(din.txt, r, stdin)
#define Write() freopen(dout.txt, w, stdout);#define M 1007
#define N 1007
using namespace std;int n,m;
char str[N][N];
bool vt[N][N];int main()
{
// Read();
cinnm;CL(vt,false);for (int i 0; i n; i){scanf(%s,str[i]);}int ans 0;for (int i 0; i n; i){int f 1;int tmp 0;for (int j 0; j m; j){if (str[i][j] S) f 0;else if (!vt[i][j]) tmp;}if (f 1){ans tmp;for (int j 0; j m; j){vt[i][j] true;}}}for (int j 0; j m; j){int f 1;int tmp 0;for (int i 0; i n; i){if (str[i][j] S) f 0;else if (!vt[i][j]) tmp;}if (f 1){ans tmp;for (int i 0; i n; i){vt[i][j] true;}}}cout ans endl;return 0;
} View Code B: 题意 给你n个点m条边m条边表示不能连接在一起的边。让我们建立这样一个图使得任意一个点都能通过至多两条边就能到达其他的任意点。 题目保证有解数出这个图的边 思路 不能再一起的点肯定是通过一个中间点连接的然后我们把不能在一起的点放进一个set(因为可能会出现重复的点题目只是说不会出现重复的边比赛时理解错了wa了一次) 然后找出一个不存在排他关系的点当做中间点所有点都连接一条边到他就好了。 #include iostream
#include cstdio
#include cmath
#include vector
#include cstring
#include algorithm
#include string
#include set
#include functional
#include numeric
#include sstream
#include stack
#include map
#include queue#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt1
#define rc m 1,r,rt1|1
#define pi acos(-1.0)
#define ll __int64
#define L(x) (x) 1
#define R(x) (x) 1 | 1
#define MID(l, r) (l r) 1
#define Min(x, y) (x) (y) ? (x) : (y)
#define Max(x, y) (x) (y) ? (y) : (x)
#define E(x) (1 (x))
#define iabs(x) (x) 0 ? -(x) : (x)
#define OUT(x) printf(%I64d\n, x)
#define lowbit(x) (x)(-x)
#define Read() freopen(din.txt, r, stdin)
#define Write() freopen(dout.txt, w, stdout);#define M 1007
#define N 1007
using namespace std;struct node
{int u,v;
}nd[N];
int len;
bool vt[N];vectorint vc;
setint X;
int n,m;int main()
{
// Read();cinnm;CL(vt,false); len 0;int x,y;X.clear();for (int i 1; i m; i){scanf(%d%d,x,y);if (!vt[x]) X.insert(x);if (!vt[y]) X.insert(y);vt[x] true;vt[y] true;}vc.clear();for (int i 1; i n; i){if (!vt[i]) vc.push_back(i);}int ans 0;ans (vc.size() - 1 X.size());cout ans endl;int mid vc[0];int sz vc.size();for (int i 1; i sz; i){printf(%d %d\n,vc[i],mid);}setint::iterator it;for (it X.begin(); it ! X.end(); it){printf(%d %d\n,*it,mid);}return 0;
} View Code C 题意 给你一个矩阵其中的每个单元都需要净化我们通过贴符的方式使得其在的行与列的所有的单元都会的到净化其中“.”表示可以贴符的单元“E”表示不可以贴符的单元。 求使贴最少的符使得所有的单元都被得到净化。 思路 我们分析可得如果该矩阵的所有单元都得到净化的话。必定是每一行都存在“.” 或者每一列都存在. 否则是不行的。然后我们只要枚举行枚举列模拟一下记录“.”的位置就好了。 #include iostream
#include cstdio
#include cmath
#include vector
#include cstring
#include algorithm
#include string
#include set
#include functional
#include numeric
#include sstream
#include stack
#include map
#include queue#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt1
#define rc m 1,r,rt1|1
#define pi acos(-1.0)
#define ll long long
#define L(x) (x) 1
#define R(x) (x) 1 | 1
#define MID(l, r) (l r) 1
#define Min(x, y) (x) (y) ? (x) : (y)
#define Max(x, y) (x) (y) ? (y) : (x)
#define E(x) (1 (x))
#define iabs(x) (x) 0 ? -(x) : (x)
#define OUT(x) printf(%I64d\n, x)
#define lowbit(x) (x)(-x)
#define keyTree (chd[chd[root][1]][0])
#define Read() freopen(din.txt, r, stdin)
#define Write() freopen(dout.txt, w, stdout);#define M 100
#define N 307using namespace std;int dx[4]{-1,1,0,0};
int dy[4]{0,0,-1,1};//иообвСсрconst int inf 0x7f7f7f7f;
const int mod 1000000007;
const double eps 1e-8;int rv[N],cv[N];
int n;
char str[N][N];
int a[N];int main()
{scanf(%d,n);for (int i 0; i n; i) scanf(%s,str[i]);CL(rv,0);for (int i 0; i n; i){for (int j 0; j n; j){if (str[i][j] .){rv[i] 1;a[i] j;break;}}}int f 1;for (int i 0; i n; i) if (!rv[i]) f 0;if (f) for (int i 0; i n; i) cout i 1 a[i] 1 endl;else{CL(cv,0); f 1;for (int j 0; j n; j){for (int i 0; i n; i){if (str[i][j] .){cv[j] 1;a[j] i;break;}}}for (int j 0; j n; j) if (!cv[j]) f 0;if (f) for (int j 0; j n; j) cout a[j] 1 j 1 endl;else printf(-1\n);}return 0;
} View Code D: 题意 给你一个矩阵其中“T”表示树“S”表示你的起点“0 - 9”表示拥有该数量的团伙的敌人“E”表示目的地你的目标是移动到E,但是在你移动的过程中会有敌人一伙一伙的来找你与你PK,当你们相遇时你必须PK掉所有的敌人才可以继续往下走。我们不管你走了多少步。我们只需要知道你在到达目的地的过程中最少的PK掉的人数。 思路 所有的人同时向目标移动移动的过程谁会碰到我呢怎么判断呢 分析可知道只要某个人到达终点的最短距离小于等于我倒终点的最短距离的一定会赶上我与我PK然后我们只要利用spfa求出终点到每个点的最短距离然后检查到达其他点的最短距离小于我的就加上即可。 #include iostream
#include cstdio
#include cmath
#include vector
#include cstring
#include algorithm
#include string
#include set
#include functional
#include numeric
#include sstream
#include stack
#include map
#include queue#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt1
#define rc m 1,r,rt1|1
#define pi acos(-1.0)
#define ll long long
#define L(x) (x) 1
#define R(x) (x) 1 | 1
#define MID(l, r) (l r) 1
#define Min(x, y) (x) (y) ? (x) : (y)
#define Max(x, y) (x) (y) ? (y) : (x)
#define E(x) (1 (x))
#define iabs(x) (x) 0 ? -(x) : (x)
#define OUT(x) printf(%I64d\n, x)
#define lowbit(x) (x)(-x)
#define keyTree (chd[chd[root][1]][0])
#define Read() freopen(din.txt, r, stdin)
#define Write() freopen(dout.txt, w, stdout);#define M 100
#define N 1007using namespace std;int dx[4]{-1,1,0,0};
int dy[4]{0,0,-1,1};//иообвСсрconst int inf 0x7f7f7f7f;
const int mod 1000000007;
const double eps 1e-8;struct node
{int x,y;int stp;node(int tx 0,int ty 0,int ts 0) : x(tx),y(ty),stp(ts) {}
};char str[N][N];
int dis[N][N];
bool vt[N][N];
int n,m;
int len;
int sx,sy;int inmap(int x,int y)
{if (x 0 x n y 0 y m) return true;return false;
}
void spfa()
{queuenode q;for (int i 0; i n; i){for (int j 0; j m; j){if (str[i][j] E){dis[i][j] 0;vt[i][j] true;q.push(node(i,j,0));}else{dis[i][j] inf;vt[i][j] false;}}}while (!q.empty()){node u q.front(); q.pop();for (int i 0; i 4; i){int tx u.x dx[i];int ty u.y dy[i];if (!inmap(tx,ty)) continue;if (str[tx][ty] T) continue;if (dis[tx][ty] u.stp 1){dis[tx][ty] u.stp 1;if (!vt[tx][ty])q.push(node(tx,ty,dis[tx][ty]));}}vt[u.x][u.y] false;}
}
int main()
{cinnm;for (int i 0; i n; i){scanf(%s,str[i]);for (int j 0; j m; j){if (str[i][j] S){sx i; sy j;}}}spfa();int ans 0;int tmp dis[sx][sy];for (int i 0; i n; i){for (int j 0; j m; j){
// printf(%c %d\n,str[i][j],dis[i][j]);if (str[i][j] 1 str[i][j] 9 dis[i][j] tmp){ans str[i][j] - 0;}}}printf(%d\n,ans);return 0;
} View Code E: 题意 给你一个n个点m条边的无向图然后让你重新构图使得旧图中的边不会存在于新图。然后旧图与新图都必须满足每个点至多有两条边与其相连两图的点的个数也必须相同。 思路 首先不会存在重复的边然后每个点至多有两条边与其相连。 该图一定是连续的链或者一个一一排列的环的组和。 我们重新构建之后以肯定也是这样的。 所以我们只要保存起来不能存在于新图的边然后利用随机函数 random_shuffle的到1-n的一个排列然后检查按照该顺序建边是否能够建造出满足条件的图如果可以直接输出就好了。 #include iostream
#include cstdio
#include cmath
#include vector
#include cstring
#include algorithm
#include string
#include set
#include functional
#include numeric
#include sstream
#include stack
#include map
#include queue#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt1
#define rc m 1,r,rt1|1
#define pi acos(-1.0)
#define ll long long
#define L(x) (x) 1
#define R(x) (x) 1 | 1
#define MID(l, r) (l r) 1
#define Min(x, y) (x) (y) ? (x) : (y)
#define Max(x, y) (x) (y) ? (y) : (x)
#define E(x) (1 (x))
#define iabs(x) (x) 0 ? -(x) : (x)
#define OUT(x) printf(%I64d\n, x)
#define lowbit(x) (x)(-x)
#define keyTree (chd[chd[root][1]][0])
#define Read() freopen(din.txt, r, stdin)
#define Write() freopen(dout.txt, w, stdout);#define M 100
#define N 100007using namespace std;int dx[4]{-1,1,0,0};
int dy[4]{0,0,-1,1};//иообвСсрconst int inf 0x7f7f7f7f;
const int mod 1000000007;
const double eps 1e-8;int n,m;
int id[N];setpairint,int st;bool solve()
{for (int i 1; i n; i) id[i] i;random_shuffle(id 1,id 1 n);id[n 1] id[1];int cnt 0;for (int i 2; i n 1; i){if (st.find(make_pair(id[i - 1],id[i])) st.end()) cnt;}if (cnt m) return false;for (int i 2; i n 1 m; i){if (st.find(make_pair(id[i - 1],id[i])) st.end()){printf(%d %d\n,id[i - 1],id[i]);m--;}}return true;
}
int main()
{scanf(%d%d,n,m);int x,y;st.clear();for (int i 0; i m; i){scanf(%d%d,x,y);st.insert(make_pair(x,y));st.insert(make_pair(y,x));}for (int i 0; i 100; i){if (solve()) return 0;}printf(-1\n);return 0;
} View Code 还有一种做法就是dfs我们按照点从小到大的顺序枚举然后不断的往后检查符合条件的点直到我们找到符合条件的边这个过程中记录我们枚举到的边然后利用set处理枚举可能会出现重复遍点的问题。 #include iostream
#include cstdio
#include cmath
#include vector
#include cstring
#include algorithm
#include string
#include set
#include functional
#include numeric
#include sstream
#include stack
#include map
#include queue#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt1
#define rc m 1,r,rt1|1
#define pi acos(-1.0)
#define ll long long
#define L(x) (x) 1
#define R(x) (x) 1 | 1
#define MID(l, r) (l r) 1
#define Min(x, y) (x) (y) ? (x) : (y)
#define Max(x, y) (x) (y) ? (y) : (x)
#define E(x) (1 (x))
#define iabs(x) (x) 0 ? -(x) : (x)
#define OUT(x) printf(%I64d\n, x)
#define lowbit(x) (x)(-x)
#define keyTree (chd[chd[root][1]][0])
#define Read() freopen(din.txt, r, stdin)
#define Write() freopen(dout.txt, w, stdout);#define M 100
#define N 100007using namespace std;int dx[4]{-1,1,0,0};
int dy[4]{0,0,-1,1};//懈芯芯斜胁小褋褉const int inf 0x7f7f7f7f;
const int mod 1000000007;
const double eps 1e-8;int n,m;
setint v;
vector pairint,int ans;
vectorint vc[N];
bool isok(int u,int v)
{for (size_t i 0; i vc[u].size(); i){if (vc[u][i] v) return false;}return true;
}
bool dfs(int u)
{if ((int)ans.size() min(n - 1,m)) return true;v.erase(u);for (setint::iterator it v.begin(); it ! v.end(); it){if (!isok(u,*it)) continue;ans.push_back(make_pair(u,*it));if (dfs(*it)) return true;else{ans.pop_back();it v.find(*it);//注意这里一定要重新定位it的值//虽然后边的点都插进来了而且是按顺序但是it的地址已经变了//如果不重新定位的话访问的将不是我们想要的值}}v.insert(u);return false;
}
int main()
{scanf(%d%d,n,m);for (int i 0; i n; i) vc[i].clear();int x,y;for (int i 0; i m; i){scanf(%d%d,x,y);vc[x].push_back(y);vc[y].push_back(x);}for (int i 1; i n; i) v.insert(i);ans.clear();for (int i 1; i n; i){if (dfs(i)){if (m n) ans.push_back(make_pair(ans[0].first,ans.back().second));for (int i 0; i m; i) printf(%d %d\n,ans[i].first,ans[i].second);return 0;}}printf(-1\n);return 0;
} View Code
